HN Theater @HNTheaterMonth

Reminds me of a fun video about speedrunning a battleship minigame in some Zelda title:

https://www.youtube.com/watch?v=1hs451PfFzQ

⬐ NaturalPhallacy

This was way more interesting than the OP lol

Thanks!

That's true. I did think about mentioning this possibility, but decided not to.

Another good example of predicting RNG, after a large amount of gameplay, for a non-turn-based game:

https://www.youtube.com/watch?v=1hs451PfFzQ

I think in certain Pokemon games, people figured out how to predict and manipulate random encounters based on an animation in the load screen.

Excellent video. I'm impressed the author went to recreate the run frame by frame, and then used those findings to analyze what was happening. Never expected this video to turn into a full on reverse engineering explanation.

As a side note, this kind of speed run has become more popular in the recent years for a combination of reasons: - First, it's difficult to improve on the regular world records since they're so optimized (just have a look at Quake Done Quick and its sequels). - Second, the emulators available to the speed running community have evolved. They now include better ways to track what's happening in memory. - Third, the games themselves are understood better (as recently exemplified by the Super Mario 64 full reverse engineering).

So it's creating a whole new genre of runs that simply isn't about execution anymore.

If you're interested in the topic, you might like the Super Mario World speed run that uses a similar technique (https://www.youtube.com/watch?v=gECESOoU8Es), or the recent work on removing randomness from Wind Waker runs (https://www.youtube.com/watch?v=1hs451PfFzQ).

⬐ lillesvin

> So it's creating a whole new genre of runs that simply isn't about execution anymore.

This sounds to me like a variant of "using glitches/sequence breaks isn't how the devs intended it to be played".

Arguably, setting up for these glitches and exploiting them in real-time (i.e. not TAS) using only a controller is still "execution".

⬐ leshokunin

Sure. I meant in the sense that if you just said execution without context, you'd simply expect that we'd be talking about mastering inputs. This requires a body of knowledge established completely outside of the game itself.

⬐ ehsankia

I'd argue that many frame perfect moves used to setting up the memory is very much execution. Maybe a different kind of execution, but still very much skill based.

⬐ hosh

In this video, the speedrunner made a mistake and had to compensate on the fly to get the enemy into the exact position when he hit the pipe. I think that is more impressive than a perfect run.

⬐ hbogert

Yes, mind was blown when he explained this. The executioner had the intrinsic knowledge of the inner workings to cope with this. Just wow.

⬐ madeofpalk

> So it's creating a whole new genre of runs that simply isn't about execution anymore.

Did we watch the same video?

It was completely about execution. You still need to be exceptionally good at the game to get those frame-perfect setups.

⬐ leshokunin

I meant in the sense that if you just said execution without context, you'd simply expect that we'd be talking about mastering inputs. This requires a body of knowledge established completely outside of the game itself.

⬐ madeofpalk

Even then, once you get past a cursory knowledge of the game and mechanics, you start getting into understanding the implementation of the mechanics of the game. Then it's just a deeper and deeper rabbit hole until you're maniupulating bytecode by throwing P Switches up in the air.

⬐ mumblemumble

Perhaps they meant, "isn't simply about execution," rather than, "simply isn't about execution?"

⬐ andrepd

Bismuth and Summoning Salt are two excellent channels about speedrunning.

⬐ kibwen

I can recommend Karl Jobst as well.

⬐ distances

> just have a look at Quake Done Quick and its sequels

For anyone else who was intrigued, I found this was a good overview of what's been going on in Quake speedrun community: https://youtu.be/43d8fICz6gM

⬐ Bnshsysjab

Also be sure to check out the super Mario world flappy bird code injection:

https://youtu.be/hB6eY73sLV0

⬐ crtasm

Plus "Mario maker" mode injected into super Mario world: starts around 11:30: https://m.youtube.com/watch?v=IOsvuEA2h4w

Although this one is unlikely to ever be performed by a human!

Good point.

That approach was in fact used for "Sploosh Kaboom", a RNG minigame in the Windwaker: https://www.youtube.com/watch?v=1hs451PfFzQ

⬐ chaorace

See also: Rainbow Tables https://en.wikipedia.org/wiki/Rainbow_table

The thing about "Sploosh Kaboom" is that the end state of the board, essentially a hash, is all you need to know to figure out the seed. That's thanks to the precomputed table embedded in the helper program.

Unlike reversing a hash, however, you actually want to crack the code using as little information as possible! Nobody wants to solve for the seed after they've already revealed the whole board, after all. The truly novel part of this particular tool is in how it leverages calculus to narrow down the seed pool by exploiting the RNG that produced the board seed. Each entry in the precomputed table is also time-indexed, since the RNG step count can be loosely approximated based upon the game's runtime. As the tool eliminates seeds from the pool, it's also gaining confidence in the exact cycle count the RNG was at when it produced the seed value for the board, which, in turn, tightens up the distribution curve of the remaining seeds.

