Around this time last year, I participated in the Google AI Challenge, eventually finishing in 47th place out of nearly 5,000 participants. The contest this year had a bit of shaky start. There was some controversy over the name of the contest as it’s wholly organized by the Computer Science Club of the University of Waterloo. Google is providing sponsorship and has agreed to allow their name to be used but is otherwise completely uninvolved in what is otherwise a student project. Hence, this year the name is simply AI Challenge with a note that it’s sponsored by Google.

That wasn’t the only problem. Despite deciding on the nature of the game to be played fairly early on, the organizing team seemed to have a great deal of trouble coming up with the required tools, documenting everything and making sure the starter packages all work properly. It was annoying to see that while the contest had already started and is open to submissions, the website and the rules of the contest were still a work in progress. Nevertheless, everything now seems to be working correctly, apart from the fact that the server is far too slow and that there aren’t enough games being played. So I’ve submitted an entry and you can track my progress here.

One reason for this confusion is that the game selected for this year’s contest is an order of magnitude more complex than last year’s Planet Wars game. Ants, as this year’s game is called, is about colonies of ants that fight each other on a map, grabbing food to spawn new ants in their hills. Here are some of the key features:

• There is fog of war. Your bot sees only what is in visual range of your ants.
• There can be multiple players on the same map. The games I’ve seen so far range from a mere two players per map to a very crowded eight players per map.
• The map wraps around. If you travel all the way to the east for example you come in from the west and so forth.
• Both ants die if they collide by ordering one to move into a space already occupied by another ant.
• Ants can’t walk into water spaces and there are a lot of water spaces on the maps, which means every map is essentially a maze.
• Battle resolution is somewhat complex. Basically the side with local numerical inferiority loses all their ants while the victors lose nothing.
• Victory is based on scoring points. You earn points by razing enemy hills and lose them by losing your own hills. You can never gain ant hills in the game, only destroy enemy hills.

Based on the above, it should be easy to see why programming a bot for this game is so much harder than one for Planet Wars. Your ants need to do pathfinding to navigate the maze. Since there is fog of war, really good bots need to remember what they’ve seen and make inferences based on that. Because the number of players on a map and the consequent size of the map is so variable, it is very difficult to make a bot that will scale appropriately to all types of maps. Far and away, the biggest challenge is to make sure that your bot doesn’t time out. Currently the turnlimit on the server is a mere 500 milliseconds whereas we had a full second to do a turn in Planet Wars. Considering how computationally expensive pathfinding algorithms are, it is very easy to unintentionally breach that limit.

Right now in fact, my bot is merely a cleaned-up version of one of the default starter bots. It times out maybe ninety percent of the time, yet is still good to get inside the top 1000. That’s a pretty good indication of just how hard it is to write a decent bot for this year’s contest. I’ll probably only be able to upload a bot that is completely my own next week, so look out for updates then.