This page describes the 2004 ICFP Programming Contest entry by Jeremy Sawicki (jeremy at sawicki dot us) and Mieszko Lis (elf at mieszko dot org).
Team name: Frictionless Bananas
Our submission: ants.tar.gz
Our ants:
solution-1.ant,
solution-2.ant
In C++ we wrote the simulator, a tool for visualizing running simulations, and a tool for running tournaments. The visualization tool simply draws the board repeatedly in text mode, using ANSI escape sequences for color.
In Haskell we wrote an assembler to convert ant code from a more easily written form to the form required by the contest. The basic assembler functionality is the ability to label states, and reference states by label instead of by number, as well as using the special keywords "next" and "afternext". The more advanced feature is that the assembler automatically converts each state into 12 states, corresponding to the six possible directions and the two possible values of the "has food" bit. This allows the ant to know its absolute direction and whether it is carrying food at all times. Parts of instructions can be parametrized based on direction or food, so for example an instruction can specify different result states for each direction, or sense different markers depending on whether the ant is carrying food.
Our main ant program evolved through roughly five major versions.
Version 1
Whenever an ant gets to a new cell, it leaves a mark indicating the direction it came from, meant to represent the direction an ant would have to walk to get back home. The mark is represented using markers 0, 1, and 2, which can be thought of as an integer from 0 to 7. The value 0 is an unvisited cell, and 1 through 6 are used for the six directions. A value of 7 is never used. When an ant stumbles upon food, it can follow the markers to quickly get back home.
Version 2
When an ant finds food and heads home, it uses markers 3, 4, and 5 to record the direction it came from. With this information, an ant can avoid wandering randomly in search of food and instead follow a trail pointing to previously discovered food.
Version 3
Eventually all the food at a location is removed, but if a trail still points to that location, ants will continue to go there. So in this version, if an ant follows a trail towards food and doesn't find any, it follows the trail in the other direction and erases it.
Version 4
With the above features, the ants can easily deliver all the food to the anthills in well under 100000 instructions, and after that they just carry food back and forth between the anthills. So in this version ants attempt to guard the food on their own anthill. Wherever food is dropped on the anthill, an ant will remain in that cell. It constantly scans for ants of the same species in neighboring cells that are carrying food, and when it sees one, it gets out of the way to let the other ant deliver its food.
Version 5
In this version, ants don't immediately begin delivering food they discover. Instead, they try to collect all food in the vicinity and hoard it in a single cell. When all the food has been moved to one cell, the ant stays there until it sees an ant of the same species not carrying food, and then gets out of the way to allow that ant to pick up some food.
Second submission
We also submitted another program that is basically the same as the above but with an additional fairly complex behavior. Forty of the ants organize themselves into a chain and wander around looking for the enemy anthill. When they find it, they surround it. It works sometimes, but other times the chain gets stuck or it doesn't find the anthill for a very long time. In general this program doesn't beat our main submission, but we included it because it is interesting.