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 board

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

    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

    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

    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

    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

    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.

Advertisements

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

  1. Pingback: Alpha Beta Search | Everything Under The Sun

  2. 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?

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

  3. 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?

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s