[Icfp04-discuss] Ant optimizers?

[Ganesh Sittampalam]

On Thu, 10 Jun 2004, Agthorr wrote:

> I had one of the minority of submissions that came close to 10000
> states.  I had developed a neat algorithm to uniquely identify each
> ant at start up, so they each had their own mini-state machine.
> Eventually most ants become one of three or four types, but initially
> they are given unique instructions (such as "put this mark on your
> initial square", "become a stationary guard", etc.).

We essentially did that too, but all our ants end up the same type after
startup.

> I generated mostly-unique rays radiating outward from the center of my
> anthill, and assigned each explorer ant a mostly-unique pattern to
> follow radially outward from the anthill until it encountered
> something interesting, laying down reverse-path markers along the
> way.  This proved extremely effective if my anthill wasn't surrounded
> by obstacles.

We just randomised deviations from a straight line path. What you describe
sounds like a much better idea; once an obstacle is hit, I would be
inclined to implement a "go round it" algorithm followed by random
movements in one general direction.

> Additionally, I used the states to keep track of which direction the
> ant is facing.

I think this is pretty much essential; the teams that do this and use
absolute direction markers are much stronger than those that don't.

> Unfortunately, I only used a single bit to encode "food this way"
> instead of encoding full directions, and I didn't get around to coding
> anything to remove food markers once placed.  So, dunkosmiloolump
> crushes me ;-)

We thought we could reduce the bits we used to encode food markers,
because they are only actually different from home markers at corners; but
we didn't actually get round to it. Removing food markers is crucial;
initially there were various situations that could lead to them not being
removed, and we ended up with a large and stuck queue of ants doing
nothing. Some careful fiddling with the algorithm eliminated this problem,
and I think is the reason we are so effective at gathering food.

> I spent too much time trying to develop an effective algorithm to
> quickly surround the enemy anthill.  In my experiments, I could
> surround the enemy anthill, but only after they've had enough time to
> collect enough food to win.  I am pretty sure now that this strategy
> just isn't workable.  I ended up disabling this code because it was
> hurting more than it was helping.

Being surrounded definitely loses us matches pretty frequently; it's only
because we are so fast at gathering food that we have a prayer against
ants that do that.

> In general, I think attacking was very difficult, so the best ants are
> those that can find and gather food fastest.

Redteam have some very effective strategies for attacking; their traps
both inside and outside the base are very neat and take out quite a lot of
our ants. Luckily one of our submissions is programmed to avoid the enemy
base (this is the only difference from the other submission).

If I wanted to write the perfect ant now, I'd use our food collection
strategy, redteam's traps, and sawicki's idea of sitting on food once
found and moving it around to bunch it up and make it easier to defend
(with some modifications). I'd also use a few ants to make a tunnel in and
out of our base to avoid encirclement. I'd consider trying to encircle
other teams but I suspect that just gathering food as fast as possible
would be better.

Cheers,

Ganesh