Description of Google AI challenge (Ants)

At the hub there is already a lot of information on this contest, but all of it illuminates certain moments of implementation, but not the whole picture. 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 discouraged the need to understand the intricacies of implementation. The post consists partly of translating materials from the official site, partly of analyzing the strategies of other bots and pure logic. Also, at the end of the post there will be a link to the PHP bot (a little more complicated than from starter-pack), which will allow you to try your hand adding the existing code. Official Contest Website: aichallenge.org

The main components of the ant colony strategy are:

1. Passive

1.1. Food collection and colony replenishment (spawn)

• Food appears symmetrically and simultaneously for each colony, so the conditions for all bots are always equivalent (cards are also generated symmetrical).
• Each collected food is added to the “repository” of the colony and at the first opportunity will turn into a new ant.
• There is the spawnradius parameter, which is always 1, that is, the ant appears in the cell where the ant hill is located.
• To collect food, it is necessary to bring the ant to a neighboring orthogonal cell with it (not a diagonal).
• The cage with food itself is not passable, that is, if the ant stands still and food appears next to it, it cannot go to this cage. You just need to leave it on this cage for one turn, and then the food will be collected.
• Only 1 ant per turn in 1 ant hill can appear. If more food was collected in the previous move than there are free anthills, then a new ant will appear with a delay.
• If the ant has remained on the cell of the anthill from the previous move, 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 is collected, then one ant appears in each anthill. If food is not enough, the priority for anthills is where the ants do not appear for the longest time, then the anthills that are not blocked, and then random.
• At the beginning of each game, 2-5 food always appears next to the anthills within sight.
• The amount of food that appears is gradually growing (this parameter is not available to the bot) and depends on the number of bots remaining (accordingly, it also appears symmetrically).

1.2. Ant hill defense

• The exit from the anthill for a new ant can always be only in 4 directions, respectively, the ants protecting the anthill are best placed 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 (more on that below) is just the destruction of enemy anthills, so the ant-defense factor is very important. It is absent in almost all bots (even top ones).

1.3. Territory reconnaissance and control

Since the scope mechanism is implemented under the conditions (see below), the bot does not know which map is in front of it, and only receives information about objects that fall into the scope of its ants. In most cases, control of the territory is not required, except for the approach of the enemies to the anthills. An ideal arrangement of ants is an algorithm in which they open the maximum field of visibility, and all unused ants are sent to the "mission" to destroy the enemy anthills (push). Accordingly, maintaining an open card has the main purpose in collecting scouts for all food that falls within the scope.

2. Active

2.1. Extermination of enemy ants

The calculation of the “attack” takes place as a whole according to a simple rule: the
difference in the strength of enemies and their owns is considered, if they are equal, everyone dies, otherwise the weaker dies and the strong one survives.
By "force" is meant how many ants have this cell (where the ant is located) in the radius of their attack. Simply put, if one ant is in the radius of attack of two, then he dies, but they do not. 2x2 - everyone dies, and so on. It is understood that the ant attacks all the ants in all the cells in the radius of attack at once.

Attention: although water is not a passable cell, an attack through it is also considered, that is, two ants on opposite sides of the water cell will kill each other.
Technical side:
Information about the enemy ants is transmitted to the bot every turn, however, the disappearance of the enemy ant from the input can mean a situation of death, as well as a situation of disappearance from the field of view. The first situation is sometimes monitored by analysis of data on the dead (dead), however, the ant could die from another ant and on the border of the field of view. This complicates the implementation of tracking the actions of each individual enemy ant, and although it can provide some benefit in calculating the approximate actions of the enemy, its implementation is not so priority.

2.2. The extermination of enemy anthills

It is one of the main ways to achieve victory. Without an anthill, the 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 also may not receive information about this or that anthill if it disappeared from the field of view or was erased. However, anthills cannot move and are not reflected in dead logs. So it makes sense to store information about the discovered anthills, however, if they were not found in the next log, but are in the visibility zone, then mark them as destroyed.
Accordingly, this allows you to direct the ants to the enemy anthill, even if it has disappeared from the field of view.
In most bots, the ant hill protection is not implemented, therefore, it is not uncommon for a “flying” ant to essentially lead to defeat by simply destroying the defenseless anthill and thereby leaving the bot without reinforcement.

The phases of the course (step)

All calculations are performed in the following order:

1. Movement
2. Attack
3. Destruction of anthills (raze)
4. Gather food
5. The emergence of new ants and food (spawn)

A few notes based on this logic:

• Food and ants always appear last, that is, it is impossible to collect the food that has just appeared (only on the next move).
• Calculation of the attack always occurs after the movements of the current move, and not based on the position in the previous 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, move number). All this you can find in the input logs of the bot.

Scope and tracking

