“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¹⁰ states. An 18-ply alpha-beta search then used these databases to prove that the value of the initial position is a draw”
So they built a database containing all all 7,673,759,269 possible positions in the endgame phase (i.e. after all stones are on the board), and then did a full-depth search for the “place stones” phase.
Paper is from 1996, so one might think current hardware could do a full search, but they show (page 10/110) a position with “White to move and win. Mill closure in 187 plies.”
So, I don’t think this game is small enough to search the full tree. They made it small by first creating an endgame database with 7,673,759,269 endgames, but that database requires over a gigabyte of data (“The hash function we decided to use maps the 7,673,759,269 states into a range of 9,074,932,579 indices.”)
Thanks for the information! That game is definitely bigger than I thought. (I knew it was solved, but I'd wrongly imagined it was solved by complete game tree search.)
http://library.msri.org/books/Book29/files/gasser.pdf:
“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¹⁰ states. An 18-ply alpha-beta search then used these databases to prove that the value of the initial position is a draw”
So they built a database containing all all 7,673,759,269 possible positions in the endgame phase (i.e. after all stones are on the board), and then did a full-depth search for the “place stones” phase.
Paper is from 1996, so one might think current hardware could do a full search, but they show (page 10/110) a position with “White to move and win. Mill closure in 187 plies.”
So, I don’t think this game is small enough to search the full tree. They made it small by first creating an endgame database with 7,673,759,269 endgames, but that database requires over a gigabyte of data (“The hash function we decided to use maps the 7,673,759,269 states into a range of 9,074,932,579 indices.”)