[CodinGame] Back to the Code: Recar and Olaf69 share their strategies

The Back to the Code competition is over and we really enjoyed watching various replays of games and learning strategies in each. We saw a fair amount of good ideas and we hope you enjoyed the game as much as we did.

Recar and Olaf69 both developed an excellent strategy that allowed them to reach the top of the tournament table and they agreed to share it, so you can discover the secret ingredients of their secret ingredient soup.

Recar

To play with 3 or 4:
')
We assume that the opponents will move in a straight line for at least 4 more moves, or until they rest in a occupied cage. This helps us to start turning earlier, so as not to give the enemy a chance to spoil the filling plan. Also, when sending in the past, we take into account the future of each of the opponents and we hope that they will walk the same way.

After 20 moves, we look to see if our path is largely the perimeter of the area we want to fill on the 20th move, then we return the time to the 1st move, so that maybe everything went better this time.

We are looking for the best course to fill:

We iterate over all the rectangles starting from 3 by 3 and choose the best one on points. Calculate points for a rectangular area. We get the number of neutral cells in the rectangle. If the number of neutral cells is greater than we need to win, then we consider the minimum necessary to win. Why risk and be greedy.

If there are enemy cells in the rectangle, then points = 0 and exit.

For an area of ​​less than 3 on any of the axes points = 1 / distance to the upper left point
We look, where there are our cells on the perimeter, and we find the cell with which we need to go in a circle so that the number of steps until the region is painted over is minimal.

To motivate the bot to paint over the current rectangle, rather than move to a new, beautiful and distant, the distance that we need to go to the point from which we will paint over multiply by 2. opponents. In the current version, this increase is equal to the number of players.

Points count as (number of neutral cells / number of steps)

Points * 2 if there are enough neutral cells to win.

For two players:
Points * 2 for the fact that the rectangle touches the edge through x = 17 and this middle line is still a little filled - there are more than 10 neutral cells.
Points / 2 if the size of the rectangle is greater than 14 on any of the axes.

For three or four players:
Points * 1.1 if the rectangle touches the edge of the field.
Points / 2 if the size of the rectangle is greater than 13, 12 on any of the axes for 3 and 4 players, respectively.
Points / 2 if for each of the opponents is closer than 2 cells to the rectangle.
Points / 10 if information from the future reports that rivals claim this rectangle.
For a more stable behavior of the selected rectangle from the previous frame, we give a bonus to the estimate 1.1.

If you have not found a single rectangle with a score of> 1, then we are looking for the nearest single cell. At the same time, we ignore all neutral neighbors with opponents. This allows us to avoid the fuss in two adjacent cells in an attempt to capture them simultaneously with the opponent.

We are looking for a non-rectangular area to capture when moving "corner" from the current position. We check all possible angles up to 20 cells long.

As a result, we get a point to which we are optimal now to go in order to fill the “optimal” selected area.

Now, if we have two players see what area he is trying to fill, just like they chose their own. If his area is better than ours and he finishes it faster, then we interfere with it. To do this, look for a point in the area that the opponent wants to fill. We select the nearest point inside, which borders on the wall already created by it. So it will be harder for him to just reduce the area to be filled.

After that we have a point where we want to go, either to close our area, or to interfere with the enemy. If this point is located diagonally from our current position, then it is advisable to pass as many neutral cells as possible along the way. It would be better to solve with the help of dynamic programming, but I have a rougher version with a simple check, how many neutral cells will be unavailable to us after the step horizontally and how many after the step vertically.

Olaf69

I have just uploaded the repository I created for the game to GutHub. In it, you can, among other things, find a list of commit notes .

In general, my AI was based on a wide search algorithm. I realized that if I want to achieve efficiency, I must evaluate in each round the return on all possible directions within the limit of 100ms.

The tree of all possible states was impressively large (close to 5 ^ number of players ^ 350 nodes), so it was necessary to come up with several rules that would limit the field of state options. By the end of the game, the tree expansion rules were:

