Algorithms – AI in Nine Men’s Morris Game

Let’s see how Artificial Intelligence form the core of the Nine Men’s Morris Game.

There are different variants of this game, each with a slightly different set of rules. Here, I will be talking about one such variant whose game board looks like the one below. Morris1

Rules of the Game

The game is played between two players who take turns to place each of their nine pieces on the point of intersection of lines on the board. The above board has 23 such intersections. A player who forms a mill (three pieces on a straight line) with his pieces is allowed to remove any one of the opponent’s pieces from the board. A player wins the game if he reduces the opponent to only 2 pieces or block the opponent from any further moves. The game has three phases.

Opening Phase – In this phase, the two players alternately place their nine pieces on the board.
Mid-game Phase – Phases 2 starts once both the players have finished placing all their pieces on the board. In this phase, each player moves his pieces along the lines on the board.
Ending Phase – The last phase starts when one of the players has only three pieces remaining on the board.

Mills: – During any phase, if a player gets three of his pieces on a single straight line on the board, then one of the opponent’s isolated pieces is removed from the board. An isolated piece is a piece that is not a part of a mill.

Game State Representation

There are multiple ways to represent a game state. The easiest way is to represent it as an array of size 23 with each index corresponding to a location on the game board. The array would look like this.

morris2

Game state can also be represented as a bit-board with each bit representing a location on the game board. A 32- bit integer should be sufficient in this case. We can maintain two integers, one for each player. A bit value of 1 represents a played move (at the board location corresponding to the bit’s location in the integer). Bit-board representation offers improvement over the array representation in terms of the memory usage. But its implementation can turn out to be fairly complicated as you will need to be familiar with the bit manipulation. To give you a flavor of how it works,

If integer A represents the bit-board of Player 1 and integer B represents the bit-board of Player 2, ~(A | B) gives you the free locations on the board.
Left shift operator can be used to check if a bit is set. (A & 1<<x) checks if the bit at location x in A is set to 1.

For the purpose of this article, let’s go with the array based representation and proceed further.

Search Algorithm

The core idea behind Morris game is very similar to the one behind tictactoe game. I strongly recommend you go through my article (here) before proceeding any further. Just like the tictactoe game, Morris game can also be framed into a typical search problem involving game trees with each node representing a game state (or game position) and each edge representing a move made by a player.

But unlike tictactoe, the game tree for Morris is very large. So if we try to dynamically evaluate game states by going all the way down to the leaf nodes, it will take us an insane amount of time, if at all our computer can process it. Therefore, we should go down only a few levels. To further improve performance, we can use a slightly modified version of the recursive minimax algorithm called recursive minimax with alpha-beta pruning. It offers drastic improvement over the regular version in terms of the number of states (nodes in the tree) evaluated.

Intuition Behind Alpha-Beta Pruning Algorithm – Alpha- Beta pruning algorithm is based on the idea that, in order to determine the static estimate associated with any node, we do not need to go down all the paths starting from that node. We can prune away sub-trees that are not going to influence the value of the static estimate.

In alpha beta pruning, we associate two variables alpha and beta with every tree node that is being evaluated. Alpha denotes the lower bound and beta denotes the upper bound for the static estimate. Initially, alpha is negative infinity and beta is positive infinity.

alphabeta

Consider the tree above, once we have estimated the static estimate for N5 (= 6), we know for sure that its parent N2, being a minimizer node will have a static estimate of at most 6. Further, once we have seen that the static estimate of node N11 is 8, there is no point exploring any of the other children of N6. Those children could only increase the value of N6, but we know that N6’s parent N2 can have a value of at most 6. So we avoid searching such nodes or in other words, we prune away a part of the tree.

Implementation Details – Following are the important functions you will need to use in the program.

miniMaxOpeningPhase(vector board, int flag, int depth, int alpha, int beta) – The inputs to this function are,

vector board – Current Game state (aka game position).
int flag – ‘1’ denotes maximizer, ‘0’ denotes minimizer.
int depth – Number of further levels to examine.
int alpha – Lower bound of static estimate.
int beta – Upper bound of static estimate.

Determines the next best move in the opening phase. Recursively traverse the tree up to the specified depth, calls evaluate() for the board positions at that depth and returns the one with the best static estimate.

/*
struct Node {
 int miniMaxEstimate;
 vector  board;
 Node(int x, vector  board) : miniMaxEstimate(x), board(board) {}};
 */

