A Thanksgiving Reminder

Vegetables are not food. Vegetables are what food eats.

And not even food eats tofu.


Just Say No To Tofurkey

About Smegging Time (or, Wallace 0.99.0 is out!)

I’ll let the following link speak for itself:

Download Wallace 0.99.0 (source tarball, 713 KB)

OK, maybe I can say a little more.

I’ve got Wallace, everyone’s favorite NES emulator for Linux with a genetic programming tool bolted on, worked into a sufficiently functional state to let the outside world play with it. Thet there link will get you a copy of the source code, which you can do the usual “./configure, make, make install” thing on to get a working copy of it.

A couple caveats to keep in mind before diving in, though. First, consider this a tech demo, or pre-alpha software at best, not a polished, finished product. It’ll probably work OK if you don’t poke or prod it too hard, though if you want to crash it or send it into undefined behavior I can think of three ways off the top of my head to do so. Also, I make no guarantees that this release will be compatible with future ones, so don’t come crying to me if the evolver you’ve been running for weeks stops working when 0.99.1 (or whatever) comes out.

And of course, I’ve only tested this on my laptop running Debian unstable. Getting it to run on some other Linux system shouldn’t be too hard. With work you might even be able to get it working on some other platform GNOME has been ported to, but I wouldn’t bet too much on it.

Now that all that’s out of the way, what’s new since the last status update? Plenty! The VM that the candidate solutions run on is now register-based (loosely based on the MIPS architecture), so solutions only crash inside the VM if they try to divide by zero nowadays. You can also save your progress in the evolver tool, it executes as quickly as possible (instead of at normal emulation speed), and you can watch and encode candidate solutions at your leisure.

So what does it take to get a little genetic programming action started? Let’s say you wanted to generate something to play Dr. Mario (since score is much more closely correlated with progress there than in Super Mario Bros.). First, you tell the Evolver what ROM image to use and what the initial state will be — here, we pick a state slot that begins on Level 10 on High speed:

Game tab on the Evolver

Next, we define our fitness function by specifying a set of metrics to measure and how to modify them. Here, our fitness will be the score plus the number of seconds before losing. Note the number of conditions we look for for when to stop evaluating a solution: the virus count dropping to zero (win!), the Game Over screen (lose!), the Pause screen (programs don’t need breaks!), and the Main Menu screen (ever try hitting A+B+Select+Start?):

Fitness tab on the Evolver

Next, we specify how we’ll be breeding our solutions. The Evolver has several knobs you can play with to control population size and how to generate new solutions from old ones. Lots more are certainly possible. For example, it’d be nice to control how important the fitness score is to surviving to the next generation — currently, the top n solutions make it and the rest are culled, instead of doing some random-by-weight sort of selection. Here’s the somewhat arbitrary settings I chose:

Breeding tab on the Evolver

Now all that’s left to do is switch over to the last tab, hit that nice green Run button, and watch the magic happen.

Population tab on the Evolver

So, how well does this work in practice? I haven’t done much intensive experimentation, but early results are encouraging. In the first generation (which are all purely randomly generated), most of the solutions either crash before getting very far or don’t do anything, letting the pills just stack up in the middle until the reach the top. A couple of solutions do exhibit slightly more interesting behavior, such as this one, which rotates like mad and shoves pills to the left as fast as it can:

Solution from Generation 1

The top performer from Generation 1, with a fitness of 16. (660 KB, 16 seconds)

Over the first few generations, the solutions that crash quickly die off, and the ones that just let the pills fall in the middle flourish. Then the ones that shove the pills to one side or another, buying a few more precious seconds and thus increased fitness, dominate. And then, in Generation 6, an exciting development: the first solution to kill a virus!

Solution from Generation 6

The top performer from Generation 6, with a fitness of 309. (383 KB, 9 seconds)

To be fair, that screenshot makes the solution look like it’s playing far more shrewdly than it really is. The video tells the whole story: it’s just shoving pills to the right, but does it at just the right rate to line up the red sections of the first three pills with the red virus.

And if you think that’s neat, check out what happens in Generation 7:

Solution from Generation 7

The top performer from Generation 7, with a fitness of 916. (700 KB, 16 seconds)

