SOLVING NINE MEN'S MORRIS

Abstract

The game of Nine Men's Morris is a draw. We obtained this result using a combination of endgame databases (10 10 states) and search. Our improved algorithm for computing endgame databases allowed the game to be solved on a personal computer. Other games have been solved using knowledge‐based methods to dramatically prune the search tree. Nine Men's Morris does not seem to profit from such methods, making it the first nontrivial game solved in which almost the entire state space has to be considered.