Node* miniMaxOpeningPhase(vector  board, int flag, int depth, int alpha, int beta) {
 if (depth == 0)
  return new Node(evaluateOpeningPhase(board), board);
 // minimizer
 if (flag == 0) {
  int ret = 100000;
  Node* temp;
  vector  bestBoard = board;
  for (int i = 0; i = beta)
        return new Node(ret, board);
       alpha = max(alpha, ret);
       board[i] = "B";}}}
    else {
     temp = miniMaxOpeningPhase(board, 0, depth - 1, alpha, beta);
     if (temp->miniMaxEstimate > ret) {
      bestBoard = board;
      ret = temp->miniMaxEstimate;}
     if (ret >= beta)
      return new Node(ret, board);
     alpha = max(alpha, ret);}
    board[i] = "x";}}
  return new Node(ret, bestBoard);}}

neighbors(int location) – This function takes a location as the input and returns a list of its neighbors with which it could form a closed mill.

vector  neighbours(int i) {
 switch (i) {
 case 0:
  return { 1,3,8 };
 case 1:
  return { 0,2,4 };
 case 2:
  return { 1,5,13 };
 case 3:
  return { 0,4,6,9 };
 case 4:
  return { 1,3,5 };
 case 5:
  return { 2,4,7,12 };
 case 6:
  return { 3,7,10 };
 case 7:
  return { 5,6,11 };
 case 8:
  return { 0,9,20 };
 case 9:
  return { 3,8,10,17 };
 case 10:
  return { 6,9,14 };
 case 11:
  return { 7,12,16 };
 case 12:
  return { 5,11,13,19 };
 case 13:
  return { 2,12,22 };
 case 14:
  return { 10,15,17 };
 case 15:
  return { 14,16,18 };
 case 16:
  return { 11,15,19 };
 case 17:
  return { 9,14,18,20 };
 case 18:
  return { 15,17,19,21 };
 case 19:
  return { 12,16,18,22 };
 case 20:
  return { 8,17,21 };
 case 21:
  return { 18,20,22 };
 case 22:
  return { 13,19,21 };
 default:
  return {};}}

miniMaxMidEndPhase(vector board, int flag, int depth, int alpha, int beta) – The inputs to this function are,

vector board – Current Game state (aka game position).
int flag – ‘1’ denotes maximizer, ‘0’ denotes minimizer.
int depth – Number of further levels to examine.
int alpha – Lower bound of static estimate.
int beta – Upper bound of static estimate.

Determines the next best move in the mid game/ end game phases. Recursively traverse the tree up to the specified depth, calls evaluate() for all the board positions that it encounters and returns the one with the best static estimate.

/*
struct Node {
 int miniMaxEstimate;
 vector  board;
 Node(int x, vector  board) : miniMaxEstimate(x), board(board) {}};
*/

Node* miniMaxMidEndPhase(vector  board, int flag, int depth, int alpha, int beta) {
 int temp = evaluateMidEndPhase(board);
 if (depth == 0)
  return new Node(temp, board);
 else if (temp == 10000)
  return new Node(10000, board);
 else if (temp == -10000)
  return new Node(-10000, board);
 else {
  // minimizer
  if (flag == 0) {
   int ret = 100000, bCount = 0;
   Node * temp;
   vector  bestBoard = board;
   vector  nb;
   for (int i = 0; i  3) {
    for (int i = 0; i < board.size(); i++) {
     if (board[i] == "B") {
      nb = neighbours(i);
      for (int tp : nb) {
       if (board[tp] == "x") {
        board[tp] = "B";
        board[i] = "x";
        if (closeMill(board, tp)) {
         for (int j = 0; j miniMaxEstimate miniMaxEstimate;}
           if (ret miniMaxEstimate miniMaxEstimate;}
         if (ret <= alpha)
          return new Node(ret, board);
         beta = min(beta, ret);}
        board[tp] = "x";
        board[i] = "B";}}}}}
   else if (bCount == 3) {
    for (int i = 0; i < board.size(); i++) {
     if (board[i] == "B") {
      for (int tp = 0; tp = beta)
            return new Node(ret, board);
           alpha = max(alpha, ret);
           board[j] = "B";}}}
        else {
         temp = miniMaxMidEndPhase(board, 0, depth - 1, alpha, beta);
         if (temp->miniMaxEstimate > ret) {
          bestBoard = board;
          ret = temp->miniMaxEstimate;}
         if (ret >= beta)
          return new Node(ret, board);
         alpha = max(alpha, ret);}
        board[tp] = "x";
        board[i] = "W";}}}}}
   else if (wCount == 3) {
    for (int i = 0; i miniMaxEstimate;}
           if (ret >= beta)
            return new Node(ret, board);
           alpha = max(alpha, ret);
           board[j] = "B";}}}
        else {
         temp = miniMaxMidEndPhase(board, 0, depth - 1, alpha, beta);
         if (temp->miniMaxEstimate > ret) {
          bestBoard = board;
          ret = temp->miniMaxEstimate;}
         if (ret >= beta)
          return new Node(ret, board);
         alpha = max(alpha, ret);}
        board[tp] = "x";
        board[i] = "W";}}}}}
   return new Node(ret, bestBoard);}}}