That solution pushes pills to the right and rotates them at just the right speed to knock out two virus with the first three pills. It is interesting how the end result after three pills is the same as what I’d do if I were behind the controller. I can’t help but wonder how an Intelligent Design proponent (that is to say, a creationist) would distinguish whether I or a seventh-generation evolved computer program were playing, given that screenshot.

Anyway, the next couple generations don’t turn up anything with a higher fitness than that, and that’s the point where I stopped it so I could work on pushing out this release. Nevertheless, Generation 9 did produce the longest-lived solution so far, clocking in at almost double the time any of its competitors does, and still managing to kill a virus along the way.

Solution from Generation 9

The longest-lived performer from Generation 9, with a fitness of 329. (1.2 MB, 29 seconds)

Not too shabby for a couple hours of evolution on a 1.7 GHz Pentium M, eh?

After all that I bet you’re dying to try this out for yourself, so I’ll reiterate:

Download Wallace 0.99.0 (source tarball, 713 KB)

gcc -c -Wall -O2 -g -fbreak-my-code main.c

You know what’s fun? When you think you have a nice big chunk of code in a state that could reasonably be considered “working” (as far as pre-alpha software goes, at least), and then you turn on optimization, and then suddenly everything falls apart.

One particularly cute way this can happen is if you tell the compiler a particular function’s return value is constant. gcc assumes that the function also doesn’t have any side effects, and will happily optimize away calls to it if you don’t use the returned value. This is a problem if the function not only has side effects, but you were calling the function precisely to carry those side effects out.

OK, technically it’s my fault for misinforming the compiler and not realizing it until the -O2 flag called me on it. But still. Besides, I still blame the optimizer for somehow finding a way into new and exciting code paths that make test cases stop working.

Apparently it’s going to take a little longer still before the next update on Wallace, since now I’ve got to go through and see what other fun little bugs the optimizer flushes out of my code. Grumble.

Not So Fast

If you believe the so-called liberal media, you might think that the Democrats just won control of the Senate. This is not true.

Assuming the current projections hold, including Webb‘s win in Virginia, that only gives the Democrats 49 seats, which makes them tied with the Republicans, who also will have 49 seats. That’s not even a plurality, let alone a majority.

But what about those other two seats, you ask? One will be held by Vermont’s Bernie Sanders, an independent, self-proclaimed socialist. It’s probably safe to say he’ll be more likely to side with the Democrats than the Republicans, which would make it effectively 50-49 in favor of the Democrats.

And then there’s Joe Lieberman, who everyone seems to keep lumping in with the Democrats, just because he was a Democrat before ditching his party after losing his primary to Lamont. But consider the following.

First, even as a Democrat, Lieberman has largely been a conservative anyway, siding with the typical Republican position on many issues. A particularly cynical person might even say he’d be a Republican if he weren’t Jewish. [Editor's note: lest someone somehow misinterpret this, this is a slam against the Republicans, not Jews.]

Second, Lieberman’s support in the election came from the Republicans, not the Democrats (much to Schlesinger‘s dismay, I’m sure).

So, considering that Lieberman was hardly a liberal to begin with, and his newfound power base lies in the Republicans, it’s foolish to just assume he can safely be counted with the Democrats. (And that’s not even counting whatever bad blood may now exist between Lieberman and the Democrats thanks to beating Lamont, plus whatever wooing the Republicans start throwing at him, assuming woo can be thrown.) In fact, it may prove more accurate to consider his voting to lean towards the Republican side, which would give you a 50-50 split in the Senate.

And since ties in the Senate are broken by the Vice President, who last I checked is very much a Republican, that means that any votes essentially along party lines will still go to the Republicans. That’s not what I’d call Democratic control.

(If my reasoning seems a bit precarious, keep in mind I haven’t also factored in the fact that several of the seats taken from the Republicans in this election were won by conservative Democrats. Social conservatives need not worry about having insufficient strength in the Senate to push their agenda, unfortunately.)

In fact, I’ll go one further. I predict that Joe Lieberman will speak at the 2008 Republican National Convention. You can write that down.

[Editor's note: the author lacks any qualifications for making any of the above statements.]