[Icfp04-discuss] Ant optimizers?

[Agthorr]

On Thu, Jun 10, 2004 at 08:49:59PM +0100, Ganesh Sittampalam wrote:
> In the end none of it mattered; none of our ants were ever close to 10000
> states pre-optimisation. But the extra headroom it provided possibly meant
> we were more willing to try stuff.

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.).

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.

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

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 ;-) 

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.

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

-- 
Daniel Stutzbach                           Computer Science Ph.D Student
http://www.barsoom.org/~agthorr                     University of Oregon