Last Updated: 2 Jul, 2021

Tic Tac Toe Winner

Hard

Asked in companies

Solve now

Problem statement

Ninja is bored and hence started playing tic tac toe with his friend. As always he started losing the game. So he approaches you to find the optimal move he needs to play at a given moment so that he can defeat his friend.

You are given the current state of the game with a 3x3 grid, of which some squares are filled with 'X', some are filled with ‘O’ and the rest are filled with ‘_’ which means that this square is empty. You need to find the best possible score our ninja can get and the position of the optimal move he should make. You always start first and your symbol is ‘X’. The scores are assigned as follows:

Win: 1

Draw : 0

Lose : -1

For Example:

Suppose the board looks as follows: 

X O X
O O X
_ _ _


We can see that if we put X at positions 3, 3 in the grid we win straightaway. Hence the best possible score is 1 (Win). If we put our symbol anywhere else we will not be able to achieve the desired score.

Note :

If there are multiple positions leading to the same score, choose the position with the minimum row. If there are still multiple positions, choose the one with the minimum column.

Input Format:

Each input is described by 3 lines each of which is a string of 3 characters denoting the state of that row of the grid.

Output Format:

Output 3 integers - the maximum score, the row and the column of the optimal move.

Note:

You are not required to print anything; it has already been taken care of. Just implement the function.

Constraints:

The size of the grid will always be 3.

Time Limit: 1 sec.

Solve now

Approaches

01 Approach

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.

Initialize best_move to {-1, -1} and best_score to -infinity.
For every possible move on the board, call the minimax function to calculate the maximum possible score possible.
If the score is greater than best_score update best_score to this score and best move to this move.
Undo the current move for the next possible move.
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.

if the board has a winner, then return -1 or 1 depending on the winner of the game.
If the board has no moves left, return 0 score indicating a draw.
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.
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

Iterate over all the squares and if a ‘_’ is found return true.
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.

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

Solve now