Date created: | Last Updated:

Category: Project

Description: Despite recent deep neural network superhuman performance in many strategic board games, such as Chess and Go, there does not yet exist an algorithm that beats “Settlers of Catan” expert human players. Towards this direction, we present a combination of modern machine learning with a traditional tree-based adversarial search algorithm for initial settlement placement, and achieve performance that essentially matches the state-of-the-art. In particular, we use the n-player general- ization of the classic Minimax search algorithm, known as Maxn, with the novelty that the evaluation function at the leaf nodes is the result of a forward pass in a trained convolutional neural network. Our work con- sists of two distinct parts that can work independently. The first is the use of the simple Maxn algorithm for the first time in this game setting. The second is the use of the neural network as an evaluation function for evaluating the initial settlement placement, and which could potentially be plugged into any adversarial search algorithm. After 10000 simulated games, which is a sufficient number to draw conclusions in this demand- ing strategic board game, we achieve performance close to the state-of- the-art; with the advantages that (a) our approach does not make use of any human-generated data corpus; and (b) that our approach’s runtime is acceptable by human players, and much lower than the state-of-the-art’s for initial placement in this domain. The research described in this paper was carried out within the framework of the National Recovery and Resilience Plan Greece 2.0, funded by the European Union - NextGenerationEU (Implementation Body: HFRI. Project name: DEEP-REBAYES. HFRI Project Number 15430).