Minimax and Alpha-Beta Pruning: Searching a Tree Nobody Can Finish

Assume your opponent is perfect

Minimax is the foundational search algorithm for two-player, zero-sum games with perfect information - tic-tac-toe, checkers, chess. It builds a tree of possible future positions, alternating between a maximising player who wants the highest score and a minimising player who wants the lowest, and it evaluates every position by assuming both players always choose their best available move from that point on. The name describes exactly this: each player minimises the maximum damage the other can do, or maximises their own guaranteed minimum outcome, depending on whose turn it is.

minimax(node, depth, maximizingPlayer):
  if depth == 0 or node is terminal:
    return evaluate(node)
  if maximizingPlayer:
    value = −infinity
    for each child of node:
      value = max(value, minimax(child, depth−1, false))
    return value
  else:
    value = +infinity
    for each child of node:
      value = min(value, minimax(child, depth−1, true))
    return value

The exponential wall

Plain minimax explores every node of the tree, and the tree's size explodes as O(b^d), where b is the branching factor (roughly 35 legal moves per position in chess) and d is how many moves ahead you look. Even a modest depth of 10 half-moves in chess already implies exploring on the order of 35^10 positions - vastly more than any computer can visit, which is why chess engines never search to the literal end of the game. Instead they search to a fixed depth and replace the true outcome with a heuristic evaluation function that scores a position by material, king safety, piece activity and similar features.

Alpha-beta: pruning what cannot matter

Alpha-beta pruning speeds up minimax without changing its answer, by tracking two bounds as the search proceeds: alpha, the best score the maximiser is already guaranteed elsewhere in the tree, and beta, the best score the minimiser is already guaranteed elsewhere. The moment a node's value would fall outside the current (alpha, beta) window - meaning a rational opponent would simply never allow the game to reach it - the remaining siblings of that node are skipped entirely, because no matter what they evaluate to, they cannot change the decision one level up.

alphabeta(node, depth, α, β, maximizingPlayer):
  if depth == 0 or node is terminal:
    return evaluate(node)
  if maximizingPlayer:
    value = −infinity
    for each child of node:
      value = max(value, alphabeta(child, depth−1, α, β, false))
      α = max(α, value)
      if α >= β: break        // β cutoff — rest of the siblings pruned
    return value
  else:
    value = +infinity
    for each child of node:
      value = min(value, alphabeta(child, depth−1, α, β, true))
      β = min(β, value)
      if β <= α: break        // α cutoff — rest of the siblings pruned
    return value

Same answer, radically less work

This is the property that makes alpha-beta pruning safe to use everywhere minimax is used: it is not a heuristic shortcut, it is an exact optimisation. Given identical search depth and evaluation function, alpha-beta always returns exactly the move plain minimax would have found, because every branch it skips has been proven irrelevant to the outcome, not merely guessed to be unpromising. In the best case, with moves searched in an ideal order, alpha-beta reduces the effective branching factor from b to roughly √b, cutting the tree from O(b^d) to about O(b^(d/2)) - which in practice means searching twice as deep for the same amount of computation.

Move ordering is the whole game

The size of the speed-up depends entirely on the order moves are tried in. Pruning only fires once a sufficiently good move has already been found at a node, so if the strongest move is searched first, the (alpha, beta) window snaps shut immediately and most of the remaining siblings are cut without ever being evaluated. Search the weakest move first instead and the window stays wide open, pruning barely triggers, and performance degrades toward plain unpruned minimax. This is why real engines invest heavily in move-ordering heuristics - trying captures before quiet moves, previously discovered best moves first, killer moves that caused cutoffs in sibling nodes - since a good ordering is often worth more to overall search speed than any other single optimisation.

Frequently asked questions

Try it live

Everything above runs in your browser — open Minimax and Alpha-Beta Pruning and change the parameters while it is running. Nothing is installed, nothing is uploaded, the whole model lives in one tab.