8000 Merge pull request #1350 from aniketsingh98571/patch-2 · FoxMD/Algorithms@cea3f8e · GitHub
[go: up one dir, main page]
Skip to content

Commit cea3f8e

Browse files
i-vishii-vishi
authored
Merge pull request VAR-solutions#1350 from aniketsingh98571/patch-2
Modified Tic-tac-toe.cpp
2 parents 96e6573 + 41c2bfd commit cea3f8e

File tree

1 file changed

+161
-0
lines changed

1 file changed

+161
-0
lines changed

‎Combinatorial Game Theory/Tic-Tac-Toe Optimal Move/Cpp/Tic-Tac-Toe.cpp

Lines changed: 161 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,161 @@
1+
// C++ program to find the next optimal move for a player
2+
#include <bits/stdc++.h>
3+
using namespace std;
4+
5+
struct Move
6+
{
7+
int row, col;
8+
};
9+
10+
char player = 'x', opponent = 'o';
11+
12+
bool isMovesLeft(char board[3][3])
13+
{
14+
for (int i = 0; i < 3; i++)
15+
for (int j = 0; j < 3; j++)
16+
if (board[i][j] == '_')
17+
return true;
18+
return false;
19+
}
20+
21+
int evaluate(char b[3][3])
22+
{
23+
for (int row = 0; row < 3; row++)
24+
{
25+
if (b[row][0] == b[row][1] &&
26+
b[row][1] == b[row][2])
27+
{
28+
if (b[row][0] == player)
29+
return +10;
30+
else if (b[row][0] == opponent)
31+
return -10;
32+
}
33+
}
34+
35+
for (int col = 0; col < 3; col++)
36+
{
37+
if (b[0][col] == b[1][col] &&
38+
b[1][col] == b[2][col])
39+
{
40+
if (b[0][col] == player)
41+
return +10;
42+
43+
else if (b[0][col] == opponent)
44+
return -10;
45+
}
46+
}
47+
48+
if (b[0][0] == b[1][1] && 8000 ; b[1][1] == b[2][2])
49+
{
50+
if (b[0][0] == player)
51+
return +10;
52+
else if (b[0][0] == opponent)
53+
return -10;
54+
}
55+
56+
if (b[0][2] == b[1][1] && b[1][1] == b[2][0])
57+
{
58+
if (b[0][2] == player)
59+
return +10;
60+
else if (b[0][2] == opponent)
61+
return -10;
62+
}
63+
return 0;
64+
}
65+
66+
int minimax(char board[3][3], int depth, bool isMax)
67+
{
68+
int score = evaluate(board);
69+
70+
if (score == 10)
71+
return score;
72+
73+
if (score == -10)
74+
return score;
75+
76+
if (isMovesLeft(board) == false)
77+
return 0;
78+
79+
if (isMax)
80+
{
81+
int best = -1000;
82+
for (int i = 0; i < 3; i++)
83+
{
84+
for (int j = 0; j < 3; j++)
85+
{
86+
if (board[i][j] == '_')
87+
{
88+
board[i][j] = player;
89+
90+
best = max(best, minimax(board, depth + 1, !isMax));
91+
board[i][j] = '_';
92+
}
93+
}
94+
}
95+
return best;
96+
}
97+
98+
else
99+
{
100+
int best = 1000;
101+
102+
for (int i = 0; i < 3; i++)
103+
{
104+
for (int j = 0; j < 3; j++)
105+
{
106+
if (board[i][j] == '_')
107+
{
108+
board[i][j] = opponent;
109+
best = min(best, minimax(board, depth + 1, !isMax));
110+
111+
board[i][j] = '_';
112+
}
113+
}
114+
}
115+
return best;
116+
}
117+
}
118+
119+
Move findBestMove(char board[3][3])
120+
{
121+
int bestVal = -1000;
122+
Move bestMove;
123+
bestMove.row = -1;
124+
bestMove.col = -1;
125+
for (int i = 0; i < 3; i++)
126+
{
127+
for (int j = 0; j < 3; j++)
128+
{
129+
if (board[i][j] == '_')
130+
{
131+
board[i][j] = player;
132+
int moveVal = minimax(board, 0, false);
133+
board[i][j] = '_';
134+
if (moveVal > bestVal)
135+
{
136+
bestMove.row = i;
137+
bestMove.col = j;
138+
bestVal = moveVal;
139+
}
140+
}
141+
}
142+
}
143+
144+
printf("The value of the best Move is : %d\n\n", bestVal);
145+
return bestMove;
146+
}
147+
int main()
148+
{
149+
char board[3][3] =
150+
{
151+
{'x', 'o', 'x'},
152+
{'o', 'o', 'x'},
153+
{'_', '_', '_'}
154+
};
155+
156+
Move bestMove = findBestMove(board);
157+
158+
printf("The Optimal Move is :\n");
159+
printf("ROW: %d COL: %d\n\n", bestMove.row, bestMove.col);
160+
return 0;
161+
}

0 commit comments

Comments
 (0)
0