SOLVING NINE-MENS-MORRIS

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 im proved algorithm for computing endgame databases allowed the game to b e solved on a personal computer. Other games have been solved using kn owledge-based methods to dramatically prune the search tree. Nine Men' s Morris does not seem to profit from such methods, making it the firs t nontrivial game solved in which almost the entire state space has to be considered.