(And later, its adaptation into an exercise in human computing and cooperative single-player gaming)
Some time ago, navaburo and I were hanging out in my dorm room, and we ended up thinking about the concept of writing an AI to find the best (shortest) path through a video game. A couple days later, we went down to the Linux Lab and fleshed out the idea on paper.
For those unfamiliar with the concept of “Tool-Assisted Speed-running,” it is a process done by some video game enthusiasts in which they play a game on a an emulated (or “virtual”) machine, using special features of the emulator to let them more easily make an almost “perfect run” of the game, where they complete the primary objective as quickly as possible. This usually involves slowing down the game to give them the opportunity to take shortcuts and pull off maneuvers that wouldn’t have been possible with the limitations of human reaction time and reflexes. Sometimes, they also use “luck manipulation,” which involves taking a snapshot of the machine’s state (also known as a “savestate”) before an event that relies on a “random” number, and restoring the machine to that state again and again, until a desired number is generated. Similarly, they often use this functionality to rewind the gameplay in case they make a mistake. When a speed-runner completes a game this way, he or she might post a replay of the “run” on the internet to share with others; there are communities on the web in which speed-runners will compete to complete classic video games with the fastest times they can manage.
navaburo and I theorized that, using an emulator for a given video game console, we could calculate the fastest possible path through the game by using a search on all of the possible inputs starting from the machine’s initial state. This is most likely very impractical to compute, even for the relatively sophisticated computer hardware we have today. Nevertheless, we decided that as long as we could provably calculate the optimal path to do some trivial task, we could also calculate the optimal path to the very end of the game. For proof of concept, we decided on Super Mario Bros. for the NES, and we’d call the program “OptiMario.” We spent some time looking into ways to bootstrap our search into the input functions of various open-source NES emulators, including the popular FCE Ultra and Nestopia, before deciding that for our purposes, the simpler (and lesser-known) NEStra would suffice. So far, we’ve hacked the beginnings of a foundation for this project into NEStra.
I won’t go too much into our methods just yet, mostly because we still haven’t implemented it and the exact method we end up using might change. However, in theory, it seems we might be able to create an artificial “ultimate speed-runner” that is able to complete a game in the fastest possible time, perhaps even using glitches and shortcuts previously unknown (if it can be done with a valid input string, and it shaves seconds off the final elapsed time, such a program (properly implemented) will find it).
I maintain that any algorithm which promises an optimum solution will take an impractically long time to evaluate. However, it may be possible for certain games to arrive at an optimum solution using an algorithm which implments certain short-cuts (probably via limitations to the variation in the input-string, ala genetic algorithms). The only danger in this is that the solution may be optimal within some genetic radius but not globally optimum.
Thankfully, we can make some restrictions on each character of the input string, for instance discarding any that has left and right pressed at the same time, etc.. For the case of SMB, we could also only consider the start button the first time it’s pressed (to start the game) and discard any input using it afterward (to pause), and we could probably do some other tricks like ignoring any inputs that change the state of the jump button after a point in Mario’s descent where the game doesn’t care about it any more. Checking for the latter might be a little computationally expensive to check for on every branch, but the time saved from actually checking two effectively identical paths should outweigh it by a long shot.
This was posted wayyyy back in June. Have you made any progress on this? Updates please. =)
We came up with the project waaay earlier than that, too. Class comes first, unfortunately =)
I re-read this article. One hour and sixty firefox tabs later, I decide not to try to work on this project again.
. Why didn’t the guy who wrote Nestra implement save-state? Grrr.
I forget, did we look at TuxNES (fork of Nestra)? I think it’s a bit further along as far as features go, though it might not have savestates either.
I did, and unfortunately it also doesn’t have a save-state feature. Saving state seems to be a matter of saving all the RAM, VRAM (perhaps this could be cut out?), and CPU registers. But, I have not managed to understand what is going on well enough to implement this, and the code of Nestopia is greek to me.
Perhaps going with Nestopia would be a better bet, despite its added complexity, because the save-state is already implemented and stable (since stability of save-state is CRITICAL to our application).