Any interesting ways to combine Monte Carlo tree search with the minimax algorithm?

Question

I've been working on a game-playing engine for about half a year now, and it uses the well known algorithms. These include minimax with alpha-beta pruning, iterative deepening, transposition tables, etc.

I'm now looking for a way to include Monte Carlo tree search, which is something I've wanted to do for a long time. I was thinking of just making a new engine from scratch, but if possible I'd like to somehow import MC tree search into the engine I've already built.

Are there any interesting strategies to import MC tree search into a standard game-playing AI?

Answer 1

There has indeed been some research towards combining MCTS and minimax-like algorithms. For example, the following two publications:

• Monte-Carlo Tree Search and minimax hybrids
• Monte-Carlo Tree Search and Minimax Hybrids with Heuristic Evaluation Functions

The basic intuition behind such combinations tends to be to use small minimax-like searches inside a larger MCTS search, and/or backing up proven wins/losses (proven in the sense that minimax-like search has established that a certain state is a certain win or loss when following perfect play) through the MCTS tree, in addition to the more standard value estimates.

but if possible I'd like to somehow import MC search into the engine I've already built.

I'm not sure how easy that would be. As I described above, I think it is more common that small minimax searches are used inside a larger MCTS search. I think that would mean that you'd first want to build an MCTS, and then try to import your already implemented minimax into it. That's kind of the opposite / other way around of what you write that you'd like to do.

I don't think integrating small MCTS searches inside a "larger" minimax would work well. The value estimates of small MCTS searches would be too unreliable for subsequent use in an "outer" minimax-like algorithm.