Your attention is the translation of the notes of the winner of the recently completed AI Challenge, which reveals the general points of the algorithm, as well as some technical details. It is also possible to inspect the source yourself.

I can not believe that I won.
And the more I can not believe that I won decisively .

I love programming competitions very much, and for me it was the largest and most exciting. My thanks to the organizers of the competition, assistants, hosters tcp-servers and all the players for a few wonderful months.
')
Here is an example of one of my games: aichallenge.org/visualizer.php?game=346288&user=4513 ( this is not the game that the author brought in his article. I can’t link to it because it is stored directly on the author’s server. - approx. Transl. ) . In this post I want to explain what my code does and how exactly it turns out to do it. There are many technical issues, and in general, the article is not about the strategy itself, but I will try to explain it more simply.

About code

I started by downloading the Java start package , renaming the files, deleting everything unnecessary, adding a new Strategy class, and soon I realized that I also needed a class representing the ant. I wrote all my code in the Strategy class, which resulted in about 1800 lines of code. Also of interest are Ant.java and Tile.java , both of which are value object with lots of fields.

I left the idea of ​​a starter pack, according to which an unknown area was considered land by default. I did not calculate the field of view of the bot, and therefore did not even know which cells were really the earth, and which ones I just had not seen.

For each cell of the card there is exactly one copy of Tile, which is used throughout the game. Ant'y are created at the beginning of each turn for all my ants and enemy ants.

If you want to look at the source yourself, you should know: there is a lot of govnod there, and I am not particularly proud of these sources. However, you probably want to look at it anyway, so you can download it here .

Strategy implementation

Many talked about some common strategies, but unfortunately I don’t have one. I do not make decisions based on the number of my ants or on the proportion of territory occupied. My bot does not change tactics when it wins or loses; he doesn't know about it at all. In addition, I do not look at what the move is now, and on the first, everything happens exactly the same as on 999 m. I can not distinguish between enemies, even during battle, and do not keep the locations of anthills. Apart from sending ants from anthills through missions, each movement depends only on the local environment of the ant.

So, what exactly happens every turn? After all initializations and pre-subsets, I call the following methods in this order:

• initMissions ();
• enemyHills ();
• food ();
• initExplore ();
• createAreas ();
• fight ();
• defense ();
• approachEnemies ();
• attackDetachedEnemies ();
• escapeEnemies ();
• distribute (true);
• explore ();
• doMissions ();
• createMissions ();
• distribute (false);
• cleanAreas ();

Below I will try to explain what all these methods do, but if in brief, they simply move ants that fit certain criteria. If any ant is pushed, information about it is instantly sent to the server, and you can no longer cancel the action.

Searches wide

