Inside the Mushroom Kingdom

I spent a ridiculous amount of time this weekend hacking on Wallace. Of course, a lot of that was due to a near-total overhaul of the earlier code, refactoring thousands of lines to make the way forward easier (since I now have a decent mental picture of what I need, instead of aping the existing FCEU code.)

Of course, that doesn’t mean refactoring was the only change since the last update. As you’ll recall, I had been using screen scraping to get information about the current state (things like score, number of lives, etc.), but along the way found it was way more complicated than I had anticipated. Plus, even Super Mario Bros. has pathological cases where screen scraping is more problematic than recognizing ten digits, as anyone who’s ever gotten more than nine extra lives can tell you.

So, screen scraping is dead and buried. (Using image recognition to detect events, however, is still there, since it’s easy to implement, easy to understand, and widely applicable.) Luckily, there’s a much richer resource for getting game information: the game’s memory itself. Naturally, in-game memory has all the information we’re likely to need, assuming we can find it, and the FCEU core’s debugging hooks lets us access it easily from code.

Ah, but how to find it? The FCEU core comes to the rescue again; part of its cheating interface lets you search game memory for interesting values. (As you may know, cheating devices like the Game Genie work by replacing values in memory; an “infinite lives” cheat, for example, just returns a constant value whenever the game looks to see how many lives are left.) Since FCEU is happy to do the heavy lifting, Wallace just has to provide a graphical interface to it.

To get an idea of how this works, let’s figure out where in memory Super Mario Bros. keeps track of the number of coins we’ve collected. We start by resetting the search, which saves a snapshot of the current contents of memory:

Before

In this example, we currently have 3 coins, and we’re about to collect 19 more. After we do so, we search for all bytes in memory that were originally “3″ but are now “22″.

After

We lucked out in this example: there’s only one byte in the address space that changed in the way we were looking for. In most cases, there’ll be some false positives, but they can be screened out by doing another search on the results.

Also, we assumed that the coin total is stored as a single byte in memory. More pathological situations are also possible, of course. For example, since the score is a six-digit number, there’s no way it can fit into a single byte (which can range only from 0 to 255), so it must be spread across multiple, presumably contiguous, bytes. Additionally, the data might not even be laid out like you’d expect a multi-byte integer to be; for example, the score in Super Mario Bros. is stored in six bytes, one byte per digit, starting with the millions digit (which only appears on screen if your score gets that high) and leaving off the ones digit (which is always 0 anyway). And, of course, endianness is also potentially an issue.

Of course, with a little trial and error, we can use the Memory Browser to find where the data we want is stored, and then extract it when we need it:

Score

Since I’m sure you’re dying to know, here’s where some interesting values can be found in Super Mario Bros.’s memory:

Data Address Format Notes
Current Score 2013 6 bytes, base 10, big-endian Multiply this by 10 to get the score
High Score 2007 6 bytes, base 10, big-endian Likewise
Coins 1886 1 byte
World 1887 1 byte Zero-based (i.e., World 1 is stored as 0)
Stage 1884 1 byte Likewise
Time Remaining 2040 3 bytes, base 10, big-endian
Lives 1882 1 byte Zero-based

So, what can we do with this? We can use the Evolver window to evaluate the fitness of an input. First, we specify our fitness function on the Fitness tab. This is mostly things we’ve seen before, just with a somewhat nicer interface. However, now a weight is associated with each metric; overall fitness is a weighted sum of all metrics.

Fitness

Next, we specify the initial conditions for our run in the Game tab:

Game

The Breeding tab will eventually be where we specify how to generate new candidate solutions in our genetic algorithm, but for the time being there’s nothing there. All we can do is do a manual test of our setup on the Population tab, where the human plays and the Evolver evaluates how well he or she does:

Playing

You’ll note that our fitness function weights world and stage much more heavily than score, as can be seen in the computed fitness value. There’s also a very heavy penalty for game over:

Over

So now, the main missing piece is the genetic algorithm.