Emulate Good Times, Come On

The crazy genetic-algorithms-v.-Super-Mario-Bros. project isn’t dead.

Wallace Preview

As you can see, I’ve successfully done a basic port of the FCE Ultra NES emulator to GTK/GNOME. It’s lacking lots of the crazy advanced features of FCEU, but the important ones are there:

  • (Unscaled) video output.
  • Audio output.
  • Keyboard input.
  • Joystick input.
  • Save states.
  • Movie recording and playback.
  • And a few other things.

It’s nothing fancy, but it’s definitely usable. It does have one advantage over the Linux version of FCEU, however:

Wallace Preview - Input Dialog

Look, it’s a way to configure your input settings without running the emulator with a special command-line switch that takes you through a series of text-based prompts for your input settings! You can’t see it in the above screenshot, but all you need to do is edit the cell with the input binding you want, and then press a key or move the joystick.

Although the source code for FCEU can be pretty ugly, it does have a pretty nice separation of the emulation code itself from the user interface, which helped a lot. Actually running the emulator is quite simple: you make a loop that calls a function that advances the emulation one frame, and gives you back the new screen contents and audio samples. (OK, it’s a bit more complicated than that, but you get the idea.)

So now “all” that’s left is the interesting part of actually using genetic algorithms to play a game. As you may recall, the two main things we need are a representation of a candidate solution (i.e., the series of controller inputs), and a fitness function to decide which candidate solutions are better than the others.

As mentioned in the above feature list, FCEU supports recording and playing back movies. These aren’t ordinary multimedia files, however — they’re a dump of the initial emulator state (essentially no different from a save state), followed by a series of controller inputs and timings. But that’s exactly what we need to represent candidate solutions! So, for generating solutions, we just need to take some initial state, generate a random series of controller inputs, write that out to a movie file, and feed that into the emulator.

The movie file format also looks to be quite amenable to the various mutations, cross-overs, and other genetic reassortments that will be necessary. The basic unit of information in a movie file is a single button change followed by a time (possibly 0) between this input change and the next one. (Or the time might preceed the input instead; I’m not entirely sure which, but it really doesn’t matter for our purposes.) With this representation, we can easily mutate fields and shuffle things around both within and between movies. If a movie file is DNA, then these little chunks are the individual nucleotides.

Of course, the tricky part will still be specifying a fitness function to use. I’ve got some ideas for how to do that, but I’ll save it for a later post.

6 Responses

  1. I can’t wait to find out more… exciting stuff!

  2. This is pretty much awesome. All over.

  3. Woo! Progress! I remember when we first talked about this in the movie store . . . Which reminds me, remember that time John picked up that video?

  4. This is the best application of computer applied biological theory I’ve ever seen! And it’s freaking cool to!

  5. This is the only application of computer applied biological theory I’ve seen…But it’s still freaking cool!

  6. Cool project, but it looks pretty tough.

    Your fitness function is going to have to detect the “Game Over” condition from the emulator, which is not trivial.

    However, this is a piece of cake compared to determining the game state in real-time. I highly doubt a raw genetic algorithm on button sequences can get past the first couple screens of the first level, much less beat the game. That is akin to monkeys banging out Shakespeare.

    You should really read the Rogue-O-Matic paper. That’s the closest thing in academia to your project, (very successful, I might add), and it used a rather different approach.

Comments are closed.