Gathering Food

In the game "Ants", one of the most important elements in winning is gathering food in an efficient manner. Whoever has gather more food at say, turn 20 will have more ants with which to kill their enemies and gather more food. A relatively small difference in performance can result in huge differences over time between opponents. My algorithm for food gathering is currently far from optimal+, but it does a pretty good job. In most of our matches, we are either ahead of or equal to our opponents when it comes to the amount of units at the start of the game.

So, let's talk about the different problems that exist with gathering food. But first, we really need to definewhat we mean by gathering food efficiently. Obviously we want to find and gather as much food as possible. Let's say there are two methods that will get us equal amounts of food, but one will give us more sooner for slightly less food later compared to the other method.

Let's say "Option A" means that we gather 2 food in 5 turns as opposed to 7 turns, but then it takes us 15 turns instead of 12 to gather 3 more food . On turn 12 we have more with "Option A", and on turns 5 we have more with "Option B". Which of these two options should we choose?

I would argue that, since the growth of your ants is exponential, the more ants you have (especially in the first few rounds) the more food you will be able to gather. Thus+, we will favor a strategy that gets us resources fastest, even at the expense of efficiency in later turns.

The very simple case

The simplest possible case is that we have a piece of food. We can see the piece of food, and we know the way to get to it. We have one ant, so we send him to get the food.

The slightly less simple case

We still have one ant and terrain is not a problem. However+, we have two pieces of food. We will gather both of these, but there are two different ways to do this , one bad and one good. We want the ant to go to the closest piece of food first and then go for the second. Now given our definition of efficient food gathering we can simply extend our algorithm to N pieces of food and say that we will get the first piece of food quickest if we go to the nearest piece of food.

It may be that the second and third pieces of food are close together, so that we can have two food faster, but we will be naive about this potential development.

The complex case:

Now here is the real problem: In the game, we will have K ants that want to collect N pieces of food.[footnote] Our current algorithm simply tried to maximize our fast gathering of food. For every piece of food we see, we try to find the ant that is closest. We then recognize the piece of food and tell the closest ant to go gather this food. This is illustrated in the figure below

The nitty gritty:

Well, this sounds all well and good, but how can we actually accomplish this complicated process? We have a list of all our ants, ants.my_ants() , as well as a list of all the ants currently assigned to gather food, self.food_ants. We also keep a list of all food that has already been assigned to some ant to collect, so that two ants do not go after the same piece of food. So the start of

the code is actually quite simple:

food_taken = [f for l in self.taken_food.values() for f in l]

available_food = [f for f in ants.food() if f not in food_taken]

We simply have to create a list of available food to check. Now this available food list will (-be a list of) contain positions representing where there

is food. The function ants.distance(loc1,loc2) returns the distance from loc1 to loc2.

for food_loc in available_food:

for ant_loc in ants.my_ants():

if ant_loc not in self.food_ants:

# If it is not an ant that is already gathering food we only need to consider the distance

distances.append((ants.distance(ant_loc,food_loc), ant_loc, food_loc))

for ant_loc in self.food_ants:

tot_dist = 0

old_path = ant_loc

for food_path in self.food_ants[ant_loc]:

tot_dist += ants.distance(food_path,old_path)

old_path = food_path

# We add the distance from each food to the next

# Distance from last food in que to new food

new_dist = ants.distance(self.food_ants[ant_loc][-1][0], food_loc)

distances.append((tot_dist + new_dist, ant_loc,food_loc))

For a given piece of food+, we now have a list of the distances from each ant to this piece of food.

Then, we simply sort the list and then assign the ant which is closest to this food to collect it. We then use the PFF.find_path(map, loc1,loc2) function, which finds the fastest path from loc1 to loc2 on the given map.

distances.sort()

for dist, ant_loc, food_loc in distances:

foodpath = PFF.find_path(ants.map, ant_loc, food_loc)

if ant_loc not in self.food_ants:

self.food_ants[ant_loc] = []

self.taken_food[ant_loc] = []

self.food_ants[ant_loc].append(foodpath)

self.taken_food[ant_loc].append(food_loc)

This is our food gathering algorithm as it is now. While I do think this algorithm is quite efficient, it suffers from being 'self centered'. In other words, it does not at all take into consideration the actions of other players. So for example it would not consider whether an enemy ant is close to a piece of food, and if we should still try to get that food. The main problem is not whether the solution itself is optimal, but the running time of the algorithm. Our bot is currently having problems with "timing out", and I believe that this food searching algorithm may be the culprit.

Some possible ways of speeding it up might be not to consider all ants, but to somehow localize ants and only search through certain sub groups of ants. But I still think this code is quite solid. There is still some tweaking and optimizing that can be done, but it is not the focus of our current efforts.

In the next article, I will discuss what is currently the weakest aspect of our bot: the combat algorithm and the thoughts that go into that.

[footnote]I realized as I was writing that it is quite possible to write this as some form of maximum flow problem and solve this problem. However at the moment+, our algorithm is far more naïve/greedy, and I think it is relatively likely that a maximum flow problem would take too long for us to solve.

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.