Nine Men's Morris
The nine-men's morris is filled up with mud;
And the quaint mazes in the wanton green,
For lack of tread, are indistinguishable.
– Midsummer Night's Dream (Act 2, scene 1), Shakespeare
Nine Men's Morris is one of the oldest of board games, known by different names and played with variations of rules in different places and periods. In France it is Marelle, in Austria it is Muhle, and in England it was also known as Peg Meryll, Meg Marrylegs, and the like, all referring to a "mill" because that is the name of a run of three counters as described below. Versions of it have been found etched into the roof of the Temple of Kurna in Egypt (dated to about 1400 BC), cut into the oak planks that form the deck of the great Viking ship discovered at Gokstad in 1880, and carved in the choir stalls of several English cathedrals.
Joseph Strutt in The Sports and Pastimes of the People of England (1801) described the rules in this way:
Two persons, having each of them nine pieces, or men, lay them down alternately, one by one upon the spots; and the business of either party is to prevent his antagonist from placing three of his pieces so as to form a row of three, without the intervention of an opponent piece. If a row be formed, he that made it is at liberty to take up one of his competitor's pieces from any part he thinks most to his advantage; excepting he has made a row, which must not be touched if he have another piece upon the board that is not a component part of that row. When all the pieces are laid down, they are played backwards and forwards, in any direction that the lines run, but only can move from one spot to another (next to it) at one time. He that takes off all his antagonist's pieces is the conqueror.
In 1996, the German mathematician Ralph Gasser used a computer to prove that Nine Men's Morris is a guaranteed draw if both players make optimal moves from the outset. He programmed the computer to figure out and tabulate 10 billion positions that were known to be a win for one side or the other, then worked forward 18 moves from the beginning of the game until his opening analysis met his endgame analysis. As a result he showed that every potentially winning position could be countered by the opponent in the early stages of the game.1
1. Gasser, Ralph. "Solving Nine Men's Morris." Computational Intelligence, 12: 24-41 (1996).