Team Tycon Mismatch entered the ICFP 2002 Programming Contest again. Last Year our program called (\x.x) got 9^th place. This year, the conference is being held in Pittsburgh (where our team is located!) so we really wanted to win on our home turf.

This year's project was to create a little virtual robot that connected to a server and delivered packages, fighting with other rival robots that it came across. While the problem was not quite as well suited to functional languages as last year's task, easy manipulation of lists and SML's static type system were invaluable in producing a correct program in a short amount of time, especially when we were up all night and not thinking straight.

Participants included: Tom Murphy VII, Dave Charlton, Kaustuv Chaudhuri, Adam Goode, Adam Chipala, and Jason Reed (though most people didn't work for the whole weekend). Several others helped us brainstorm at the beginning, though our early idea of creating several entries, some of which would attempt to recognize and help our "premiere entry," was aborted when the contest organizers changed the rules to only allow one entry per team. We wasted a lot of time trying to implement a server and being a bit too ambitious (as usual), but spent the last day/night and a half very productively.

Our robot, Zol, implements the following features:

- Written in Standard ML (along with a tiny bit of C code to implement TCP/IP sockets). We compiled to a fast and lean binary with MLton. This year, Tycon Mismatch's was the only entry in SML!!

- Fast path-planning using Dijkstra's algorithm. Path planning performs robot avoidance by treating paths through robots as much longer. Our code is fast enough to run every turn without any kind of caching.

- Heuristics for approximating solutions to the knapsack and traveling salesman problems. In our opinion, this is where the real competition will be! Our algorithm works by attempting to collect close packages (or packages along a path) into "clusters" and then running a limited knapsack problem solver on them.

- Very simple local death avoidance and opportunistic robot killing tactics. We thought about implementing some sort of game-tree search when near other robots, but eventually decided that this was a pain and probably wouldn't be worth it.

- Pruning of impossible-to-deliver packages (because the destinations are unreachable, in water, etc. or they are too heavy) and removal of empty bases.

- Color ANSI graphics:

Reading over the other team web pages and supposing that most of the best teams were proud enough to make pages for their bots, I think we will be competitive but probably not victorious unless we are lucky. In particular, I am worried that our robot will have trouble with the following:

- Robots that hide packages. While we don't assume that a dropped package was delivered, we also don't bother walking towards these squares. Hiding packages is really clever; we didn't think of it. I can only hope that some maps hurt hiding robots because the cash supplies are so low that they waste their money hiding packages that nobody would ever be able to afford delivery of.

- Other deterministic bots with similar strategies. For instance, two copies of our bot trying to pass each-other in a two-space-wide corridor (under certain circumstances) will endlessly attempt to side-step each other.

- Maps with lots of robots and lots of shoving. While I don't believe many robots will do well in this kind of map, we don't handle dropping packages very well (though we do notice if we're attempting to deliver a package we don't hold and change our plan).

If you're curious, you can download our entry with source code (291kb). Feel free to run it in unofficial battles.

Update: The #haskell team has some Software for running and visualizing robot games. Unfortunately, the two games they show for Tycon Mismatch also show off two serious bugs of ours: First, if we are pushed and as a result drop our last package, then we will throw an exception when we look through our empty package list for another destination. This mission-changing stuff was a last minute addition and I screwed it up. (Sorry team!) Second, if we are "lucky" enough to kill another robot by pushing him into water that is 2 or more spaces wide, our driver code will not notice the death of that robot and attempt to push him again (by stepping into the water that he just died in!!). I simply didn't realize that robot death wasn't implemented in the driver. Given these, I suppose Zol will have a good showing in the 1-on-1 maps, but many very short multiplayer games unless we are lucky.

Update 2: Well, the results are in, and by my estimation we got about 9th place again (though we were as high as 6th place after some rounds). I was quite surprised that we were the only SML entry, but that had the nice side effect of making SML the language with the highest average score across all entries. (Just barely edging out Forth, heh.)

In any case, we had fun and we'll be back again next year! See you at ICFP!

- Tom 7