A Study of UCT and its Enhancements in an Artificial Game

Abstract. Monte-Carlo tree search, especially the UCT algorithm and its en-hancements, have become extremely popular. Because of the importance of this family of algorithms, a deeper understanding of when and how the different en-hancements work is desirable. To avoid the hard to analyze intricacies of tournament-level programs in complex games, this work focuses on a simple abstract game, which is designed to be ideal for history-based heuristics such as RAVE. Ex-periments show the influence of game complexity and of enhancements on the performance of Monte-Carlo Tree Search.