Some coders truly are rising stars… Recar and Romka, 1st and 3rd on The Great Escape contest’s podium, shared with us their insights about their code and strategies. Thanks a lot, guys, for your contributions and again, congrats for your ranking!

Recar, (1st place, C++, Ukraine)

I tried two approaches.

Mini-max

First was mini-max with alpha beta pruning. However, after some tries, I decided to experiment with simple heuristics version and it shows not bad result. I had some ideas how to improve mini-max version but it has not so much sense =)

Heuristic Version

One of unusual things =) Max path length heuristic. I called this one “path area”. It counted as sum of all areas, which connected to my dragon and to exit or which connected to my dragon’s area at least with two cells. Exit cells considered as impassable.

Here are some examples. “Path area” for Orange dragon marked by green:

The Great Escape coding game
Calculating the max path area for your dragon

The opponent cannot make my path longer than this “path area”. Sometimes it is greater than actual max path length but never is less.

Turn algorithm

1. Rival selection

Usually, our rival is the next player. However, if he already won or his minimal path is longer than my maximal path I take
next rival. Alternatively, if my minimal path is better and rival has no walls
to change it.

2. Hardcoded turn for pattern

How to place the first wall in The Great Escape

If enemy puts first wall on one of those lines then I put my wall near with one cell gap. This pattern become active in last day, so it was fast fix =)

3. Check if enemy can cut his max path by placing one wall and if we can block this turn – block it.
In this Replay1 my first wall prevents closing area by red player.

4. Find if I can cut my maximal path with three walls for 2p game or with two walls for 3p game then do it. If this is multiwall
solution then select wall which makes enemy path longer and put this wall first.
Example Replay.

5. If enemy can put super blocking wall and we can block his turn – do it. Super blocking is depends from number of walls we have and from number of players. Usually, it is from three to five cells.

6. Looking for one blocking wall on entire board, which can delay enemy at least on five cells. Check if enemy cannot use it on next turn to super block me. If he can’t then place this wall.

7. Finding best blocking wall with in depth search.
Some kind of mini-max but very limited. Enemy can only select one of decreasing his path turns. Walls placed only to block opponent from one of next moves or we can skip place wall. Depth is about 10 and maximal amount of our walls is four.

After wall placing turn found, check if enemy cannot use it to delay me more. If he cannot do this turn.

8. If we are here, it means we decide not to place wall on this turn. I just check all equal decreasing our path moves and selecting best which rival can delay less.

Optimizations

Pathfinding 
I looking for only next steps not entire path. Only cells marked by green on this image:

Pathfinding was key in The Great Escape puzzle

I send wave from all target points until it reaches my dragon.

100000 calls of this function on empty board from (8,5) for red player consumes about 110-120ms on codegame’s servers.

Minimal path length

Often I need only minimal path length, but do not care about path itself. So, for this case I have separate function. It sends wave from dragon until it reaches any exit point.100000 calls of this function on empty board from (8,5) for red player consumes about 75-80ms on codegame’s servers.

Romka, (3rd place, C++, Belarus)

As this is my first contest here at Codingame, I’d like to say a few words about this platform. I think it is very cool because it supports a lot of languages. There are a lot of single player tasks where you can practice and earn some funny achievements. Player for battles is also very cool and handy. I appreciate a lot the frequency of battles between players, which allows to estimate your new AI version in less than hour.

Now about my AI, which was quite good, but of course not so good as Recar’s one =)

At the beginning of the contest I decided that minimax is not the way to go because of large amount of possible wall placements on each turn. So I ended up with some kind of a greedy algorithm, that was some mix of heuristics and brute-force methods with some reasonable assumptions. I said this algorithm is greedy because it tries to do some actions in the fixed order of their importance, and performs first suitable action. On each turn my AI used the following scenario without any information from the previous turns:

1) If I have a path to the goal, such that no opponent can finish before me and no wall can block this path, I’ll go straight to the goal.
2) If I can put some wall which will lead to the situation above, I’ll do this. This search was done with backtracking with depth = 3. That means I do recursive search of all possible placements of three walls discarding the actions of the opponent.
3) If opponent can put some wall with similar property, I find a wall to prevent this and put this wall.
4A) Find wall which I can put now in order to make opponent’s path as long as possible. This search was done with backtracking with depth = 5, assuming that opponent won’t put any walls and will just move towards his goal. Lets say this is currentBestWall.
4B) Find similar wall, but for the next turn, when opponent made one step. Lets say this is nextBestWall.
4C) If nextBestWall will make opponent’s path not so long as currentBestWall, put currentBestWall right now.
5) If I can put some wall which will leave me in small part of map, I’ll do this. This search was done with backtracking with depth = 3.
6) If opponent can put some wall with similar property, I find a wall to prevent this and put this wall.

7) Otherwise I move towards my goal.For 1vs2 battles I decided that my opponent is always the next player. I thought:

“If I am player 0, and player 2 is about to win, why should I spent my turn in order to prevent it? There is player 1 who can block him, so I will care about blocking player 1 supposing that he will block player 2! 🙂 “

Of course, there are many details and optimizations which allowed to perform all this recursive searches in less than 100 ms. The final version of my AI has 1200 lines of code.