Description of Google AI challenge (Ants)

At Habré there is already a lot of information on this contest, but all of it covers specific points of implementation, but not the picture as a whole. I will try to correct this situation as briefly as possible, but in general.
This description is intended for those who have heard something about this event, but all the desire to do something has repelled the need to understand the intricacies of the implementation. The post consists partly of the translation of materials from the official site, partly of an analysis of the strategies of other bots and pure logic. Also at the end of the post will be a link to the PHP bot (slightly more complicated than from the starter-pack), which will allow you to try your own strength by adding the existing code. Official site of the contest: aichallenge.org

The main components of the ant colony strategy are:

1. Passive

1.1. Collecting food (food) and replenishing the colony (spawn)

• Food appears symmetrically and at the same time for each colony, so that the conditions for all bots are always equivalent (maps are also generated symmetrical).
• Each collected food is added to the colony's “vault” and, at the earliest opportunity, becomes a new ant.
• There is a parameter spawnradius, which is always equal to 1, that is, the ant appears in the cell where the anthill is located.
• To collect food, you need to bring the ant to the next orthogonal cell with it (not diagonal).
• The cage itself with food is not passable, that is, if the ant is standing still and food appears next to it, it cannot go to this cage. You just need to leave it on this cage for one move, and then the food will be collected.
• Only 1 ant per 1 move in 1 anthill can appear. If more food was collected for the previous move than there are free anthills, then a new ant will appear with a delay.
• If an ant has remained on the anthill's cage from the previous turn, then it is considered blocked and new ants do not appear.
• If two warring ants try to take food at the same time, then it disappears (no one gets it).
• If there are several anthills and enough food has been collected, then one ant appears in each anthill. If there is not enough food, the priority is to appear in anthills where the ants did not appear the longest, then not blocked anthills, and then randomly.
• At the beginning of each game, 2–5 meals always appear near the anthills within sight.
• The number of appearing food is gradually increasing (this parameter is not available to the bot) and depends on the number of remaining bots (respectively, it also appears symmetrically).

1.2. Protection of the nest (hill)

• The exit from the anthill for a new ant can always be only in 4 directions, respectively, the ants protecting the anthill are best located in diagonal cells.
• An anthill is considered destroyed if one of the enemy ants successfully descends on its cage.
• One of the main elements of the strategy (see below) is the destruction of enemy anthills, so the factor of protection of the anthill is very important. He is absent in almost all bots (even top ones).

')

1.3. Intelligence and territory control

Since under the conditions the mechanism of scope is implemented (see below), the bot does not know which card is in front of it, and receives information only about the objects that fall within the scope of its ants. In most cases, control of the territory is not required, with the exception of approaching enemies to anthills. The ideal location of ants is the algorithm in which they open the maximum field of view, and all unused ants are sent to the "task" to destroy enemy anthills (push). Accordingly, the maintenance of an open map has the main purpose in the collection by scouts of all food that comes across in the field of visibility.

2. Active

2.1. Extermination of enemy ants

The calculation of the "attack" occurs in general according to a simple rule:
It is considered the difference between the forces of enemies and their own; if they are equal, everyone dies, otherwise someone dies weaker and the strong survive.
By “power” is meant how many ants have this cage (where the ant is located) in the radius of their attack. Simply put, if one ant is in the attack range of two, then it dies, but they do not. 2x2 - all die, and so on. It is understood that the ant attacks all the ants in all the cells within the attack radius at once.

Warning: although water is not a passable cage, an attack through it is also considered, that is, two ants from different sides of the water cage will kill each other.
Technical side:
Information about the enemy ants is transmitted to the bot every turn, but the disappearance of the enemy ant from the input data can mean a situation of death as well as a situation of disappearance from the field of visibility. The first situation is sometimes monitored by analyzing data about the dead (dead), however, the ant could die from another ant and at the boundary of the field of view. This complicates the implementation of tracking the actions of each individual enemy ant, and although it may provide some benefit in calculating the enemy’s approximate actions, its implementation is not so important.

2.2. Extermination of enemy anthills

