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

Question

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.

Answer 1

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.

Answer 2

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.

Answer 3

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)