Minimax and Alpha-Beta Pruning

Minimax is the classic algorithm for playing perfect-information, zero-sum games like tic-tac-toe, checkers, or chess. The idea is simple: one player tries to maximize the score while the other tries to minimize it, and each assumes the other will always play the best move available. If you search the game tree all the way to the end, minimax tells you the value of a position under optimal play by both sides. Let’s implement it in Go for tic-tac-toe, small enough that we can search the entire game tree, and then look at alpha-beta pruning, an optimization that throws away branches that can’t possibly affect the result.

Representing the Game#

We need very little to represent a game of tic-tac-toe. The board is nine cells in row-major order, and each cell is either empty or owned by one of the two players. We’ll represent the two players as 1 and -1, which will turn out to be convenient when we score positions.

const (
    empty = 0
    X     = 1
    O     = -1
)

type board [9]int

There are only eight ways to win in tic-tac-toe: three rows, three columns, and two diagonals. We can list them once as triples of indices into the board.

var winningLines = [8][3]int{
    {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
}

With those lines in hand, checking for a winner is a matter of scanning each triple for three matching non-empty cells. We return the winning player (X or O) if there is one, and empty otherwise.

func (b board) winner() int {
    for _, line := range winningLines {
        if b[line[0]] != empty && b[line[0]] == b[line[1]] && b[line[1]] == b[line[2]] {
            return b[line[0]]
        }
    }
    return empty
}

We also need to know when the board is full, since a game with no winner and no empty cells is a draw.

func (b board) full() bool {
    for _, c := range b {
        if c == empty {
            return false
        }
    }
    return true
}

Scoring Terminal Positions#

Minimax works by assigning a numeric score to every terminal position (one where the game is over) and then propagating those scores back up the tree. A position is terminal when there’s a winner or the board is full. Every score is expressed from X’s perspective: positive is good for X, negative is good for O, and zero is a draw. That single fixed perspective is why X maximizes and O minimizes.

This is where representing the players as 1 and -1 pays off. If w is the winner, then w is already +1 for X and -1 for O, so we can just multiply it by some positive magnitude. There’s one subtlety worth handling: we’d prefer to win quickly and lose slowly, so a win that happens sooner should score higher in magnitude than one that happens later. We track depth, how many moves deep the search has gone, and subtract it from the magnitude.

// inside minimax, at a terminal node:
if w := b.winner(); w != empty {
    return w * (10 - depth)
}
if b.full() {
    return 0
}

A fast X win (few moves played, small depth) scores close to +10, while a slow one scores closer to +1. The mirror holds for O. A draw scores 0. Without the depth term, minimax would consider all wins equally good and might dawdle, choosing a win in five moves over a win in three because both simply score “win”.

The Minimax Recursion#

Now for the core of the algorithm. At each node we look at whose turn it is. The maximizing player (X) tries every legal move, recurses to find the value of the resulting position, and keeps the largest value. The minimizing player (O) does the same but keeps the smallest.

func minimax(b board, player, depth int) int {
    if w := b.winner(); w != empty {
        return w * (10 - depth)
    }
    if b.full() {
        return 0
    }

    if player == X {
        best := math.MinInt
        for i := 0; i < 9; i++ {
            if b[i] != empty {
                continue
            }
            b[i] = X
            best = max(best, minimax(b, O, depth+1))
            b[i] = empty
        }
        return best
    }

    best := math.MaxInt
    for i := 0; i < 9; i++ {
        if b[i] != empty {
            continue
        }
        b[i] = O
        best = min(best, minimax(b, X, depth+1))
        b[i] = empty
    }
    return best
}

The two branches are near mirror images: the maximizer seeds best with math.MinInt and takes the max, the minimizer seeds with math.MaxInt and takes the min. Each move is applied to the board, evaluated by a recursive call for the opponent, and then undone¹. The recursion bottoms out at the terminal checks we wrote earlier.

To pick an actual move rather than just score a position, we run the same loop one level up: try each legal move, score the resulting position with minimax, and keep the move with the best score for the player to move. Here it is for X, who wants the highest-scoring reply:

move, best := -1, math.MinInt
for i := 0; i < 9; i++ {
    if b[i] != empty {
        continue
    }
    b[i] = X
    if v := minimax(b, O, depth+1); v > best {
        best, move = v, i
    }
    b[i] = empty
}

O is the mirror image: seed best with math.MaxInt and keep the move with the smallest score.

Running It#

The natural first question is: what does minimax say about tic-tac-toe from an empty board? We can evaluate the starting position with X to move and count how many nodes the search visits along the way.

plain minimax:  value=0 nodes=549946

Two things fall out of this. First, the value is 0, which is the well-known result that tic-tac-toe is a draw under optimal play: neither side can force a win against a perfect opponent. Second, searching the full tree from the empty position visits 549,946 nodes². That’s a lot of work for such a simple game. Some of it is genuinely wasted: there are only 5,478 distinct reachable positions in tic-tac-toe, so the vast majority of those half-million nodes are the same board arrived at by a different order of moves and re-searched from scratch. A transposition table would cache them. But the deeper problem is that the game tree grows exponentially with depth. Tic-tac-toe has at most 9! move sequences, but for a game like chess the tree is astronomically large, and searching all of it is hopeless. We need a way to avoid visiting nodes that can’t change the answer.

Alpha-Beta Pruning#

Here’s the key observation. Suppose the maximizer is partway through evaluating its options and has already found a move guaranteeing a score of at least 5. Now it starts evaluating another move, and while exploring the minimizer’s responses it finds one that scores 3. Since the minimizer is choosing among these replies, the branch is worth at most 3 to the maximizer. But the maximizer already has a 5 in hand. There’s no point examining the minimizer’s remaining replies in this branch, because none of them can make it good enough to be chosen. We can stop, or prune, right there.

Here is that situation as a slice of the game tree, with the maximizer on top choosing between two moves and a minimizer under each (scores are from X’s perspective, as always):

                 MAX  (X to move)
                /                \
          MIN = 5             MIN <= 3
          /    \              /       \
         5      8            3      (pruned)

The left move settles at 5, so the maximizer walks into the right move already holding a 5. The right minimizer’s first reply is 3, and since it only goes lower from there, that whole move is worth at most 3. It can never beat 5, so the pruned leaf is never even generated.

Alpha-beta pruning formalizes this with two values that we thread through the recursion:

• alpha: the best score the maximizer can already guarantee somewhere higher up the tree.
• beta: the best score the minimizer can already guarantee.

At any node, alpha is a lower bound and beta an upper bound on scores that are still relevant. Both live in the same X-perspective scale as our terminal scores, so their meaning never flips with the side to move. The moment they cross, that is beta <= alpha, we know the current node can’t influence the final decision and we cut off the rest of its moves. Crucially, pruning never changes the value minimax computes; it only skips work that provably doesn’t matter.

Implementing Alpha-Beta#

The structure is identical to plain minimax, with two additions per branch: after updating best, we tighten the relevant bound (alpha for the maximizer, beta for the minimizer), and then check for the cutoff.

func alphabeta(b board, player, depth, alpha, beta int) int {
    if w := b.winner(); w != empty {
        return w * (10 - depth)
    }
    if b.full() {
        return 0
    }

    if player == X {
        best := math.MinInt
        for i := 0; i < 9; i++ {
            if b[i] != empty {
                continue
            }
            b[i] = X
            best = max(best, alphabeta(b, O, depth+1, alpha, beta))
            b[i] = empty
            alpha = max(alpha, best)
            if beta <= alpha {
                break
            }
        }
        return best
    }

    best := math.MaxInt
    for i := 0; i < 9; i++ {
        if b[i] != empty {
            continue
        }
        b[i] = O
        best = min(best, alphabeta(b, X, depth+1, alpha, beta))
        b[i] = empty
        beta = min(beta, best)
        if beta <= alpha {
            break
        }
    }
    return best
}

When the maximizer raises alpha to or above beta, it has found a move so good that the minimizer, one level up, would never have let the game reach this node, so we break out of the loop and stop generating moves. The minimizer’s cutoff is the symmetric case. We kick off the search with the widest possible window, alpha = math.MinInt and beta = math.MaxInt, so that nothing is pruned at the root.

Results#

Running alpha-beta from the same empty board:

plain minimax:  value=0 nodes=549946
alpha-beta:     value=0 nodes=20866
nodes pruned:   529080 (96.2% fewer)

The value is still 0, exactly as before, confirming that pruning didn’t change the answer. But we reached it by visiting 20,866 nodes instead of 549,946, a 96.2% reduction, skipping the vast majority of the tree.

One caveat worth stating: how much alpha-beta prunes depends heavily on move ordering. The earlier a strong move is examined, the sooner alpha and beta tighten and the more the remaining branches get cut. Our implementation just walks cells 0 through 8 in order, which is a naive ordering, and still prunes 96% of nodes. With perfect ordering, alpha-beta only needs to examine on the order of the square root of the nodes that plain minimax does³, which is why real game engines put so much effort into examining promising moves first.

Conclusion#

Minimax is a satisfying algorithm: the whole thing is just two mirror-image branches and a scoring convention for terminal positions, yet it plays tic-tac-toe perfectly. Alpha-beta pruning then buys an enormous speedup for a few extra lines, without ever changing the answer, by refusing to explore branches that can’t matter. The same two ideas scale up, with the addition of depth limits and heuristic evaluation of non-terminal positions, to the engines that play chess and other far larger games. If you want to go deeper, the chess programming wiki has a wealth of material on move ordering, transposition tables, and the many refinements built on top of this foundation.