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.
Ralph Gasser calculated a strong solution for the moving phase of the standard Nine Men's Morris, and established the game-theoretic value of the game to be a draw REF .
Solving Nine Men’s Morris
Computational Intelligence
Computer Science