# Status of brute forcing all possible memory states of a video game [closed]

For an old video game that has a small enough memory footprint, it should be possible on exponentially larger modern systems to create a graph of all possible states of memory and the inputs that transition between them. With this information, one can, for instance, solve for an optimal tool-assisted speedrun.

Has this actually been accomplished? My search only turned up this video: https://www.youtube.com/watch?v=Q2g9d29UIzk which proposes such a search for Pokémon Blue, but that seems like much too large of a game to get a full graph of memory states for.

If not, I would still be interested in similar projects that have actually been carried out, where modern computers have allowed us to reason in some way about the possible memory states of much older games.

• Sounds more like a math questions - after all, already the Atari VCS, with just a 64 bytes of memory (not counting it's I/O registers) present 2^512 possible states, that (~10^150) is already incredible larger than the number of atoms in the universe (~10^80). So unless someone comes up with a real clever solution (generic or procedural) to cut that down by far, you won't find any computable solution (not to mention that states also include time and sequence). Commented Aug 28, 2022 at 21:19
• You may find this interesting: github.com/efa/Wilderland Commented Aug 28, 2022 at 21:20
• @Raffzahn They don't need to brute force every possible memory configuration allowed by the hardware, though. They only need to brute force the possible game-relevant memory configurations, which will be many, many orders of magnitude smaller. Commented Aug 29, 2022 at 12:17
• If we had a computer that could flip bits using the minimum amount of energy physically possible, it would take more energy than exists in the entire Sun to brute-force 32-bytes (256 bits) of state Commented Aug 29, 2022 at 12:27
• @Raffzahn Here is a GitHub repo that searches all possible memory states for Dragster (as mentioned in the top-voted answer): github.com/esnard/dragster. This is done on the Atari 2600, which has 128 bytes of memory, which has around 2^1024 possible states. With the right game and the right algorithm, it is empirically possible to brute force search a game's possible memory states. Commented Aug 29, 2022 at 12:39

An analysis such as you describe has been performed for the Activision game "Dragster" for the Atari 2600. The game polls controller inputs once per frame, and a spreadsheet has been produced describing all control input sequences in the roughly 350 frames between the start of a game and the fastest possible win. Dragster is perhaps one of the easiest games with which to perform this type of analysis, since the number of possible states of the game after 350 control inputs is very limited, making it possible to throughly debunk certain people's claims of having achieved record-setting times which are faster than everyone else's on a properly-functioning cartridge and console (if someone were to flip the power switch rapidly, one might manage to induce a malfunction, but records that result from malfunctions don't count; people who covertly and deliberately induce malfunctions to achieve records are prone to be disqualified from participation in leader boards, and even malfunctions which occur due to perfectly honest causes(*) will result in records being withdrawn).

(*) The first person to achieve a score of one billion points on Rock-ola's game Nibbler received a free arcade machine as a prize. When the person used that machine in competition, it was discovered that a bad connection on the 6502's "ready" line reduced the amount of time the machine required to perform some animations, which gave an unfair advantage to the player. This defect was almost certainly present when the machine was manufactured, and there is no evidence that anyone was aware of it until the machine was very throughly analyzed after the competition. Records the person had set with the machine were subsequently withdrawn, but without any dishonor, and the machine's owner would be free to attempt to set new records with a repaired machine.

• How can a simple spreadsheet describe more than one or two sequences of inputs? Commented Aug 29, 2022 at 14:34
• Went looking for the spreadsheet and found this Google sheet via speedrun.com but it only has 184 frames noted. Is this a different sheet or am I perhaps misreading it? Commented Aug 29, 2022 at 14:53
• I don't remember the exact details, but the game kept a relatively small number of "variables" for engine speed, vehicle speed, vehicle distance traveled, and current gear; with the exception of the current gear, which had a small number of discrete states, every variable was monotonic with respect to performance. If e.g. five frames into the simulation, some particular state did not have at least one variable whose value was more favorable than some other known possible state, such a state could not achieve a faster race time than the other state. Commented Aug 29, 2022 at 14:54
• @TylerW: Looking briefly at that sheet, I think it represents a distillation of information that had been compiled in a larger one. There are many situations where at e.g. frame 47, a state X might have a higher engine speed than some other state Y where the vehicle has traveled a certain distance faster, but no aspect of any frame-48 state that was reachable from X would be superior to any aspect of the best frame-48 state that was reachable from Y. What's essential to note is that the every possible state was either examined individually, or shown to be in no way superior to... Commented Aug 29, 2022 at 15:11
• ...some other state which was examined. The nature of the game and the way it was coded made it possible to prune the range of states enough to allow exhaustive searching. Commented Aug 29, 2022 at 15:12

It sounds very unlikely using an unguided brute force solver. Take chess - it's a "finite state" game with only a few possible transitions per node - the memory footprint is 32 pieces on 64 squares, it should be simple enough to brute force, right? Except that's still at least 10^45 possible states, which is why no serious chess-playing computers use a purely brute-force approach.

Pure brute force has been done for very simple and short games like Dragster on Atari. I believe that a form of brute-forcing was also used to solve for the dimension-hopping long jump mathematics used in the Mario 64 "0 Keys" TAS.

Beyond that you have to think of galactic-sized possible memory states. Like Pokemon Blue - the search space includes every possible combination of mons in your team and in your box, with all possible combinations of stats and IVs, multiplied by the player being at potentially any tile in the map at any stage of the main quest. Maybe, maybe, possibly you could craft a program that uses external knowledge about the game to guide the analysis towards more likely states, the same way that modern chess solvers do. That might get you through, say, a simple arcade rail shooter - although the approach is not much different from human-guided routing since you to give the program certain assumptions when you make it, and I assume the whole point of the program is to challenge those assumptions.

You could scope it to only a very tiny portion of the game with the goal of like "get the player through this locked door" to possibly discover individual glitches. But then you might have the problem of "how does the program know when it has reached an interesting end state?" in case it does discover a new route or glitch? It's tricky.

A dumb brute force would be very slow even for simple games. Take pong, the ball would have an x and y coordinate (let's assume an unsigned 8-bit value) and two paddle heights (also assumed to be unsigned 8-bit values). This would give you 255*255 possible states for the ball, 255 states for each paddle and would give you a total search space of 255^4 or an unsigned 32-bit number which if you were to hold every possible state that may occur in pong would be computable on modern hardware. This is before factoring in score values which would increase that value by ~81.

As you can see this approach will not scale well and a smarter approach would be needed. For long it's simple - just have the computer play the game, taking physics into account, brute-forcing all possible memory states is cool but even a mere 8 bytes already contains a gigantic search space of 2^64 which is the largest hardware-accelerated integer value that modern hardware performs - save more exotic architectures and vector extensions with a bit of software-based processing added.

A different approach may be to only consider the player-accessible inputs rather than memory states, but this falls down in games that can go on forever either because no inputs are pressed or some circular path, this will raise the question "How do you decide when to quit a search?" One answer is a function that evaluates player-trackable game properties such as a score and should the change of score be too low for too long, end this search and begin the next. This would still leave a gigantic search space and may cut out interesting bugs that may occur but require considerable time and little 'progress' to set up. Despite this reduction of search space by brute forcing inputs over time rather than all states still isn't really possible - you aren't going to be brute forcing super Mario bros anytime soon, you would be lucky to complete it.

So taking the above into consideration, how do you actually perform such a search? Currently, the best answer that I have is reinforcement learning which is still slow but at least it will complete within a few hours to weeks rather than several thousand lifetimes and works by randomly performing actions and over time learning a connection between actions and 'rewards'. The main algorithms used are NEAT (Think natural selection) and Q/deep-Q learning (Kind of like what you were after with the memory state of the entire game, but doesn't consider all possible states)

• For the original Pong(R) brand video game, at each time the system's main scan line counter wraps around, the only aspects of state which would be relevant to any subsequent operation would be the "game active" latch, the score counters, horizontal and vertical counters for the ball, a three-bit vertical speed/direction latch, a volley counter, and a horizontal direction latch, and the capacitor charge state of a 555 timer which controls beep duration but is not otherwise fed back into game logic. Commented Aug 29, 2022 at 15:22