Introduction to This Blog

Lately I'm spending much of my free time writing an AI for the Google AI Challenge. In the following posts, I will try to explain what this year's Challenge is, as well as some of the reasoning behind the Algorithms that I have written for it. So without further ado, let us jump right in.

What is the Google AI challenge?

Twice per year, Google and the University of Waterloo in Canada arrange an AI challenge. A game is chosen by the organizers and thousands of programmers from all over the world try to write an AI that will be the best at beating the game. As the AIs play against each other, the algorithm with the best implementation and strategy will win. The previous two AI challenges were the games Tron and Planet Wars. There is a longer description available at this years homepage but I will try to summarize it more succinctly below.

This year, the chosen game is 'Ants', which is not a well known game unlike the two previous choices. It is, in some ways, a very simplified version of modern Real Time Strategy (RTS) games.

So what is this Ants game?

Now the easiest way to get an understanding of the game is to simply watch it played. Then when you wonder about more specific rules, you can read here or at the AI challenge home page.

The game is in principle quite simple, and can be summarized into 8 rules:

1 - The game is played on a square grid, where the size varies from game to game.Examples of maps can be seen here [pictures]. The size of the maps and the number of players will vary.

However, the maps will always be symmetrical so that the starting position for every player is identical. The maps will also always be on a torus, so if an ant walks up on the topmost square, it will re-emerge at thebottom square, and the same for the most eastern and western squares.

2- At the start of the game, every player is given a single ant and at least one ant hill.

In almost all games players are given a single ant nest but it is possible to have several. Your first ant is

identical to all other ants you are going to have. It can move once per turn horizontally or vertically (but not diagonally). It has a certain field of vision that will vary from game to game. It can also gather food and fight, as described below.

3- Food is spawned randomly across the map.

There are a predetermined number of food pieces already on a map. Much like the maps themselves, they are spread symmetrically, so that no player has more food than any other. New food will spawn in equally symmetric ways; however, when and how much will vary between games.

4- When an ant walks on a square next to food, a new ant is spawned in the ant hill.

Gathering food is perhaps the most important part of the game, even though it does not give you any points in and of itself. You cannot defeat a player that has many times more ants than you do, and the only way to get new ants is to gather food.

5- When two ants walk within a game varying distance "r_fight" of each other, they will fight.

When there is just one ant within the fighting radius of one other ant, they both die. If one ant is within the fighting radius of two different picenemy ants, and no other friendly ant is nearby, it will die and both enemy ants will survive. When there are many ants walking in different number of radii (and so on) things get a bit complicated. The exact rules will be specified later when talking about the strategies surrounding formations. In short, the greater amount of ants will defeat the lesser amount unless they are very poorly managed.

6- When a enemy ant walks on your ant hill, it is eliminated. You will lose a point and your opponent will gain a point.

This is the only way to gain points, and is thus the second most important part of the game. While it is true that you can sometimes catch

an opponent with far more ants off guard and kill their nest, this presumes your opponent is making a critical mistake in their play

and as such this cannot be your main strategy.

7- Each turn, players move all their ants, gather all food next to their ants, and fight all ants within a fighting radius.

8- When there is one player left alive, the game is over. Each player is ranked based on their number of points.

This means that even if you lose but come second in a game with many players, your AI will stillget a good score, and you will be ranked higher than if you had placed last. Technically, there are also other ways the game will end, such as when a specific number of turns are reached or all the AI "time out".

How should you play the game

Now that we know the rules of the game, we can start thinking about what will make a good strategy. After reading the rules, I basically decided that the most important part of the game is the food gathering (known in the RTS gaming community as the 'macro'), the large scale structure of the game. This system is in contrast to the micromanagement (known as "micro") of each ant in a battle scenario.

However, there are far more aggressive ways to approach the game. For example, the battle mechanics make it so that an AI with very good battle management, or 'micro', can avoid losing almost a single ant to a player with bad micro who sends ants to battle one at a time. This means that a player who gathers up a dozen or so ants and then goes to kill a enemy ant hill can be very successful.

But enough about all that--here are the principle strategic ideas behind my AI, the BlackSobboT.

• Attempt to have vision of all parts of the map, or to put it bluntly, try to spread out the ants quite a bit.
• Gather all food that you can see as quickly as possible.
• Gather an army only when your lead in ants is quite substantial compared to your opponent.

The first two points are connected--by having a large area of the map visible, we can see more food, and we can also be closer to more food. This means we will gather a lot of food and hopefully gain a lead over our enemy. Once we have a good number of ants that are gathering food, we will try to attack the enemy ant hills with all the extra ants that we have.

Designing and implementing these two steps (gathering food and attacking) will be the subject of the next two entries, so stay tuned.