It is one of the main ways to achieve victory. Without an anthill, a colony does not produce new ants, but those who are still alive continue to fight.
Technical side:
As well as information about enemy ants, information about all (including yours) anthills is transmitted every turn. That is, you can also not get information about an anthill if it disappeared from view or was erased. However, anthills can not move and are not reflected in the dead logs. So it makes sense to store information about the detected anthills, however, if they were not found in the next log, but are in view, then mark them as destroyed.
Accordingly, it allows you to direct ants to an enemy anthill, even if it has disappeared from scope.
Most bots do not implement anthill protection; therefore, it is not uncommon for a “stray” ant to essentially defeat simply by destroying a defenseless anthill and thus leaving the bot without reinforcement.

Phase of the move (step)

All calculations are made in the following order:

1. Move
2. Attack
3. Anthill destruction (raze)
4. Gather food
5. The emergence of new ants and food (spawn)

Small comments based on this logic:

• Food and ants always appear last, that is, you cannot collect food that has just appeared (only on the next move).
• The calculation of the attack always takes place after the movements of the current turn, and not on the basis of the position in the last move.
• New ants appear only if the anthill was not destroyed this turn.

With each move, the following information is transmitted to the bot (water, ants, anthills, dead ants, food, turn number). All this you can find in the bot's input logs.

Scope and situation tracking

The anthill itself has no scope, that is, if there is not one ant next to it, the appearance of the enemy over your anthill will be an unpleasant surprise for you.
At the start of the bot, the configuration of the current map is transferred, which also shows the scope, attack and spawn. It is the square of hippotenuse between two cells (the square was chosen in order to preserve the whole value).
Standard options:
visibility - 55 (radius about 7 cells),
attack - 5 (radius of about 2 cells).
spawn - 1 (current cell).
Since the incoming data reflects only the situation (changes) on a given move, the following approach is taken for practice:

• Initially, the entire map is filled with earth, and when “water” appears in the logs, the map is corrected.
• All other data are considered dynamic, however, and they can be controlled. The approach to controlling anthills and enemy ants was described above.
• Tracking your ants is much easier:
• Ensure that the ant does not go in with the same ant in the same cell (this leads to the death of both).
• With each move update the list of their ants based on the log of "dead ants".
• Updating of ants' objects (their coordinates) is easily realized on the basis of storage in the object of the cell coordinates, where the ant was ordered, respectively, he died there, or moved into this cell.
• Take into account that the move to a blocked cell (with food or water) is not given.
• The map is cyclically closed on the sides, which is important to consider when calculating coordinates and areas of visibility.
• If the one who was not “updated” from the previous move is found in the input list of his ants, then this is a new ant.

Defeat conditions

1. All bot ants are dead.
2. The bot crashed.
3. The bot is frozen (timeout).
4. The bot is trying to execute code that is prohibited by the rules of the contest.

Once again, I note that the loss of all anthills is not a defeat, the bot continues to fight until the loss of all ants.
Important point:
If the enemy bot has flown or frozen, its ants remain on the battlefield, but do not receive commands. This is not reported in any way to other players who continue to receive information in its previous form. In this regard, it is even possible to implement an algorithm that monitors “collapsed” players (this is rare, but it happens), so as not to waste their own army on them or “carry out” them given that they are immobilized, which is very easy to do.

Calculation of points per game

Each bot starts with 1 point for each anthill.
Destroy the enemy anthill +2 points.
The loss of the anthill -1 points.
If there is only one bot left and not all enemy anthills are destroyed (but all enemy ants or other bots are killed, “stuck” or “fell”), then for each remaining enemy anthill, the bot gets points, as if he had destroyed it, that is, +2 and -1 owners anthills.

Constituent elements of strategies

1. Movement, finding the way to the point, choosing goals

