A colony of exploding ants (Iridomyrmex explodiferus) lives in a cell
of a two-dimensional world. Unfortunately, the nest has collapsed,
and the colony has to find a new breeding site. Each colony has one
queen ant, and some number 
of worker ants. will be reasonably
large, at least 100, and maybe as many as 1000. The objective is to
have the queen ant and at least
worker ants reach
a common new candidate breeding site. (There may be more than one
candidate site, and somehow the ants have to coordinate.)
The queen ant gives off a special pheremone that ants on adjacent cells can perceive. Other ants are odorless. However, a worker ant may choose (instead of moving) to sacrifice himself and explode on his current cell. (That's why they're called exploding ants, of course!) When an ant explodes, he marks the cell he is occupying with a new pheremone, chosen from a palette of 15 pheremones. Worker pheremone markings are permanent and cumulative. So if another ant explodes on the same cell but leaves a different pheremone, both pheremones are perceptible to surviving ants. (But if the same pheremone is left twice on the same cell, the scent is not any stronger than if it is left once.) Note that the queen's pheremone is not permanent: it moves when the queen moves.
Ants can move one cell at a time, orthogonally or diagonally, or they can just stay put. All ants move in a synchronized fashion. Many ants can be on a single cell, so moves do not conflict with one another. Explosions are resolved after moves, so that a newly applied pheremone is only perceptible on the following turn.
Cells may be either open, blocked, or nestable. An open cell may be
traversed by ants. A blocked
cell is impassable. Different maps will have different patterns of
impassable cells that will influence how easily the map can be
searched. A nestable cell is like an open cell, except that it
represents a candidate nesting site. The simulation terminates when
the queen and at least
ants occupy a single
nestable cell. The colony's score is the time taken to achieve this
state. If, after a large number 
of moves, this state has not been
attained, the simulator will stop and the score will be .
Ants can sense their environment, but only weakly. Ants can determine whether there are any ants on adjacent cells (orthogonal or diagonal) but not how many. Ants can also determine which of the 16 pheremones (including the queen ant's special pheremone) is present on the ant's current cell. Finally, an ant can tell whether its current cell is nestable. The queen ant has exactly the same powers as a worker ant, although she knows she is the queen ant, and (for obvious reasons) she should not explode.
Ants have limited brain capacity, and can only remember one byte of information from one turn to the next. The simulator will hand this byte (0 on the first step) to the ant ``player'' on each invocation: the player should not keep any other persistent state. Exactly how the simulator expects this byte to be returned at the end of a move will be specified later. The simulator will also hand each ant a (different) random byte, in case you want to program a player with some random behavior. Each ant works alone, and does not have access to the state of the other living ants.
The ant world is described by a map, which has one start cell (where all ants are initially located) and one or more nestable cells. Ants don't know their coordinates, or the size of the map. You may assume that the perimeter of the map is surrounded by blocked cells, so that ants don't disappear over the edge of the world. We'll try a variety of maps:
For the tournaments, we'll use a variety of maps, including some that are previously unseen. Some things to think about:
Note: A similar project was given in the Stanford version of the class in 1989. See the background reading for more details.