FCEU Redux

Well, I’ve decided to give that crazy idea about using genetic algorithms to “teach” a computer to play Super Mario Bros. We’ll see how well this turns out.

The first step, of course, is to retrofit a NES emulator to be able to do the input and output manipulation I need. And being a Linux user, the best NES emulator around is FCE Ultra, even despite not having been actively maintained for quite some time. Plus, FCE Ultra has built-in support for making and playing movies (really, recording and replaying input), which should be very helpful. In fact, FCE Ultra movies are one of the preferred formats for people who do that sort of thing.

One of the few obnoxious things about FCE Ultra, however, is the utter lack of a GUI under Linux — everything is passed on the command line, and you have to remember the keys to activate the various features. That’s not quite going to cut it for my purposes.

So, the first step is to port FCE Ultra to GTK (and, to a lesser extent, GNOME). That way there’ll be a usable GUI on which to add an interface for working with the genetic algorithms (and, of course, making it easier to play around in general).

Now, I’ve had a little experience before hacking on FCE Ultra — the SDL joystick code is derived from a patch I wrote a few years back. And I remember that the FCE Ultra source code isn’t pretty to look at. The emulator’s an impressive piece of work at run-time, but the main developer really could’ve used that space bar a lot more, and one-space tabs really don’t cut it. It’s not like he used the saved space for comments or anything.

However, despite its flaws, the FCE Ultra source code does have one thing going for it: it already has a pretty good separation between the emulation code itself and the platform-specific interfaces. Sure, the “drivers” for different platforms are fairly tangled together at first glance, but it does mean that porting things to GTK is essentially just a matter of implementing a new driver and plugging it into the rest of the program. It also means that going further to shovel input in and analyze the output of the emulator should be quite doable.

So, at this point, I’m working on implementing basic GTK support into the last official release of FCE Ultra, thus familiarizing me with the ins and outs of the code and providing a friendlier interface for when I get to start working on the fun stuff.

Quote of the Week #98

All science is either physics or stamp collecting.

– Ernest Rutherford

Comments Off

Mario Meiosis

Here’s a (possibly) crazy idea: is it possible to use a genetic algorithm to “teach” a computer to play Super Mario Bros.?

For those of you wondering what that last sentence said, here’s the basic idea. A genetic algorithm is a technique based on evolution for finding a solution to a problem. You start off with a bunch of randomly-generated candidate solutions, which are probably all pretty bad, but that doesn’t matter. You apply a fitness function to decide how good each candidate solution is; even though they’re all bad, some are going to be less bad than others. Then take the best candidate solutions and use them to generate new ones, such as by mutation (changing parts of them randomly) or crossover (swap parts of two different solutions). Repeat until you get a solution that’s good enough.

So, can you use this technique to have a computer discover a way to win Super Mario Bros.? It seems like the answer should be “yes.” We just need to define two things: what candiate solutions look like, and what our fitness function is.

Candidate solutions are easy: a series of button inputs. The NES controller has eight buttons: Up, Down, Left, Right, Select, Start, A, and B. Each button can either be pressed or released at any given instant, and we can easily represent the state of the controller in one byte. (Naturally, not all 256 possibilities are valid, since you can’t press Up and Down simultaneously, and games wouldn’t quite know what to do if you could.)

But how do we define fitness? Intuitively, we want the fitness function to measure how far the computer gets into the game; a solution that gets to World 4-3 is better than one that only gets as far as World 1-2. However, this is much too coarsely grained, as we have no way of measuring progress within a single level. For example, consider when we’re just starting the algorithm, and we’re comparing purely random solutions. It’s very unlikely that any of them will get all the way to the end of World 1-1, but some of them will get farther than the others, and we want to select for them.

Ah, but how do we measure “progress” within a level? We intuitively know what we mean, but how to define it in terms the computer can understand? A naive approach might be to somehow watch the background to determine when the screen scrolls to the right; the more it scrolls, the more progress has been made. Unfortunately, this doesn’t handle warp pipes, since they let you shortcut part of the stage. We want a solution that takes the shortcut in World 1-1 and gets to the staircase to be “fitter” than one that skips the shortcut but dies before reaching the stairs, even though the latter solution scrolled through more of the stage.

