Abstract
Settlers of Catan (Catan) is a popular board game featuring expansion, resource management, negotiation, and long-term planning decisions. Unlike traditional turn-based strategy games like Go or Chess, which have been effectively mastered by AI agents, Catan presents a far greater challenge due to its stochastic nature, non-stationary dynamics, and multi-agent interactions—with up to 4 players in the base game. Catan also features slow-paced gameplay with frequent low-impact actions, such as unsuccessful trade proposals or inconsequential dice rolls. These elements lead to long decision sequences with limited immediate feedback, which have made it difficult for both AI-based and game-theoretic models to outperform the average human player.
To address this challenge, we leverage two emerging areas of research: Turn-Based Multi-Agent Reinforcement Learning (TMARL) and Graph Neural Networks (GNNs). TMARL provides a learning framework where agents iteratively improve their decision-making through experience in multi-agent environments. Meanwhile, GNNs offer a powerful representation learning approach that captures both local and global structures within a game state.
In this paper, we investigate key factors that influence the effectiveness of TMARL agents in the environment of Catan. Specifically, we examine the impact of: (1) a GNN-based state-to-action network designed to leverage the board's spatial and relational structure, (2) various exploration strategies to navigate extended decision-making phases, (3) different replay sampling distributions to prioritize learning from high-impact decisions, and (4) an ensemble model to mimic strategies employed by human players.
Our findings will provide valuable insights into the challenges and opportunities of applying RL to complex, multi-agent environments. The simultaneous interplay of competing objectives and diplomatic negotiations presents a unique challenge for AI—one that remains largely unsolved. Therefore, our results also have broader implications for the development of decision-support systems in military strategy, where turn-based simulations are commonly used to model future engagements, resource allocation, and coalition dynamics—similar to Catan.