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.