• If there is at least one neutral cell around me, I consider each neutral cell, but skip the busy ones.
• If there are no neutral cells around, I leave this area, along the first computed path, without considering all the rest

And finally, if I did not find a path that would allow me to increase the score, I moved to the nearest neutral cell. This could be due to the way I evaluated my rivals' paths.

In the course of advancement, I also had to evaluate the most likely course of each of the opponents. Ideally, I should use the alpha-beta algorithm, which involves evaluating each possible opponent's move and assigning him a point, but this would be very far from reality in the light of the incredible number of possible states that would have to be generated (and calculated everything in just 100 ms ). So I had to be content with a much simpler, but risky solution, which was to move opponents in a deterministic way according to the following rules:

• If the cell in front of it is neutral, it will move to it (it is assumed that you know where it is going)
• Otherwise, if if he turned to the right with the last move, then on the next move he will try to stand on the neutral cell on the right and then on the left. Conversely, if the last move was to the right.
• If there is no neutral cell nearby, then it will move to the nearest one.

These rules assumed that the opponent would not act aggressively and would give preference to increasing his account, instead of trying to hinder my progress.

At the very beginning, my strategy was aimed more at defense, assuming that my opponents would recursively move to each cell to which they would have access. This allowed me to assess areas that I was more likely to close, but they were much smaller — and therefore less interesting — than those I could get with the help of my final code.

In fact, with those expansion rules, I was still too limited in the available time, I could only evaluate shallow depths (close to 10-12, approximately 60,000 branches). A scant 12 cells was not enough to form a large rectangle on a grid of 35x20 cells. In fact, it made me move more along a spiral path.

The idea that helped me make significant progress was to further limit the number of possible directions by moving three cells per turn (only neutral). Thus, I could estimate the direction of 30 cells forward, and sometimes more.

If I could see the whole tree (often during the game), then I tried to reduce the step to 2 cells, and then - to one.

Another big problem was the assessment of each direction. Initially, the criterion was simple: the number of points. But it was not very satisfying to me and this grid shows why:

00000000001111111111222222222233333
01234567890123456789012345678901234
+ ----------------------------------- +
0 | xxxxxxxxxxxx ................ ooooooo | 0 o: cells belonging to me
1 | xxxxxxxxxxxx. oo | 1 O: My position
2 | xxxxxxxxxxxx. oo o | 2.: Best calculated path
3 | xxxxxxxxxxxx. oo | 3
4 | xxxxxxxxxxxx. oo | 4 Problem, I will close the area in only 22 rounds ...
5 | xxxxxxxxxxxx..Ooooooo oo | 5
6 | xxxxxxxxxxxx oo oo | 6
7 | xxxxxxxxxxxx o oo o | 7
8 | xxxxxxxxxxxx ooo o | 8
9 | xxxxxxxxxxxx oo o | 9
10 | xxxxxxxxxxxx oo | 10
11 | xxxxxxxxxxxx oo | 11
12 | xxoo | 12
13 | xoo | 13
14 | xo ooooooooo | 14
15 | x ooo | 15
16 | x | 16
17 | x | 17
18 | x | 18
19 | Xxxxxxx | 19
+ ----------------------------------- +
00000000001111111111222222222233333
01234567890123456789012345678901234

With a single criterion in the form of points, capturing more and more areas is the most interesting behavior. And in the end your plans are thwarted by your opponents. I decided to use two different formulas:

• The number of additional points / the remaining number of steps → it becomes more interesting to close small areas
• Total points / total steps → optimizes areas a little, but they remain too large

In the end, I decided to focus on the following: The number of extra points + 20 / the remaining number of steps + 20

In addition, there were a few more improvements that helped me move forward. For example:

• Limit the number of requests to the filling function;
• Optimize the calculation of the account;
• Optimize the search for the nearest neutral cell;
• Efficient memory management branches of the search tree;

And yet, I regret that I did not have enough time to apply all my ideas, namely, to use the opportunity to go back in time!