This page describes the 2002 ICFP Programming Contest entry by Mieszko Lis (elf at mit dot edu) and Jeremy Sawicki (jeremys at mit dot edu).
Team name: Frictionless Bananas
Program name: Skipperdee
Our submission: skipperdee.tar.gz
The program is written in Haskell, with a little C++ for speed.
Our plan was to focus mainly on delivering packages well in the absence of other robots. After seeing how our program behaved on the multi-player servers provided by the judges, we made a few enhancements to deal with other robots, but we mostly concentrated on delivering packages.
Our program uses a simple breadth first search to find shortest paths to all board locations from a given starting point in linear time. This was originally implemented in Haskell, but it was rewritten in C++ for speed. The C++ version is fast enough to call once per move on a 1000x1000 board with time to spare. (Alas, it also contains a bug that will likely make it crash on the tree-like boards described by Team Radical Too. Hopefully the judges won't be so cruel.)
The breadth first search produces a table of distances that can be used to plot a path to any location. When reading an path from the table, there are sometimes several possible moves that will result in the shortest distance. In those cases, we favor squares that aren't adjacent to water, and otherwise choose randomly.
Once we have decided to travel to a given location, the path to the location is remembered for use on later moves, so on some turns the shortest path algorithm is not called at all. On the other hand, it may be called multiple times in a single turn when we are planning the best route to deliver packages to multiple destinations.
Our program keeps track of packages it has seen, as well as a list of unexplored bases. Unfortunately, it doesn't make any attempt to remember packages that have been dropped, so it can be fooled by robots that hide packages. Due to a bug, it also won't remember packages that it sees when it is carrying too much to be able to pick them up.
When the robot is not carrying any packages, it will head for the nearest location where it thinks there may be some, either an unexplored base or a location where it has previously seen packages (that haven't since been picked up).
Once it reaches a location with some packages, it will pick up as much as it can carry using a greedy strategy, favoring packages with closer destinations, and among those with the same destination, favoring larger packages.
After picking up some packages, the robot may decide to look for more packages before beginning delivery. This is done if 25% of its carrying capacity is still available, and if it estimates that it has enough time to deliver everything it is currently carrying. The intention is to pick up a large load before delivering, even if the packages are scattered among many bases, to allow us to plan a more efficient delivery route. There is some danger that given the right distribution of package sizes and a world with many bases, we may spend a lot of time exploring new bases to try to fill our remaining carrying capacity instead of delivering what we already have.
Eventually our robot will decide to stop picking up packages and start delivering. If it is carrying packages headed for multiple destinations, it attempts to solve a traveling salesman problem to find the shortest route to deliver all of the packages. If the number of destinations is small enough, it will solve the problem exactly, otherwise it will approximate the solution using a minimum spanning tree. The need to return to a base to pick up more packages after the delivery is not considered.
Solving the traveling salesman problem requires knowing the distances between all pairs of destinations, which means running our shortest path algorithm once for every destination. The program keeps track of how much time it takes to run the algorithm, and it also keeps track of its CPU usage, so it can tell if it has enough time to compute the distances needed to solve the traveling salesman problem. If there is not enough time, it resorts to greedily heading to the closest destination.
Our program detects the simplest situations where it can be pushed into the water or it can push another robot into the water. If it can be pushed, it bids 10% of its remaining money, and makes the same move that it otherwise wanted to make. If it can push another robot into the water, it bids 5% of its remaining money to push it in. Besides the very large bids near water, the program bids 2 when it is adjacent to another robot, and 1 otherwise.
The program also contains a crude mechanism for avoiding deadlock situations. If there are other robots in the world, it will move in a random direction every 100 moves or so. While it would be better to detect repeated positions and get out of them more quickly, at least with this quick hack we will only be stuck for 100 turns instead of 5000.