Constructing a forward-looking adaptation of retrograde analysis through the lens of Onitama

In this thesis we study the board game Onitama, focusing on methods of determining this game's optimal strategies in order to find strong and weak solutions for this game and generalisations thereof. We apply a general-purpose algorithm for strongly solving similar chess-like games called retrograde analysis, and prove its infeasibility to strongly solve Onitama by providing upper and lower bounds for the number of distinct game states it has to analyse. We introduce a new algorithm based on retrograde analysis that we formally prove is capable of weakly solving the game for all non-losing players instead, called forward-looking retrograde analysis. We also provide a useful symmetry that can be applied to the state space of this game to cut its size in half, significantly reducing retrograde analysis' runtime. This analysis is done on a generalisation of the game with respect to the dimensions of the game board. The largest board size retrograde analysis is able to solve in under...Show moreIn this thesis we study the board game Onitama, focusing on methods of determining this game's optimal strategies in order to find strong and weak solutions for this game and generalisations thereof. We apply a general-purpose algorithm for strongly solving similar chess-like games called retrograde analysis, and prove its infeasibility to strongly solve Onitama by providing upper and lower bounds for the number of distinct game states it has to analyse. We introduce a new algorithm based on retrograde analysis that we formally prove is capable of weakly solving the game for all non-losing players instead, called forward-looking retrograde analysis. We also provide a useful symmetry that can be applied to the state space of this game to cut its size in half, significantly reducing retrograde analysis' runtime. This analysis is done on a generalisation of the game with respect to the dimensions of the game board. The largest board size retrograde analysis is able to solve in under two hours is 3x4, with forward-looking retrograde analysis being able to increase this to 4x3. While making use of symmetries, forward-looking retrograde analysis is also able to solve the 3x4 board roughly 98.30% faster than retrograde analysis.Show less

Leiden University Student Repository

Documents

In Collections

Constructing a forward-looking adaptation of retrograde analysis through the lens of Onitama