Team Tycon Mismatch participated in the ICFP Programming Contest for the fourth time in 2004.

This year's project was similar to the 2002 problem. In it, entrants had to create "ant brains" in an extremely limited programming language. These ant brains, loaded into simulated ant colonies, were simulated in 1-on-1 battles with other entrant's ant brains. Score is based on the total number of battles won, where a battle is won if the ant colony collects more food than its opponent. Because the ant brain language is so simplistic, it was necessary to develop tools for programming in a more civilized way. In order to test and compare our brains, it was necessary to create a simulator, and in order to debug them, it was necessary to develop a visualization system. (Reading the contest task will make it easier to understand the discussion on this page!)

Participants this year were: Tom Murphy VII, Derek Dreyer, Adam Goode, Jason Reed, Daniel Spoonhower, and Joe Vanderwaart. Almost everyone worked throughout the weekend in the cluster, including some late nights and caffeine-addled giggling fits.

We implemented the following stuff, all in Standard ML:

A simulator for the ant brain arena, implemented according to the specification. Amazingly, Jason and I got this to be correct the first time it ran, which is a testament to the power of statically typed functional languages. Unfortunately, we spent two hours "debugging" it, which is a testament to our ability to not read the documentation accompanying the sample data. The simulator was pretty fast (after a little profiling we could run a 100,000 step battle in about 4 seconds, even while keeping the code quite clean), and once we cached the results of battles (which are deterministic), it was not a bottleneck in evaluating our brains, even across all 10 sample worlds. Owing to our experience in Grid Computing ;) we managed to get the entire cluster (about 20 computers) working for us constantly, running battles of our current creations and displaying the results via a projector on the wall. This really raised morale, since we'd get instant feedback on the little tweaks (or totally new strategies) we'd make.

An "assembler" that supported labels, if-then-else, conjunctive and disjunctive conditions, constants, "functions," and a minimal amount of state. The assembler grew in functionality as we realized what was important in writing brains, so we ended up supporting a lot of legacy ant code in less than ideal ways. Joe and Spoons wrote almost the entirety of the assembler (especially joe), although Tom contributed a correct optimization pass that made most ants perform worse. (!!)

Some nice visualization of ant battles, which Adam did using Tom's crappy and incomplete port of Xlib to SML. We lived with cryptic ASCII art for a long time before this was developed.

screenshot 1, screenshot 2

A compiler for a high level language. Derek wrote this, but I don't think it really got used, because we didn't understand how to modify it.

A mutator that would attempt to cross-breed ant brains to produce better ant brains ("genetic programming"). Joe got started on this fairly late, and we didn't really get any interesting results from it: every ant either (a) behaved exactly the same as another non-mutant ant or (b) performed really badly. Despite the naive appropriateness of genetic programming, I will be really surprised if any entry created this way does well. I believe that brute cleverness will win the contest easily.

At least 82 ant brains. We had much joy in tweaking in renaming ants throughout the weekend. Here is a cute family tree (130k PDF) leading up to our ultimate solutions, meatwad and catsnip.

meatwad devotes a few ants to creating 'spokes' from the base that direct ants with food back to it. Base defense is accomplished with the 'stapler' strategy (which leaves a bunch of our ants randomly crawling in and around our base, chewing up enemy ants that they find). Additionally, ants that find food create food spokes, directing ants without food to food. Meatwad does not do any attacking, but places highest in our private arena.

catsnip is mostly the same as meatwad, but attempts to attack and surround the enemy base without entering it. catsnip defeats meatwad, although it places much lower in our battle arena.

Since entering, we've run our ant brains against other contestants who have posted their brains on the web. Some teams have some really clever strategies that defeat our ants to varying degrees. However, we've found that it is really hard to tell what ant will emerge as the overall winner from one-on-one battles--it depends much more on the overall composition of the entry pool. For instance, we had several rock-paper-scissors situations in our set of solutions.

If you're curious, you can download our entry with source code (412 kb). Here are direct links to our two solutions: meatwad.icfp, catsnip.icfp. Feel free to run these in unofficial battles!

We had a really great time with this contest and applaud the PLClub for their excellent taste and the exemplary quality of the task specification. We'll be back next year!

- Tom 7