Adversarial search

Alpha-Beta Pruning

Minimax's clever twin that skips moves it already knows won't matter.

Interactive demo coming soon — read the theory below

The idea

Alpha-Beta Pruning is a speed-up for Minimax, the algorithm two players use to pick the best move by assuming both play perfectly. It watches two running values while it searches: alpha (the best score MAX can already guarantee) and beta (the best score MIN can already guarantee). The moment a branch proves it can never beat what the other player will already allow, the search abandons it unexplored ("prunes" it). You get the exact same move Minimax would choose, but by looking at far fewer positions.

How it works

Start Minimax at the root: MAX wants the highest score, MIN wants the lowest. Carry two values down the tree, alpha = -infinity (best MAX can guarantee so far) and beta = +infinity (best MIN can guarantee so far).
Go deep first. Recurse to the bottom (a game-over or depth-limit position) and read its score using an evaluation of who's winning.
At a MAX node, look at children left to right. Each child's returned value that beats the current best raises alpha (MAX now has a stronger guarantee).
At a MIN node, do the mirror: each child that is lower lowers beta (MIN now has a stronger guarantee).
After updating, check the cutoff test: if alpha >= beta, stop examining this node's remaining children and prune them. They cannot change the result because one player already has a better option elsewhere.
Return the node's value up to its parent, which keeps folding these values into its own alpha/beta.
When the root finishes, the child that produced the root's value is the best move, identical to what plain Minimax would pick.
Search more positions per second by ordering likely-best moves first, which triggers cutoffs earlier and prunes even more.

OPEN, CLOSED & the data structures

A game tree explored by recursion (the call stack is the working memory, one frame per position from the root down to the current leaf). Each recursive call carries the current player's role (MAX or MIN) plus two numbers threaded through the search: alpha (best value MAX can guarantee on the path so far) and beta (best value MIN can guarantee). Optionally, a chosen best-move pointer at the root and an ordered move list per node to improve pruning.

Pseudocode

function alphabeta(node, depth, alpha, beta, maximizing):
    if depth == 0 or node is terminal:
        return evaluate(node)

    if maximizing:                       # MAX's turn
        value = -infinity
        for child in children(node):
            value = max(value, alphabeta(child, depth-1, alpha, beta, false))
            alpha = max(alpha, value)    # raise MAX's guarantee
            if alpha >= beta:
                break                    # beta cutoff: prune the rest
        return value
    else:                                # MIN's turn
        value = +infinity
        for child in children(node):
            value = min(value, alphabeta(child, depth-1, alpha, beta, true))
            beta = min(beta, value)      # lower MIN's guarantee
            if alpha >= beta:
                break                    # alpha cutoff: prune the rest
        return value

# start: alphabeta(root, D, -infinity, +infinity, true)

At a glance

Complete?Yes. If the tree is finite (a real game or a depth-limited search), it always finishes and returns a value. It examines fewer nodes than Minimax but is guaranteed to reach a decision.

Optimal?Yes, it plays optimally: it returns exactly the same value and best move as full Minimax. Pruning only removes branches that provably cannot affect the outcome, so nothing that could change the answer is ever skipped.

TimeWorst case O(b^d) (same as Minimax, where b is moves per turn and d is depth). With good move ordering, roughly O(b^(d/2)), which effectively doubles the depth you can search in the same time.

SpaceO(b*d) (or O(d) storing one move at a time) for the recursion path from root to leaf, the same as Minimax, since pruning saves time, not memory.

👍 When to use it

Two-player, turn-based, zero-sum games where one side's gain is the other's loss (chess, checkers, tic-tac-toe, Connect Four, Othello).
Any situation where plain Minimax is correct but too slow, and you want the identical answer faster.
Games with a reasonable branching factor and a decent evaluation function, especially when you can order moves so promising ones are tried first.
As the engine behind depth-limited search with iterative deepening, where earlier results help order later moves.

⚠️ Watch out for

It gives the same answer as Minimax, not a better one. It is purely a speed optimization, so don't expect stronger play from pruning alone.
The savings depend heavily on move ordering. Bad ordering degrades it back toward full Minimax's O(b^d).
The cutoff is alpha >= beta. Getting the comparison or which value you update (alpha at MAX, beta at MIN) backwards silently breaks pruning or, worse, prunes valid branches.
Pass alpha and beta by value down the recursion; each node needs its own copy, not a shared mutable one.
It assumes the opponent also plays optimally. Against a weak or random opponent, the 'optimal' move may not be the highest-scoring one in practice.
Like Minimax, it still needs a depth limit and an evaluation function for large games; you rarely search a full game to the end.