# minimax reverse engeneering 01

Apr 13th, 2024
688
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
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.