Linepithema humile

An entry for the The Seventh Annual ICFP Programming Contest.

The results are out. Linepithema humile placed 13th of 361 ants (9th of 230 teams) in the main division. It was the leading ML (SML or OCaml) entry in the main division.

[Screenshot 12_tiny]

Programming Language

This ant (tarball) is written in `pheremonials' above OCaml. This is a low-tech language approach: we define a symbolic ant code which is just an extension of the real ant code with symbolic labels. Various OCaml functions construct lists of symbolic instructions, for spinning, following marked trails, etc. They typically take several ant continuations as arguments and sometimes also additional parameters for marks, follow-states etc. We use a mixture of idioms, combining these functions with fix and seq combinators and writing explicit automata with labelled states. This worked ok for the strategies we were dealing with, where most of the effort was in fine-coding the detail, but it would not scale well to much bigger ants. It's not clear what would be ideal: on the one hand one needs parameterisation for code reuse and state, but when tuning an ant a single multiple recursive definition structure is desirable, so that one can shift states freely. We thought about implementing better support for per-ant state (in principle we have about 4.7 bits available, as our ant is only 382 instructions long) but did not have sufficient will (or a sufficiently compelling application that could easily be combined with the rest of our strategy).

Ant Strategy

Fast Food Finding

We try to find food and get it back to the nest as fast as possible, tuning the strategy to minimise the time taken to find 50% and 95% of the food. With perfect defending the game reduces to a simple food-finding race. Running two copies of the strategy on the sample boards finds 95% of the food by step 14000 - 51000, mean 35500.

Defending

Once we have food, we want to keep it!

The Cyclists

Reflections

After the contest, having run against a few other ants:

The Simulator

Our simulator is hacked up in OCaml, very closely based (by cut-and-paste...) on the sample code provided in the task description. The board and ants are both dealt with imperatively. Significant effort went into providing useful displays and statistics. It can show either the whole board, with limited display of marking (tuned to our ant strategy) or a zoomed view with all the marks, ant directions etc. Graphs of the nest scores, in-transit food and remaining food are drawn; these are very useful to understand the game shape. The step speed can be altered dynamically, so one can explore both detailed and whole-game behaviour. It is reasonably fast. Without the interactive display it takes 1.5 minutes to play two ants both ways on each of the 10 sample worlds, on a 2.80GHz Pentium; about 5 seconds per game. This is fine for interactive use, but still slightly annoying when collecting statistics to tune a parameter with. The final display at the end of a run (on sample9.world) is shown above, and below in a full-size version. This is the non-zoomed display. It shows most of the marking for the red ants, as dots, and the disjunction of the marking for the black ants, as commas. Ants carrying food are capital R and B, those without are r and b. Food is shown as green numbers; there is none left except in the nests.

[Screenshot 1] [Screenshot 2]

Finally, many thanks to the organisers for a great challenge problem.

Peter Sewell and Francesco Zappa Nardelli

[Validate this page.]