Applications of genetic algorithms to finding strategies in games with randomness on the example of "Settlers of Catan"

Abstract

The goal of this thesis was to define key behaviours and preferences (strategy), which the player should assume, in order to increase the chance of winning. To achieve that goal, we used a combination of genetic algorithm and graph methods (such as Dijkstra method). The game - “Settlers of Catan” - is a well-known tabletop game for 2-8 players, however in this instance, its ruleset was modified for accommodating only 2 players. Example of such rule change would be removal of the “thief” mechanic. Our decision to program the game stems from the fact that it allowed us to implement the “evaluator” - a class responsible for the player's decision-making process, depending on strategy attributes given (“comparison strategies”) or generated (strategies generated by genetic algorithm). Additionally, we decided to experiment with both the hyperparameters of the genetic algorithm to see if e.g., increased mutation probability would lead to better or different results. This implementation also allowed us to design a graphical interface for human players to play against the strategy.