Tic-Tac-Toe: Minimax and Alpha-Beta Pruning

The classic two-player game as an AI problem — the game tree, why minimax guarantees perfect play, how alpha-beta pruning cuts the work by 90%, and a complete unbeatable player in Python.

Every other problem on these pages has one thing in common: you are the only one making moves. Tic-tac-toe breaks that. Between each of your moves, somebody who wants you to lose gets a turn.

That single change breaks BFS, DFS and A* completely. You can’t plan a path, because your opponent controls half of it. You need a different idea: minimax — assume the opponent plays perfectly, and pick the move that’s best against that.

The problem

Rules. Two players, X and O, alternate marking empty squares on a 3×3 grid. The first to complete a line of three — row, column or diagonal — wins. If all nine squares fill with no line, it’s a draw.

State representation

# 9 characters, row-major. ' ' = empty.
state = ('X', ' ', 'O',
         ' ', 'X', ' ',
         'O', ' ', ' ')

Two things a state must let you compute instantly:

Whose turn is it? You don’t need to store it — count the marks. X always goes first, so:

def player(state):
    return 'X' if state.count('X') == state.count('O') else 'O'

Has someone won? Precompute the eight lines as index triples and check each:

LINES = [(0,1,2), (3,4,5), (6,7,8),    # rows
         (0,3,6), (1,4,7), (2,5,8),    # columns
         (0,4,8), (2,4,6)]             # diagonals

def winner(state):
    for a, b, c in LINES:
        if state[a] != ' ' and state[a] == state[b] == state[c]:
            return state[a]
    return None

The state space

Count	Value	Meaning
Naïve upper bound	$3^9 = 19{,}683$	Every square is X, O or blank
Legal positions	5,478	Reachable and not past a win
Distinct games	255,168	Complete move sequences
Games, X plays first	131,184 X wins · 77,904 O wins · 46,080 draws

Note the gap between $3^9$ and 5,478. Most of the $3^9$ arrangements are illegal: five O’s and one X can’t happen, and neither can a board where both players have a completed line. Always compute the reachable space, not the combinatorial one — for many problems it’s an order of magnitude smaller, and that’s the number that governs your runtime.

5,478 is tiny. We can search the entire game tree, every time, and still respond instantly. That’s what makes tic-tac-toe the perfect teaching example: you get to see optimal play with no approximation anywhere.

Minimax: the core idea

Label the two players by what they want the score to do:

MAX (say, X) wants the final score as high as possible.
MIN (O) wants it as low as possible.

Score the terminal positions only:

Outcome	Score
X wins	+1
Draw	0
O wins	−1

Now propagate those numbers back up the tree. At a MAX node, take the maximum of the children. At a MIN node, take the minimum. The value that arrives at the root is the game’s true value under perfect play — and the child that produced it is your move.

Read the middle branch carefully. Both of its leaves are +1, so MIN — who is trying to minimise — is stuck: whatever O does there, X wins. That’s why MAX chooses it. The left branch has a −1 available, and MIN will certainly take it. The right branch lets MIN hold X to a draw.

Minimax is pessimism used constructively. You evaluate each of your options by assuming the worst possible reply, then pick the option whose worst case is best.

def minimax(state):
    """Return the true value of `state` under perfect play by both sides."""
    w = winner(state)
    if w == 'X': return  1
    if w == 'O': return -1
    if ' ' not in state: return 0          # board full → draw

    if player(state) == 'X':               # MAX node
        return max(minimax(s) for s in moves(state))
    else:                                  # MIN node
        return min(minimax(s) for s in moves(state))

That’s the whole algorithm — nine lines, and it plays perfectly. The recursion bottoms out at terminal boards, so there’s no depth limit and no evaluation function to tune.

Alpha-beta pruning: same answer, a tenth of the work

Plain minimax on an empty board explores 549,946 nodes. Most of that work is provably wasted, and you can prove it while you search.

Here’s the insight. Suppose you’re at a MAX node and you’ve already found a move worth +1. You start examining the next move; its first reply gives −1. MIN is choosing there, so that branch’s value is at most −1. You already have +1. Nothing you learn from the rest of that branch can change your decision — so stop looking.

Carry two numbers down the tree:

$\alpha$ — the best value MAX can already guarantee (starts at $-\infty$ )
$\beta$ — the best value MIN can already guarantee (starts at $+\infty$ )

The moment $\alpha \ge \beta$ , the current node is irrelevant. Cut.

def alphabeta(state, alpha=-2, beta=2):
    w = winner(state)
    if w == 'X': return  1
    if w == 'O': return -1
    if ' ' not in state: return 0

    if player(state) == 'X':                      # MAX
        value = -2
        for s in moves(state):
            value = max(value, alphabeta(s, alpha, beta))
            alpha = max(alpha, value)
            if alpha >= beta:
                break                             # β-cutoff
        return value
    else:                                         # MIN
        value = 2
        for s in moves(state):
            value = min(value, alphabeta(s, alpha, beta))
            beta = min(beta, value)
            if alpha >= beta:
                break                             # α-cutoff
        return value

The result is identical to plain minimax. Pruning never changes the answer — it only skips branches that provably cannot affect it. On an empty tic-tac-toe board:

