Monte Carlo Tree Search with Metaheuristics

Monte Carlo Tree Search/Upper Confidence bounds applied to Trees (MCTS/UCT) is a popular and powerful search technique applicable to many domains, most frequently to searching game trees. Even though the algorithm has been widely researched, there is still room for its improvement, especially when combined with metaheuristics or machine learning methods. In this paper, we revise and experimentally evaluate the idea of enhancing MCTS/UCT with game-specific heuristics that guide the playout (simulation) phase. MCTS/UCT with the proposed guiding mechanism is tested on two popular board games: Othello and Hex. The enhanced method clearly defeats the well-known Alpha-beta pruning algorithm in both games, and for the more complex game (Othello) is highly competitive to the vanilla MCTS/UCT formulation.