closeMill(vector board, int location) – This function takes a game state (aka game position) and a location as inputs. Returns true if the location forms a close mill with any of its neighbors. False otherwise.

bool closeMill(vector  board, int pos) {
 switch (pos) {
 case 0: {
  if ((board[1] == board[0] && board[2] == board[0]) || (board[3] == board[0] && 
  board[6] == board[0]) || (board[8] == board[0] && board[20] == board[0])) 
  return true;
  else return false; }
 case 1: {
  if ((board[0] == board[1] && board[2] == board[1])) return true;
  else return false; }
 case 2: {
  if ((board[0] == board[2] && board[1] == board[2]) || (board[5] == board[2] && 
  board[7] == board[2]) || (board[13] == board[2] && board[22] == board[2])) 
  return true;
  else return false; }
 case 3: {
  if ((board[0] == board[3] && board[6] == board[3]) || (board[4] == board[3] && 
  board[5] == board[3]) || (board[9] == board[3] && board[17] == board[3])) 
  return true;
  else return false; }
 case 4: {
  if ((board[3] == board[4] && board[5] == board[4])) return true;
  else return false; }
 case 5: {
  if ((board[2] == board[5] && board[7] == board[5]) || (board[3] == board[5] && 
  board[4] == board[5]) || (board[12] == board[5] && board[19] == board[5])) 
  return true;
  else return false; }
 case 6: {
  if ((board[0] == board[6] && board[3] == board[6]) || (board[10] == board[6] 
  && board[14] == board[6])) return true;
  else return false; }
 case 7: {
  if ((board[2] == board[7] && board[5] == board[7]) || (board[11] == board[7] 
  && board[16] == board[7])) return true;
  else return false; }
 case 8: {
  if ((board[0] == board[8] && board[20] == board[8]) || (board[9] == board[8] 
  && board[10] == board[8])) return true;
  else return false; }
 case 9: {
  if ((board[8] == board[9] && board[10] == board[9]) || (board[3] == board[9] 
  && board[17] == board[9])) return true;
  else return false; }
 case 10: {
  if ((board[8] == board[10] && board[9] == board[10]) || (board[6] == board[10] 
  && board[14] == board[10])) return true;
  else return false; }
 case 11: {
  if ((board[7] == board[11] && board[16] == board[11]) || (board[12] == 
  board[11] && board[13] == board[11])) return true;
  else return false; }
 case 12: {
  if ((board[11] == board[12] && board[13] == board[12]) || (board[5] == 
  board[12] && board[19] == board[12])) return true;
  else return false; }
 case 13: {
  if ((board[11] == board[13] && board[12] == board[13]) || (board[2] == 
  board[13] && board[22] == board[13])) return true;
  else return false; }
 case 14: {
  if ((board[6] == board[14] && board[10] == board[14]) || (board[15] == 
  board[14] && board[16] == board[14]) || (board[17] == board[14] && board[20] 
  == board[14])) return true;
  else return false; }
 case 15: {
  if ((board[14] == board[15] && board[16] == board[15]) || (board[18] == 
  board[15] && board[21] == board[15])) return true;
  else return false; }
 case 16: {
  if ((board[14] == board[16] && board[15] == board[16]) || (board[19] == 
  board[16] && board[22] == board[16]) || (board[7] == board[16] && board[11] == 
  board[16])) return true;
  else return false; }
 case 17: {
  if ((board[3] == board[17] && board[9] == board[17]) || (board[18] == 
  board[17] && board[19] == board[17]) || (board[14] == board[17] && board[20] 
  == board[17])) return true;
  else return false; }
 case 18: {
  if ((board[15] == board[18] && board[21] == board[18]) || (board[17] == 
  board[18] && board[19] == board[18])) return true;
  else return false; }
 case 19: {
  if ((board[17] == board[19] && board[18] == board[19]) || (board[5] == 
  board[19] && board[12] == board[19]) || (board[16] == board[19] && board[22] 
  == board[19])) return true;
  else return false; }
 case 20: {
  if ((board[0] == board[20] && board[8] == board[20]) || (board[21] == 
  board[20] && board[22] == board[20]) || (board[14] == board[20] && board[17] 
  == board[20])) return true;
  else return false; }
 case 21: {
  if ((board[20] == board[21] && board[22] == board[21]) || (board[15] == 
  board[21] && board[18] == board[21])) return true;
  else return false; }
 case 22: {
  if ((board[20] == board[22] && board[21] == board[22]) || (board[16] == 
  board[22] && board[19] == board[22]) || (board[2] == board[22] && board[13] == 
  board[22])) return true;
  else return false; }
 default:
  return false;}}