Method	Nodes visited
Minimax	549,946
Alpha-beta	18,297
Alpha-beta + best-move-first ordering	~2,300

Move ordering is everything. If you always examine the best move first, alpha-beta’s effective branching factor drops from $b$ to $\sqrt{b}$ — meaning you can search twice as deep in the same time. That result is why chess engines invest so heavily in guessing which move to try first: captures, checks, and the move that worked at a shallower depth.

The complete unbeatable player

LINES = [(0,1,2), (3,4,5), (6,7,8),
         (0,3,6), (1,4,7), (2,5,8),
         (0,4,8), (2,4,6)]

EMPTY = (' ',) * 9


def player(state):
    return 'X' if state.count('X') == state.count('O') else 'O'


def winner(state):
    for a, b, c in LINES:
        if state[a] != ' ' and state[a] == state[b] == state[c]:
            return state[a]
    return None


def moves(state):
    """Yield every board reachable by the player to move."""
    mark = player(state)
    for i, cell in enumerate(state):
        if cell == ' ':
            lst = list(state)
            lst[i] = mark
            yield i, tuple(lst)


def alphabeta(state, alpha=-2, beta=2, depth=0):
    """Score the position. Prefer faster wins and slower losses via `depth`."""
    w = winner(state)
    if w == 'X': return  10 - depth
    if w == 'O': return depth - 10
    if ' ' not in state: return 0

    if player(state) == 'X':
        value = -99
        for _, s in moves(state):
            value = max(value, alphabeta(s, alpha, beta, depth + 1))
            alpha = max(alpha, value)
            if alpha >= beta:
                break
        return value
    else:
        value = 99
        for _, s in moves(state):
            value = min(value, alphabeta(s, alpha, beta, depth + 1))
            beta = min(beta, value)
            if alpha >= beta:
                break
        return value


def best_move(state):
    """The index the player to move should take."""
    mark = player(state)
    pick = max if mark == 'X' else min
    return pick(((alphabeta(s, depth=1), i) for i, s in moves(state)))[1]


def show(state):
    for r in range(0, 9, 3):
        print(' ' + ' | '.join(state[r:r+3]))
        if r < 6:
            print('---+---+---')


if __name__ == '__main__':
    board = EMPTY
    while winner(board) is None and ' ' in board:
        if player(board) == 'X':
            i = best_move(board)                       # AI
            print(f'\nAI (X) plays {i}')
        else:
            show(board)
            i = int(input('\nYour move (0-8): '))       # human
            if board[i] != ' ':
                print('Taken — try again.'); continue
        lst = list(board); lst[i] = player(board); board = tuple(lst)

    show(board)
    w = winner(board)
    print('\n' + (f'{w} wins!' if w else "It's a draw."))

The `depth` term

Notice the score isn’t just $\pm 1$ — it’s 10 - depth for a win and depth - 10 for a loss. Without that, the AI treats “win now” and “win in five moves” as equally good, and will happily dawdle while you set up a fork. With it, the AI prefers the fastest win and the slowest loss, which is what makes it feel like it’s actually trying.

This is a general trick in game AI: when several moves have the same outcome, break the tie with something that reflects style of play.

What perfect play looks like

Tic-tac-toe is a solved game: with best play from both sides, it’s always a draw. Some specific facts falling out of the full search:

Every opening draws. Run minimax on all nine first moves and each scores 0. There is no winning first move; against perfect defence the game is dead from move one.
But the centre is the strongest against imperfect play. It sits on 4 of the 8 winning lines — more than any other square. Corners sit on 3, edges on 2. More lines through your square means more ways for a fallible opponent to let you fork.
A corner opening has exactly one non-losing reply: the centre. Minimax scores all eight other replies to X in a corner as +1 — a win for X. That’s the single sharpest fact in the game, and it’s why “X takes a corner” is the standard trap against a casual player.
The dangerous pattern is the fork — one move that creates two threats at once. You can only block one.

Minimax finds forks automatically. You never have to teach it the concept — it falls out of looking two moves ahead and seeing that every opponent reply leads to a loss.

Beyond tic-tac-toe: how this scales

The reason to learn minimax on a 5,478-state game is that the same machinery runs on games you can’t search exhaustively.

Game	State space	What changes
Tic-tac-toe	$10^3$	Search to the end — solved
Connect Four	$10^{13}$	Solved (1988) — first player wins
Checkers	$10^{20}$	Solved (2007) — a draw
Chess	$10^{47}$	Depth-limited + evaluation function
Go	$10^{170}$	Minimax fails — needs MCTS + neural nets

For anything past Connect Four you can’t reach terminal positions, so you add two things:

A depth limit — stop after $d$ plies.
An evaluation function — a heuristic score for a non-terminal position. In chess: material count, pawn structure, king safety, mobility.

That’s the entire architecture of Deep Blue: alpha-beta, a hand-tuned evaluation function, and enough hardware to search 12+ plies. AlphaGo replaced the evaluation function with a neural network and the tree search with Monte Carlo Tree Search — but the shape of the idea, look ahead and assume the opponent plays well, is unchanged from the nine lines above.

Where to go next

Problem Solving with AI: The State-Space Framework — how this fits the wider picture
The 8-Puzzle — single-agent search with heuristics
Travelling Salesman Problem — pruning applied to optimisation