Advertisement
0draude

minimax reverse engeneering 01

Apr 13th, 2024
688
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.81 KB | None | 0 0
  1. // C++ program to find the next optimal move for
  2. // a player
  3. #include<bits/stdc++.h>
  4. using namespace std;
  5.  
  6. struct Move
  7. {
  8.     int row, col;
  9. };
  10.  
  11. char player = 'x', opponent = 'o';
  12.  
  13. // This function returns true if there are moves
  14. // remaining on the board. It returns false if
  15. // there are no moves left to play.
  16. bool isMovesLeft(char board[3][3])
  17. {
  18.     for (int i = 0; i<3; i++)
  19.         for (int j = 0; j<3; j++)
  20.             if (board[i][j]=='_')
  21.                 return true;
  22.     return false;
  23. }
  24.  
  25. // This is the evaluation function as discussed
  26. // in the previous article ( http://goo.gl/sJgv68 )
  27. int evaluate(char b[3][3])
  28. {
  29.     // Checking for Rows for X or O victory.
  30.     for (int row = 0; row<3; row++)
  31.     {
  32.         if (b[row][0]==b[row][1] &&
  33.             b[row][1]==b[row][2])
  34.         {
  35.             if (b[row][0]==player)
  36.                 return +10;
  37.             else if (b[row][0]==opponent)
  38.                 return -10;
  39.         }
  40.     }
  41.  
  42.     // Checking for Columns for X or O victory.
  43.     for (int col = 0; col<3; col++)
  44.     {
  45.         if (b[0][col]==b[1][col] &&
  46.             b[1][col]==b[2][col])
  47.         {
  48.             if (b[0][col]==player)
  49.                 return +10;
  50.  
  51.             else if (b[0][col]==opponent)
  52.                 return -10;
  53.         }
  54.     }
  55.  
  56.     // Checking for Diagonals for X or O victory.
  57.     if (b[0][0]==b[1][1] && b[1][1]==b[2][2])
  58.     {
  59.         if (b[0][0]==player)
  60.             return +10;
  61.         else if (b[0][0]==opponent)
  62.             return -10;
  63.     }
  64.  
  65.     if (b[0][2]==b[1][1] && b[1][1]==b[2][0])
  66.     {
  67.         if (b[0][2]==player)
  68.             return +10;
  69.         else if (b[0][2]==opponent)
  70.             return -10;
  71.     }
  72.  
  73.     // Else if none of them have won then return 0
  74.     return 0;
  75. }
  76.  
  77. // This is the minimax function. It considers all
  78. // the possible ways the game can go and returns
  79. // the value of the board
  80. int minimax(char board[3][3], int depth, bool isMax)
  81. {
  82.     int score = evaluate(board);
  83.  
  84.     // If Maximizer has won the game return his/her
  85.     // evaluated score
  86.     if (score == 10)
  87.         return score;
  88.  
  89.     // If Minimizer has won the game return his/her
  90.     // evaluated score
  91.     if (score == -10)
  92.         return score;
  93.  
  94.     // If there are no more moves and no winner then
  95.     // it is a tie
  96.     if (isMovesLeft(board)==false)
  97.         return 0;
  98.  
  99.     // If this maximizer's move
  100.     if (isMax)
  101.     {
  102.         int best = -1000;
  103.  
  104.         // Traverse all cells
  105.         for (int i = 0; i<3; i++)
  106.         {
  107.             for (int j = 0; j<3; j++)
  108.             {
  109.                 // Check if cell is empty
  110.                 if (board[i][j]=='_')
  111.                 {
  112.                     // Make the move
  113.                     board[i][j] = player;
  114.  
  115.                     // Call minimax recursively and choose
  116.                     // the maximum value
  117.                     best = max( best,
  118.                         minimax(board, depth+1, !isMax) );
  119.  
  120.                     // Undo the move
  121.                     board[i][j] = '_';
  122.                 }
  123.             }
  124.         }
  125.         return best;
  126.     }
  127.  
  128.     // If this minimizer's move
  129.     else
  130.     {
  131.         int best = 1000;
  132.  
  133.         // Traverse all cells
  134.         for (int i = 0; i<3; i++)
  135.         {
  136.             for (int j = 0; j<3; j++)
  137.             {
  138.                 // Check if cell is empty
  139.                 if (board[i][j]=='_')
  140.                 {
  141.                     // Make the move
  142.                     board[i][j] = opponent;
  143.  
  144.                     // Call minimax recursively and choose
  145.                     // the minimum value
  146.                     best = min(best,
  147.                         minimax(board, depth+1, !isMax));
  148.  
  149.                     // Undo the move
  150.                     board[i][j] = '_';
  151.                 }
  152.             }
  153.         }
  154.         return best;
  155.     }
  156. }
  157.  
  158. // This will return the best possible move for the player
  159. Move findBestMove(char board[3][3])
  160. {
  161.     int bestVal = -1000;
  162.     Move bestMove;
  163.     bestMove.row = -1;
  164.     bestMove.col = -1;
  165.  
  166.     // Traverse all cells, evaluate minimax function for
  167.     // all empty cells. And return the cell with optimal
  168.     // value.
  169.     for (int i = 0; i<3; i++)
  170.     {
  171.         for (int j = 0; j<3; j++)
  172.         {
  173.             // Check if cell is empty
  174.             if (board[i][j]=='_')
  175.             {
  176.                 // Make the move
  177.                 board[i][j] = player;
  178.  
  179.                 // compute evaluation function for this
  180.                 // move.
  181.                 int moveVal = minimax(board, 0, false);
  182.  
  183.                 // Undo the move
  184.                 board[i][j] = '_';
  185.  
  186.                 // If the value of the current move is
  187.                 // more than the best value, then update
  188.                 // best/
  189.                 if (moveVal > bestVal)
  190.                 {
  191.                     bestMove.row = i;
  192.                     bestMove.col = j;
  193.                     bestVal = moveVal;
  194.                 }
  195.             }
  196.         }
  197.     }
  198.  
  199.     printf("The value of the best Move is : %d\n\n",
  200.             bestVal);
  201.  
  202.     return bestMove;
  203. }
  204.  
  205. // Driver code
  206. int main()
  207. {
  208.     char board[3][3] =
  209.     {
  210.         { 'x', 'o', 'x' },
  211.         { 'o', 'o', 'x' },
  212.         { '_', '_', '_' }
  213.     };
  214.    
  215.     for(int i = 0; i < 3; i++){
  216.         for(int j = 0; j < 3; j++)
  217.             printf("%c  ", board[i][j]);
  218.         printf("\n");
  219.     }
  220.    
  221.     printf("***************************************\n");
  222.  
  223.     Move bestMove = findBestMove(board); /*what is the value of best move*/
  224.  
  225.     printf("The Optimal Move is :\n");
  226.     printf("ROW: %d COL: %d\n\n", bestMove.row,
  227.                                 bestMove.col );
  228.                                
  229.                                
  230.     board[bestmove.row][bestmove.col] = 'o';
  231.    
  232.     for(int i = 0; i < 3; i++){
  233.         for(int j = 0; j < 3; j++)
  234.             printf("%c  ", board[i][j]);
  235.         printf("\n");
  236.     }
  237.    
  238.     return 0;
  239. }
  240.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement