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

The Back to the Code competition is over and we really enjoyed watching different games and learning strategies in each. We saw enough 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 standings and they agreed to share it, so you can discover the secret ingredients of their secret-ingredient soup.

Recar

For a game with 3 or 4: We

assume that the opponents will move in a straight line for at least 4 more turns, or until they hit a busy cell. This helps us to begin to turn earlier, in order to prevent the enemy from accidentally ruining the filling plan. Also, when sending to the past, we take into account the future of each of the opponents and hope that they will go the same way.

After 20 moves, we look to see if our covered path is to a large extent the perimeter of the area that we want to fill on the 20th move, then we return the time to the 1st move, so that perhaps everything goes better this time.

We are looking for the best way to fill:

We sort through all the rectangles starting from size 3 by 3 and select the best one by points. We 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 for victory. Why take the risk and be greedy.

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

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

To motivate the bot to paint over the current rectangle, rather than move to a new beautiful and distant one, we need to multiply the distance that we need to go to the point at which we paint over. To slightly motivate the bot to take larger rectangles, add a constant number depending on the number opponents. In the current version, this increase is equal to the number of players.

Points are counted 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 rectangle touching 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 along any axis.

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 along any of the axes for 3 and 4 players, respectively.
Points / 2 if each of the opponents is closer than 2 squares to the rectangle.
Points / 10 if information from the future reports that rivals are claiming this rectangle.
For more stable behavior, the selected rectangle from the last frame gives a bonus to the rating of 1.1.

If you did not find a single rectangle with an estimate> 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 hustle and bustle in two neighboring cells in an attempt to capture them simultaneously with the opponent.

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

As a result, we get the point at which it is optimal for us to go now to fill the “optimal” selected area.

Now, if we have two players, we look at what area he is trying to fill, just as they chose their own. If his area is better than ours and he finishes it faster, then we interfere with him. To do this, look for a point in the area that the enemy wants to fill. We select the nearest point inside that borders the wall that he has already created. So it will be more difficult for him to simply reduce the fillable area.

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, it is advisable to walk along as many neutral cells as possible. It would be better to solve this using dynamic programming, but I have a rougher version with a simple check how many neutral cells will become inaccessible to us after a horizontal step and how many after a vertical step.

Olaf69

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

All in all, my AI was based on a breadth-first search algorithm. I realized that if I want to achieve efficiency, I have to evaluate in each round the return on all possible directions within the 100ms limit.

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 rules for expanding the tree were as follows:

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

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

When moving forward, I had to also evaluate the most likely move of each of the opponents. Ideally, I should use the alpha-beta algorithm, which involves evaluating each possible move of the opponent 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 calculate everything in just 100 ms ) So I had to be content with a much simpler, but risky decision, which consisted in moving 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 means that you know where it is moving)
• Otherwise, if by the last move he turned right, then on the next he will try to stand on a neutral cage on the right, and then again on the left. And vice versa, if the last move was to the right.
• If there is not a single neutral cell nearby, then it will move to the nearest one.

These rules assumed that the opponent would not act aggressively and would prefer to increase 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 every cell to which they would have access. This allowed me to evaluate areas that I was more likely to close, but they were much smaller - and therefore less interesting - than those that I could get with my final code.

In fact, with those expansion rules, I was still too limited in the available time, I could only evaluate the paths of small depth (close to 10-12, about 60,000 branches). The meager 12 cells were not enough to form a large rectangle on a 35x20 cell grid. 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 in a turn (only in neutral). Thus, I could evaluate the direction 30 cells forward, and sometimes more.

If I was able to view 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. At first, the criterion was simple: the number of points. But it was not very satisfying for me and this grid shows why:

0000000000111111111122222222222233333
01234567890123456789012345678901234
+ ---------------------------------- - +
0 | xxxxxxxxxxxx ................ ooooooo | 0 o: cells that belong to me
1 | xxxxxxxxxxxx. oo | 1 O: My position is
2 | xxxxxxxxxxxx. oo o | 2.: The best calculated path
3 | xxxxxxxxxxxx. oo | 3
4 | xxxxxxxxxxxx. oo | 4 Problem, I will close the area only after 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 | 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 the only criterion in the form of the number of points capture larger and larger areas is the most interesting behavior. And in the end, your plans are frustrated by your opponents. I decided to use two different formulas:

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

In the end, I decided to focus on the following: Additional points + 20 / remaining steps + 20

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

• Limit the number of requests to the filling function as much as possible;
• Optimize invoice calculation;
• Optimize the search for the nearest neutral cell;
• Efficient search tree branch memory management;

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!