More on Wallace Jr.

To elaborate somewhat on my previous post, this is the input file I gave to Wallace Jr. in the run used to ultimately generate that video:

mednafen        /home/paul/mednafen-eval/instdir/bin/mednafen
 
buttons         right left up down b a
rom             /home/paul/roms/nes/Mega Man 2 (U).nes
initial_state   /home/paul/.mednafen/mcs/Mega Man 2 (U).0527a0ee512f69e08b8db6dc97964632.nc0
organism_size   1000
granularity     5
population_size 200
generations     50
parallelism    2
 
metric          health    0x06c0 1
metric          enemy     0x06c1 1
functions       megaman2.py
 
tournament_size             50
homologous_crossover_rate   40
arbitrary_crossover_rate    40
point_mutation_rate         10
reproduction_rate           10
 
point_mutation_probability  0.01

Note that the run used populations of 200 candidate solutions per generation. Each initial solution was 1,000 inputs long, with input granularity set to 5 frames — i.e., the same button input would be used for 5 consecutive frames (about 1/12 of a second) before advancing to the next. This was used to prevent solutions from being to spastic.

The various _rate settings specify how to generate new solutions from existing ones:

  • Homologous crossover takes one solution, deletes a randomly selected range within it, and replaces it with the corresponding range from another solution.
  • Arbitrary crossover is similar, but doesn’t require the two ranges to correspond to one another.
  • Point mutation randomly mutates each input with some small probability (here, 1%).
  • Reproduction just copies a solution unchanged from the previous generation.

When picking solutions for any of these techniques, Wallace Jr. uses a basic form of tournament selection. In tournament selection, you take a random subset of the population and pick the element with the highest fitness. This way, fitter solutions will get selected more frequently than less fit ones, but there’s still some randomness in the process. After all, if you always picked the fittest organism, you’d eliminate all the diversity in the population.

The metric lines specify addresses in game memory that store interesting values. Here, it’s the health of Mega Man and of the boss of the stage. Each is just one byte, which makes things easy. These values are actually ignored by Wallace Jr. itself; instead, my hacked copy of Mednafen uses these to decide what values to output after each frame.

For the actual fitness function, I decided to just specify those in Python instead of coming up with some way to express it in the configuration file. Here’s what megaman2.py has in it:

#! /usr/bin/env python
 
def compute_fitness (current_metrics, old_metrics, context):
    """
    Reward damage done to the enemy and health preserved.  Penalize runs that
    end before someone dies via a penalty for frames where both are still
    alive.  Also try to penalize activation of the door glitch by watching
    for increases in health, which indicate death-by-spikes.
    """
 
    def increased (key):
        return key in old_metrics and current_metrics[key] > old_metrics[key]
 
    fitness = current_metrics["health"] - current_metrics["enemy"]
    if "battle_started" not in context:
        fitness -= 500
    if current_metrics["health"] > 0 and current_metrics["enemy"] > 0:
        fitness -= 100
    if increased ("health"):
        fitness -= 500
    return fitness
 
def should_terminate (current_metrics, old_metrics, context):
    """
    Terminate once someone dies or the aforementioned sign of the door
    glitch is observed.
    """
 
    def dropped_to_zero (key):
        return current_metrics[key] == 0 and key in old_metrics and old_metrics[key] > 0
    def increased (key):
        return key in old_metrics and current_metrics[key] > old_metrics[key]
 
    if "battle_started" not in context and increased ("enemy") and current_metrics ["enemy"] == 28:
        context["battle_started"] = True
 
    return dropped_to_zero ("health") or dropped_to_zero ("enemy") or increased ("health")

The interface between Wallace Jr. and the fitness code can definitely stand to be improved. The functions are passed the current values of the metrics, the previous values of the metrics, and a context value it’s free to manipulate as it chooses to save information between calls. Most of the complexity is to handle the cases I mentioned in the previous post about avoiding undesirable outcomes like running out of input or activating the door glitch.

The astute reader will notice that I ran things out to 50 generations, but the video only shows examples up through Generation 13. Why? This:

Fitness of Wallace Jr. run

