Calculating Ultra-Strong and Extended Solutions for Nine Men's Morris, Morabaraba, and Lasker Morris
This work provides extended game-theoretic solutions for board game variants, with incremental algorithmic improvements for ultra-strong play.
The researchers tackled the problem of calculating extended strong solutions for board games Nine Men's Morris, Morabaraba, and Lasker Morris, finding that most equal-stone starting positions in Morabaraba are wins for the first player, unlike the draws in the other games. They developed a multi-valued retrograde analysis algorithm for ultra-strong solutions, improving the chance of achieving better results against fallible opponents compared to random optimal move selection.
The strong solutions of Nine Men's Morris and its variant, Lasker Morris are well-known results (the starting positions are draws). We re-examined both of these games, and calculated extended strong solutions for them. By this we mean the game-theoretic values of all possible game states that could be reached from certain starting positions where the number of stones to be placed by the players is different from the standard rules. These were also calculated for a previously unsolved third variant, Morabaraba, with interesting results: most of the starting positions where the players can place an equal number of stones (including the standard starting position) are wins for the first player (as opposed to the above games, where these are usually draws). We also developed a multi-valued retrograde analysis, and used it as a basis for an algorithm for solving these games ultra-strongly. This means that when our program is playing against a fallible opponent, it has a greater chance of achieving a better result than the game-theoretic value, compared to randomly selecting between "just strongly" optimal moves. Previous attempts on ultra-strong solutions used local heuristics or learning during games, but we incorporated our algorithm into the retrograde analysis.