// 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; 
} 

returns:

The value of the best Move is : 10
 
The Optimal Move is :
ROW: 2 COL: 2