Differences

This shows you the differences between two versions of the page.

--- chess:programming:minimax_algorithm:a_program_to_illustrate_the_minimax_algorithm [2021/10/30 22:08] – created peter
+++ chess:programming:minimax_algorithm:a_program_to_illustrate_the_minimax_algorithm [2021/10/30 22:30] (current) – peter
@@ Line 3: / Line 3: @@
 <code cpp>
-// Program to find the next optimal move for a player.
+// A simple C++ program to find maximum score that maximizing player can get.
 #include<bits/stdc++.h>
 using namespace std;
-struct Move
+// Returns the optimal value a maximizer can obtain.
+//
+// depth is current depth in game tree.
+// nodeIndex is index of current node in scores[].
+// isMax is true if current move is of maximizer, else false.
+// scores[] stores leaves of Game tree.
+// h is maximum height of Game tree.
+int minimax(int depth, int nodeIndex, bool isMax, int scores[], int h)
 {
-  int row, col;
+  // Terminating condition. i.e leaf node is reached.
-};
+  if (depth == h)
+    return scores[nodeIndex];
-char player = 'x';
-char opponent = 'o';
-// This function returns true if there are moves remaining on the board.
-// It returns false if there are no moves left to play.
-bool isMovesLeft(char board[3][3])
-{
-  for (int i = 0; i<3; i++)
-    for (int j = 0; j<3; j++)
-      if (board[i][j]=='_')
-       return true;
-  return false;
-}
-// This is the evaluation function.
-int evaluate(char b[3][3])
-{
-  // Checking for Rows for X or O victory.
-  for (int row = 0; row<3; row++)
-  {
-    if (b[row][0]==b[row][1] &&
-        b[row][1]==b[row][2])
-    {
-      if (b[row][0]==player)
-        return +10;
-      else
-      if (b[row][0]==opponent)
-        return -10;
-    }
-  }
-  // Checking for Columns for X or O victory.
-  for (int col = 0; col<3; col++)
-  {
-    if (b[0][col]==b[1][col] &&
-        b[1][col]==b[2][col])
-    {
-      if (b[0][col]==player)
-        return +10;
-      else
-      if (b[0][col]==opponent)
-        return -10;
-    }
-  }
-  // Checking for Diagonals for X or O victory.
-  if (b[0][0]==b[1][1] && b[1][1]==b[2][2])
-  {
-    if (b[0][0]==player)
-      return +10;
-    else
-    if (b[0][0]==opponent)
-      return -10;
-  }
-  if (b[0][2]==b[1][1] && b[1][1]==b[2][0])
-  {
-    if (b[0][2]==player)
-      return +10;
-    else
-    if (b[0][2]==opponent)
-      return -10;
-  }
-  // Else if none of them have won then return 0.
-  return 0;
-}
+  //  If current move is maximizer, find the maximum attainable value.
-// This is the minimax function.
-// It considers all the possible ways the game can go and returns the value of the board .
-int minimax(char board[3][3], int depth, bool isMax)
-{
-  int score = evaluate(board);
-  // If Maximizer has won the game return his/her evaluated score.
-  if (score == 10)
-    return score;
-  // If Minimizer has won the game return his/her evaluated score.
-  if (score == -10)
-    return score;
-  // If there are no more moves and no winner then it is a tie.
-  if (isMovesLeft(board)==false)
-    return 0;
-  // If this is maximizers move.
   if (isMax)
-  {
+    return max(minimax(depth+1, nodeIndex*2, false, scores, h),
-    int best = -1000;
+           minimax(depth+1, nodeIndex*2 + 1, false, scores, h));
-    // Traverse all cells.
+  // Else (If current move is Minimizer), find the minimum attainable value.
-    for (int i=0; i<3; i++)
+  else
-    {
+    return min(minimax(depth+1, nodeIndex*2, true, scores, h),
-      for (int j=0; j<3; j++)
+           minimax(depth+1, nodeIndex*2 + 1, true, scores, h));
-      {
+}
-        // Check if cell is empty.
-        if (board[i][j]=='_')
-        {
-          // Make the move.
-          board[i][j] = player;
-          // Call minimax recursively and choose the maximum value.
-          best = max( best, minimax(board, depth+1, !isMax) );
-          // Undo the move.
-          board[i][j] = '_';
-        }
-      }
-    }
-    return best;
-  }
-  // If this minimizers move.
+// A utility function to find Log n in base 2.
-  else
+int log2(int n)
-  {
-    int best = 1000;
-    // Traverse all cells.
-    for (int i=0; i<3; i++)
-    {
-      for (int j=0; j<3; j++)
-      {
-        // Check if cell is empty.
-        if (board[i][j]=='_')
-        {
-          // Make the move.
-          board[i][j] = opponent;
-          // Call minimax recursively and choose the minimum value.
-          best = min(best, minimax(board, depth+1, !isMax));
-          // Undo the move.
-          board[i][j] = '_';
-        }
-      }
-    }
-    return best;
-  }
-}
-// This will return the best possible move for the player.
-Move findBestMove(char board[3][3])
 {
-  int bestVal = -1000;
+  return (n==1)? 0 : 1 + log2(n/2);
-  Move bestMove;
-  bestMove.row = -1;
-  bestMove.col = -1;
-  // Traverse all cells, evaluate minimax function for all empty cells.
-  // And return the cell with optimal value.
-  for (int i=0; i<3; i++)
-  {
-    for (int j=0; j<3; j++)
-    {
-      // Check if cell is empty.
-      if (board[i][j]=='_')
-      {
-        // Make the move.
-        board[i][j] = player;
-        // Compute evaluation function for this move.
-        int moveVal = minimax(board, 0, false);
-        // Undo the move.
-        board[i][j] = '_';
-        // If the value of the current move is more than the best value, then update best.
-        if (moveVal > bestVal)
-        {
-          bestMove.row = i;
-          bestMove.col = j;
-          bestVal = moveVal;
-        }
-      }
-    }
-  }
-  printf("The value of the best Move is : %d", bestVal);
-  return bestMove;
 }
 // Driver code.
 int main()
 {
-  char board[3][3] =
+  // The number of elements in scores must be a power of 2.
-  {
+  int scores[] = {3, 5, 2, 9, 12, 5, 23, 23};
-    { 'x', 'o', 'x' },
+  int n = sizeof(scores)/sizeof(scores[0]);
-    { 'o', 'o', 'x' },
+  int h = log2(n);
-    { '_', '_', '_' }
+  int res = minimax(0, 0, true, scores, h);
-  };
+  std::cout << "The optimal value is : " << res << std::endl;
-  Move bestMove = findBestMove(board);
-  printf("The Optimal Move is :");
-  printf("ROW: %d COL: %d", bestMove.row, bestMove.col );
   return 0;
 }
@@ Line 224: / Line 55: @@
 <code cpp>
-The value of the best Move is : 10
+The optimal value is:  12
-The Optimal Move is :
-ROW: 2 COL: 2
 </code>
+----
+===== References =====
+https://tutorialspoint.dev/algorithm/game-theory/minimax-algorithm-in-game-theory-set-1-introduction