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.

9 Responses

  1. I’m glad you found a superior alternative to screen-capture for the number. Actually, I saw an article on slashdot about how google released some something called “tesseract” which seems to do image recognition. Seems kinda like the thing to get around those E-mail signup things with the picture of numbers to prevent automated programs from [more] easily spamming. Anyways, the memory capture idea seems to be a lot more sensible and clean. I’m really looking forward to seeing how you do on this! It’s absolutely awesome!

  2. Please please please keep going with this project. I completely love it!

    Also, if there ever was one of these, I think you should make it:
    http://www.irregularwebcomic.net/967.html

    P.S. – read it. All of it. Consider this my gift to you comparable to Schlock Mercenary.

  3. ” more than nine extra lives ” is a broken link :(

  4. The link should go to something non-broken now.

  5. Also, do you really think I’m going to abandon this project just as I’m getting close to it realizing its goal? I mean, besides you trying to sabotage the project by distracting me with webcomics with massive archives.

  6. Poppycock. I’ve seen IWC for all of 3 days and I’m at 1200 already. Just put some hustle behind the muscle.

    And no, I don’t expect you to wimp out, I was just cheering you on.

  7. It’s beautiful! *wipes away a single tear* Just beautiful…

  8. Finally you get to the good stuff…

    And by the good stuff I mean the part I understand and am anxious to see your implementation…

    I gotta ask, though, did all the stress over a fitness function come down to a weighted average? :)

    Also, I understand what you’re trying to do, but is there no way of finding a metric that indicates stage progress? It seems that ‘within a stage’ your determination for fitness comes down to score… I would suppose that by the very nature of genetic programming, and given the complexity of the problem, solutions will tend to progress together through the game (i.e. the majority of the first generation will likely all end up still in the first stage)… As the solutions evolve, the best-of-fit ones will still, by nature-of-the-beast, dominate the population basis for each generation resulting in the same like-progress among members… It just seems that no matter what, you’re ultimately coming down to the score as your basic measure of fitness…

    I don’t remember how score gets accumulated in the game, but couldn’t you almost finish a stage with damn near no score? Which would make a solution that, say, jumps on everything and gets every coin but doesn’t get halfway through the stage ‘more fit’…

    Lastly (for now), will your evaluations be taken at real time for each solution in the population? I assume a fairly substantial population size; won’t that take a lot of time (especially as the solutions become more fit) for each generation to evaluate? Not to mention actually applying evolutionary algorithms to the members…

    Now get back to work… :p

  9. The trickier part about the fitness function is *getting* the values to plug into the weighted average. I’m not sure if weighted average will be enough for fitness functions like “get to the end of the stage, and if you got to the end, the faster the better”. Though it might be possible to move conditionals like that into the events-and-actions tree instead of the fitness score computation.

    The best way to measure progress within a stage would be to find a value in game memory that correlates with progress. I assume something like that has to exist somewhere, but it might not be represented as a simple scalar value. If such a thing could be found, of course, that’s what you’d want.

    “Highest score” is at best a rough proxy for “farthest through the game”, but if you end evaluation once you lose a life, eventually the only way to increase your score is to make it to the end.

    And of course, there’s no reason you couldn’t read the metrics you’re interested in only when you detect a end-evaluation condition, which would save a little time.

Comments are closed.