⬐ ekimekim

Previous discussion (8 days ago) https://news.ycombinator.com/item?id=23442998

⬐ rsoto

This is what I love about speedruns: it's basically the core of the hacker mindset—solving problems through creativity, often to a insane degree.

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

⬐ vga805

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.

⬐ keenmaster

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.

⬐ saagarjha

Actually, it turns out that you can save a couple hundred frames at the beginning if you enter the video holding down A.

⬐ keenmaster

What does that do from a technical standpoint?

⬐ saagarjha

Nothing, it's a reference to the "Watch for Rolling Rocks 0.5x A Presses" video: https://www.youtube.com/watch?v=kpk2tdsPh0A

⬐ s1artibartfast

amazing

⬐ wrnr

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.

⬐ raldi

You can use the Lens of Truth to cheat and see the contents of the chests before opening them.

⬐ boringg

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 :)

⬐ VHRanger

There's intrinsic satisfaction in optimising on a closed problem.

Speedruns might seem pointless, but they provide that satisfying closed problem.

⬐ jsnell

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.

⬐ boringg

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.

⬐ shaftway

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.

The fastest Super Mario Brothers speedrun is under 5 minutes: https://www.youtube.com/watch?v=Gum4GI2Jr0s

⬐ thatswrong0

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

⬐ Agent766

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.

⬐ pmezard

> Thanks the NSA for the beautiful piece of software called Ghidra

(had to look it up: https://ghidra-sre.org/ ).

⬐ saagarjha

I’m very happy to see that Ghidra is commodifying reverse engineering tools and making them available to efforts like these.

⬐ Scuds

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

⬐ fingerlocks

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.

⬐ Jasper_

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.

⬐ milesvp

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.

⬐ remram

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!

⬐ yomly

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.

But now it feels pretty timeless...

⬐ CarVac

The version shown is the Wii U version which has some updated graphical effects.

I'm playing through the original right now and while it's quite decent-looking, it's not as polished as the update.

⬐ yomly

Good catch - I had a feeling it might be.

Still, WW always amazed me for a GC/PS2 era game.

⬐ testplzignore

One of my great achievements in life is getting a score of 10 in this game. Perhaps someday I'll get a perfect 9.

⬐ s_Hogg

This is great. Bayes' theorem is such a simple principle, which is precisely why it's so powerful.

⬐ abetusk

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

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.

⬐ abetusk

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]

[1] https://en.wikipedia.org/wiki/Secretary_problem

⬐ nullc

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.

⬐ TAForObvReasons

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

⬐ Agent766

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.

⬐ thatthatis

Why not just agree that speed runs exclude the time between minigame start and minigame end, vs allowing an external tool?

⬐ navhc

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.

⬐ montebicyclelo

[This is a rough summary of the video, which explains things much more clearly and thoroughly (using animated plots). I have no affiliation with the creators of the video.]

The goal is to be able to quickly solve a particular mini-game (Sploosh Kaboom) in the game The Legend of Zelda: The Wind Waker (WW). Sploosh Kaboom is like a 1 player version of battleships.

WW uses the Wichmann-Hill random number generator, and always seeds it with (100, 100, 100). A single generator is used globally for all kinds of things, and each call causes the generator state to update.

One of the things the generator is used for is to determine the (hidden) position of the 'squids' in Sploosh Kaboom.

However, on average, each frame of WW calls Wichmann-Hill dozens of times. It isn't possible to know exactly where in the sequence of generated numbers we are.

However, given the time that the game has been running for, and the first state of the game Sploosh Kaboom, it is possible to massively narrow down the estimate of where in the random number generator the game is (although there may be multiple gaussian curves on the line of possible positions in the sequence).

By then trying out different squares on the Sploosh Kaboom board it is possible to determine where in the sequence of random numbers we are, and determine the state of the board before it is fully revealed (allowing the mini-game to be beaten).

⬐ dragontamer

While this video is ~20 minutes long, it breaks down the Wind Waker RNG, creates a few prior probability heatmaps, and ultimately creates a tool for speedrunners to more quickly beat a notoriously luck-heavy part of the 100% speedrun.

With the tool in hand, players no longer have to guess randomly (and therefore add random variance) to their 100% speedruns, but instead can near instantly get the correct board.

⬐ csunday95

Hi there, I'm one of the people that worked on this project. By way of summary, we used Ghidra to reverse engineer Wind Waker's binary and discovered its using a very weak RNG and a fixed seed. With that we used statistical methods to determine our position in the RNG period and narrow the game randomness to the point of guaranteeing a win.