MorrisTalkPlay freeEnglish · Deutsch
MorrisTalk › Learn Morris › Is Nine Men's Morris solved?
Is Nine Men's Morris solved?
Yes, and the answer is a draw. If neither player ever slips, nobody wins. That is why the videos promising a win every time turn out to beat one particular computer opponent, not the game itself.
The result: a draw from the empty board
In November 1993 Ralph Gasser announced that he had worked out the value of Nine Men's Morris from the empty board. Neither side can force a win. If both players find the best move every turn, the game ends level, and all that is left to argue about is who slips first. His full paper, "Solving Nine Men's Morris", appeared in 1996 in the collection Games of No Chance.
He used the method that gave us chess endgame tables. Start at the end and work backwards: a position where a side has two men left, or cannot move, is lost for that side; a position where you have a move into such a position is won; and so on, layer by layer, until every position of the moving phase carries a label. The tables came to about ten billion positions. Then the placing phase, which is 18 plies long (nine men each), was searched forwards from the empty board until every line ran into a labelled position. The empty board came out as a draw.
What "strongly solved" means
Gasser's tables know the right answer for every position that can occur, not just the starting one. So a program built on them plays perfectly even after you have blundered, and it can tell you for any position whether the side to move wins, draws or loses.
Gábor Gévay and Gábor Danner (Eötvös Loránd University and the University of Szeged) rebuilt and extended this work, and released a free program called Malom. Their paper points out a catch. A program that just picks any drawing move draws a great deal, "even against novice players", as they put it, because most drawing moves give the opponent nothing to go wrong on. So they built an ultra-strong version: when several moves are equally good, it prefers the one after which the opponent has the most ways to throw the game away. The compressed database is about 12 GB (78 GB unpacked), and the code is open source under the GPLv3.
So there is no way to win every time
Against a perfect opponent there is nothing to win. The "win every time" videos are of two kinds.
The first kind beats a specific computer opponent, usually the one inside a video game. That opponent answers the same way in the same position, so once you have its replies written down, you can repeat the game. It is memorising a program. It tells you nothing about a friend across the table.
The second kind shows a trap, almost always the one that gives you two open mills at once (see the opening guide for the exact shape and the cheap answer to it). It does work on a player who has not seen it before, and it fails against anyone who has.
How you do beat a person
Many positions that are drawn in theory are drawn only just: one side has to find the only good move, the other can wander. Gévay and Danner say so directly. That is where human games are decided. Some habits that follow from it, offered as advice and not as a proof:
- Keep your men mobile. A blocked side loses, and the placing phase leaves only six empty points when no man has been taken (24 points, 18 men).
- Look for positions where you have three plausible moves and your opponent has one good one, then play on until they miss it.
- Learn the double mill. It is the pattern that turns a small edge into a won game.
- Play with a clock. Tournaments of the World Mill Game Federation (WMD) use chess clocks, 5, 7 or 10 minutes a side, partly to keep the number of draws down.
Does moving first matter?
In theory no: both the first and the second player can hold the draw. German Wikipedia adds a practical note, that the second player puts down the eighteenth man and so sees the whole placing phase before committing the last stone. It is a small edge, and only if you use it.
Other boards, other answers
Lasker Morris, the ten-man version where you may move while you still have men in hand, is also a draw. The twelve-man board with diagonals, played in southern Africa as Morabaraba, is different: Gévay and Danner found it to be a win for the first player under their rules. MorrisTalk's Twelve Men's game has its own details (flying at three men, a draw if the board fills up), so do not read that as a promise for it.
Where this leaves you in MorrisTalk
The robot opponents look a few moves ahead. They are not Malom, and the traps in these guides work on them. A game is drawn if the same position appears three times, or if 50 moves go by without a man being placed or taken. If you want to know how a game should have gone, run it through Malom afterwards. During the game, it is just you, your friend and the voice channel.
Frequently asked questions
Is Nine Men's Morris a solved game?
Yes. Ralph Gasser showed in 1993 that with perfect play from both sides the game is a draw. Gévay and Danner later built the Malom program on a stronger solution.
Can the first player always win Nine Men's Morris?
No. Both the first and the second player can hold the draw, so neither has a forced win.
Is there a trick to win Nine Men's Morris every time?
Not against an opponent who answers correctly. Traps such as the two-open-mills opening beat careless players and fixed computer opponents, but perfect play is a draw.
Can I download a Nine Men's Morris solver?
Yes. Malom, by Gábor Danner and Gábor Gévay, is open source (GPLv3) and plays from precomputed databases of about 12 GB compressed. It is best used to review a game afterwards.
More Morris guides
Sources
- Ralph Gasser, Solving Nine Men's Morris, Games of No Chance (MSRI Publications 29), 1996
- Gábor Gévay and Gábor Danner, Calculating Ultra-Strong and Extended Solutions for Nine Men's Morris, Morabaraba, and Lasker Morris (arXiv:1408.0032)
- Malom, project page, University of Szeged
- Mühle (Spiel), Wikipedia (German)