Tic Tac Toe is a Flutter apllication which is made using BackTracking MinMax algorithm.

1. Finding the Best Move :

We shall be introducing a new function called findBestMove(). This function evaluates all the available moves using minimax() and then returns the best move the maximizer can make. The pseudocode is as follows :

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

2. Minimax :

To check whether or not the current move is better than the best move we take the help of minimax() function which will consider all the possible ways the game can go and returns the best value for that move, assuming the opponent also plays optimally The code for the maximizer and minimizer in the minimax() function is similar to findBestMove() , the only difference is, instead of returning a move, it will return a value. Here is the pseudocode :

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