One solution could be to encode knowledge of each stage’s layout into the fitness function, so it can determine exactly how far we get each time. This would work, but means that we need to feed a lot of information into the fitness function. Not only is this time consuming, but it makes it very difficult to apply the same approach to another side scroller, even one that has essentially identical mechanics, such as The Lost Levels.

So, even though “progress though the game” is the most intuitive choice for a fitness function, it’s problematic and difficult to actually use. We may be better off with some other metric that’s easier to obtain and that is correlated with progress.

One candidate is the score at the upper-left corner of the screen. In most cases, your score goes up as you go through more of the game, so higher scores should generally indicate more progress. And since the score is displayed on screen, it’s very easy to access. This approach might work, though it could get caught in a “local optimum” that never leads to winning the game. For example, if there’s a 1-up in the stage, you can collect it, earn some points, die deliberately, and then go back to the stage to repeat the process indefinitely. The score keeps going up, but you never get any farther.

Having the fitness function also consider time might help prevent the search from getting trapped in these dead ends. All else being equal, we want a solution that takes less time than the alternatives. A solution that rushes to the flagpole to get points from the time remaining should be better than one that keeps replaying the same stage to get more points. Of course, favoring time too much could lead to the “best” solution being the one that runs right into the goomba at the beginning of World 1-1 repeatedly — fast, but no progress. The fitness function would need to find a good balance between the two measures.

So, it seems as though a good fitness function for Super Mario Bros. considers multiple factors in hopes of indirectly measuring progress through the game.

What happens if we try this approach with different games? Our solutions still look the same — a series of controller states — but the fitness function will depend on which game we want to play. Pac-Man is obvious — fitness equals the score you end with. Not only is score closely correlated with progress (you can’t replay a level to get more points), but we also select for “better” play for each level (eating all four ghosts with each power pellet is better than always avoiding the ghosts).

Galaga is similar, but we might also want to consider the hit percentage as well as the final score; having 95% of your shots hit is better than having only 47% of them hit.

Of course, there are also games where finding a good fitness function is more difficult than for Super Mario Bros. For example, Mega Man 2 is also a side-scroller like Super Mario Bros., but there’s no score whatsoever. On the other hand, since there aren’t any shortcuts, measuring how far the screen scrolls might work (as long as we distinguish the different directions, so as not to reward pacing back and forth).

And if we want to really get crazy, what kind of fitness function would you use for Final Fantasy, without encoding detailed information about plot points and each of the dungeons? Measuring experience points would probably be a factor in the fitness function, but some other indicator of how close you are to beating Chaos would be needed so you don’t just keep walking around Corneria indefinitely fighting Imps. And I’m sure there are other games where finding a simple, effective fitness function is even harder.

Remember, we want the fitness function to be as smooth as possible. A fitness function made only of a few sudden steep steps will increase the time before a candidate solution crosses the magic threshold, as there’s no way to tell ahead of time which candidates are closer. (Compare the refutation of the creationist claim that the eye is “too complex” to have evolved: you don’t need to jump from “no eye” to “eye” in one step, as there’s lots of small, incremental improvements forming a continuum between the two extremes.)

Considering the challenge of choosing a good fitness function for some games, the technical issues of actually implementing a genetic algorithm pale by comparison. All you really need is a way to feed input into the game and screen-scrape the output to get information for the fitness function. Both of these should be fairly straightforward to implement in an emulator. The trick is to give the user a flexible way to specify the fitness function that should be used, which is more a UI issue than anything.

Quote of the Week #97

Today, we are seeing hundreds of years of scientific discovery being challenged by people who simply disregard facts that don’t happen to agree with their agendas. Some call it “pseudo-science,” others call it “faith-based science,” but when you notice where this negligence tends to take place, you might as well call it “political science.”

Michael Bloomberg

Comments Off

Music Applet 0.9.2 Released

