Differences

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

--- chess:programming:minimax_algorithm:a_program_to_illustrate_the_minimax_algorithm2 [2021/10/30 22:24] – created peter
+++ chess:programming:minimax_algorithm:a_program_to_illustrate_the_minimax_algorithm2 [2021/10/30 22:28] (current) – removed peter
@@ Line 1: / Line 1: @@
-====== Chess - Programming - Minimax Algorithm - A program to illustrate the Minimax Algorithm2 ======
-<code cpp>
-// Program to find the next optimal move for a player.
-#include<bits/stdc++.h>
-using namespace std;
-struct Move
-{
-  int row, col;
-};
-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;
-}
-// 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)
-  {
-    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] = 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.
-  else
-  {
-    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;
-  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] =
-  {
-    { 'x', 'o', 'x' },
-    { 'o', 'o', 'x' },
-    { '_', '_', '_' }
-  };
-  Move bestMove = findBestMove(board);
-  printf("The Optimal Move is :");
-  printf("ROW: %d COL: %d", bestMove.row, bestMove.col );
-  return 0;
-}
-</code>
-returns:
-<code cpp>
-The value of the best Move is : 10
-The Optimal Move is :
-ROW: 2 COL: 2
-</code>