evaluateOpeningPhase(vector board) – This function takes a game state (aka game position) as the input and returns a static estimate for it in the opening Phase.

int evaluateOpeningPhase(vector  board) {
 totalEvaluated++;
 int whitePieces = 0, blackPieces = 0;
 for (int i = 0; i < board.size(); i++) {
  if (board[i] == "W")
   whitePieces++;
  else if (board[i] == "B")
   blackPieces++;}
 return (whitePieces - blackPieces);}

evaluateMidEndPhase(vector board) – This function takes a game state (aka game position) as the input and returns a static estimate for it in the mid-Game and End-Game Phase.

int evaluateMidEndPhase(vector  board) {
 totalEvaluated++;
 int white = 0, black = 0;
 for (int i = 0; i < board.size(); i++) {
  if (board[i] == "W")
   white++;
  else if (board[i] == "B")
   black++;}
 if (black <= 2)
  return 10000;
 else if (white <= 2)
  return -10000;
 int numBlackMoves = 0;
 vector  nb;
 int bCount = 0;
 for (int i = 0; i  3) {
  for (int i = 0; i < board.size(); i++) {
   if (board[i] == "B") {
    nb = neighbours(i);
    for (int tp : nb) {
     if (board[tp] == "x") {
      board[tp] = "B";
      board[i] = "x";
      if (closeMill(board, tp)) {
       for (int j = 0; j < board.size(); j++) {
        if (board[j] == "W" && !closeMill(board, j))
         numBlackMoves++;}}
      else
       numBlackMoves++;
      board[tp] = "x";
      board[i] = "B";}}}}}
 else if (bCount == 3) {
  for (int i = 0; i < board.size(); i++) {
   if (board[i] == "B") {
    for (int tp = 0; tp < board.size(); tp++) {
     if (board[tp] == "x") {
      board[tp] = "B";
      board[i] = "x";
      if (closeMill(board, tp)) {
       for (int j = 0; j < board.size(); j++) {
        if (board[j] == "W" && !closeMill(board, j))
         numBlackMoves++;}}
      else
       numBlackMoves++;
      board[tp] = "x";
      board[i] = "B";}}}}}
 if (numBlackMoves == 0)
  return 10000;
 else
  return (1000 * (white - black)) - numBlackMoves;}

Evaluation Function

As we don’t go all the way down to the leaf nodes,the quality of the evaluation function plays a crucial role in determining the next best move. The better our evaluation function, the more chances of getting an accurate static estimate of the board states. There are a number of estimators that we can string together with appropriate coefficients(weights) to form a good evaluation function. Some of such estimators that we can use for a given game state (aka game position) are,

Potential Close Mills – Number of pairs of pieces on a single line that can form a close mill by the addition of one more piece to the line.
Number of blocked opponent’s pieces – Number of pieces of the opponent that are blocked.
White Pieces – Number of white pieces.
Black Pieces – Number of black pieces.
Double Close Mill – When you can move a piece from one close mill and form another close mill, you have a double close mill.
Opponent Moves – Number of states that can be generated from the current state by a an opponent move.

You can always come up with better estimators than the ones listed above. There is no standard way to combine them to create an evaluation function. You could try out different combinations with varying weights and pick the best out of them. Below are example evaluation functions that could be used.

Evaluation Functions for Opening Phase (assuming we play white pieces)

return (White Pieces- Black Pieces)

Evaluation Functions for Mid-Game/Ending phases (assuming we play white pieces)

if (Black Pieces less than or equal to 2) return(10000)
else if (White Pieces less than or equal to 2) return(-10000)
else if (Black Moves is 0) return(10000)
else return ( 1000*(White Pieces – Black Pieces) – Black Moves)
Here, Black Moves is same as Opponent Moves

One thought on “Algorithms – AI in Nine Men’s Morris Game”

Add yours

shilkaren says:

November 2, 2020 at 6:54 am

Hi
It’s a great article.
It’s very interesting to read more about how AI can be used in the industry.
You would love to see my artificial intelligence course in delhi site as well.
Thanks once again.

LikeLike

Sharing is Caring

One thought on “Algorithms – AI in Nine Men’s Morris Game”

Add yours

Leave a comment Cancel reply