Towards Improving Monte Carlo Tree Search for Games with Imperfect Information

Monte Carlo tree search (mcts) is a commonly used search algorithm for games. Impressive results have been achieved in perfect information games, and the algorithmemerged as the preferred method within the more challenging field of general game playing,where agents are required to play games without knowing their rules beforehand.However, many improvements and optimizations for mcts are not available in imperfect(or hidden) information games or in general game playing. Therefore, new developments for mcts with a focus on these constraints were necessary. To improve playing strength,the author of this thesis proposed the novel approach of limiting the search tree’s expansion depth. The approach required to identify a baseline mcts modification and a meansto configure the maximum expansion depth. Subsequently, the approach was quantitatively evaluated with an experiment. This required implementing an engine capable of orchestrating general game playing matches, interpreting imperfect information games,and a set of agents. This thesis highlights the key details of the engine’s and agent’simplementations. It presents analysis of suitable mcts modifications. Additionally, it examines the use of feature extraction as a means of configuring the maximum expansion depth. Finally, the thesis reports on the results of two tournaments, conducted to evaluate the change in playing strength when limiting the expansion depth.For the considered cases, multi observer-information set mcts (mo-ismcts) was the preferred modification. Feature extraction was helpful, but not sufficient for configuring the agent using limited expansion depth. This agent had a distinct playing strength compared to the baseline agent. Surprisingly, in the game of the Corridor family, it achieved a 6.67% higher win rate (10 more, out of 150 matches) compared to the baseline.As a consequence, mo-is mcts with a limited expansion depth should be considered for imperfect information games. It remains unclear whether the advantage is only applicable to the chosen games, or if it applies to a wider class of games. Future efforts will be focused on addressing this question and further developing the engine.