Things kind of hit a wall after Generation 13, with no real improvement any way you look at things. I suspect this was due to a combination of a fairly small generation size (200) and having 80% of each generation produced by crossover of existing solutions, with only 10% undergoing a handful of point mutations. Presumably, around the time Generation 13 was reached, the population had become a sort of inbred monoculture with little diversity between organisms, meaning it would take a long time for beneficial mutations to arise.

Sadly, I don’t have any way to go back and test this hypothesis, since the only organisms I saved were the peak performers of each generation. It may be worthwhile for later versions to compute Hamming distances or something like that to get a measure of how much diversity is in the population, and see how that changes over time.

One big limitation to Wallace Jr. currently is that it evolves input sequences, which are inherently going to be very specific to the initial state of the game when the solution starts playing it. In other words, if I played up to Air Man in a different playthrough and handed control off to the peak performer, it wouldn’t do nearly as well, since the state of the game wouldn’t match up with what it “expects”.

It’s like if you memorized the directions for getting to the store as a series of turns to make at each intersection — right, left, straight, right, right, etc. You’d do fine, unless I had you start a block or two over from your expected starting point. Suddenly, the directions are no longer correct.

What would be more interesting is to evolve programs to play the game, rather than mere input sequences. Of course, this would be a fair bit more difficult to implement, since now the solutions will need a way to observe the state of the game as part of their computation of what button input to produce. One way to do this would be to let it inspect the part of PPU memory where sprite information is stored, sort of letting it “read” what sprites are on the screen and where they’re at. The tricky part is getting Wallace Jr. and Mednafen to talk to each other like that while the emulation is going on — right now Wallace Jr. generates a Mednafen movie file and hands it off to Mednafen to play.

It’s not insurmountable, but having programs talk back and forth to each other is always a bit tricky, especially to avoid deadlocks: A is waiting for B to say something, and B is waiting for A to say something. Especially when B was never intended to talk to A to begin with.

If you’re interested in learning more about the theory behind genetic algorithms and genetic programming, you may want to take a look at A Field Guide to Genetic Programming, which is a freely downloadable book.

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.

Urandom fun fact

In turns out that if you’re wiping an external 1 TB hard disk using pseudorandom garbage, the process is CPU-bound and not I/O-bound:

