The return of Wallace!

For whatever reason, I recently got it in my head to take another stab at my long-since-abandoned effort to apply genetic algorithms to the utterly pointless task of playing old video games. Here’s the result:

The gruntwork seen above was done using Wallace Jr., which as its name suggests, is a significantly stripped-down version of Wallace, my original attempt from a couple years back. Wallace’s ultimate failing was trying to do a little bit of everything: being a graphical emulator front-end, reverse engineering memory locations, doing the genetic algorithm itself, video encoding, etc. As a result, it did none particularly well, and continuing problems trying to shoehorn GStreamer into the processing pipeline ultimately led to its abandonment.

Instead, Wallace Jr. just does the genetic algorithm stuff: generating organisms, evaluating them, and spawning new generations. That’s it. The emulation itself is passed off to a modified version of Mednafen — specifically, a version hacked to enable noninteractive use and to dump interesting memory values while executing. The actual reverse engineering bit is left to something else; it accepts a list of memory locations to use as metrics when evaluating fitness, but leaves it up to you to find a way to figure them out.

As a result, Wallace Jr. accomplishes its core mission without getting bogged down in other things. Also, by offloading emulation into a separate process, it has the nice side benefit of enabling parallelism, since for whatever reason emulator authors seem to love global variables for all important state, which pretty much eliminates any hope of emulating more than one thing at a time in the same memory space.

Wallace Jr. is still pretty basic, but it’s still complete enough to generate the results in the video, wherein a set of controller inputs capable of defeating Air Man in Mega Man 2 in just 11 generations. In that demonstration, fitness is basically defined as Mega Man’s health minus Air Man’s health, with the goal of maximizing the fitness measure.

I say “basically” because genetic algorithms, much like biological evolution, is prone to finding clever ways to solve problems, and the naive fitness measure I just described lets some of these slip through. In particular, if input ends before either Air Man or Mega Man dies, the fitness will still be the difference between their health meters. If input ends really early, like, say, before the battle starts when Air Man has nominally zero health, the outcome is the optimal fitness measure of 28, even though that solution really isn’t what we want. The real fitness measure I used checks for that, and throws in a -100 penalty if input ends before a death, and a -500 penalty on top of that if the battle hasn’t even begun yet.

More amusingly, seen in the “outtake” at the end of the video, in one of the runs I attempted while developing Wallace Jr., it managed to randomly hit upon controller input that activated the Air Man door glitch. I didn’t even know that was possible without using Item 1, but apparently it is. I had to adjust the fitness function to penalize that as well.

I hope you appreciate that video, since it took a ridiculous amount of effort to make. For starters, Mednafen doesn’t have a way to output a normal video file — the movies it makes are just recordings of controller input. Hacking in a way to dump the raw audio samples to a file was simple enough, but video proved to be more problematic; raw video data is too large to write to a file without making the emulator horrifically I/O-bound, disrupting emulation as it tries to frame-skip to recover. Integrating a true video encoder into Mednafen was more work than I wanted to do, so I took the extraordinarily hackish solution of adding a way to dump PNG screenshots every couple frames (since doing it every frame ran into the same I/O issues).

Luckily, MEncoder has a way to convert a series of PNGs into a more conventional video file, but that still left the issue of stitching them all together into a single movie. I managed to use PiTiVi for that, despite its best efforts to be a bug-ridden half-working pile of something you’d expect to find Mike Rowe knee-deep in. Sadly, the alternatives for non-linear video editing on Linux are even worse.

The interstitials were a pain to make, since PiTiVi doesn’t provide a way to add captions to video clips. For that, I wound up manually putting together a GStreamer stream via gst-launch-0.10 and the textoverlay element. The trick there was making sure to encode the resulting video stream in a format that GStreamer could then read back when used by PiTiVi. For some reason, GStreamer will happily encode to lossless MJPEG but has no idea how to decode it!

Once that was finally done, I switched back to MEncoder to add the background music. Yes, I know the last note gets cut off at the end, but I wasn’t about to wrestle with PiTiVi again to lengthen the video by a couple seconds, especially given that PiTiVi doesn’t let you save your project! The mind boggles.

Splicing in a separate audio track also nicely hides how my hack of dumping screenshots rapid-fire instead of making a proper video causes synchronization problems when trying to combine it back with the dumped audio. I could never get the framerate quite right, but without the original audio, it’s more difficult to notice in the video.

Plus, it’s an appropriate song, even if its central premise gets refuted by Generation 10.