Here I will talk about how BFS happens to me at all. For performance reasons, each Tile has links adjacent to them (except water), and thus there is no need to refer to a two-dimensional array and use the rows and cols properties. ( I doubt it gave a tangible increase in productivity - approx. Transl. ) A typical BFS (and I use A LOT of them) looks like this:

 LinkedList<Tile> openList = new LinkedList<Tile>(); LinkedList<Tile> changedTiles = new LinkedList<Tile>(); openList.add(foodTile); foodTile.dist = 0; foodTile.isReached = true; changedTiles.add(foodTile); while (!openList.isEmpty()) { Tile tile = openList.removeFirst(); if (tile.dist >= 10) break; for (Tile n : tile.neighbors) { if (n.isReached) continue; if (n.type == Type.MY_ANT) { // found one of my ants at the tile n } n.isReached = true; n.dist = tile.dist + 1; changedTiles.add(n); openList.add(n); } } for (Tile tile : changedTiles) tile.isReached = false; 

In this example, we start at the foodTile point and look for our ants reachable in 10 steps. Perhaps it would be more efficient to use HashMap to store already visited cells, then it would be possible to get rid of the loop at the end.

Initialization course

At the beginning of each turn, I pretend all sorts of ratios for ants, such as the number of "their" nearby or a list of nearby enemies and their distances. This is somewhat confusing, since the distances here are considered both Euclidean and Manhattan and by the number of steps in the BFS.

Depending on the distance to the enemies, my ants have flags indicating whether they are in (possibly indirect) danger. For the enemies, it was checked whether they were isolated (that is, if they still have enemy ants near them).

Another task performed during initialization is to identify those enemy ants that did not move for several moves. If the number of such moves reached five, then it was assumed that they would stand on the next turn.

Research and missions

The departure of the ants away from my anthills, the study of the new terrain and the maximization of the visible area in my implementation are very closely related to each other. Perhaps this is the most important part in the behavior of my bot.

Study

For each cell, exploreValue is stored on the map, which is incremented by 1 each turn if this cell is not reachable with BFS in 10 moves by at least one of my ant. If the cell is reachable, then the counter is reset to zero. Thus, exploreValue is a measure of how long I didn’t know what was going on in the cage.

So, in the explore method from all ants that were not used for another task, BFS is launched with a maximum depth of 11 steps, while we are only interested in the last step (since the first 10 exploreValue is guaranteed to be 0). If all the cells reachable at step 11 have exploreValue equal to zero, this means that the ant is surrounded by “its own” or water. Otherwise, I move the ant in the direction where the sum of exploreValue at step 11 is maximum (that is, the sum of exploreValue of all the cells reachable from the cage into which I will move, in 10 steps). Since it is possible to reach any cell in 11 steps by taking two different first steps, a list of one or two first moves is stored with BFS.
This way I explore the map and provide visibility to all sites.

Missions

So, what if the ant is surrounded by its own? Move it to the border, of course! A more precise definition of the border is in the createAreas method, more on that later. Moving to the border is what I call missions. The mission consists of only two things: an ant and a target cell at the border. Missions are an example of the few data that is stored between turns, although the path to the goal is recalculated each time with A *. If the ant already has a mission, he continues to fulfill it, otherwise a new one is created. If the ant had a mission, but it was used for other purposes (food gathering, battle, defense), the mission is canceled.

Sites and Border

The createAreas method splits the map into parcels. I run the next BFS, this time from all ants (including enemy) at the same time. At the start, each ant has its own area, to which all the cells, which were reached during a wide walk, are joined. But when areas belonging to one player collide, they merge into one large area, which can then be merged again and again. After BFS, I look at all the cells in my areas, and every cell in which at least one neighbor belongs to another area is considered a boundary cell. In this BFS, I do not go deeper than 20 moves, and thus two ants at a distance of 39 steps will be in the same area, even if there is a fog of war between them. This ensures that there are no borders that suddenly appeared in areas that clearly belong to me. It turns out that the boundary cells are those cells that are either equidistant from my level and from the enemy, or are 20 steps from my ants, and there are no enemies in sight. In the second case, it may turn out that the boundary cell is on water that I have not seen before, and then I delete the mission as soon as I discover the water.

When creating a mission, you must select one of the boundary cells as the target. If the ant does not stand on my anthill, the boundary cell is selected for it, to which it is the fastest to go (determined with the help of BFS). Otherwise, the target cell is determined by some complex formula that uses the ratio of the number of its own and enemy ants close to this cell, the likely distance to enemy anthills, the number of ants that already have the mission to go to nearby cells, and how long it takes them walk ... Come on, just kidding :) This is determined by chance. Absolutely by chance. Like this:

 target = area.border.get(turnRandom.nextInt(area.border.size())); 

This was my first implementation, and it worked quite well, so I did not bother to change. Please note that the behavior was still not entirely random, because when the mission was interrupted by other tasks (collecting food and the like), the new one was then chosen deterministically. In addition, since the boundaries on each turn are different, missions need to be updated from time to time. This is done every turn, if there is enough time, and always at least once in 10 moves.

Still different

It can be noted that a cell is reachable in 10 moves - not exactly the same as the distance to the cell is not more than 77 , but they are quite close, and with this I have never had any problems.

It often happens that some ant goes back and forth for quite a long time. For example, if he is alone in a cave surrounded by water, with only one exit. In this case, every second turn, the ant is forced to step into the cave, because he needs to investigate a cage located there at a distance of 11 turns. And the next turn it turns out that there is nothing to explore, and therefore the ant goes to the border, and the next turn the story repeats. This is not so scary, because the creation of the mission - a cheap operation. ( well, yes, but an obviously idle ant is already worse. - approx. transl. )

Food

There is nothing particularly interesting. I run BFS from all visible food, and send the nearest found ant in its direction. I do not store the location of food and do not think that one ant can collect two meals that are close to each other. However, there is a special logic, according to which I act, if there is an enemy next to the food. Usually I try to avoid the exchange of ants, but if there is another ant next to the food, I am ready to sacrifice one if the enemy decides to try to collect food.

McLeopold wrote a good post in which he told how it happened with him.

Enemy anthills

As with food, I do BFS, starting from enemy anthills. I send to the assault no more than four ants, located at a distance of no more than 20 steps from the enemy anthill. If I have 10 or less ants, I send only one in order to avoid problems on the initial handouts of the game on the cards, where the enemies' nests are very close to each other. I never send more than 4 ants directly to an anthill, but since there are often enemy ants there, and I play very aggressively, I will still have a lot of ants there.

The battle

Well, that began the most interesting! Undoubtedly, the most discussed issue was precisely the logic of combat.

My approach is this: divide the combatants into groups, and then see what can happen next turn. I do this by simulating everything (not quite everything, starting from version 2, more on this below) the possible moves that my ants can do, and for all combinations I look at the opponent’s possible moves, then I evaluate the situation and choose the most profitable option, assuming that the adversary knows how I look like, and comes in the most dangerous way for me.
This is quite similar to minimax and alpha-beta clipping , you just need to have several max-nodes in a row (for my ants) and min-nodes for the enemy.

Example

Let's look at the situation below. Ants A, B and C are mine (green), and enemies are ants X and Y (blue). ( percent - water, points - ground - approx. transl. )

 % % % % % % % % A % % % % % . B % % % % . . C % % X . . . % % % Y . . % % % % % % % 

I was not even too lazy to draw a small diagram showing what was happening:
N / E / S / W means moving north / east / south / west respectively, and “-” means staying in place.

The tree is generated on the fly using DFS. We start by considering possible movement for ant A, simulate this movement and continue for ant B. After the last enemy ant has moved, we assess the situation using a simple formula: (number of dead enemy ants) minus (the number of my dead ants). Enemy nodes (min) always choose moves that lead to the smallest result, our nodes (max) choose values ​​for which the value of this formula is maximum. If we move A, B, and C south (left subtree), both enemies will die regardless of where they go, so the value is +2. But if we leave A in place and move only B and C, then both enemies can go east, with the result that everyone will die, and the final value will be 2 - 2 = 0. This is great because we can cut off some of the options and do not look at anything else in the brown frame, because it is already known that there is a combination that can lead to a result of 2, but since the enemy always chooses the least favorable movements for us, a value not exceeding zero will be selected in this brown frame .

As you can see, I did not paint some subtrees. In addition, the number of possible movements is very small, and there are only five ants, therefore in real cases the tree grows much stronger, exponentially from the number of ants.

The implementation in pseudocode looks like this:

 List myAnts List enemyAnts bestValue = -Infinity void max(antIndex) { if antIndex < myAnts.size myAnt = myAnts[antIndex] for each possible move of myAnt simulate move max(antIndex+1) undo move else value = min(0) if value > bestValue bestValue = value save the current simulated moves of all my ants } int min(antIndex) { if antIndex < enemyAnts.size minValue = +Infinity enemyAnt = enemyAnts[antIndex] for each possible move of enemyAnt simulate move value = min(antIndex+1) undo move if value < bestValue return -Infinity // cut! if value < minValue minValue = value return minValue else return evaluate() } 

It is necessary to fill in the lists of ants, and then call max (0), as a result getting a list of optimal movements.

Optimization

Two neighbor ants that do not make a move are the same as if they are swapped, so the second option can be ignored. To achieve this, I maintain the position of each ant before the fight.

In the first version, I used the combat algorithm for no more than seven ants, because for eight sometimes I needed up to several hundred milliseconds. This is clearly too much, as there may be several battles at the same time.

Lists of checked movements

By the second version I experimented with different optimizations, which allowed me in many situations to support noticeably larger groups. Let's look at another example, this time without water, where for each ant there are 5 different turn options (not counting when two ants go to the same cage):

 . . . . . . . . A . . . . . . B . . . . . . C . . . . . . . . XY . . . . . . . . . 

What can happen to ant A? If he goes to the south, he can join the battle, but if he stays in place, he will be away from the battle. Of course, we need to consider both cases, since we do not yet know whether it makes sense to attack. But how about A going west, north or east? So he definitely will not get into battle, and the score will be exactly the same as if he stays in place, then these movements are not significant, and they should not be considered. But if B and C remain in place, then Y can attack them, stepping north. You can also notice that for B and C, the estimation of movement to the north is equal to the assessment of movement to the east, but I did not take this into account. So, for each ant, you can choose a list of movements that should be checked. There are a lot of nested loops, because you need to check all nearby cells for all enemies nearby with each ant in the group.

For enemies, you can do something similar, but slightly different. Let A remain in place, and B and C go north. Now X and Y are out of the access zone, because they wouldn’t do, the rating will be the same as if you stay in place. If B still does not go to the north, but remains in the same place, Y will have to consider the move to the north, since now it will lead to battle. It turns out that in order for the enemy to know whether it is necessary to consider a movement, you need to know whether my ant is on a particular cell or not. Thus, for each enemy there is a match from the cage (where my ant can be) to the list of movements that need to be checked. These matches are built with even more nested loop clouds ...
I hope you like the examples, because here’s another one that shows the dependency table, this time with the row and column numbers (denoted row / column):

  0 1 2 3 4 5 0 . . . . . . 1 . . , A . . 2 . . . , B . 3 . . . . , . 4 . X . . . . 5 . . . . . . 

If there is an ant on (1/2), ant X should check (3/1). If there is a (2/3), then you should check (3/1) and (4/2). For (3/4) you need to check (4/2). Here is the table:

 (1/2) => [ (3/1) ] (2/3) => [ (3/1), (4/2) ] (3/1) => [ (4/2) ] 

These lists greatly reduce the branching of the tree, but now, unfortunately, it is difficult to estimate how long the calculations can take. I do not cut off groups based on the number of ants, but I impose a limit on the number of my own moves to be considered and on the number of enemies.

When making groups, I randomly select my first ant, and then add to the group all the enemy ants that could fight with him if he and they move. Then I check to see if these enemies have my ants nearby, which they can attack. If there are several of these, I first add someone closer to the first ant, and for him I seek enemies. The process is repeated until the limit is reached, or until those who can be added run out. It is important that for each of my ant, in his group are all his enemies. In this case, my ant can only be in one group, but the enemy may well be in several at once.

Evaluation

The evaluation function considers not only the number of killed and others, but also the distance between my and the enemy ants. Here she is:

 if (beAgressive) return enemyDeadCount * 300 - myDeadCount * 180 - distValue; else return enemyDeadCount * 512 - myDeadCount * (512+256) - distValue; 

If the flag is beAgressive, then a dead enemy costs 300 points, and a dead ant fines him 180. Thus, I will sacrifice one ant to kill one opponent, three ants, to kill two, but not two, to kill one. In the non-aggressive mode, the bot does not make equal exchanges, but is quite ready to give two for three. distValue - the sum of the distances from each of my ant to the nearest enemy, we deduct this amount, since it is better to be closer to the enemy.

So when is beAgressive set to true? It has nothing to do with the total number of ants or the positional advantage, it depends only on the number of ants that are close to the battle. More precisely, the flag is set if the maximum of the number of ants in battle (precisely in battle, and not in a group) with my ant in the neighborhood next is greater than or equal to 14. Why? Basically because 42 is divisible by 14!

Approaching enemies

The approachEnemies method is invoked right after the battles, and sends those of my ants that are close to the enemies, in their direction. For each of my ant, I first launch A *, which runs only on free cells (i.e., does not check cells on which there are other sums), and is limited in depth by a three-fold Manhatton distance to the nearest enemy. If there was a way this way, the first movement of that way was performed. It is for this reason that my bot often lined up, as if a void had formed on the front line, someone from the second line would immediately go there.

There is also a method called attackDetachedEnemies, the remainder of the beta version, which made you approach the isolated enemies first.

Protection

In the first version of the protection was not at all, but the second version, when the cards with many ant-nests became more popular, I added it all the same. I protect my anthills only when I have no more than four of them. Not sure that this sounds reasonable, but I don’t really like it when there are a lot of them. I'm looking for enemies in the vicinity of my anthills with the help of - you won’t believe - search wide! Then I sort these enemies by distance, and for each of them I try to find one defender. First, I search among those who are close to the path that the enemy must go through in order to reach the anthill. It is easy to get this way, you just need to run back through the previous cells, information about which is stored at BFS. If the defender is not there, I launch another BFS, which is looking for my ant, who is closest to 1/4 of that enemy’s path.I send this guardian half way. I do not check whether it is safe, because it is less scary to exchange a 1-by-1 ant than to lose an anthill.

Avoiding enemies

In general, I try to avoid exchanges of 1 to 1, so my lone ants run away at the sight of one or more enemies. I consider all possible movements of my ant, trying to find a safe one. If there is no such thing, I make a move that will at least kill the enemy if he goes in my direction.
Most of the time, it’s possible to make a few safe moves, so in order to choose, I added logic, which turned out to be one of the last added changes in version 3 in a hurry. maze maps. I escaped from this by running BFS with maximum depth in ESCAPE_CHECK_DIST (equal to eight) and adding values ​​for all safe movements, while the close cells had more weight, their ants were good, and the enemy were bad:

 int addValue = (ESCAPE_CHECK_DIST+1-tile.dist); if (tile.type == Type.MY_ANT) addValue *= 3; else if (tile.type.isEnemy()) addValue *= -3; 

Distribution

-, . - , , .
BFS , , , , , , . ( , ! — . . ) .
, , .

Well that's all!

, , , . , - , , , .
IRC, , .

Honestly, I was very surprised when I read this note. The winner’s algorithm had a huge number of flaws: it’s worth remembering about constants taken from the ceiling and coefficients or not taking into account many very important factors. Nevertheless, it is difficult to criticize the winner, because, as they say, “get it first!”. The most successful algorithm was the conduct of the battle: quite simple, but apparently extremely effective, because in the direct fight, xathis was a clear leader. It is necessary to assume that on the basis of his ideas a more general system with a dynamic selection of coefficients will soon be created, and then on TCP servers there will be extremely epic battles.

I hope you were interested.