Analysis of different MCTS implementations of artificial intelligence for the Children of the Galaxy computer game

Monte Carlo Tree Search (MCTS) is a popular game AI algorithm that searches the state space of a game while using randomized playouts to evaluate new states. There have been many papers published about various adjustments of the original algorithm, however, work that compares multiple of these algorithms together does not seem to exist. This lack of data can make it difficult to decide which variant to use without implementing and testing them which is potentially quite time-consuming. The aim of this thesis is therefore twofold. First to create such a comparison in a specific setting and second to introduce a new variant, WP MCTS, which is based on the idea that one should be able to gather more information from a playout by taking a look at all the states encountered during its computation. For our setting, we chose battles between small armies in a 4X computer game called Children of the Galaxy. The results presented here indicate that many, though not all tested variants outperform basic MCTS in this setting.