Back to the Code: Recar and Olaf69 share their winning strategies

STAY CONNECTED, FOLLOW CODINGAME NOW

Back to the Code is now over and we had a lot of fun watching the different replays and studying everyone's strategy. We saw plenty of great ideas and we hope you enjoyed this edition as much as we did!


Recar and Olaf69 had both great strategies which took them to the top of the leaderboard and they accepted to share them with us, so you can discover their special ingredients here:

Recar:

"1. I find the most optimal rectangle to fill by counting the number of neutral cells inside and the number of steps to surround.

2. I try to find if the areas under my control allow me to fill a bigger number of cells by connecting them between each other and if it is more optimal I use this move instead rectangle filling.

For a two players game, I check which rectangle my opponent wants to surround, and if his target is better than mine, then I move inside this area."

  • For 3 or 4 player games:
I assumed that my opponents would progress straight forward for at least 4 turns or until they find an opponents cell. This strategy helps to make a turn before someone could ruin my plan of closing the area. Also, if I travel back to the past I tried to take into consideration my opponents' moves and assumed they would remain the same. Every 20 turns I analyzed my path and if it did not lead towards filling the area I traveled back and tried again hoping this time it would go better.

To find the best area I sorted trough rectangles starting at 3 by 3 and chose the one that brought me the most points. To calculate points for the area I took the number of cells in the area, then if the number of calculated points was bigger than needed to win, then I set this number as a minimum. No need to be greedy :) If there were enemy cells in the area then I reset to 0 and exit.

For an area less then 3 cells long on whatever axis, the points were calculated as such: 1 divided by the number of cells in the path to the upper left corner.

Then I search for my cells on the perimeter and choose the cell from which the roundabout path is the shortest to fill the area. To make my bot fill the current rectangle instead of going to the brand new fancy but very distant place, I multiplied by 2 the number of moves needed to reach the first cell of that area. To add even more motivation to the bot in order to take bigger areas, I added a constant value to the number of steps , which depended of the number of players.

Points were calculated as such:

Number of neutral cells by number of turns.
I multiplied points by 2 if the score for neutral cells was enough to win.

  • For two player mode:

I multiply points by 2 if my rectangle's border goes along 17-th line on x-axis, and there are more than 10 free cells on it.
I divide points by 2 if the rectangle is more than 14 cells in any direction.

For three and four player modes:
I multiply points by 1.1 if the rectangle touches the edge of playing field.
I divide points by 2 if the rectangle is more than 13 cells for three players or 12 cells for four
I divide points by 2 for each of my opponents closer to my rectangle less than 2 cells
I divide points by 10 if information from the future tells me that one of my opponents is aiming towards this area.

In order to stabilize bot's behavior I gave the 1.1 bonus to the rectangle from the past move.
If there are no rectangles estimated for more than 1 point, then I look for the closest single cell, ignoring those adjacent to an opponent. This helps to escape a mess with your rivals while trying to capture the neighboring cells at the same time.
I started to search for non rectangular areas in an "L-shape" from the current position and checked all of them up to 20 cells long. As a result I got the optimum amount of points which I should get to in order to fill the best chosen area.

Next thing I do is guess the area which my opponent will try to fill, with the same method I chose mine. If his area is bigger than mine and it seems he will fill it quicker than me, then I try to interfere. To make his efforts futile I search for the closest cell next to the border of the area he tries to close.
After that I had to either close my area or deal with my opponent. If the path to the target point is diagonal, then I should make my way trough as many neutral cells as possible. The best way to solve this was dynamic programming, but what I did was just check availability of cells after each step vertically or horizontally.



Olaf69:

"I just finished uploading to GitHub the repository I created to play the contest. On it you can see among other things a list of commit messages.

On the whole, my AI is based on an breadth-first-search algorithm. I believed that to be efficient I had to estimate on each turn the performance of a maximum of possible paths, within the 100ms limit.

The tree of all possible states of the game was particularly big (close to 5^nbPlayers^350 nodes), so it was necessary to come up with a few rules to limit the amount of possible states. At the end of the contest, my tree expansion rules were as follows:
  • If there is at least 1 neutral cell around me, I consider each neutral cell, but I leave out non-neutral cells. 
  • If there are no neutral cells around me, I’ll leave the area by making sure to never consider 2 different paths to the same non-neutral cell
