BotForTheGoogleAIChallenge

Erik Cowley
December 12, 2011

Attach:ecowley_final_paper.pdf
Attach:ants.tar.gz

My project is a bot which plays the game Ants from the Google AI challenge. Ants is a strategy game in which each bot controls an ant colony, with the objectives being to explore the map, gather food, and ultimately raze the opponent's ant hill. The bot competes with other submissions from competitors around the world.

My submission at the AI challenge website is http://aichallenge.org/profile.php?user=11589.

Concepts Demonstrated

A* Search is used to compute optimal paths between individual ants and their objectives.
Markov Decision Processes and value iteration are used in combat to compute strong points and vulnerabilities around enemy ants.

Innovation

The most innovative aspect of the bot is that it dynamically creates a graph of map locations during game play, for use by the A* search function.

This innovation was not part of the original bot concept, but it was necessary for several reasons. Firstly, the typical game map has several hundred rows and columns, so it's extremely costly to search through individual tiles. The game enforces a time limit of 500 milliseconds per turn for each bot, so efficiency is crucial. Secondly, due to the fog of war mechanic, the bot does not know anything about the map at the start of the game, therefore a locations graph cannot be precomputed.

When the bot is initially exploring an area, it performs tile-by-tile A* searches to compute a path from ants to their objectives. Then, it identifies straight sections of the path (edges), and junctions (vertices) in a waypoint system. Subsequently, the A* search function attempts to find paths through the area in terms of the existing graph.

The bot is able to send ants to (in the order of precedence) attack the enemy hill, gather food, attack enemy ants, and explore the map. It is able to calculate complex paths in order to navigate maze-like maps.

When confronting enemy ants, the bot orders its ants to attack if they have a numerical advantage, and back off otherwise (the game's combat mechanic gives an advantage to groups of ants).

Evaluation of Results

I have come up with two final versions of the bot.

One is an early version of the bot which uses a basic implementation of A* search, and does not implement MDPs at all. Despite its relative simplicity, it performs quite well: it was active online for several weeks and ranked in the top 10% of contestants (in the 600s).

The most recent, most sophisticated version does not perform as competitively as hoped. It has an intermittent issue with timeouts along with several other bugs. One such issue is that ants have a tendency of getting stuck in loops. I will probably continue working on it until the deadline for the AI challenge on December 18th.

Additional Remarks

In the picture on the poster, Blue is the earlier version and Orange is the later version. It can be seen that the earlier version has achieved numerical superiority, while the later version groups its ants together to gain an advantage in combat.

I chose to code the bot in Python because of time constraints. If I were to do it over, I would have chosen a more efficient language, since I ended up spending considerably more time on optimization than on the core algorithms.