Nine Men's Morris, also known as Mills, Merrills, is a two-player strategy game with a long history in Europe. Each player has nine pieces which move between the twenty-four intersections of three interlocking squares.
The object of the game is to remove all the enemy pieces. Every time a player forms a line of three (a mill) on any line drawn on the board, he is entitled to remove one enemy piece, with the proviso that a piece may not be removed from an enemy mill.
The game starts with the board empty. Players take turns placing pieces on any empty intersection. After all eighteen pieces have been placed, players take turns moving. A move consists of sliding a piece along one of the board lines to an adjacent intersection.
An ideal position, which typically results in a win, is to be able to shuttle one piece back and forth between two mills, removing a piece every turn. For example, in the diagram below red has a won game even if blue moves first.
When a player is reduced to three pieces, those pieces may fly from any intersection to any intersection. This appears to be a powerful resource for an underdog, but in fact rarely changes the outcome of a game.
A common variant of Nine Men's Morris adds four diagonal lines to the board. This makes the game faster and more tactical.
The number of legal positions in Nine Men's Morris is estimated to be 1010, the total number of possible games is approximately 1050. In October 1993, Ralph Gasser solved Nine Men's Morris - he showed that it ends in a draw with perfect play. Gasser also developed an AI, called Bushy that is regarded as the world's strongest player.
The World Merrills Association ran the World Championships annually at the Ryedale Folk Museum, Hutton le Hole, York, England.
Shakespeare's Mechanicals of A Midsummer Night's Dream apparently play it: (Act 2, Scene 2), "The Nine Men's Morris is filled up with mud." Adult players used to cajole children of light or dark hair to move from hole to hole to act as pieces for the game.
Related games: Kensington similarly has two phases of play.