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.
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 =)
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 opponent cannot make my path longer than this “path area”. Sometimes it is greater than actual max path length but never is less.
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
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.
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.
I looking for only next steps not entire path. Only cells marked by green on this image:
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
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:
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.