As a last resort, if I haven’t found a path that will allow me to improve my score, I will move towards the closest neutral cell. This can happen because of the way I estimate the paths of opponent players.

On each expansion, I must also estimate the most probable move of each opponent. Ideally, I would've liked to implement an alpha-beta type algorithm - which consists of evaluating every possible move the opponents can make and assigning a score to each state - but that would have been completely unrealistic in light of the inordinate amount of possible states that would generate (and only 100ms to compute them all)... So what I did was to settle with a much simpler - but risky - solution which consists of moving the opponents in a deterministic way following these rules:
  • If the cell in front of them is neutral, they will move onto it (this implies you know in which direction they are moving). 
  • Otherwise, if their last move was to go left, they will first attempt to go on a neutral cell on their right, then on their left. It’s the other way round if their last move was to go right. 
  • If no neutral cells are around them, he will move towards the closest one. 
These rules assume that the opponents will not act aggressively, they will always privilege scoring points over disturbing my progress.

At the very start, I had implemented a way more defensive strategy, assuming my opponents would recursively move onto EVERY SINGLE cell they had access. This allowed me to evaluate the shapes I was sure I could close, but they were all much smaller - and thus less interesting - than the ones I get with with my final code.

Actually, with those rules of expansion I was still too limited by the available time, I could only estimate paths to quite shallow depths (close to 10-12, approx. 60000 nodes). A meager 12 cells isn’t enough to form large rectangles on a 20x35 grid! In fact, it mostly made me move in spiral shaped paths!

On idea that truly helped me make progress was further limitation of possible paths by performing 3 cell steps (only across neutral cells). At this point, I could evaluate paths across 30 cells, sometimes even more.

If I succeed in exploring the entire tree (frequent during endgame), I will then try again with a step of 2 cells, and then with a step of 1 cell.

Another major problem was to evaluate each path. At first my criteria was simple: the amount of points. But this was not very satisfying, this grid illustrates why:

00000000001111111111222222222233333
01234567890123456789012345678901234
+-----------------------------------+
0|xxxxxxxxxxxx................ooooooo|0 o: cells I own
1|xxxxxxxxxxxx. o o|1 O: were I am
2|xxxxxxxxxxxx. oo o|2 .: Best path I computed
3|xxxxxxxxxxxx. o o|3
4|xxxxxxxxxxxx. o o|4 Problem: I won't close a shape for another 22 turns...
5|xxxxxxxxxxxx..Ooooooo o o|5
6|xxxxxxxxxxxx oo o o|6
7|xxxxxxxxxxxx o oo o|7
8|xxxxxxxxxxxx ooo o|8
9|xxxxxxxxxxxx oo o|9
10|xxxxxxxxxxxx o o|10
11|xxxxxxxxxxxx o o|11
12| x x o o|12
13| x o o|13
14| x o ooooooooo|14
15| x ooo |15
16| x |16
17| x |17
18| x |18
19| Xxxxxxx |19
+-----------------------------------+
00000000001111111111222222222233333
01234567890123456789012345678901234


With the amount of points as the sole criteria, surrounding a larger, and larger zone is always the most interesting behavior. As such, you’ll always end up getting thwarted by your opponents. I proceeded to try a few different formulas:
  • Amount of extra points / remaining number of steps → closing a small zone becomes too interesting
  • Amount of total points / total number of steps → enables light optimization of generated shapes, but they remain too big.
Finally, I opted for this compromise:
  • (Amount of extra points + 20) / (remaining number of steps + 20) 

Additionally, there were a few optimizations that helped me advance. For example:
  • Limit as much as possible the amount of calls to the fill-in function. 
  • Optimize score calculation. 
  • Optimize the search for the closest neutral cell. 
  • Efficient memory management of nodes from the search tree. 
And yet I regret not having had time to implement all of my ideas, namely to exploit the back in time command!"


Thank you very much to both of them for their contribution! :-)





2 comments :

  1. Just a correction regarding my strategy: it is a breadth-first-search (not a depth-first-search)!

    ReplyDelete
  2. Corrected! Thanks for telling us :)

    ReplyDelete