Playing Carcassonne with Monte Carlo Tree Search
  Monte Carlo Tree Search (MCTS) is a relatively new sampling method with
multiple variants in the literature. They can be applied to a wide variety of
challenging domains including board games, video games, and energy-based
problems to mention a few. In this work, we explore the use of the vanilla MCTS
and the MCTS with Rapid Action Value Estimation (MCTS-RAVE) in the game of
Carcassonne, a stochastic game with a deceptive scoring system where limited
research has been conducted. We compare the strengths of the MCTS-based methods
with the Star2.5 algorithm, previously reported to yield competitive results in
the game of Carcassonne when a domain-specific heuristic is used to evaluate
the game states. We analyse the particularities of the strategies adopted by
the algorithms when they share a common reward system. The MCTS-based methods
consistently outperformed the Star2.5 algorithm given their ability to find and
follow long-term strategies, with the vanilla MCTS exhibiting a more robust
game-play than the MCTS-RAVE.
