Domain independent enhancements to Monte Carlo tree search for eurogames

Abstract: The Monte Carlo tree search-algorithm (MCTS) has been proven successful when applied to combinatorial games, a term applied to sequential games with perfect information. As the focus for MCTS has tended to lean towards combinatorial games, general MCTS-strategies for other types of board games are hard to find. On another front, board games under the name of “Eurogames” have become increasingly popular in the last decade. These games introduce yet another set of challenges for game-playing agents on top of what combinatorial games already offer. Since its initial conception, a large number of enhancements to the MCTS-algorithm has been proposed. Seeing that eurogames share much of the same game-mechanics with each other, MCTS-enhancements proving effective for one game could potentially be aimed towards eurogames in general. In this paper, alterations to the expansion phase, the playout phase and the backpropagation phase are made to the standard MCTS-algorithm for agents playing the game of Carcassonne. To detect how enhancements are affected by chance events, both a deterministic and a stochastic version of the game is examined. It can be concluded that a reward policy relying solely on in-game score outperforms the conventional wins-against-losses policy. Concerning playouts, the Early Playout Termination enhancement only yields better results when the number of MCTS-iterations are somewhat restricted. Lastly, delayed node expansion is shown to be preferable over that of conventional node expansion. None of the enhancements showed any increasing or declining performance with regard to chance events. Additional experiments on other eurogames are needed to reaffirm any findings. Moreover, subsequent studies which introduce modifications to the examined enhancements is proposed as a measure to further increase agent performance.