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
Opponent cannot make my path longer than this “path area”. Sometimes it is greater than actual max path length but never is less.
Usually our rival is 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.
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 =)
Check if enemy can cut his max path by placing one wall and if we can block this turn – block it.
In this Replay my first wall prevents closing area by red player.
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.
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.
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.
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.
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.
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.