Contents

Rules
Using the Mouse
Menu Commands and Options
Hints and Tips on Strategy
History of the Game

Author's Notes


Rules

Phase One:
Each player has nine pieces and enters them alternately one at a time onto any vacant point (the mouse turns into a crosshair on legal points). If a player forms a row of three pieces (a MILL) along the side of a square or along one of the four lines crossing the squares, he removes one of his opponents pieces, but not one which is itself in a mill. (Except for if all the opposing pieces are in mills, because then it is legal to capture any one of them.)
When all the pieces have been entered on the board the next phase begins.

Phase Two:
The players continue in alternate turns of play by moving a piece to an adjacent vacant point along a line. If one player forms a mill, it works just like before: an enemy piece is removed.

Phase Three:
A player who has only three pieces left enters this phase. It is just like phase two except for that one is allowed to move the pieces to any vacant point.

But who wins?
There are two ways to win. One is to reduce your opponents pieces to a mere two. The other is to block all of your opponents moves.

Other rules:
* You may not pass.
* Mills can be opened and closed any number of times.

Author imposed rules:
* The game is a draw if:
1) 200 moves (per player) are played.
2) 50 moves (per player) are played without captures.
3) a position is repeated three times with the same player to move. The positions from phase one do not count!
* White always moves first.


Using the Mouse

An Example:
To perform a capture in phase two or three (see Rules) you must first choose which piece to move. This is done by moving the cursor to the piece in question and when the cursor turns into a crosshair, clicking the left mouse button. A red dot shows which piece you have chosen. Next, choose where to move by using the same method, and after that, click on the piece you want to capture. Your move has now been completed! (Legal captures are of course also indicated by the cursor turning into a crosshair.)
This is the way all moves are made.

The Cursor:
...can have three shapes when on the board:
Arrow: Click here and nothing will happen.
Hourglass: The computer is thinking about his move, and if you click, nothing will happen.
Crosshair: A legal move! Left click here and something will happen!

Left Mouse Button:
Chooses the move indicated by the cursor, and executes it, if it is the last part of the move.

Right Mouse Button:
Ooops! You chose the wrong piece to move but you still haven't chosen where to move it. This button takes you back to the first step in the move selection process. For more serious regrets, use Take Back (Ctrl-T) (see  Menu Commands and Options).


Menu Commands and Options

Game
New: Play a new game with the same options as before.
Exit: To take a break and write me a letter or call.

Actions
Hint: The cursor places itself on the move considerd best by the computer. The computers opininon might change, if you give it some time. Also, if you use this command during the computer's turn, the hourglass will place itself on the move which the computer currently likes the most.
Take Back: Did you make a stupid move? This lets you correct your misstake.
Replay: Hmm.. maybe it wasn't so stupid after all. This command takes back the Take Back command. Actually it does more than that; Let's say that you want to examine a played game, to find the point where that stupid computer lost (congratulations!). The best way to do this is to choose Human vs. Human mode and turn on the Thought Process window. Now you can move around in the game with Take Back and Replay, and at the same time the Thought Process window will show you the computer's analysis of the current position.

Options
Deep Thinking: The computer uses your thinking time to guess your best response, and starts to think about its own response even before you have made your move!
Random Play: Lowers performance slightly for a given thinking time, but provides more varied play.
Third Repetition Rule Used In Thinking: Check this item if you want the computer to consider T.R.R. ties when it thinks about a position. WARNING! In calm games without captures this option seriously hampers performance.
Show Thought Process: Displays/undisplays a window with the following information about the thought process:
Seconds spent: is the time the current position on the board has been the current position.
Positions seen: is the number of new positions generated during the search.
Search depth: is the number of half moves ahead the search has progressed.
Game value: predicted value of the game (moves ahead).
Cutoff ratio: search performance measurement.
Best: is the current best line.
Current: is the line currently being examinated.
Who's playing options: can be used anytime during a game.
Thinking Time: the computer plays better if you give it more time (pretty obvious!). This setting does NOT force human players to make a move within a certain time limit.


History of the Game

Nine Men's Morris (NMM from now on) is one of the oldest board games in the world. An NMM board has been carved into the stone of the Kurna temple in Egypt, probably by the workers who built the temple around 1400 BC. Other boards have been found in Troj and in the strange bronze age tombs of County Wicklow, Ireland. Many hundred years later, the game was also popular among the Vikings. A board has been found in in a king's burial ship on the Gokstad Farms, near Sandefjord, Norway. That grave is dated to about AD 900.
During the 14th century, a version of the game with twelve men and diagonals became popular in the royal courts of Europe,  a version which is still being played today in the USA.
NMM is mentioned in both the Talmud and in Shakespeare's "A  Midsummer Night's Dream".


Author's Notes

This game is my second Windows project. I programmed it because I like playing other small Windows board games (see Credits below), and also because no one ever wants to play Nine Men's Morris with me in real life.
I'm rather pleased with the playing strength of this version, but I realize that many aspects of the program could be improved, so stay tuned for the next version (= send money!).
I usually play the game with a Thinking Time of 10 seconds, with both Deep Thinking and Random Play turned on. If you are a beginner and want to boost your self-confidence, play with Deep Thinking off and Random Play on, plus set Thinking Time to one second
 Technical stuff: The game is built around an incrementing alpha-beta search inside a PeekMessage loop (to provide background thinking). Two methods are used two improve the search:
1) Moves that cause cutoffs are placed at the front of the move list (= the killer heuristic[Beal]).
2) Move lists (levels in the search tree) that are saved are sorted on the basis of how good they are one ply ahead.
The search tree is saved to a depth of 2 or more plies depending on the current fanout (number of legal moves). The "horizon effect" is almost eliminated by using the fairly standard technique of searching unstable positions an extra ply until a stable position is reached. Positions with only one legal move are also searched one more ply.
The biggest drawback of this program is the evaluation function. It is very stupid and greedy. If I make another version of N.M.M. for Windows the evaluation function will be the first thing to be improved.

Credits go to:
Chih-Hung Hseih, the author of WMake5, a very nice five-in-a-row shareware game for Windows.
The Author of Reversi for Windows v3.1. More options in the next version?
David N L Levy for being the editor of "Computer Games" I and II (Springer Verlag).
Anna, my girlfriend, for being wonderful in every way. She, by the way, credits Peter Siamidis, the author of Ms Chomp for Windows.
Gustaf von Blixen for the computer, and most of my other equipment. Thanks Dad!
Anyone who has a programming job for me or registers this software.
Ralph Gasser who has solved Nine Men's Morris! The game is a tie! Well done Mr. Gasser, but what am I going to do now? Well, don't be surprised if the next version of this game plays Hex, Action Lines or Yote.


Hints and Tips on Strategy

This is a collection of conclusions I have drawn from playing Nine Men's Morris for Windows:

Study how the computer plays on high levels.
Probably the best way to get better at this game. The most lessons to be learned from the computer are found somewhere at the end of phase one and the beginning of phase two.

Try to think far ahead in the beginning.
Because of the many legal moves in the beginning of a game, the computer can't search very deep.

Be careful before you put your opponent in phase three.
It is often easier to block all of his moves instead, at least if you have seven or more pieces left.

Don't close mills early!
I have seen this in almost every description of the game so far. At first I thought it wasn't true, but I have almost changed my mind. Closing a mill in the beginning (move 3 to 5?) may cause severe loss of mobility and initiative.
The computer doesn't realize this, and you can use that fact to take the game into a slow few-pieces-endgame where you will have the advantage! That is if you turn the Third Repetition Rule Used In Thinking option ON (see Menu Commands and Options).