The anthill itself has no scope, that is, if not one of your ant is next to it, then the appearance of the enemy above your ant hill will be an unpleasant surprise for you.
When the bot starts, the configuration of the current map is transmitted, which also indicates the scope, attack and spawn. It is a square of hippotenuses between two cells (a square is chosen in order to maintain an integer value).
Standard parameters:
visibility - 55 (radius of about 7 cells),
attack - 5 (radius of about 2 cells).
spawn - 1 (current cell).
Since the incoming data reflect only the situation (changes) for the 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 adjusted.
• All other data are considered dynamic, but they can also be controlled. An approach to controlling anthills and enemy ants has been described above.
• Tracking your ants is much easier:
• Make sure that the ant does not go in with the same ant in the same cage (this leads to the death of both).
• With each move, update the list of your ants based on the log of "dead ants."
• Updating the objects of ants (their coordinates) is easily implemented on the basis of storing in the object the coordinates of the cell where the ant was ordered to go, respectively, he either died there or moved to this cell.
• Take into account that no move is made to the blocked cage (with food or water).
• The map is cyclically closed on both sides, which is important to consider when calculating coordinates and visibility areas.
• If someone 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 freezes (timeout).
4. The bot tries to execute code that is prohibited by the rules of the competition.

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.
An important point:
If an enemy bot crashes or freezes, its ants remain on the battlefield, but do not receive commands. This is not reported to other players who continue to receive information in the same form. In this regard, it is even possible to implement an algorithm that tracks “crashed” players (this is rare, but happens) so as not to spend your own army on them or “take them out” given that they are immobilized, which is very easy to do.

Calculation of points per game

Each bot starts with a 1st point for each anthill.
Destruction of an enemy anthill +2 points.
Anthill loss -1 points.
If there is only one bot left and not all the enemy anthills are destroyed (but all the enemy ants are killed or the other bots are “stuck” or “dropped”), then for each remaining anthill the bot receives points as if it destroyed it, i.e. +2 to itself and -1 to the anthill owners.

Elements of strategies

1. Movement, search for a way to a point, choice of goals

The usual priority of goals: first food, then enemy anthills, then enemies.
The simplest path-finding algorithm is a breadth-first search , or slightly more complex A * . The most primitive and fastest way can be considered the choice of direction for movement on the basis of reducing the difference in coordinates (such a mechanism is implemented in starter-packs), but of course it gives a lot of 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 analysis of actions is easier on average), so the choice and implementation of the algorithm greatly affects the final result of the bot. Accordingly, those bots whose performance is higher are more capable (you understood correctly, the whole top is written in C, C ++ and Java).
The main priority in the absence of targets nearby is best to consider the area outside the range of visibility, this is the best way to make the ants "creep" on the map. As soon as an enemy anthill is discovered, all new ants (or their percentage) can be sent in a chain to storm it, and then again for reconnaissance. Control over the scope and movement to undiscovered areas will allow ants to be evenly distributed over the map space without arranging gatherings that are needed only when the enemy’s push.
A useful technique is blocking for the course of cells that have water on 3 sides (there is almost no practical sense in such cells), which can be done by analyzing the map and storing such cells in memory.
The same applies to dead-end “unicellular” tunnels, but make an exception for them if they find a target (for example, food).
A useful element is sometimes the preservation of the "last priority direction" when he prefers to move in one of the sides at the first opportunity, so that the bot does not develop every obstacle, then it will maintain the course.

3. Defense and attack

In general, the mechanism of attack is quite obvious. The approximate moves of the enemy are calculated (for example, given that his priority goals are the same as yours: food, other anthills, enemies), then the “power map” of the enemy is calculated, and then the moves of your ants are calculated taking into account the enemy’s power map and priority goals, that is, what move provides your ant with the closest cell to the target with an advantage of the "forces" in the cell in your direction. This is a rather complicated algorithm, since it is necessary to calculate various combinations of motion of several ants at the same time, but it is quite feasible, since large "fronts" are quite rare, most often these are separate collisions.
As a result, the ants will move towards the target (anthill or the enemy) as if "as carefully as possible", thereby destroying the enemy as soon as they can.
There is no ideal solution, because most cases are ambiguous and even “random,” but this is already enough to minimize your losses.
Also, as already mentioned, do not forget about protecting your own anthill, where you can leave 2-4 “guards” nearby in diagonal cells, which will also collect food next to you.

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

GreenTea
MomoBot
FlagCapper
Some games are quite interesting to watch, especially knowing that these are bots.

PHP bot for seed

The bot is almost rewritten from scratch in the OOP format. Various behavioral strategies are much more conveniently tried (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 it is quite readable.
The general strategy of the bot: just wander around the map, collect food, avoid enemies, and at the first opportunity, cowardly destroy the enemy anthills. Enough to stay in the ranking of about 50-60 positions (max skill 49). Accordingly, he beats bots from starter-pack easily. Further already at your discretion. Just for fun.
Download bot from Yandex

Bot debugging

On the official website, it is not written exactly how it is better to debug the bot.
In the standard pack (tools), to view the bot’s games, use the play_one_game_live.sh file ,
in which you must specify the address to your bot. This is described in detail in the topic. We are writing our bot for the Google AI Challenge. Fast start. . To this, it’s worth adding that the console and logs will not display any messages about the reasons for the bot to fail (crushed). To do this, you need to slightly modify the file play_one_game_live.sh , adding the keys to run the script (replacing So with SoeEIO ): Now in the console, and in the logs in the game_logs directory
./playgame.py -SoeEIO --player_seed 42 --end_wait=0.25 --verbose --log_dir game_logs .....

All information about what happens during the game will be displayed (including errors of the bot’s actions, such as a double move for one ant). This information should be enough to analyze the bot.
To better understand the technical side (specifications), it is best to "dig" start-packs for a language that interests you. In general, to begin with, they are quite enough.

In conclusion

The proposed “battlefield” of bots turned out to be 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 competition, which is why this article was written. Good luck in creating your own artificial anthill.