Nine Men's Morris is a DRAW
Ralph Gasser
As there are different variations of NMM being played, I will first specify
the rules I used, then give a short summary of how the solution was computed.
RULES
-----
Nine Men's Morris is played on a board with 24 points where stones may be
placed.
+--------+--------+
| | |
| +-----+-----+ |
| | | | |
| | +--+--+ | |
| | | | | |
+--+--+ +--+--+
| | | | | |
| | +--+--+ | |
| | | | |
| +-----+-----+ |
| | |
+--------+--------+
Both players start with nine stones each.
The game goes through three phases
- opening phase
Players alternately place stones on an empty point.
- midgame phase
After all stones are placed, players slide stones to
any adjacent vacant point.
- endgame phase
When a player has only three stones left, she may
jump a stone to any vacant point.
When closing a mill (three-in-a-row), any opponent's stone
which is not part of a mill may be removed. If all the
opponent's stones are part of mills, any stone may be removed.
Closing two mills simultaneously (opening phase) only allows
one of the opponent's stones to be removed.
- The first player who has less than three stones loses.
- The first player who cannot make a legal move loses.
HOW IT WAS SOLVED
-----------------
Retrograde Analysis (well known from Chess) was used to compute
databases for all mid- and endgame positions (about 10 billion
different positions). These positions were split into 28
separate databases characterized by the number of stones on the
board i.e. all the 3 White stone against 3 Black stone
positions, the 4-3, 4-4 ... up to 9-9 positions.
An 18 ply alpha-beta search for the opening phase then found
the value of the initial position (the empty board). Only the
9-9, 9-8 and 8-8 databases were needed to establish that the
game is a draw.
Ralph Gasser (gas...@inf.ethz.ch)
Informatik, ETH
CH-8092 Zurich
Switzerland