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.