An AlphaZero Agent for Just 4 Fun, a Non-Deterministic Game with Imperfect Information

Abstract

Im Streben nach Fortschritt in der künstlichen Intelligenz und den Suchalgorithmen wird ein Agent als ein System betrachtet, das Entscheidungen trifft und Aufgaben auf der Grundlage seines Verständnisses der Situation oder des Environments ausführt. Dieses Environment ist das umgebende System oder die Welt, mit der der Agent interagiert. Nichtdeterministische Environments mit unvollständigen Informationen sind durch Zufallsereignisse und einen Zustand gekennzeichnet, der den Agenten vollständig oder teilweise verborgen bleibt.Das AlphaZero-Framework ist bei mehreren schwierigen Spielen wie Go, shogi und Schach sehr erfolgreich. Es verfügt über einen Baumsuchalgorithmus, der von einem deep neural network geleitet wird. Das Netzwerk wurde ohne Verwendung menschlichen Expertenwissens, außer den Spielregeln, durch self-play mithilfe eines allgemeinen reinforcement learning Algorithmus trainiert.Bis vor Kurzem gab es keine allgemeinen Frameworks für nichtdeterministische Environments mit unvollständigen Informationen. In dieser Arbeit schlagen wir eine neuartige Erweiterung von AlphaZero vor, die in solchen Umgebungen funktioniert.Unser Algorithmus, betitelt AlphaJust4Fun, unterscheidet sich von AlphaZero, indem wir die Monte Carlo Baumsuche durch den Single-Observer Information Set MCTS Algorithmus ersetzen. Der Single-Observer Information Set MCTS Algorithmus ist nicht von vollständig bekannten Umgebungen abhängig, da die Suche auf Knoten durchgeführt wird, die die Suchstatistiken zufälliger Instanziierungen der verborgenen Teile eines bestimmten Umgebungszustands kombinieren.Wir implementieren einen Prototyp und evaluieren ihn mit dem hybriden Brett- und Kartenspiel Just 4 Fun im Zwei-Spieler-Modus. Wir evaluieren unseren Algorithmus mit zwei verschiedenen Netzwerkarchitekturen an Testsätzen, die auf bestimmte Aspekte des Spiels abzielen, und in einem Benchmark. Als Referenzalgorithmus für den Benchmark verwenden wir einen Monte Carlo Tree Search Algorithmus, dem die sonst verborgenen Teile der Spielzustände bekannt sind, und menschlichen Spielern.Die Ergebnisse zeigen, dass AlphaJust4Fun mit den verborgenen Informationen und dem Nichtdeterminismus in Just 4 Fun erfolgreich umgehen kann. Es übertrifft den Referenzalgorithmus und kann auch mit erfahrenen menschlichen Spielern mithalten. Unsere Experimente zeigen, dass die Kombination des DNN und der Baumsuche des AlphaJust4Fun-Agenten besser abschneidet als jede Komponente für sich. Im Gegensatz zu neueren AlphaZero-Erweiterungen, die mehrere zusätzliche neuronale Netzwerke verwenden, erfordert AlphaJust4Fun nur einen zusätzlichen Hyperparameter.

In the pursuit of advancements in artificial intelligence and search, an agent can be considered as a system that makes decisions and performs tasks based on its understanding of the situation, or the environment. This environment is the surrounding system or world that the agent operates in, providing the agent with information and responding to its actions. Non-deterministic environments with imperfect information are characterised by chance events and a state that is fully or partially hidden from the agents.The AlphaZero framework has great success in several hard games like Go, shogi, and chess. It features a tree search algorithm that is guided by a deep neural network. The network was trained without using any human expert knowledge besides the rules of the games through self-play using a general reinforcement learning algorithm.Not until very recently, there were no general frameworks for non-deterministic environments with imperfect information. In this thesis, we propose a novel extension of AlphaZero which does work in these environments.Our algorithm is termed AlphaJust4Fun. The difference to AlphaZero is that we replace the Monte Carlo Tree Search with the Single-Observer Information Set MCTS. The Single-Observer Information Set MCTS does not depend on perfect information, as the search is performed on nodes that combine the search statistics of random instantiations of the hidden parts of a particular environment state.We implement a prototype and evaluate it on the hybrid board and card game Just 4 Fun in its two-player setting. We evaluate our algorithm with two different neural network architectures on test sets which target certain aspects of the game and a benchmark. As a baseline for the benchmark, we use a Monte Carlo Tree Search algorithm that searches with full knowledge of the hidden parts of the game state and human players.The results indicate that AlphaJust4Fun successfully handles hidden information and non-determinism in Just 4 Fun. It outperforms the baseline and can also compete with experienced human players. Our experiments indicate that the AlphaJust4Fun agent’s combination of the DNN and the tree search performs better than each component on its own. In contrast to more recent AlphaZero-extensions that use multiple neural networks, AlphaJust4Fun requires only one additional hyperparameter.