6 ms·
This was surprisingly awesome. There's a "battleship" like game in Zelda that is "required" (I guess) to be won three times in quick succession for a complete
by abetusk 6y ago
This was surprisingly awesome.
There's a "battleship" like game in Zelda that is "required" (I guess) to be won three times in quick succession for a complete speedrun. Trying to get three wins in a row is too slow, so they developed a method that uses knowledge of the random number generator to find the answers.
The method is, as I understand it:
* The seed for the RNG is fixed (RNG is Whichmann-Hill with a seed of 100,100,100, apparently)
* The RNG is used throughout the game and is called upwards of 5.5M times before they get to the "battleship" challenge, so there's a bell curve distribution on what state the RNG is in by the time the player arrives at the challenge
* The bell curve is too wide to effectively be used to narrow the search down initially, so a few "battleship" games are played (and lost) to guess the state of the RNG
* From the last step, this narrows the search down to a few "key states" of the RNG, each with their own bell curve distribution of what state the RNG is when next used to create the random mini-game
* A new distribution 'heat map' of possible ship positions is generated so players can have an increased probability of solving the puzzle
* Each subsequent guess and/or win give more information about the RNG state to effectively narrow down the search
The key point here is that the RNG is used throughout the game, with an unknown number of calls in between when it's being called for the Zelda mini-game they're trying to win.
Since the method is out of game (as in, not reading memory from the game, using only input from the player out-of-game), it's allowed in speed-runs, much like consulting a web-site with a tech-map or other quick calculations to help the player in game.
I'm no expert but this sounds almost verbatim what cryptoanalysts do to break some encryption protocols with known seed states or other 'side band' information.
- dane-pgp 6y agoThe video is definitely worth watching, but that's an excellent summary, thank you. It seemed to me that there might be a trade-off (when selecting a square in the game) between squares that have a high probability of containing a ship/squid and squares that are a good choice for carrying out a binary search of the remaining possible board states. Presumably, though, the remaining board states are sufficiently random that no square is significantly better than any other in terms of the binary search.
- abetusk 6y agoYeah, that's an interesting point. I think the information gained from the first sacrificial game is enough to reduce the search space so they can plow through the remaining games. There's obviously some tradeoff for a generalized system. I guess the framework for this is some type of "best choice problem" to find optimal strategy switching? [1] [1] https://en.wikipedia.org/wiki/Secretary_problem https://en.wikipedia.org/wiki/Secretary_problem
- nullc 6y agoI implemented a solver for the computer hacking minigame in fallout 3 (? whatever one is the oldest with the hacking minigame)-- it was sort of a 'mastermind' but with words. My solver eventually always won, without anything as fancy as reverse engineering the game. But to get there I had to both choose the option that maximized the information gain and look ahead many moves to make that estimation accurate-- the choices were non-independent so a simple entropy estimate (e.g. picking the choice closest to 50% on their heatmap) won't necessarily give the best play. Sometimes the move that distinguished the answer list the best was was not the first move in the pair (or n-tuple) of moves that best distinguished the list. By lookahead I mean for each ultimate answer, play out the game many moves taking all (or a pruned set of choices) and measure how much narrowing you get after several moves conditional on the first move. IIRC without the lookahead the entropy based play was worse than playing the most likely choice, and with just the most likely choice my solver wasn't good enough to always win without retrying, so I had an incentive to overcome the local minima of using just the most likely. Something similar might apply to this, as the geometry of the targets makes the choices non-independent. But it sounds like taking the most likely choice is good enough in this game so perhaps they stopped their development there.
- Agent766 6y agoUsually external tools like this wouldn't be allowed, but the community decided on allowing it because the minigame is so brutal. It's pure RNG and I've seen runs lose 15 minutes to it. This tool removes the random element from it and makes the total run time better reflect a player's skill rather than just their luck.
- thatthatis 6y agoWhy not just agree that speed runs exclude the time between minigame start and minigame end, vs allowing an external tool?
- navhc 6y agoI don't think that excluding sections from a speed run is a thing; the whole setup for speedrunning means splits and total time passed, not manually adding up splits ignoring some, or pausing timer at any point. Also, this could open up room for exploitation, such as intentionally failing for a long period of time to make a certain amount of time pass in game to get to some desired state, while not being counted in total time.
- TAForObvReasons 6y agoThe minigame has 3 rewards: piece of heart (first win), treasure chart (second win), and a second treasure chart (win within 20 moves). The theoretical minimum number of times you need to play the minigame is 2 (if you win within 20 moves the first time) but the 3-round setup is consistent