Democracy Backfires

I think I’ve found a flaw in cunning plan to vote by absentee ballot: I now appear to be on just about every campaign’s mailing list. Oh joy.

(And lest you think I’m just being paranoid, more than one of the campaign letters I’ve received make explicit mention of the fact that they got my name from the absentee voter list.)

A few interesting observations (not to be confused with fun facts, as while these may be facts, they aren’t really fun) from the mailings:

  • The attack ads are purely negative, as in they avoid any mention of who they want you to vote for, just who they want you to vote against. And I’m cynical enough about politics to take this to mean that the candidate I’m supposed to not vote against has the exact same flaw he’s attacking in his opponent. (Especially when it’s a Republican ad accusing the Democratic candidate of increasing spending, when the Republicans of late haven’t exactly been paragons of fiscal responsibility themselves.)
  • All of the Republican ads have been pure attack ads. Only some of the Democrat ads have been pure attack ads.
  • All the Democrat ads are addressed to “Paul Kuliniewicz”, whereas all the Republican ads are addressed to “The Kuliniewicz Family”. I guess they didn’t get the memo; the former lives in Maryland, whereas the latter lives in Missouri, and I’m pretty sure the Maryland State Board of Elections wouldn’t like the latter voting in a Maryland state senate race. Plus, one of my cynical rules of thumb as far as politics go is to be suspicious as soon as someone says the word “family”.

(And lest you get the wrong impression from the above list, no, I’m not voting straight Democrat. And no, that’s not just because in one of the races a Republican is running unopposed (yes, in Maryland!). Who taught you to be so cynical about politics? Sheesh. It’s just that the Republican ads so far have been easier to poke at.)

Also, one thing you learn from perusing the ballot is the races with people you’ve never heard of for offices you never even knew existed. I mean, everyone knows about the races for governor or Congress or the state legislature, and even if they don’t, it’s pretty well-known what those people do. But then you run into something like electing the Register of Wills. I’m not entirely sure how that’s a partisan office. And wait, I’m supposed to pick three out of a pool of six people to be a Judge of the Orphans’ Court? Which doesn’t even have anything to do with children?

And if you think that’s weird, try this on for size: the Libertarians, Greens, and Populists are all backing the same candidate for the U.S. Senate! How exactly does a Libertarian, a Green, and a Populist agree on anything?

Baleeted! (or, Return of the Halting Problem)

It seems as though my account on Purdue’s web server has finally been disabled. Hopefully you updated your bookmarks to point to this server by now….

Of course, anything of value that used to be hosted there is also available here. For example, this Dinosaur Comics fan comic on the Halting Problem I made a while back.

To my Maryland readers

Did you know that Maryland voters can vote by absentee ballot, no questions asked? Just send in the request form by the end of the month and you’re good to go.

Why would you want to do this? Two reasons spring to mind:

Fun fact: Maryland’s governor is encouraging voters to use absentee ballots instread of Diebold’s machines as well. And being an election year, people will argue about why that is.

Comments Off

Attack of the Underflow

In principle, the last major piece of Wallace has landed: randomly generating solutions, evaluating them, throwing away bad ones, and generating new solutions through asexual (cloning and mutating) and sexual (using crossover) reproduction.

However, there’s two small problems. First, the stack-based VM is exceptionally prone to crashing. Second, the stack-based VM is exceptionally prone to crashing. Now I know technically speaking that’s only one problem, but I thought it was such a big one, it was worth mentioning twice.[0]

The implementation of the VM, of course, is fine. (At least, there aren’t any known bugs in it.) Rather, the programs that are running within the VM have a tendancy to perform an illegal operation and crash. There are four ways in which a program can crash inside the VM, most common first:

  • Stack underflow: It tries to pop a value off the stack, but the stack is empty.
  • Reserved opcode: It tries to execute an opcode that has no operation associated with it.
  • Stack overflow: It tries to push a new value onto the stack, but the stack is already full.
  • Divide by zero: Because you can’t.

Reserved opcodes could be eliminated by assigning them to something, but the stack underflows are quite problematic. Out of 89 operations the VM supports, only 6 of those don’t try to pop anything off the stack. The vast majority of operations not only need to pop their operands, but they also leave the stack with fewer values on it than it originally had. So naturally, when you’re randomly generating programs to run in the VM’s instruction set, most of the time they’ll trigger a stack underflow and crash.

In fact, the vast majority of programs crash on their very first instruction. Furthermore, in a trial using a population size between 100 and 500 candidate solutions, measuring fitness solely by how many instructions got executed before a crash, even after 50 generations the typical candidate solution still only managed to successfully execute 2 instructions before crashing.

