Watt's ICFP 2002 Entry

I spent the first 1 1/2 days trying to find a decent winning strategy. Unfortunately, I didn't find one and just started hacking up something heuristic, which meant I only had 1 1/2 days left. I vaguely remember that I did the very same mistake last year.

So, this robot doesn't care much about other robots, nor does it care about water, although it won't step into water unless pushed by some better entry ;-). Well, at least it has a decent search algorithm which was fun to write. Now, one day after the contest, I see lots of little things I could change to seriously improve the robot's AI. However, I am not entirely sure if that would really make much of a difference. The combinatorics of pushing battles seem to be quite hard to implement, let's see whether entries that care about them perform so much better.

My solution consists of only 686 lines of Common Lisp code, including empty lines and debugging code (there is only one commentary line). There isn't anything you could call design in it, as I don't intend to change anything after submission, anyway. But when I read a printout again during lunch today, it didn't look as bad as I expected. Actually it is quite readable, I think.

I liked this year's task very much. What I didn't like was that you only had three days instead of three months which seems more adequate for a problem with so many facets.

My submission can be found here.

P.S.: I just realized that I did something really stupid: If a home base contains thousands of packages, and my robot has just delivered a package and is wondering about what to do next, he'll compute a path to each package, which means he'll compute the same path thousands of times. Doh. I still think memoizing every path computation isn't worth the effort and only costs memory, but this really calls for a temporary hash table. Adding one would be an additional three lines or so but what the heck, that's life. I'll win next year ;-)

Nils Gösche