Abstract. We describe the combination of two search methods used to solve Nine Men's Morris. An improved retrograde analysis algorithm computed endgame databases comprising about 10 10 states. An 18-ply alphabeta search then used these databases to prove that the value of the initial position is a draw. Nine Men's Morris is the first non-trivial game to be solved that does not seem to benefit from knowledge-based methods.
Gasser REF showed that the game of Nine Men's Morris is a draw, using a combination of endgame databases and search.
Solving Nine Men’s Morris
Computational Intelligence
Computer Science