At long last, the version 0.9.2 of Music Applet is out! This release adds two significant features:

  • Support for Muine.
  • The ability to launch your favorite music player if needed. When there’s no music player running, Music Applet shrinks down to an ordinary launcher.

There’s also several bug fixes (especially in the Banshee support) and a few new translations too.

Video! Video! Video!

Remember that big Ship of Fools / Andy Ober Orchestra show back in March?

Well, a video of that improv show is now available! Now you can relive your favorite moments, or experience them for the first time if you missed it live, or print each frame on a separate piece of paper and make a giant flip book out of it, if deforestation’s your thing.

Helpful Google Video tip: a higher-quality version can be obtained by clicking the “Download” link to the right of the video. The version of the video displayed on that page is at a much lower resolution to save bandwidth.

If you’re wondering where the second half of the evening is, the one with Andy Ober Orchestra, well, the recording of that didn’t come out so well. The image is fine, but a lot of the lyrics are awfully hard to hear. If there’s enough call for it I can upload that video too, but a lot of that AOO magic is sadly lost.

[Crossposted to the main Ship of Fools website.]

Quote of the Week #96

We must never forget that the Rule of Law is not a conservative or a liberal value. It is assuredly not a Republican or Democratic value. Rather, it is an American value. Confidence in the Rule of Law rests entirely at any given point in time on the character and the integrity of the individual American judge and on that judge’s absolute commitment to fairness and impartiality.

Judge John E. Jones III

Comments Off

Die Busting a Gun

As you may recall, not too long ago I watched Gunbuster in preparation to watch its sequel: Gunbuster 2: Diebuster. If you’re wondering what would possess me to want to watch a sequel to something I hadn’t seen the original of, well, you clearly didn’t read that earlier post. It’s because Gunbuster 2 is being directed by Kazuya Tsurumaki, the lunatic/genius responsible for FLCL.

Well, now that I’ve watched the first five (out of six) episodes of Gunbuster 2, how is it? Does it live up to its predecessors? How does it stand on its own? When will Gainax release the final episode? Read on, as I will expound on 75% of those questions below.

At first, the connections between Gunbuster 2 and its predecessor are unclear. While they both involve people piloting Buster Machines to fight enigmatic space monsters, for the first few episodes the plot similarities end there. Gunbuster 2 takes place hundreds, if not thousands, of years after the original Gunbuster. The breakneck pace of technological advancement seen in the original series seems to have abated, and mankind has resigned itself to staying within the confines of the solar system. Nevertheless, space monsters have infiltrated the solar system and continue to threaten mankind. And the only people capable of repelling the alien menace are topless.

Wait, it’s not that kind of show. Let me explain.

In Gunbuster 2, “topless” (a noun) refers to someone with the innate ability to pilot a Buster Machine to its full potential. The unusual name is a twist on the original Gunbuster’s “Top Division.” It’s not fully explained what toplessness consists of, but there are a few clues offered. Toplessness fades with age, it emanates from the forehead, and can be blocked by wearing a seal on said forehead. Topless abilities include perfoming “exotic maneuvers” with a Buster Machine (your typical called attacks) and the ability open a portal and warp your Buster Machine to your present location. Toplessness and one’s state of undress are orthogonal, despite one character’s initial confusion.

At this point, fans of FLCL will find this brand of toplessness familiar. One of the many unusual plot points in FLCL was using people’s heads to open up interstellar portals that robots or guitars could emerge from, and one of the characters tried to prevent this by wearing obviously fake eyebrows at all times. While forehead portals aren’t the only FLCLism to appear in Gunbuster 2, their appearance, along with other fanciful elements and designs, drops off sharply after the first episode. For example, cats being used as communications devices and main character Nono’s ability to accidentally break almost anything in half (from dinner plates to industrial refrigerators) both get left on the cutting room floor after the first episode. There’s still creative and unusual designs to be found, of course, but it’s toned down considerably. One wonders if the creators thought the first episode’s strangeness was too deliberate and forced, and scaled it back afterwards. You could even say that it becomes less FLCL and more Gunbuster as the series progresses. This is Gunbuster 2, not FLCL 2, after all.

