I’ve not taken part in an AI Challenge before but with the next few weekends looking pretty quiet I decided to sign up. The latest challenge, run as a collaboration between Google and the University of Waterloo Computer Science Club, simulates a competitive environment in which two or more ant colonies fight for survival on a selection of maps.

The contest is distinctive for the broad range of languages supported. You code up your entry, zip it and upload it where it is compiled (where necessary) on the server and put into a queue to fight against other players’ creations. There are starter packages provided so that you don’t have to parse all of the incoming data and wrap up the output.

You control an ant colony located somewhere on a map. By commanding your ants to move to and collect food you spawn new ants from your anthills. Survival is key, but a scoring system also encourages attacking behaviour – get close enough to another ant and you’ll attack it, and if you manage to land on an undefended ant-hill that hill is lost and no longer produces ants for the opposing player.

Your code has a limited amount of time to perform its processing per time-step, and if it exceeds that time then your bot is eliminated. Equally if your bot crashes during execution then you’re also out. Winning or losing changes your rank based upon the Trueskill algorithm and your bot will keep being queued for more battles in a round-robin fashion for a number of days after you upload it.

I’ve decided to try a diffusion approach which I suspect many others will be trying too. The idea is reasonably simple – goal items in the world exude a digital pheremone that makes them attractive to your ants, and this pheremone is diffused throughout the map over time by simple averaging in adjacent cells. For example, a food item might have a score of 1000 scent units in time step 0; in time step 1 its neighbours will have attributed themselves some proportion of that scent, and in time step 2 their neighbours will also be imbued. If you consider the scent of food to be a surface then we iteratively smooth out sharp peaks caused by goal items throughout the rest of the surface.

That means that we can find food or unexplored squares (if we associate a suitable attraction score to cells we’ve not yet visited) by simple hill-walking per-ant. When an ant is deciding where to move it examines the squares to the north, west, east and south of it and picks the direction with the highest scent value. It also means that we get pathfinding for free by clamping the ability of wall-cells to propagate scent to zero – any other cell adjacent to a wall cell will have a higher attractiveness, so the ant will not consider the move.

There are substantial kinks to work out in my implementation but I’ve only just started. For now, my bot (not yet uploaded) seeks only to explore the map without bothering to look for food (though there is enough food that it’ll stumble upon some accidentally fairly often). This video shows the pheremone trails over time; the green on the left is the ‘unexplored’ pheremone, while the red on the right is the ‘food’ pheremone. Just now the ants are configured to consume the unexplored pheremone when they are within a cell such that any ants following behind will seek different routes.

The ants are starting from near the top-left of the map. The green pheremone quickly ramps up across the map even in regions the ants cannot yet see because we do not yet know where the walls are in those sections – ants have a limited field of view. Once we start exploring these regions the wall cells start to clamp correctly and the map topology becomes a lot clearer.

On the red side the food pheremone pulses as new food items are added randomly. When an item is consumed its red signal falls off over a few time units.

The contest closes for new entries in December on the 18th, after which the tournament-proper starts – I’ve enough time to hopefully get something based on this diffusion approach uploaded by then!