How We Solved the Worst Minigame in Zelda's History [video]
youtube.com
youtube.com
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.
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.
I guess the framework for this is some type of "best choice problem" to find optimal strategy switching? [1]
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.
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.
If you don't feel like watching a 24-minute video, please do yourself a favor and resist that urge. It really pays off.
And if you enjoy it, take a look at these channels:
- https://www.youtube.com/channel/UCtUbO6rBht0daVIOGML3c8w
- https://www.youtube.com/user/BismuthWasTaken
- https://www.youtube.com/user/karljobst
The issue with this minigame was apparently that players would need to waste a basically random amount of time on the minigame, it was necessary to win the minigame to finish the game (in a way that meet these particular speedrun constraints).
If the game takes two hours to finish and the minigame can take 1 minute or 5 minutes of it, an attempt where it takes 5 minutes is probably never going to beat the record. You might as well scrap it. And in this case you would not know until half an hour into the game whether this attempt you'd get lucky, or if it was a total waste of time. So this group wanted to find a way to mitigate the randomness, such that the viability of an attempt was determined by player skill rather than luck in a bullshit minigame.
The fastest Super Mario Brothers speedrun is under 5 minutes: https://www.youtube.com/watch?v=Gum4GI2Jr0s
Speedruns might seem pointless, but they provide that satisfying closed problem.
Sort of related, it’s awesome to see that they’re still finding massive bugs in these old games (such as Ocarina if Time, which only recently have a proper ACE exploit found) 20+ years later and figuring out _why_ these bugs happen so they can figure out easier ways to make it happen so they can actually use them in runs. It’s fascinating to watch the progression of these exploits
(had to look it up: https://ghidra-sre.org/ ).
How did they figure out the RNG method, and the initial seed values? And how were they able to count the number of RNG invocations while the game was running? This information was crucial for the rest of the setup, but not at all obvious how it was acquired.
But now it feels pretty timeless...
I'm playing through the original right now and while it's quite decent-looking, it's not as polished as the update.
Still, WW always amazed me for a GC/PS2 era game.