I am implementing an AI player for this board game.

I am using AB minimax with memory (MTD(f)) for search, but I am having trouble finding a good heuristic for the evaluation function, and even if I want to use reinforcement learning I need to find a good set of features to represent the board states since the state space is very large. How should I approach this problem?

Thanks

That looks like a very tricky problem. I am not even certain minimax is the right approach. Perhaps Monte Carlo methods might work better.

Are there people that are good at playing it? Any strategy guides?

wow - nice problem to solve. I think minimax certainly will be useful as you start approaching the end of the game, for two main reasons.

The branching factor reduces to reasonable numbers for minimax to handle well. And there appears to be opportunity to use a quiescent search as it appears

that many forcing moves will become apparent when there is an opportunity to block merging (or creation in a limited space) of groups (which I assume becomes very important near the end of the game).

I have one thought about this game that might be relevant: This game is played on a graph, in the sense that the geometry of the hexagonal pattern (e.g., what's aligned) does not matter. It could be played on any other graph just fine. Towards the end of the game, small groups that cannot grow because they are totally blocked by the other color are irrelevant and can be removed from the internal description of the board. Similarly, large groups are equivalent, whether they have 5 stones or 15. This allows to simplify the graph structure towards the end of the game. The are more simplifications available, like identifying "pass" cells (empty cells where you can prove that it won't matter whether they end up being black or white) and ignoring what they attach to. I believe only the parity of the number of "pass" cells on the board really matters.

If you explore a position using minimax and you get a winning or losing score, you can store the simplified graph of the position (or some hash of it) and its score. Over time you can build a database of endgame positions that way, and then you can query this database in the search. If the graphs simplify as much as I think they will, this should allow you to deduce the true score of positions from pretty early on in the game.

Right now I am using iterative deepening AB minimax with memory(MTD(f)) + Monte Carlo search as the evaluation function and it is performing better than my earlier minimax algorithm and better than a basic Monte Carlo search.

The algorithm is performing like a Monte Carlo search in the beginning: the search depth is in the range [1-4] (branching factor ~ 122 and the leaf nodes are evaluated using Monte Carlo search which takes time) but since it's storing the node's evaluation in a transposition table, this guides minimax later when the search can go deep towards the end of the game. I am trying to find a good combination of Monte Carlo and minmax especially that the current implementation suffers from the horizon effect and has a very small search depth at the beginning.

I am thinking about the following approaches to improve my player:

- Improve the evaluation function (Alvaro's suggestions sound reasonable) and maybe use quiescence search to mitigate the horizon effect.

- Implement my AI using a purely Monte Carlo search (it's Aheuristic nature might work for this game)