juniorGame Theory

What is the minimax algorithm and how does alpha-beta pruning improve it?

Updated Feb 20, 2026

Short answer

Minimax searches a two-player zero-sum game tree assuming both players play optimally: one maximises the score, the other minimises it. Its cost is O(b^d) in branching factor and depth, which is unusable beyond shallow trees. Alpha-beta pruning discards branches that cannot influence the result, and with good move ordering reduces the effective cost to O(b^(d/2)) — doubling the depth searchable in the same time.

Deep explanation

Python
def minimax(node, depth, maximizing):
    if depth == 0 or node.is_terminal():
        return node.evaluate()
    if maximizing:
        return max(minimax(c, depth-1, False) for c in node.children())
    return min(minimax(c, depth-1, True) for c in node.children())

Alpha-beta adds two bounds carried down the tree. Alpha is the best value the maximiser is already guaranteed; beta is the best the minimiser is guaranteed. When alpha ≥ beta, the current node cannot affect the outcome and the remaining children are skipped.

Python
def alphabeta(node, depth, alpha, beta, maximizing):
    if depth == 0 or node.is_terminal():
        return node.evaluate()
    if maximizing:
        value = float('-inf')
        for child in node.children():
            value = max(value, alphabeta(child, depth-1, alpha, beta, False))
            alpha = max(alpha, value)
            if alpha >= beta:
                break              # beta cutoff: minimiser avoids this branch
        return value
    value = float('inf')
    for child in node.children():
        value = min(value, alphabeta(child, depth-1, alpha, beta, True))
        beta = min(beta, value)
        if beta <= alpha:
            break                  # alpha cutoff
    return value

The reasoning behind a cutoff. If the maximiser has already secured a score of 6 elsewhere, and the current branch has shown the minimiser can force 4, the maximiser will never choose this branch. Whatever the remaining children hold, they can only lower it further — so evaluating them is wasted work.

Alpha-beta returns exactly the same value as minimax. It is not an approximation; it only skips provably irrelevant subtrees.

Move ordering is everything. With perfect ordering — best moves examined first — the complexity is O(b^(d/2)), effectively doubling searchable depth. With worst-case ordering there is no saving at all. Real engines therefore invest heavily in ordering heuristics: the best move from a shallower search (iterative deepening), killer moves that caused cutoffs at the same depth, and transposition tables caching previously-evaluated positions.

Practical extensions. Iterative deepening searches depth 1, 2, 3… so there is always a usable move under a time limit, and each pass improves the ordering for the next. Quiescence search extends past the depth limit through capture sequences to avoid the horizon effect, where the evaluation stops mid-exchange and badly misjudges the position.

Real-world example

A tic-tac-toe move chooser — small enough to search exhaustively:

Python
def best_move(board):
    best_score, best = float('-inf'), None
    for move in board.legal_moves():
        board.push(move)
        score = alphabeta(board, depth=9, alpha=float('-inf'),
                          beta=float('inf'), maximizing=False)
        board.pop()
        if score > best_score:
            best_score, best = score, move
    return best

Tic-tac-toe has about 255,000 nodes without pruning and roughly 20,000–30,000 with it. Chess has a branching factor near 35, so a depth-8 search is around 2.2 trillion nodes with plain minimax and roughly 1.5 million with well-ordered alpha-beta — the difference between impossible and instant.

Common mistakes

  • - Initialising alpha and beta to arbitrary finite values rather than negative and positive infinity, which prunes valid branches and returns a wrong result.
  • - Ignoring move ordering, which is where nearly all the benefit lives — badly ordered alpha-beta is barely better than plain minimax.
  • - Assuming alpha-beta approximates the answer
  • it returns exactly the minimax value.
  • - Searching to a fixed depth without quiescence, so evaluation lands mid-capture and misreads the position.
  • - Applying minimax to non-zero-sum or multiplayer games, where one player's gain is not another's loss and the assumption breaks down.
  • - Forgetting to undo a move after recursing, corrupting the board state for sibling branches.

Follow-up questions

  • Why does move ordering determine how much alpha-beta saves?
  • What is the horizon effect?
  • What is iterative deepening and why is it not wasteful?
  • How does Monte Carlo Tree Search differ from minimax?

More Game Theory interview questions

View all →