$ sudo dd if=/dev/urandom of=/dev/sdb bs=4K
dd: writing `/dev/sdb': No space left on device
244190647+0 records in
244190646+0 records out
1000204886016 bytes (1.0 TB) copied, 136230 s, 7.3 MB/s

For those of you who have trouble dividing by 3600 in your head, 136,230 seconds works out to about 37.8 hours, with the CPU pegged at 100%. (Well, 50% since it’s a dual-core system, but whatever.)

My guess is that the process of actually encrypting the disk (once I initialize a file system on it) will take even longer, assuming that AES-256 encryption is slower than whatever PRNG algorithm Linux uses to drive /dev/urandom is.

Edit: Actually, that’s extremely incorrect. Encrypting the partition doesn’t actually write anything to it other than some kind of header identifying it as an encrypted partition. Yes, that means that almost all sectors are initially garbage if you try to decrypt them, but with a brand-new partition all sectors are initially garbage anyway. Creating the file system itself doesn’t try to read anything, either; it just writes to the sectors that will make up its index. And once you’ve mounted the file system, you’ll never try to read uninitialized sectors anyway, since there aren’t any files there.

In other words, the only O(n) step when creating an encrypted disk is wiping its previous contents; everything else is O(1) or O(log n) at worst. So why wipe with pseudorandom garbage instead of all zeros, which would be much faster? It’s (hopefully) computationally infeasible to distinguish uninitialized sectors (which look like random garbage because they are random garbage) from encrypted sectors (which look like random garbage because they’re encrypted with a strong algorithm). Not being able to tell where the data even is on the disk makes an attacker’s job more difficult.

Thanks to strong encryption, an attacker now has to either throw a lot of CPU power at the problem or use alternative means for recovering the data.

You cannot grasp the true form of Mother 3 spoilers

Seriously now, major Mother 3 spoilers ahead. I’m going to discuss major plot points in the game. I’m even putting everything behind a cut, to prevent you from reading anything accidentally. OK?

Read the rest of this entry »

Comments Off

Aahh, doorknob! I mean, Mother 3!

Mother 3 title screen

Mother 3 is better than EarthBound (a.k.a. Mother 2).

For those of you who have no idea what I’m talking about, Mother 3 is the game where Lucas and the New Pork City stage in Brawl come from. (Tip: if you want to avoid Mother 3 spoilers, don’t play Brawl.)

Mother 3 delivers the same style of humor as its predecessor, despite having a more serious, even depressing, storyline. And manages to pull it off, no less. To avoid spoilers, I’ll save further discussion and speculation on that for a separate post, but suffice it to say I’m still trying to figure out whether or not I liked the ending. (And EarthBound’s cast list at the end blows Mother 3′s out of the water, but never mind that.)

Graphically, it has the same cartoony 16-bit sprite style of EarthBound, but larger and with much more detail. Whereas EarthBound gave you a two-frame walk animation, Mother 3 has sprite animation like this:

The battle system is much the same as in EarthBound, including the rolling HP meter. Fighting in Mother 3 relies on more exploitation on that mechanic, however; there are plenty of enemies that do lots of damage, but beating them quickly lets you exit battle before most of the HP drop occurs. Likewise, which characters you rely on to heal makes a difference, since the longer you wait, the closer everyone else could come to death. There’s also a new combo mechanic, where tapping the button in time with the rhythm of the background music deals more damage. Together, they keep battles fast-paced, despite being rooted in an archaic choose-everyone’s-action-at-the-start-of-the-turn system.

Even better, the final battle doesn’t depend on spamming a command that is either only available in the final battle (Sing in the original Mother) or is largely useless until the final battle (Pray in EarthBound). Instead, the final battle in Mother 3 is… something else entirely. But enough about that, without getting into spoilers.

Hippo Launcher

Like EarthBound, the enemies you fight skew strongly towards the goofy. In particular, the villains in Mother 3 spend a lot of time making chimeras, so when you aren’t fighting the Pigmask army you’ll be facing off against kangasharks (kangaroo + shark, complete with a joey + shark in its pouch), cattlesnakes (not a cat + rattlesnake, but cattle + snake), and hippo launchers (which do not launch hippos, but rather are a hippopotamus + rocket launcher, and are just as dangerous as you’d expect).

I’d say that the Pigmask army’s geneticists have too much free time, but their orders come from the top. Normal animals are boring, after all.

The music in Mother 3 is very good, and there’s plenty of it. The sound player accessible from the title screen has no fewer than 250 songs in it. In particular, there’s a lot of variety in the music that plays during battle, which prevents the tap-in-time-to-the-rhythm mechanic from being too easy, especially since some songs don’t have a steady beat to them. My only complaint musically is that the villain’s leitmotif is very heavily represented throughout the soundtrack, so if you don’t like it, that’s going to pose a bit of a problem.

Restrooms

While the “dungeon”-type areas you fight through are generally good, a few in particular stand out. Tanetane Island is wonderfully creepy and disturbing, and the boss at the end was indeed magnificent. The tower in Chapter 8, whose name I won’t mention due to it being a spoiler, is quite possibly the greatest final dungeon I have ever seen in an RPG. At the very least, it has the best use of toilets in a video game, period.

Although having experienced EarthBound isn’t strictly necessary to understand Mother 3, I’d recommend it. Not just because I’d recommend playing EarthBound in general, mind you, even though I would. There are connections to be found between the two games, which I’ll probably ramble on about at great length in the spoilery companion to this post. Maybe someday EarthBound will finally be released on Virtual Console.

Finally, I must say that the Mother 3 translation is very well done. The project’s blog goes into great detail about all the challenges involved in making it, and the end result shows a lot of polish and attention to detail. It wasn’t just a matter of replacing Japanese text with English text; there were lots of technical problems that had to be hacked through along the way, all without anything to go off of except the binary code of the game.

So stop reading this and go play Mother 3.

[Image credit: starmen.net]

On the skillfulness of Maryland drivers, or the lack thereof

I may have the perfect anecdote to describe the average Maryland driver’s complete inability to handle any winter precipitation on the road, despite how getting snow or ice isn’t that unusual during winter.

This morning, there was maybe an inch of loose, powdery snow on the ground. On my commute, I had to change lanes to avoid a car jutting halfway into the right lane after having failed to allow for adequate stopping distance. Just before I passed, said car was in turn rear-ended by another car who likewise had failed to allow for adequate stopping distance.

Comments Off