Mixed Strategies in Machine Learning and Catan

Abstract

This paper follows research applying Machine Learning to the board game Settlers of Catan with the aim of comparing the performance of pure strategies to those of mixed strategies. The mixture of deterministic and non-deterministic elements in Catan presents a unique challenge for AI development, leading to a well-established area of research devoted to the subject. Most existing research implements pure AI strategies that focus either on top-down or bottom-up techniques. Top-down AI aim to capitalize on an AI's ability to outclass human's implementation of proven techniques. Bottom-up AI aim to combine a general learning algorithm with a vast memory database of previously encountered gameplay that will improve the AI's performance as the database grows. Both have their respective weaknesses as top-down strategies tend to neglect prior information and bottom-up strategies tend to struggle to adapt to novel situations.

The mixed strategy developed by the author seeks specifically to combine both pure top-down and bottom-up AI strategies where each would compensate for the other's weakness. The pure top-down AI strategy was implemented through an Alpha-Beta search algorithm that prunes decision-making trees generated from gameplay. The pure bottom-up AI strategy was independently defined and developed by the author and operated on two simple concepts: gameplay configuration mapping and mapping comparison. The mixed strategy AI was implemented as the previously defined pure bottom-up AI with a top-down AI acting as a failsafe for move quality.

The performance of these three strategies against an AI playing random moves was used to compare them. The thesis of this paper is that the mixed strategy AI would outperform both pure strategy AIs. Initial results showed the pure top-down AI performing the best, followed by the mixed strategy AI, followed by the pure bottom-up AI. While this tentatively supports the author's thesis, further research is needed to make a stronger conclusion. Future research would likely also include testing against human players and adapting implementation to support Catan expansions.