The usual priority goals: first food, then the enemy anthills, then the enemies.
The simplest pathfinding algorithm is a wider search , or a bit more complicated than A * . The most primitive and fast way can be considered the choice of direction for movement based on reducing the difference in coordinates (such a mechanism is implemented in starter-packs), but of course it gives many failures (for example, if the target is on the other side).
Finding paths is one of the most resource-intensive operations in calculating the course (even analyzing actions on average is easier), so the choice and implementation of the algorithm greatly influences the final result of the bot's work. Accordingly, there are more opportunities for those bots whose performance is higher (you understood correctly, the entire top is written in C, C ++ and Java).
The main priority in the absence of targets nearby is best to consider the area out of sight, it is best to cause the ants to “crawl” around the map. As soon as an enemy anthill is discovered, all new ants (or their percentage) can be sent by chain to storm it, and then again to reconnoiter. Control over the scope and movement to the undiscovered areas will allow ants to be evenly distributed over the space of the map without arranging gatherings that are needed only when pushing the enemy.
Of the useful techniques, blocking is for cells that have water from 3 sides (there is almost no practical sense in such cells), which can be done while analyzing the map and storing such cells in memory.
The same applies to dead-end "single-celled" tunnels, but for them to make an exception if there is a goal (for example, food).
A useful element is sometimes the preservation of the “last priority direction” when he prefers to move to one of the parties at the first opportunity so that the bot does not unfold every obstacle, then he will maintain the course.

3. Defense and attack

In general, the mechanism of attack is quite obvious. Approximate moves of the enemy are calculated (for example, taking into account the fact that its priority goals are the same as yours: food, other anthills, enemies), the "force map" of the enemy is then calculated, and after that, the moves of your ants are calculated taking into account the enemy's card and priority goals, that is, which move provides your ant as close as possible to the target with a margin of “forces” in the cage in your direction. This is a rather complicated algorithm, since it is necessary to calculate various combinations of movements of several ants at the same time, but it is quite realizable, since large “fronts” are quite rare, most often these are separate collisions.
As a result, the ants will move to the goal (an ant-hill or an enemy) as if “as carefully as possible”, thereby destroying the enemy as much as they can.
There is no perfect solution, because most cases are ambiguous and even “random”, but this is already enough to minimize your losses.
Also, as already mentioned, you should not forget about the protection of your own anthill, where you can leave 2-4 "guards" in the diagonal cells, which will also collect food next to you.

Examples of these strategies can be found in the competition top.

Greentea
Momobot
Flagcapper
Some games are interesting enough to see, especially knowing that these are bots.

PHP bot for priming

The bot is almost rewritten from scratch in OOP format. It is much more convenient to try different behavioral strategies (for example, each ant is stored in a separate object), so you can just do $ ant-> stay () or $ ant-> doMove (). There are few comments in the code, there are pieces of unused test functions, but quite readable.
The overall strategy of the bot: just wander around the map, collect food, avoid enemies, and at the first opportunity cowardly destroy enemy anthills. Enough to stay in the ranking of approximately 50-60 positions (max skill 49). Accordingly, the bots from the starter-pack, he beats easily. Further already at your discretion. Just for fun.
Download bot from Yandex

Debug bot

The official site does not describe how exactly it is best to debug the bot.
In the standard pack'e (tools), the play_one_game_live.sh file is used to view bot games.
in which you must specify the address to your bot. This is spelled out in detail in the topic of writing a bot for the Google AI Challenge. Fast start. . To this it is worth adding that no messages will be displayed in the console and logs about the reasons for the bot's failure (crushed). To do this, you need to slightly change the play_one_game_live.sh file by adding keys to run the script (replacing So with SoeEIO ):
./playgame.py -SoeEIO --player_seed 42 --end_wait=0.25 --verbose --log_dir game_logs .....

Now, all information about what happens during the game will be output to the console, and to the logs in the game_logs directory (including errors of bot actions, like a double move for one ant). This information should be enough to analyze the bot.
In order to better understand the technical side (specifications), it is best to “dig” start-packs for an interesting language. In general, for the beginning they are quite enough.

As a conclusion

The proposed "battlefield" bots turned out very interesting for those who like to practice algorithms. Of course, I would like to see more of our players in the top of this contest, which is why this article was written. Good luck in creating your own artificial anthill.