And being Gunbuster 2, while the storyline connections to the original series aren’t elaborated on until several episodes in, there are plenty of nods and references to Gunbuster to be found throughout, the aforementioned use of “topless” being just one example. Besides passing references, there are several scenes that parallel ones in Gunbuster, though frequently they end up playing out quite differently. The plot does tie in to the original eventually, and like Gunbuster takes a turn for the darker about halfway through, though the details are definitely spoilers I shan’t divulge here. And despite taking place long after the events in Gunbuster, there is continuity to be found; for example, Jupiter has been replaced by a massive space station built out of an old spaceship, and there’s a small trans-Plutonian black hole named Exelio in the outer reaches of the solar system. Despite initial appearances, this isn’t just a giant-robots-versus-monsters show with the Gunbuster name bolted on as an afterthought.

Back to the plot, which I got sidetracked from talking about toplesses. The story follows Nono, a naïve, starry-eyed (both literally and figuratively) girl who runs away from home with dreams of piloting a Buster Machine and fighting the space monsters. Of course, she’s lacking in everything that Fraternity is looking for (namely, toplessness), and she ends up cleaning dishes at a nearby diner. There, Nono crosses paths with Lark, the lead topless, who saves her from being harassed by some grunt mech operators. Nono sees Lark as her role model, despite Lark’s not caring and seeing Nono as a nuisance at best. Nevertheless, Nono manages to help Lark defeat a space monster discovered on the Martian surface, and as a result finds a place in Fraternity doing, well, janitorial work. After that, Nono keeps trying to become a Buster Machine pilot so she can be a Nonoriri, something which nobody has any idea what she’s babbling about (and not until episode 5 are any hints presented). To avoid dropping any spoilers, that’s all the plot summary you’re getting.

So, in the penultimate analysis, Gunbuster 2 is entertaining in its own right. The visuals look great, the music’s pretty good (complete with an annoyingly catchy opening theme), and the story, once it gets into gear, is pretty decent. You don’t really need to have seen Gunbuster to enjoy it, though it’d help you at least catch the numerous references to it. It’s certainly no FLCL (but then, what else is?) and, especially considering the initial confusion as to what it’s trying to be, doesn’t top the original Gunbuster (whether or not that’s its aim[1]). Nevertheless, it’s a good series in its own right.

Now I just have to wait however many months it takes for Gainax to release the final episode (late August, apparently) and for it to get fansubbed to see how it all ends.

[1] You see, because the Japanese title of the original series is “Aim for the Top: Gunbuster”, and I said that if it aimed to top Gunbuster, it… oh, forget it.

Comments Off

Pork Chop Sandwiches

G.I. Joe: Sigma Six is a cartoon and line of toys.

G.I. Joe: Six Sigma is a process improvement methodology applicable when fighting Cobra Commander.

Discuss.

Hotel Axioms

1. The probability that a hotel offers free Internet access is inversely proportional to the average nightly rate for a room.

2. Hotels always give you soap and shampoo. Hotels never give you toothpaste. Nobody thinks this is weird.

3. Hotel TVs never carry Comedy Central.

4. Hotel TVs always carry Cartoon Network.

5. Family Guy and/or Futurama and/or whatever show has been moved to the 11 pm EST slot on the [adult swim] lineup can temporarily suffice as a substitute for The Daily Show.

5′. The Oblongs is not, I repeat, not, an acceptable substitute for The Daily Show, not even on a temporary basis. [adult swim], what were you thinking?

6. [adult swim], don’t think running Family Guy opposite The Colbert Report makes up in any way for axiom 5′. [adult swim], you’re on notice.

7. As soon as 11 pm EST rolled around, this suddenly turned from a list of axioms about hotels to a rant about [adult swim]‘s weeknight schedule.

8. And to think I used to find the periodic and unexplained swapping of Futurama and Family Guy’s slots with each other amusing.

Quote of the Week #95

In the twenty years since the Chernobyl tragedy, the world’s worst nuclear accident, there have been nearly [FILL IN ALARMIST AND ARMAGEDDONIST FACTOID HERE].

Greenpeace “fact sheet” against nuclear power

Comments Off