I recently participated in a Bot contest organized by HackerEarth. We had to write a bot to play a two-player game called Isola. First of all, let me say this was an amazing problem to start the series with. It had some algorithmic subtleties, and it also required a lot of optimizations.

I used Negamax search (https://en.wikipedia.org/wiki/Negamax) with iterative deepening. This meant that I started by considering all possible moves at 1 depth, 2 depth and so on until I ran out of the time. Due to the exponential nature of the search tree only the last iterative deepening iteration mattered in terms of the runtime.

The main hurdle was the fact that Isola has a really high branching factor (there are potentially (# of available moves for your peg) times (# of possible cells to erase) options on each step which can easily go to over 100 options per step which is huge).

Therefore, I started by only considering erasing cells adjacent to the enemy peg. I had a special case for when there were very few empty cells near the enemy, when I also allowed cells at distance 2.

I managed to get 3-4 ply search depth in the early game with this method.

As a heuristic function for when I couldn't expand nodes further, I looked at the A * # of possible moves of my peg - B * # of possible moves of the enemy. It was more important reducing his mobility than my own mobility, so that B > A (I think that I had A = 1, B = 3 but other values work).

I also had a basic opening book for the first 3 moves which was basically move your peg towards the center and erase central cells in front of the enemy.

Finally, the thing I was most proud of was that I had a special algorithm for the case in which both pegs ended in the same connected component. For that case, if there were less than 16 cells in the connected component, I applied dynamic programming with bitmasks on the cells in the connected component to compute the optimal strategy. Notice that you only needed the parity of number the cells outside of the connected component, not their whole number.

I was also close to implement the same thing for when the pegs were in different connected components which were small enough in size. The optimal strategy would always involve erasing cells in the enemy connected component, therefore a dynamic programming algorithm could be run independently on the 2 connected components.

Additional stuff:

• hashing didn't really help at all
• move generation was heavily optimized with bitmasks since it was the most time consuming part
• heuristic function (the one using mobility) was also optimized using bitmasks