Granted, that’s up from a median of 0, but it’s still not very encouraging. And to keep this in perspective, you’ll obviously want these programs executing more than one instruction per emulated frame, and there’s slightly over 60 such frames per second. Programs that die after only a handful of instructions aren’t going to get anywhere.

(As a side note, however, one candidate solution — one of the initial randomly-generated ones — actually managed to hit the 6000-instruction timeout I arbitrarily set! I wasn’t able to peek into it and see what it was doing, but I strongly suspect it managed to jump into the “uninitialized” portion of memory, which would be filled with 0 bytes, all of which map to nop. Whatever it did, that “gene” never got passed on to anyone else in the population.)

I’m forced to conclude that, despite the stack-based VM being attractive from an implementing-the-VM perspective, it’s quite unsuitable when throwing random code at it. A register-based VM would be infinitely more robust, since the registers the instructions operate on will always be there; just the values stored inside them would change. Alas, this change involves replacing just about everything in the VM except for the mutation engine, which is a large chunk of tedious (but relatively straightforward) coding. But unfortunately, it must be done.

Footnotes

[0] To steal a line from my laptop’s namesake.

Best Wikipedia Quote Ever

Hammerspace should not be confused with Hammertime.

[taken from Hammerspace]

Comments Off

Science!

Science again! I said science again!

Ahem.

So, guess who has an autographed copy of Sean Carroll’s new book The Making of the Fittest?

OK, considering where you’re reading this, you can probably hazard a guess. But wouldn’t you like to know how I got one? No? Too bad.

The Carnegie Institution down in D.C. has a roughly-monthly free science lecture series. Go ahead, click that link; I dare you to find one that doesn’t sound interesting.

