[Icfp04-discuss] Ant entries

[Guillaume Marceau]

Here is our ant. We used the plt-scheme macro system to quickly define a
compiler for a small ant language with rudimentary variables. That left
about a day to tune our ant.

Our ant leaves bread crumbs to find our to the food and the way back
using the three marker bits to encode six directions (like
other people did). We drunkenly follow the marks, since we found that any
perfectly deterministic behavior lead to dead-lock and traffic grid-locks.
We run some local pattern matching while following train to smoothen them
out over time. We erase food trails once they cleared all the food at the
destination, otherwise you get a bunch of ants wondering where the food went.

We also attempt to steal other people's food from their ant hill, and we
have home guards so that our food cannot be stolen in return. Our guards
form a U-shaped trap that every so often kills an unlucky enemy ant.
Finally, we do some martial arts, we run after enemy ants on the off chance that we
might kill then. Plus, with a small probability, ants take the role of a
soldier. Soldier wander around our ant hill, next to the guards, with hope
to trample passer-by more effectively.

The parameters for all the coin flips in our ants where tuned using
a distributed genetic algorithm (to generate a pool of successful
parameters), and tournament elimination (to trim the pool down to one
best parameter-set). The final numbers were: 7% soldiers, 15% dead-lock
avoiding random moves, 3% ignoring food scents, and one out of four step
(25%), we take the time to smoothen the path locally.

The ant-plters are: Matthew Flatt, John Regehr, Greg Cooper,
Melissa Chase, Michael Greenber, Kathryn Doiron and myself.

  http://www.cs.brown.edu/~gmarceau/files/ant-plter.tar.gz

-- 
"The thing I remember most about America is that it's silly.
 That can be quite a relief at times."  -- Thom Yorke, Radiohead

- Guillaume