During one month and a half Elvis and I were involved in the AI Challenge, a crazy game which has the objective of creating a computer program (bot) to control a battalion of Ants with the goal of destroying all enemies. The challenge is sponsored by Google and more than 7.000 teams participated of the 2011 edition.
The AI Challenge - Ants (fall 2011) was the third edition of the competition which had it first edition in winter of 2010 with Tron. You can find more details about Ants and the other editions as well in the official website aichallenge.org.
Ants is a multi-player strategy game (turn-based) set on a plot of dirt with water for obstacles and food that must be harvested to increase the Ant army. The objective is to seek and eliminate all enemies ant hills (headquarters) while defending their own hills.
Ants is a multi-player strategy game (turn-based) set on a plot of dirt with water for obstacles and food that must be harvested to increase the Ant army. The objective is to seek and eliminate all enemies ant hills (headquarters) while defending their own hills.
Our crazy Ants was divided into five army units: battle, food harvest, defense, attack and explore. The idea of each unit is explained in the next lines and if you are too tired to read the more detailed explanation about the strategies, I recommend you to skip this part and read only the slide presentation with the general ideas of our project ;)
Battle
Battle is responsible to control ants during battles. The Ants which are facing enemies are divided into battle groups according with their position on the battle field. For each group is calculated all possible movements and depending on the battle strategy the best movement is chosen. There are three battle strategy: NORMAL, AGGRESSIVE and CRAZY.
NORMAL strategy is applied when the ant is exploring the map or just moving from one point to another and face an enemy. We do not want that our ant get stuck trying to kill the enemy, run to food or just try to scape is smarter than fight. On the other hand we must be AGGRESSIVE when we are defending our hill or we have much more ants then the enemy. And as in life, sometimes we must be CRAZY, not worrying about what we lose but what we win. Ants get crazy when they are about to destroy an enemy hill and there are much more ants than enemies.
Food Harvest
Food harvesting is the most important action in the game, specially at the begging. The fast you harvest food, faster your army increase allowing you to explore the map, find the enemy hills and destroy them. We have implemented two different strategies, one for the first 60 turns and another for the rest of the game. The basic difference is that in first strategy we harvest all known food while in the second one only the visible food are harvested. The basic idea of our food harvester algorithm is that the closest ant to the food is sent to take it. But there is one case that this rule is not followed, when the closest ant sees the enemy hill. In this case, destroy the enemy hill is more important, then another ant is chosen to harvest the food.
Defense
To protect the hill the most important action is keep the vision of the map, what permits you to see when the enemy is coming and build up your resistance. To do that we create checkpoints, which is the smaller set of points which guarantees visibility of whole map, and send ants (Sentinels) to be on those points. When enemies are seem by the sentinels, the property number of ants to kill the enemies are sent. Send the property number of ants is very important, otherwise you can send too much ants to one side and leave the other one unprotected!
Attack
Attack the enemy hill is the unique way to win the game and it must be very efficient. Our algorithm send to destroy the enemy hill 5 ants more than the size of the enemy defense. With this numerical advantage, Battle can manage to destroy the enemy hill. If it has passed more than 300 turns and we know only one enemy in the map, then the number of soldiers which are sent to destroy the enemy is increased in 10. It is done to try to finish the game as soon as possible.
Explorer
Explorer is the last action to be executed in the turn. It uses the checkpoints created by Defense to open the map sending free ants to checkpoints which are not opened and when all checkpoints are opened, send ants to closed points in the map, if there is any.
Battle
Battle is responsible to control ants during battles. The Ants which are facing enemies are divided into battle groups according with their position on the battle field. For each group is calculated all possible movements and depending on the battle strategy the best movement is chosen. There are three battle strategy: NORMAL, AGGRESSIVE and CRAZY.
NORMAL strategy is applied when the ant is exploring the map or just moving from one point to another and face an enemy. We do not want that our ant get stuck trying to kill the enemy, run to food or just try to scape is smarter than fight. On the other hand we must be AGGRESSIVE when we are defending our hill or we have much more ants then the enemy. And as in life, sometimes we must be CRAZY, not worrying about what we lose but what we win. Ants get crazy when they are about to destroy an enemy hill and there are much more ants than enemies.
Food Harvest
Food harvesting is the most important action in the game, specially at the begging. The fast you harvest food, faster your army increase allowing you to explore the map, find the enemy hills and destroy them. We have implemented two different strategies, one for the first 60 turns and another for the rest of the game. The basic difference is that in first strategy we harvest all known food while in the second one only the visible food are harvested. The basic idea of our food harvester algorithm is that the closest ant to the food is sent to take it. But there is one case that this rule is not followed, when the closest ant sees the enemy hill. In this case, destroy the enemy hill is more important, then another ant is chosen to harvest the food.
Defense
To protect the hill the most important action is keep the vision of the map, what permits you to see when the enemy is coming and build up your resistance. To do that we create checkpoints, which is the smaller set of points which guarantees visibility of whole map, and send ants (Sentinels) to be on those points. When enemies are seem by the sentinels, the property number of ants to kill the enemies are sent. Send the property number of ants is very important, otherwise you can send too much ants to one side and leave the other one unprotected!
Attack
Attack the enemy hill is the unique way to win the game and it must be very efficient. Our algorithm send to destroy the enemy hill 5 ants more than the size of the enemy defense. With this numerical advantage, Battle can manage to destroy the enemy hill. If it has passed more than 300 turns and we know only one enemy in the map, then the number of soldiers which are sent to destroy the enemy is increased in 10. It is done to try to finish the game as soon as possible.
Explorer
Explorer is the last action to be executed in the turn. It uses the checkpoints created by Defense to open the map sending free ants to checkpoints which are not opened and when all checkpoints are opened, send ants to closed points in the map, if there is any.
Ai challenge - The Ants game
View more presentations from Jordan Silva
You can check out how that strategy works in a real battle here: ignite.ou.
Our goal was to be among the first one hundred positions in the final rank, but we got 118 with skill 75.35. This position was enough to put us in the first position among the Estonian participants :)
The main problem not to achieve our goal was the timeout. When our army become big, Battle and Defense take lot's of time and not even all checkpoints set in the code was enough to avoid the timeout.
The first position was taken by xathis, a student from Universität zu Lübeck in Germany.
Our goal was to be among the first one hundred positions in the final rank, but we got 118 with skill 75.35. This position was enough to put us in the first position among the Estonian participants :)
The main problem not to achieve our goal was the timeout. When our army become big, Battle and Defense take lot's of time and not even all checkpoints set in the code was enough to avoid the timeout.
The first position was taken by xathis, a student from Universität zu Lübeck in Germany.
