Tic Tac Toe Winner

We will be using the minimax algorithm to evaluate the score of the board. Our objective will be to maximize the score we can get across all possibilities, while the objective of the opponent will be to minimize the score. So at every stage we will maintain whose turn it is now, if it is ours we maximize across all the remaining states else the opponent minimizes across all possible moves on the current board.

Algorithm:

findTheWinner(board, player) finds the best score achievable and the position of the move to make.

1. Initialize best_move to {-1, -1} and best_score to -infinity.
2. For every possible move on the board, call the minimax function to calculate the maximum possible score possible.
3. If the score is greater than best_score update best_score to this score and best move to this move.
4. Undo the current move for the next possible move.
5. Finally, return the array containing best_score and best_move.

minimax(board, turn) takes the state of the board and the player whose turn it is. It evaluates the board to check for final state (when one of the players wins or no moves are left) and returns a score based on that.

1. if the board has a winner, then return -1 or 1 depending on the winner of the game.
2. If the board has no moves left, return 0 score indicating a draw.
3. if turn == 1 (means it is our turn)
   1. assign score = -infinity
   2. For each empty square try to place our symbol.
   3. update the score = max(score, minimax(new_board, !turn))
   4. undo the move.
   5. return  the final score.
4. else (means it is the opponent’s turn)
   1. assign score = +infinity
   2. For each empty square try to place the opponent's symbol.
   3. update the score = min(score, minimax(new_board, !turn))
   4. undo the move.
   5. return  the final score.

isMovesLeft(board) returns true if the board has a move left else returns false

1. Iterate over all the squares and if a ‘_’ is found return true.
2. Else if no empty square is found return false.

isGameOver(board) returns 1 if you have won the game, -1 if the opponent won the game, else 0.

1. For each row check if the characters are the same.
   1. if the symbol is ‘X’ return 1 else return 0.
2. For each column check if the characters are the same.
   1. if the symbol is ‘X’ return 1 else return 0.
3. For both diagonals check if the characters are the same.
   1. if the symbol is ‘X’ return 1 else return 0.
4. return 0

O((N^2)!), Where ‘N’ is the size of the board. 

At every stage, if there are ‘E’ empty squares, then we branch ‘E’ times and the subspace reduces to size ‘E’ - 1.

So T(E) = E*T(E - 1) which gives T(E) = E!. Since at the beginning of the game we can have (N^2) empty squares it gives the time complexity is O((N^2)!).

O(N),  Where ‘N’ is the size of the board

Since a recursion depth of size N is reached in the minimax tree.