Why did I just watch this? Fascinating but I don't even know what a speed run is. In terms of the statistics, heat map and mini game breakdown - pretty slick. I just don't understand why so much effort was put into unpacking this game within a game :)
A speed run is an attempt to finish a game faster than anyone else. (Within some set of constraints; e.g. it might mean seeing the credits, it might mean explicitly winning every stage or ever boss in the game, etc).
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.
Got it - I didn't realize speedruns we're so popular for this game and that this minigame was the crux of the speed run problem. Impressive dedication to such a minute problem.
There are different categories for speedruns within a game. The most popular is for completion, then for 100% completion. Sometimes other restrictions too. Like Super Mario Brothers has ones for winning with and without warp pipes.
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.
The 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.
Yeah, 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]
I 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.
Usually 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.
I 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.
The 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
Totally agree. I cannot recommend the first link posted here enough, Summoning Salt's channel. Some of the stuff that people discover about games, and then use to their advantage to shave off mere tenths of a second of a speed run is mind-blowing, and really does capture the essence of hacking. Sometimes thy literally hack the game by exploiting known memory flaws to skip sections, etc. etc.
The proper way to watch a speed run video is with a speed run. Watch at 2x speed or more for < 12-minute completion time with a possible gain in comprehension.
Linkus7 at Awesome Games Done Quick 2020 exploiting memory leaks so that the Gamecube can't malloc RAM for a barrier wall thus skipping over a large amount of the game
https://youtu.be/7XBPrFYN1MU?t=3106
The speedrun community is wonderful for this sort of thing. And tbh it’s therapeutic to have on in the background as I’ve been WFH since COVID started.
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
Check out the history of Wind Waker's barrier skip as well. I believe it saves 30 minutes of a 3.5 hour run. It's always been known that finding a way to skip Wind Waker's barrier would be massive, but it resisted any attempts to bypass it until a year ago. The barrier blocks off the final dungeon of the game.
I clicked on the link wondering if it was the battleship minigame. I hated this minigame so much, I too ended up writing code to help me figure out optimal moves just get past the dumb thing, and I wasn’t even trying to speed run the damn thing.
There is this mini game in Ocarina of Time where you enter a room with two locked exits and a chest containing either a key or some consolation price. Every exit leads to a new room with a chest. You win the game by picking the room with a key N times but price in the next room is always random. At some point I got stuck and the best thing I could think of was to open random doors. A hole day I picked the wrong door and at the end only got a quarter extra health for my effort and was still stuck at the game. Had to find this enter-hook think hidden in some old grace.
As an aside, Wind Waker is so beautiful. I remember at the time merely thinking "this is an opinionated visual style" but man did it fracture gamers at the time.
This video left me with a lot of unanswered questions, probably because I know nothing about reverse engineering console games.
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.
Nintendo left symbol maps for the game on the disk, so they likely found the random number generator function within that, which is named cM_rndF. To count invocations, you could patch the game to increment a counter on every RNG call, and try an example speedrun. Or you could do a brute force to find the rough invocation count from the internal state.
I can tell that so much effort went into this video, with so much explanations and those impressive animations, but then the sound was set to -18dB on export, making it barely audible. Oops!
36 comments
[ 4.7 ms ] story [ 66.5 ms ] threadThe 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.
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]
[1] https://en.wikipedia.org/wiki/Secretary_problem
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
- https://www.youtube.com/channel/UCIyZiiHXIH7KkqfaDvBmG-Q
- https://www.youtube.com/user/RWhiteGoose
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
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.
(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.