← back

Minimax Algorithm for Tic-Tac-Toe

#171 · Game Theory · Medium

⊣ Solve on deep-ml.com

Problem

Implement the Minimax Algorithm for Tic-Tac-Toe. The algorithm explores the full game tree to find the optimal move for the current player, assuming both players play perfectly.

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
from typing import List, Optional, Tuple

def minimax_tictactoe(board: List[List[str]], is_maximizing: bool) -> Tuple[int, Optional[Tuple[int, int]]]:
    def check_winner(b):
        for i in range(3):
            if b[i][0] == b[i][1] == b[i][2] != '':
                return b[i][0]
            if b[0][i] == b[1][i] == b[2][i] != '':
                return b[0][i]
        if b[0][0] == b[1][1] == b[2][2] != '':
            return b[0][0]
        if b[0][2] == b[1][1] == b[2][0] != '':
            return b[0][2]
        return None

    def is_full(b):
        return all(b[i][j] != '' for i in range(3) for j in range(3))

    winner = check_winner(board)
    if winner == 'X':
        return 1, None
    if winner == 'O':
        return -1, None
    if is_full(board):
        return 0, None

    best_move = None
    if is_maximizing:
        best_score = -float('inf')
        for i in range(3):
            for j in range(3):
                if board[i][j] == '':
                    board[i][j] = 'X'
                    score, _ = minimax_tictactoe(board, False)
                    board[i][j] = ''
                    if score > best_score:
                        best_score = score
                        best_move = (i, j)
        return best_score, best_move
    else:
        best_score = float('inf')
        for i in range(3):
            for j in range(3):
                if board[i][j] == '':
                    board[i][j] = 'O'
                    score, _ = minimax_tictactoe(board, True)
                    board[i][j] = ''
                    if score < best_score:
                        best_score = score
                        best_move = (i, j)
        return best_score, best_move

Explanation

  1. Base cases: If X wins return +1, if O wins return -1, if board is full return 0 (draw).
  2. Maximizing player (X): Try every empty cell, recursively evaluate, and pick the move with the highest score.
  3. Minimizing player (O): Try every empty cell, recursively evaluate, and pick the move with the lowest score.
  4. The algorithm guarantees optimal play: in Tic-Tac-Toe, perfect play by both sides always leads to a draw.

Complexity

  • Time: O(9!) in the worst case (all possible game states), though pruning and terminal checks reduce this significantly
  • Space: O(9) for recursion depth (at most 9 moves deep)
← #170#172 →