Next Optimal Move in Tic Tac Toe

Next Optimal Move in Tic Tac Toe

You are given a middle game situation of the game Tic Tac Toe.It is given that it is player "X's" turn and you need to give to mostoptimal position for the turn. The situation is given as a 3 x 3 character matrix. '_' refers to the place is empty. 'o' refers thatplayer O marked it in his turn at some time and 'x' refers that player X
marked it in his turn at some time. It is player X's turn. Tell him the most optimal solution. (Assume player O played first)

function findBestMove (board):
bestMove = NULL
for each move in board:
if current move is better than bestMove
bestMove = current move
return bestMove


function minimax (board, depth, isMaximizingPlayer):

if current board state is a terminal state:
return value of the board

if isMaximizingPlayer:
bestVal = -INFINITY
for each move in board:
value = minimax (board, depth + 1, false)
bestVal = max (bestVal, value)
return bestVal

else:
bestVal = + INFINITY
for each move in board:
value = minimax (board, depth + 1, true)
bestVal = min (bestVal, value)
return bestVal


function isMovesLeft (board):
for each cell in board:
if current cell is empty:
return true
return false


if maximizer has won:
return WIN_SCORE - depth

else if minimizer has won:
return LOOSE_SCORE + depth


#include <bits / stdc ++. h>
using namespace std;
char a [3] [3], player = 'x', opponent = 'o';
int isleftmove ()
{
for (int i = 0; i <3; ++ i)
{
for (int j = 0; j <3; ++ j)
{
if (a [i] [j] == '_')
return true;
}
}
return false;
}
int evalscore ()
{
for (int row = 0; row <3; ++ row)
{
if (a [row] [0] == a [row] [1] && a [row] [1] == a [row] [2])
{
if (a [row] [0] == player)
return 10;
else if (a [row] [0] == opponent)
return -10;
}
}

for (int col = 0; col <3; ++ col)
{
if (a [0] [col] == a [1] [col] && a [1] [col] == a [2] [col])
{
if (a [0] [col] == player)
return +10;
else if (a [0] [col] == opponent)
return -10;
}
}
if (a [0] [0] == a [1] [1] && a [1] [1] == a [2] [2])
{
if (a [0] [0] == player)
return +10;
else if (a [0] [0] == opponent)
return -10;
}
if (a [0] [2] == a [1] [1] && a [1] [1] == a [2] [0])
{
if (a [0] [2] == player)
return +10;
else if (a [0] [2] == opponent)
return -10;
}
return 0;
}
int minmax (int depth, bool ismax)
{
int score = evalscore ();

if (score == 10 || score == - 10)
return score;

if (isleftmove () == false)
return 0;
if (ismax)
{
int best = -10000;
for (int i = 0; i <3; ++ i)

{
for (int j = 0; j <3; ++ j)
{
if (a [i] [j] == '_')
{
a [i] [j] = player;
best = max (best, minmax (depth + 1,! ismax));
a [i] [j] = '_';
}
}
}

return best;
} else {
int best = 10000;
for (int i = 0; i <3; ++ i)
{
for (int j = 0; j <3; ++ j)
{
if (a [i] [j] == '_')
{
a [i] [j] = opponent;
best = min (best, minmax (depth + 1,! ismax));
a [i] [j] = '_';

}
}
}
return best;

}
}
int main () {
// code
int t;
cin >> t;
while (t--)
{


for (int i = 0; i <3; ++ i)
{
for (int j = 0; j <3; ++ j)
{
cin >> a [i] [j];
}
}

int bestmove = -10000, x = -1, y = -1;
for (int i = 0; i <3; ++ i)
{
for (int j = 0; j <3; ++ j)
{
if (a [i] [j] == '_')
{
a [i] [j] = player;
int moveval = minmax (0, false);
a [i] [j] = '_';
if (moveval> bestmove)
{
x = i, y = j;
bestmove = moveval;
}
}
}

}
cout << x << "" << y << "\ n";


}
return 0;
}