Linepithema humile

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.

Programming Language

Ant Strategy

Fast Food Finding

• `Trailing' ants, from most of the outer two nest rings, quickly paint the board with `to nest' trails, marking [0,1,01] (yellow,blue,green). These are followed by ants carrying food.
• After trailing, these ants and most others look for food. When they find it, they leave short `to food' trails, marking [4,5,45] (purple, blue, white), to assist others in finding food. They then return to the nest, with a random walk until a `to nest' trail is found.
• The random walks are straight lines in free space. Experiment showed that adding random turning led to slower food finding.
• The `to nest' trails are broad, to avoid congestion problems when in use and to get good board coverage in the face of some obstacles. They are straight, for simplicity and speed. We experimented with stochastically adding branches to get better board coverage, but this did not improve the food-finding time. Further, it must be done with care to avoid creating cycles that confuse the ants following the trail. After the contest we see another team used left/right turning, marking the distance from the nest (modulo 3) - that looks better.
• The `to food' trails are harder as they are created asynchronously by various ants. In the end we make simple single lines, of stochastic lengths. We carefully tuned this length parameter to minimise the food finding time. With too much `to food' trailing it is easy to confuse the ants following them (as we have less geometric control than for the `to home' trails). Note that `to food' trails simply need to increase the food cross-section so that random walking finds it quickly; it is surprising how sparse they can be and still be very effective. An alternative that occurred to us after the contest is to mark food by walking around it in concentric rings (inspired by Keith Wansbrough's wall-following ants).
• If a food-finding ant reaches the end of a `to food' trail and there is no immediately-obvious food a delicate algorithm is used. Various experiments showed (surprisingly) that it doesn't pay to be too smart here.
• When an ant finds food it spins to face the opposite direction before starting back. This is a big win for food close to the nest and (we guess) a small cost for food far away, where the nest is in a randomly-distributed direction.
• Food in clear view on the foe's nest is detected (and trailed towards) in exactly the same way as other food. This means that if the foe is not defending we will tend to steal all their food. We intended to make additional trails to the foe nest, which would likely be useful in the latter part of the game when free food is exhausted, but did not. One might also consider erasing old trails.

Defending

• The third ring out from the centre of our nest is marked as a guardian ring. A number of ants are tasked with defending: they stay on the ring until they sense food just outside, whereupon they quickly move to it, pick it up, return, and drop it.
• Meanwhile, food-found ants follow the `to nest' trails all the way to ring 4, just outside the guardian ring, where they drop their food.
• The size of the ring was picked, by guesswork, to avoid congestion among the returning ants. Probably it is too big. A typical high food aquisition rate, in the early part of the sample9 world, is 1 every 50 steps; the ring does not become saturated, though edges close to food do sometimes.
• After the contest we see several teams using single-point defenders, which may well be better and are certainly much simpler. The (hypothesised) advantage of the ring is in the case where there are many foe ants in our nest. The ring sharply reduces the number of foe ants who can be in a position to steal food (or disrupt our collection mechanism) by moving onto the hoard while the defender is picking up new food. We have not yet played against a foe that does this, so it is hard to tell how much of a danger it is.
• Nonetheless, the return of the defender to the ring can fail, if a foe ant or another defender has moved there. It does something sensible in this case. The number of defenders is (stochastically) a few more than the length of the ring so that gaps can be plugged quickly - whether this is worthwhile is unclear.

The Cyclists

• Foe ants just outside the guardian ring are a problem in two ways. First, they may move onto the hoard while a defender is picking up food, and secondly (if there are many), they may disrupt our delivery. To protect against this a few ants are devoted to cycling around the two rings outside the guardian - stochastically, 1+ on ring 4 and 2+ on ring 5. Of the latter, (stochastically) half move slightly slower than the other. The result is to form an intermittent trap: say there is a foe ant in ring 4. After some time a ring 4 cyclist will be adjacent, and some time after that the ring 5 cyclists will come past, killing the foe ant. Moreover, it will be killed in exactly the right place to be picked up by the defenders.

Reflections

• We did not attempt any explicit attacks on the foe nest beyond food stealing, instead concentrating on finding food as fast as possible. We see in the `Red Team' submission a severe attack, constructing a wall of foe ants around our nest, entirely blocking it in. The game turns into a race betwen our food finding and their blocking (which does require a large number of ants). We were surprised how quickly blocking could be done: the race is won more often than not (6 to 3?) by the foe. We chose not to construct any explicit traps except for the cyclists, which was probably a mistake. A small number of ants devoted to a trap or two would be a very useful defense against blocking attacks. The trap could be either static or - rather more complex - mobile around a ring or - yet more complex - also moving occasionally between rings.
• A different form of explicit trap (generalising traps we saw in another entry after the contest) would be to make the outer ring of the nest (or perhaps ring 4 or ring 5) composed entirely of trap hexes, with the `to nest' food delivery trails leading to the trap hexes. Foe ants would die and be scored without further ado, with no movement required; smart food-finding foes would be particularly disadvantaged. More than one trap is certainly required to avoid congestion problems.
• Our initial `to nest' trailing ants ignore food, for the sake of quickly laying trails that cover much of the board. This delays `to food' trailing; one should investigate the tradeoff.
• There is considerable unused potential. We use only 2/3 or 1/26 of the ant brain (8.6 of 13.3 bits, 382 of 10000 instructions), outside the nest we have two unused markers, and we never use markers for dynamic communication (we never erase markers). Moreover we do not make use of much of the ant sensorium.

The Simulator

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

Peter Sewell and Francesco Zappa Nardelli