Nine Men’s Morris is a two-player strategy board game. The game has three clearly delimited phases:

**Phase 1: Placing pieces**- Players alternatively place their pieces on the board. If a player closes a morris (or mill), she will grab one of her opponent’s piece. Strategically placing the pieces is more important than closing a morris in this phase.
**Phase 2: Moving pieces**- Players alternatively move their pieces one at a time to an adjacent empty point, close morrises and grab pieces.
**Phase 3: Flying pieces**- A player reaches phase 3 when she is left with only 3 pieces. She can now move any of her piece to any empty point on the board.

A player wins by reducing her opponent to two pieces, or by leaving her without a legal move.

I wrote a bot for Nine Men’s Morris for a contest and here, I describe the evaluation functions I used for each of the three phases. The evaluation functions were linear functions of features of the game state. Following features were considered to calculate the evaluation functions:

**Closed Morris:**1 if a morris was closed in the last move by the player (and an opponent’s piece should be grabbed in this move), -1 if a morris was closed by the opponent in the last move, 0 otherwise**Number of Morrises:**Difference between the number of yours and yours opponent’s morrises**Number of blocked opponent pieces:**Difference between the number of yours opponent’s and yours blocked pieces (pieces which don’t have an empty adjacent point)**Number of pieces:**Difference between the number of yours and yours opponent’s pieces**Number of 2 piece configurations:**Difference between the number of yours and yours opponent’s 2 piece configurations (A 2-piece configuration is one to which adding one more piece would close a morris)**Number of 3-piece configurations:**Difference between the number of yours and yours opponent’s 3 piece configurations (A 3-piece configuration is one to which a piece can be added in which one of two ways to close a morris)**Double morris:**Difference between number of yours and yours opponent’s double morrises (A double morris is one in which two morrises share a common piece)**Winning configuration:**1 if the state is winning for the player, -1 if losing, 0 otherwise

For the particular contest settings (elimination with the player having more pieces winning if neither side could force a win so there was a strong aversion to sacrificing material) and bot settings (depth limited to 8 and branching factor limited to 20; at each step, top 20 moves sorted by the evaluation function were selected), I found the following feature combinations to work well (‘(1)’ represents the first feature: Closed Morris and so on):

The evaluation functions were motivated by this paper.

You can play a game of Nine Men’s Morris online here or download it from android app store.

Pingback: Alpha Beta Search | Everything Under The Sun

Hello Kartik. Thanks for the post.

I think a double morris should be two morrises that share the same piece so every time you move that piece you make a morris, do you undestand? Am I wrong?

No, you are right. That’s exactly what the post says: “A double morris is one in which two morrises share a common piece”.

But there is one more condition: every time you move the shared piece you make a morris, like in first image here, every time you move the e3 to d3 and back you make a morris. This more than just share a piece.

Hello, Kartik. Thank you for the post, it’s very useful.

Am I right, that when you count number of “two pieces configurations” you DO NOT count number of “three pieces configuration”? I mean, “three pieces configuration” is two “two pieces configuration”. So, am i right?

As I implemented it, a 3-piece configuration contributed two 2-piece configurations. Double counting shouldn’t be a problem because the evaluation function is a linear feature combination. That just means more weight for 3-piece configurations.

Thank you very much! Now I’ve got it out.

Did you use Alpha Beta Pruning for the search? Or how did you do it?

Yes, it used alpha beta search.

Did you use hashing for finding visited nodes to improve the pruning? and have you got an idea for a hashfunction?

I encoded states in a bitwise representation (24 bits for piece present or not for each side), which is readily hashable.

Kay had the same idea, positive aspect: you can store in a 64 bit system the numbers of stones you can set, so that you can create a hash value for every phase of the game. do you think that this is usefull? example: aaaa aaaa aaaa aaaa aaaa aaaa bbbb bbbb bbbb bbbb bbbb bbbb cccc dddd, where a ist either 0 or 1 for pieces set of player a, b is either 0 or 1 for pieces set of player b,c for a bitwise number of stones to set for player a, and d the same for player b. [you need 4 bits for numbers 0 to 9 for each player] so there is no need for zobrist hashing, isnt it?

I don’t know what zobritst hashing is. But a state of this game is pretty simple. There are just 27 places to put pieces on. All pieces of a player are identical so we just care about piece presence or not. We need 27×2=54 bits which fits in a 64 bit integer.