Heuristic/Evaluation Function for Nine Men’s Morris

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.

Nine Men’s Morris

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:

1. 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

Closed Morris

2. Number of Morrises: Difference between the number of yours and yours opponent’s morrises
3. 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)

Blocked piece

4. Number of pieces: Difference between the number of yours and yours opponent’s pieces
5. 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)

2-piece configuration

6. 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)

3-piece configuration

7. 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)

Double Morris

8. 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.

13 thoughts on “Heuristic/Evaluation Function for Nine Men’s Morris”

1. 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.

2. Sergey says:

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.

• Sergey says:

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

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

• 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.