Team Tycon Mismatch made a valiant return to the ICFP Programming Contest in 2005. This was their fifth time; see also web pages for 2001, 2002, 2004.

This year's problem was loosely based on the board game Scotland Yard (a Spiel des Jahres winner), set in the mean streets of post-robocalypse Chicago. Teams submitted both a "robber" program (which tried to rob banks and avoid the law) and a "cop" program (which cooperated with other cops to try to capture the robber, whom they could not usually see). This year provided a special twist: two weeks after the initial entry, a revision to the specification was published, with only 24 hours to adapt our players to the new game. You can read the original and twist specs for more details on the rules.

Main participants this year were: Tom Murphy VII, Adam Goode, Daniel Spoonhower, and William Lovas, Noam Zeilberger, and Neel Krishnaswami. Tom and Spoons both worked remotely, sometimes without contact for many hours. We also received short-term help from Jason Reed and some game theory and calculus advice from Neal Martin.

As always, we programmed in Standard ML, using the mlton compiler for its nonpareil speed (and now, even better error messages than SML/NJ).

Like we did in 2004, we implemented many different cops and robbers, and then ran hundreds of simulated battles on clusters full of computers with a "scoreboard" to compare their performance. This was much harder than in 2004—sad to say, in part, because of bugs in the simulation software provided by the organizers. Unlike last time, it also was much more difficult to anticipate the possible range of strategies, and we often saw behavior that strongly contradicted our intuition. However, this was a delicious way to gauge our progress and compete with one another. Here is a picture of some of us standing in front of the scoreboard at 5:30am on the last day. We all look pretty stupid, but it is hard to stare into that thing so late at night.

Despite frustrations, you can see that we are clearly still having a good time.

Our entries were as follows, separated into original entries and twist entries:

Robbers

(original) Francois is a famous French thief, for whom Spoons will perhaps write a description soon.

(twist) OptimusPrime performed probablistic game tree search using hypotheses about where the cops would think that he was. Using these hypotheses he was able to form hypotheses about where cops would be in the future, etc. Playing against multiple opponents in uncertain circumstances is computationally (very) expensive, but through various concessions we were able to search to a depth of about 8 half-moves before applying a heuristic. Thanks to timely help from the mlton team, we were able to time limit these computations to stay within the rather strict 5-seconds-or-disqualified boundaries. Although OptimusPrime is tactically very good, he lacks overall strategy and can be trapped into doing pointless things by certain long-term cop arrangements. We submitted two differently-tuned versions of OptimusPrime.

Cops

(original) CirclerElect, ProtectorElect had a simple strategy for patrolling banks. They also tried to rig the election to gain bonus points for themselves, ignoring the other cops' proposed plans.

(twist) Agent Smith considers Neo his mortal enemy. We submitted two versions.

Moreso than previous years, last minute delirium left us with generally low confidence in our entries. They are very likely correct (modulo possible CPU- and memory-limit issues), but we did not spend enough time tweaking the numerous parameters for real battle. We will be quite interested in the results, but the variance in our arena tests leave us with little way to predict performance.

If you're curious, you can download our entry with binaries and source code (442 kb).

- Tom 7