Wednesday’s lecture was given by, you guessed it, Sean Carroll, wherein he talked about all sorts of evidence of evolution we’ve discovered thanks to our newfound ability to study genomes. The talk had everything: fish with antifreeze for blood, rodents living in desert lava flows (a domestic version of the famous peppered moths, birds that see ultraviolet light so they can find vole urine trails, Monty Python, and more! He even managed to hold off plugging his book until the Q&A session that ensued.

Needless to say, he was on hand to sign copies of his book, an opportunity I availed myself of.

Also, for the record, last month’s talk on supersymmetry was also very interesting. Dr. Gates did a great job explaining how supersymmetry relates to both “normal” particle physics and string theory and how experiments at the LHC will test it, and doing so in a way that didn’t presuppose any familiarity on the subject in the audience. (How does one pull off such a feat? Lots of animations helps.)

As an added bonus, you get to walk past the Iraqi embassy on the way from Dupont Circle to the Carnegie Institution. You know, in case you want to pick up a contact insurgency.

If the quality of the talks I’ve attended so far is any indication, if you have even the slightest interest in science, it’d be well worth it to check them out.

(Note to the junk mailers in the audience: yes, I learned about these talks from somehow getting on the Carnegie Institution mailing list. Just because I made an exception for them doesn’t mean I’m still not going to put any of the junk you want to send me directly into the shredder.)

LIFO the Party

Time for your irregularly scheduled Wallace update.

As you’ll recall, there are two key things you need for genetic programming (or, more generally, any evolution-like process): chunks of information that gets replicated imperfectly, and a metric for evaluating each chunk’s fitness; the less-fit chunks are discarded, and the more-fit chunks go through the process again.

Well, we now have a data representation for our “solutions” to the “playing Super Mario Bros.” problem. While a simple sequence of button presses could’ve worked, it feels like we’re working with recordings rather than organisms. (Actually, we would be; an FCEU movie file is little more than a compressed sequence of button presses.) So if we want better verisimilitude with biological evolution, we want our candidate solutions to be more “alive” than that.

So, why not make our solutions computer programs themselves?

Before going into too great of detail how I’ve gone about doing this, here’s an example of a very simple program playing Super Mario Bros., and doing surprisingly well considering it was my first attempt. (There’s no genetic programming going on here; the program playing in the video below was hand-coded.)

Mario v. a quick-and-dirty program to try to play it

Ogg Theora video, 938 KB, 37 seconds. Ogg codecs for Windows might be found here.

Over the weekend I’ve implemented a quick-and-dirty virtual machine in which you can write programs that try to play Nintendo games. The VM provides some key services:

  • A simple instruction set similar to machine code to build the programs out of.
  • A means for sending button presses to the emulator.
  • A means for reading the game’s memory.
  • A sandbox to prevent a misbehaving program from doing any damage to the actual system.

Unlike the instruction set probably used by the computer you’re sitting in front of right now, the VM is a stack-based (as opposed to a register-based) machine. There’s a stack that just about every instruction uses; each instruction pops its arguments off the stack, does its work, and pushes the results onto the stack.

This kind of architecture saves us from having to worry about what addressing modes we need for each instruction; everything simply uses the stack. Granted, since the VM I’ve written can work with both 8-bit and 16-bit values (the NES uses an 8-bit processor, but we need 16 bits to easily address all memory locations), the instructions do worry a little about the types of data on the stack. Of course, it would be possible to store type information in the stack as well, but then the instructions all need to be clever about how they handle each possible data type, which makes implementing the VM more error-prone.

Anyway, I’m sure you’re dying to see what program generated that video that manages to get all the way to the halfway point of World 1-1. Well, here it is, converted to an assembly language-style format:

start:     push_i8u 0x82       ; RIGHT + B buttons
           pop_r               ; write to output register
mainloop:  push_i8u 20         ; will loop for 20 vblank periods
waitloop:  pause               ; wait for next vblank period
           push_i8u 1          ; decrement our counter ...
           sub_i8u             ;   ... by one
           dup                 ; push a copy of the result
           push_i16 waitloop   ; if counter isn't zero ...
           cja                 ;   ... go back to waitloop
           pop                 ; throw away counter
           push_r              ; get our current output
           push_i8u 0x01       ; A button ...
           xor_8               ;   ... gets toggled
           pop_r               ; write to output register
           push_i16 mainloop   ; and go back to top ...
           ja                  ;   ... of mainloop

OK, so I lied; all instructions except the push immediate instructions get their arguments from the stack.

Anyway, as you can see from the comments, all this program does is hold the Right and B buttons constantly, and every 20 emulation frames (about every 1/3 of a second) it either presses or releases the A button. As a result, Mario constantly runs to the right and jumps periodically. It’s surprising how far this 16-line dumb-as-a-post program gets on its second life!

So now all that’s left is a way to generate new programs for the VM, making them reproduce and mutate, and pitting them against each other in a battle-to-the-death.

Columbus Day

Today is Columbus Day. To help you avoid getting dragged into yet another asinine argument over whether Columbus Day should even exist since the Vikings were here first, an argument over that argument since the people who walked across the Bering land bridge were really here first, or hearing Ohioans boast about how Columbus Day is way better than South Carolina’s lame Columbia Day, here’s a question you can use to distract argumentative people with:

Was Greenbelt, Maryland named that because it’s where the Washington Metro‘s Green Line meets the Beltway, or was the Green Line named that because it ends where the Beltway passes through Greenbelt?

Napoleon Dynamite

I don’t get it.

Crossing the Streams

The latest update to Wallace, despite the delay since the last installment, doesn’t actually add any features directly related to its ultimate goal of using genetic algorithms to evolve something that can play Super Mario Bros.

Instead, it ports the audio/video code from SDL and drawing-pixmaps-on-the-window, respectively, to the GStreamer framework.

One of the neat things about GStreamer’s design is that it uses pipelines of elements to process multimedia streams, sort of like how you’d put together a bunch of simple programs on a Unix command line. Under this model, doing different things with the data just involves using different elements to process it. For example, taking the emulator’s output and sending it to the screen and speakers involves this pipeline:

Output pipeline

Walemulatorsrc is a custom-made element that acts as a source for the emulator’s output audio and video streams. The two queues act as buffers. Gconfaudiosink and gconfvideosink output the audio and video streams, respectively, using the user’s preferred output methods. This, for example, could let us render to video memory directly. But since the emulator has a very specific format for its audio and video streams, which may not match what those two sink elements accept, the streams are first passed through filters that can convert between different audio (audioconvert) and video (ffmpegcolorspace) formats.

The advantages of using a pipelined series of elements like this is what happens if, say, instead of drawing to the screen and playing to the speakers, you want to encode a video file instead? Well:

Encoder pipeline

Now after converting the streams to a convenient format, we run the audio stream through a Vorbis encoder, run the video stream through a Theora encoder, multiplex the two streams into an Ogg media file, and write the result to a file. Of course, there’s no reason you couldn’t generate a video file in whatever your favorite format is, either; it all depends on what elements you plug into the pipeline.

And as proof that this works, you can watch me beat up Metal Man from Mega Man 2:

Mega Man v. Metal Man
Ogg Theora video + Vorbis audio, 2.8 MB, 40 seconds. Windows users might be able to find the necessary codecs here if they don’t have them already, I guess.

Also, using GStreamer elements to render video on-screen scales the video to fill the window for free, which is a nice side benefit.

As nifty as all this is, and as simple as it seems in principle, implementing it turned out to be trickier than I expected. The main source of headaches was the need to implement that walemulatorsrc element myself. No prior experience writing elements + non-trivial behavior (two source pads, fed asynchronously by the emulation core) = lots of aggravation. I’m sure anyone who groks GStreamer would shudder at the code inside that element, which, let’s be honest, has a fair amount of the proverbial duct tape and baling wire.

Also, I had expected outputting the video via GStreamer to be faster than drawing a pixmap image onto the window about 60 times a second, but it turns out the GStreamer solution takes more CPU time than the “ugly and wrong” way. A little tentative profiling with Sysprof suggests that 20% of the CPU time is being spent inside that ffmpegcolorspace element, converting the 8-bit RGB bitmaps generated by the emulation core into the YUV color space that elements like gconfvideosink and theoraenc seem to want. It may be worthwhile in the future to eschew ffmpegcolorspace and do the conversion within walemulatorsrc, but you know what they say about premature optimization.

I promise, the next status update will actually further Wallace along to its ultimate goal. I can’t wait to see how what I have planned next stacks up.

[Editor's note: your homework exercise is to figure out why that last sentence is a combination clue and pun.]

Beat Frequencies

Apparently I’m not the only one who notices that just about any pair of cars’ turn signals produces a beat frequency. I’ve never gone this far with it, though:

Turn Signals, from xkcd

Triumphant/Abundant Return

Since last Saturday was Chuck and Christina’s wedding, I headed back to West Lafayette, Indiana for the weekend. Of course, the wedding itself was just part of an elaborate plan to trick me into returning to campus during Purdue’s homecoming weekend. (That’s right, I know all about The Plan; what did you think I was reading on the plane, anyway?) Despite being aware of this foul play, I decided to go nonetheless, as I didn’t want Them to know I knew.

Unlike last time I headed to Indiana for a wedding, the travel itself went off without a hitch, aside from the fact that I now understand that your typical driver in Lafayette would get eaten alive in Maryland. I finally got to campus in time to catch the tail end of that evening’s improv club meeting, the running of which is going smoothly under its new management.

On the way to head out en masse for food after the meeting, I rode by the new CS building, you know, the one they’d been talking about ever since I was a freshman and that finally opened this semester. From the glimpse I got going past it looked as though they had picked up the stargate from Cheyenne Mountain‘s going-out-of-business garage sale, but apparently it was just some some loopy “sculpture” in the lobby.

After that, T-Rex, Tripod, and Alex graciously let me crash at their apartment. Luckily and strangely, they had a spare matress and box spring in their hallway which I was able to avail myself of. (I can only assume the hallway matress is there in case Hallway ever needs to do his eponymous thing.) Given the free mattress, only downside to crashing at Ryan’s apartment is the near-constant Game loss when in his proximity.

Come Saturday morning, I drove down to, um, the greater Lebanon area, I guess, for the wedding. This is where my deepest fears about The Plan coming to fruition made themselves felt, as the directions took me from interstate highway to rural highway to lane-and-a-half rural routes through cornfields. Fortunately, the little resort where the wedding was to be held finally emerged. I thus felt a little safer, but only a little, because statistically speaking it was probably one of the roughly infinity billion potential terrorist targets in Indiana according to DHS.

The wedding went off with only two hitches. The first was the wedding being moved indoors due to the threat (presumably due to the aforementioned terrorists) of rain. The second hitch was, of course, the wedding itself. The reception afterwards offered up plenty of oddness, and I’m not just talking about the orange cake in the buffet line. For example, the bride and groom sat at a small table apart from everyone else, including the rest of the wedding party. I can only assume it was meant to symbolize their new ostracism from the community, I guess? There was also the band, who I’m going to affectionately call The Sound Check Experience, because they spent way more time than anybody needs doing sound checks, including, in what I thought was a particularly tasteful decision, during the pre-meal prayer and the toasts by the best man and maid of honor.

After food and lots of time catching up with more friends I hadn’t seen in months (including Andy “I caught E. coli before catching E. coli was coolOber), we blew bubbles at the bride and groom as they left, because apparently throwing rice causes birds’ stomachs to explode, and throwing birdseed attracts birds (go figure!). Or at least, some of us tried, but the wind preferred to blow them back in our faces.

After driving back up to West Lafayette, I hanged out for a while with Tripod’s extended D&D group, which was just wrapping up in time for dinner, followed by a little Katamari and Smash Bros. action. And after that I went over to Hillenbrand Hall for some Settlers of Catan action with T-Rex, Jenny, Tripod, Cowboy, and an RA.

Fun fact: that Saturday was the longest continuous time in which I wore a tie.

Sunday, Tripod and I attempted to get a network game of Alpha Centauri, but judging from Wireshark‘s output, the Windows and Linux version of the game use not only different ports but also different protocols (TCP v. UDP, though I can’t remember which does which), so we ended up hotseating for a while. Also, I’m not entirely sure, but Tripod and T-Rex might’ve gotten me hooked on House.

Alas, after adjusting for travel time, the weekend soon drew to a close, and soon I had to head back down to Indy for my flight back out east. Stupid passage of time. But I showed it; I waited a week before writing this. In your face, fourth dimension!