Developing a game AI for Murus Gallicus

Abstract

The development of game AIs has been a popular challenge in the last years. One of the best game agents, AlphaZero, was developed by DeepMind in 2017 and superseded by MuZero in 2019. Both agents are based on algorithms that perfectly learn to play any game within not even a day, given they are fed the game’s rules. The development of such game AIs does not necessarily require big computation centers like the ones Google has. In this work, we show how to develop and implement a Murus Gallicus game AI using mainly GOFAI (Good Old-Fashioned Artificial Intelligence) methods. We start with a comparison between different search tree algorithms, including MiniMax, NegaMax, NegaScout (principal variation search) and show how transposition tables can be used for optimization. Furthermore, we demonstrate the advantages of a dynamic value function and time management while searching for the best move. Lastly, we evaluate the application of Evolutionary Learning (EL), explaining how we trained specific parameters.