Towards improving Monte Carlo tree search for games with imperfect information

Abstract

Die Monte-Carlo-Baumsuche (mcts, engl. Monte Carlo tree search) ist ein weit verbreiteter Suchalgorithmus für Spiele. Bei Spielen mit perfekter Information wurden bereits beeindruckende Ergebnisse erzielt, und der Algorithmus hat sich als bevorzugte Methode im anspruchsvolleren Bereich des allgemeinen Spielens herauskristallisiert. Beim allgemeinen Spielen müssen Agenten Spiele meistern, ohne deren Regeln vorher zu kennen. Viele Verbesserungen und Optimierungen für mcts sind jedoch bei Spielen mit imperfekter(oder versteckter) Information oder beim allgemeinen Spielen nicht verfügbar. Daher waren Neuentwicklungen für mcts mit dem Fokus auf diese Beschränkungen notwendig.Um die Spielstärke zu verbessern, schlug der Autor dieser Arbeit den neuartigenAnsatz vor, die Expansionstiefe des Suchbaums zu begrenzen. Der Ansatz erforderte dieIdentifizierung einer grundlegenden mcts-Modifikation und ein Mittel zur Konfiguration der maximalen Expansionstiefe. Anschließend wurde der Ansatz in einem Experiment quantitativ bewertet. Dazu musste eine Engine implementiert werden, die in der Lageist, allgemeine Spielpartien zu orchestrieren, Spiele mit imperfekter Information zu interpretieren und eine Reihe von Agenten zu entwickeln. In dieser Arbeit werden die wichtigsten Details der Engine- und Agentenimplementierungen vorgestellt. Sie präsentiert eine Analyse geeigneter mcts-Modifikationen. Außerdem wird die Verwendung von Merkmalsextraktion als Mittel zur Konfiguration der maximalen Expansionstiefe untersucht. Abschließend wird über die Ergebnisse zweier Turniere berichtet, die durchgeführt wurden, um die Veränderung der Spielstärke bei Begrenzung der Expansionstiefe zu bewerten.Für die betrachteten Fälle war die Multi-Beobachter-Informationsset mcts (mo-ismcts,engl. multi observer-information set mcts) die bevorzugte Modifikation. Die Merkmalsextraktion war hilfreich, aber nicht ausreichend, um den Agenten mit begrenzter Expansionstiefe zu konfigurieren. Bei diesem Agenten war im Vergleich zum Basisagenten ein deutlicher Unterschied in der Spielstärke. Überraschenderweise erreichte er in einer Variante von Corridor eine um 6, 67% höhere Gewinnrate (10 mehr, von 150 Spielen) im Vergleich zum Basisagenten. Infolgedessen sollte mo-ismcts mit einer begrenzten Expansionstiefe für Spiele mit imperfekter Information in Betracht gezogen werden. Es bleibt unklar, ob der Vorteil nur für ausgewählte Spiele gilt oder ob er auf eine breitere Klasse von Spielen anwendbar ist. Zukünftige Arbeiten werden sich auf die Klärung dieser Frage und die Weiterentwicklung der Engine konzentrieren.

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.