Project #3 The Nine Men's Morris Tournament


(Rules courtesy of Cliff Hamer)
Nine Mens' Morris is known by many names, including Merrills and Mühle.
There may be other variations on the rules, but according to Cliff Hamer's
information, these are the rules used by the World Merrills Association
for the World Championships and by the Welt-Mühlespiel-Dachverband for
the European Championships. (More information can be found at Cliff Hamer's
Merrills Page.)

Rules of Nine Mens' Morris (NMM)


Nine Mens' Morris is a game for two people, played on a special board
with nine pieces, pegs or counters each.
The board has three 'concentric' squares linked at the mid points of
their sides. This provides 24 intersecting points arranged in 16 lines
of three.

     A   B   C   D   E   F   G

 

 1   +-----------+-----------+

     |           |           |

 2   |   +-------+-------+   |

     |   |       |       |   |

 3   |   |   +---+---+   |   |

     |   |   |       |   |   |

 4   +---+---+       +---+---+

     |   |   |       |   |   |

 5   |   |   +---+---+   |   |

     |   |       |       |   |

 6   |   +-------+-------+   |

     |           |           |

7                 +-----------+-----------+

 

 



Play is divided into three stages, but the object throughout the game
is to get three pieces in a line - called a mill. On forming a mill,
one of the opponent's pieces is removed from the board and the game
is won by the player who reduces an opponent's remaining pieces to two.

The opening stage begins with an empty board. Each player has nine
pieces which are placed one at a time in turn on any vacant point on
the board until both have played all nine. If a mill - a line of three -
is made, the player making it removes any one of the opponent's pieces
that is not itself part of a mill. Throughout the game, pieces forming
a mill are therefore safe from capture.

Once a piece is removed from the board it takes no further part in the
game. It is important to note that mills can only be made along the
horizontal and vertical lines on the board, never across the diagonals
where no lines are marked.

The middle stage starts when all the pieces have been used. Play
continues alternately with the opponents moving one piece to any
adjacent point. A couple of tactics are often used in this stage.

Firstly, once a mill is formed it may be opened by moving one piece
from the line and closed by returning it to its original position in
the next move. Alternatively, in a running mill opening one mill will
close another one so that an opponent's piece is removed on every turn.

A player who is blocked, i.e. is unable to move any piece, loses the
game, this is the way that many games are won.

The end stage allows a player with only three pieces to jump, i.e.
to move one piece to any empty point on the board regardless of
position. The other player must continue to move normally unless
both are reduced to three pieces. The game ends when one player is
reduced to two pieces and so can no longer form a mill.

Move Notation
When placing a piece on the board at the beginning of the game,
simply give the coordinates where the piece should be placed. e.g. D2
When moving a piece, give the source and destination coorindates. e.g. D2-F2

When you form a mill and capture a piece, give the coordinate of the
piece you want to capture at the end of the move. e.g. D3,G1 (drop and
capture) or A7-D7,B2 (move and capture)


 Your task:

 Implement the Alpha-beta Game playing algorithm (and associated
 static evaluator functions) and prepare your program for battle.


 A random pair-off tournament will be conducted by the TA's to determine
 the best program. Those that loose the first round are simply graded
 as any other ordinary project.

 Those that proceed to a second round (winners of the first round,
 a 50% chance)are awarded +5 valuable extra points on the base grade.
 Each successive winning round produces yet another +5 valuable extra points
 on the grade.

 Now, at certain rounds there will be an odd outlier who is not able
 to compete.  That program will pair off against one of the randomly
 chosen winners of that round! So if you are really lucky, and if your
 program wins twice in one round, you can earn a cool +10 points! However,
 if you are chosen to compete twice in a round and if you loose, you
 don't proceed on to the next round (but you do keep  your points).

 Good luck to your programs.

 Oh yes, to be fair, a time limit will be imposed by the TA's when
 playing. We want to be fair, but make sure the
 tournament ends within a couple of days! and not next semester....... :)
 And, if you don't produce a program on time by the due date, well, you
 can't win unless you enter!

 Don't forget to NOT BE MYOPIC. Your program might have to take on the
 role of black and white at different rounds of the tournament. So don't
 write your program with only a single player in mind.

 You may argue that it would be "faster" to simply exchange the boards
 among programs when playing. That is generally the case (increased
 I/O notwithstanding), except that checking moves for legality might be
 easier exchanging individual moves  than checking your opponent
 cheated and made several moves! which would require analyzing the board. :)