Computer Engineering is coming soon

We're still writing and reviewing the notes for every subject, and we'll open it when every subject is ready. Meanwhile you can practise aptitude, ask Aria about any subject, or see the branches that are ready.

Alpha–beta pruning

Alpha–beta pruning speeds up minimax search in two-player, zero-sum, perfect-information games by cutting branches that cannot affect the final decision.

Drafted with Aria, reviewed by the AiCanCode.org team · Updated . How we write and check our notes. Spotted an error? Use Give Feedback at the bottom of the page.

Why it matters

Alpha–beta pruning is used by engineers to make game-tree search (minimax) much faster. In practice it lets programs play deeper (more plies) within the same time limit for chess-like, deterministic, perfect-information games or any adversarial search where moves are alternated and utility is numeric.

Key ideas

  • Alpha and beta: alpha is the best (highest) value that the MAX player can guarantee so far on the path to the root. Beta is the best (lowest) value the MIN player can guarantee so far on the path to the root. These are bounds propagated during the depth-first search.

  • Cutoff (pruning): while exploring a node, if alpha >= beta at any point, further siblings (or deeper nodes) cannot change the minimax choice at an ancestor and can be safely pruned (not searched). This does not change the final minimax value under the standard minimax assumptions.

  • Correctness statement (informal theorem): With the standard minimax assumptions (two players, zero-sum, deterministic, perfect information, and either a finite game tree or the same depth limit and evaluation function for cutoff search), alpha–beta pruning returns the same minimax value at the root as the ordinary minimax algorithm (with the same depth limit, if any), but visits no more nodes and often far fewer. Proof sketch: by induction on tree height. Leaves obviously return the same utility. Suppose alpha–beta returns correct minimax on subtrees of height ≤ k; then when working on height k+1, the algorithm either fully evaluates a child (giving correct child minimax) or prunes when an already-known bound makes the child irrelevant; pruning discards only children that cannot affect the ancestor's minimax decision by the definitions of alpha and beta.

  • Assumptions: two-player, alternate-move, zero-sum (utility to MAX is the negative of utility to MIN); terminal tests and utility function are correctly defined; search is depth-limited or finite so recursion terminates.

  • Node ordering matters: the amount of pruning depends on the order in which children are examined. Best ordering (examining best moves first) yields maximum pruning. With optimal ordering, the time complexity can drop from O(b^d) to O(b^{d/2}).

  • What to draw for exam diagrams: draw a small game tree with root (label MAX), next level (label MIN), leaves with numeric utilities. On each internal node annotate current alpha and beta values while traversing left-to-right. Mark any subtree pruned with an 'X' and show which inequality triggered the prune (e.g., alpha >= beta at the MIN node). Show final minimax values at internal nodes and selected best root move.

Formulas

T_minimax = Θ(b^d) — time complexity of simple minimax, where b is branching factor (average number of moves per position) and d is search depth (plies). Applies when no pruning.

  • b: branching factor (moves per node), unitless, average number of child nodes.
  • d: depth in plies (half-moves), unitless.

T_alpha-beta = Θ(b^{d/2}) (best case, with perfect move ordering) — effective branching factor reduced; applies under ideal child ordering producing maximum pruning.

T_alpha-beta = Θ(b^d) (worst case) — no pruning if ordering is bad.

S = Θ(b·d) — typical space complexity for depth-first alpha–beta (stack depth d and up to b children in hand), unitless. Applies to recursive DFS implementation.

alpha, beta ∈ ℝ ∪ {−∞, +∞} — initial values set to -∞ and +∞ at the root.

Worked examples

Example 1 — manual step-by-step (exam-style model answer): Question: Given the tree below, perform alpha–beta pruning and find the minimax value and best root move. Draw the tree and show alpha/beta updates. (Describe the tree as you draw it.) Tree description to draw: Root (MAX) with three children A, B, C (MIN nodes). Each MIN node has two children which are leaves with these utilities: A: leaves 3, 5; B: leaves 2, 9; C: leaves 0, 7. Draw root at top labelled MAX, three child nodes labelled A (left), B (middle), C (right); under each, draw two leaves with their numbers. Steps (left-to-right traversal):

  1. Visit A (MIN): visit A's left leaf 3. At MAX root alpha = -∞, beta = +∞; at A (MIN) current value = 3. Visit A's right leaf 5: MIN chooses min(3,5)=3. So A returns 3. At root, MAX so far best = 3, update alpha = 3.
  2. Visit B (MIN): initial beta = +∞ (in B). Visit B's left leaf 2. For B, min value = 2. Now compare at root: if B can be ≤ 2, root's alpha = 3 means B cannot improve root (MAX already has 3). Before exploring B's right leaf 9, we check alpha >= beta. At B, beta is currently 2 and alpha from the ancestor is 3; since alpha (3) >= beta (2), we prune the remaining subtree under B. So B returns 2 without visiting 9.
  3. Visit C (MIN): visit C's left leaf 0. For C, min currently 0 which is < alpha(3). At this point C cannot give MAX a value better than 3 at the root; however we still must explore until a cutoff triggers. After seeing 0, beta at C becomes 0; alpha at root is 3 so alpha >= beta (3 >= 0) — prune remaining child (7). Result: A returned 3, B returned 2 (with right leaf pruned), C returned 0 (right leaf pruned). MAX chooses the maximum: max(3,2,0) = 3 and the chosen child is A. Comment: We saved exploring two leaf nodes (9 and 7) compared to full minimax.

Example 2 — runnable Python program (complete) that implements alpha–beta and prints best value and move index for a small tree. Copy exactly and run as a script.

# Simple alpha-beta on a tree represented by nested lists and integers for leaves.
# MAX at root, alternates MAX/MIN by depth.

def alphabeta(node, alpha, beta, maximizing):
    # Leaf test: integer -> terminal utility
    if isinstance(node, int):
        return node
    if maximizing:
        value = -float('inf')
        for child in node:
            value = max(value, alphabeta(child, alpha, beta, False))
            alpha = max(alpha, value)
            if alpha >= beta:
                break
        return value
    else:
        value = float('inf')
        for child in node:
            value = min(value, alphabeta(child, alpha, beta, True))
            beta = min(beta, value)
            if beta <= alpha:
                break
        return value


def best_move(root):
    best_val = -float('inf')
    best_index = None
    alpha = -float('inf')
    beta = float('inf')
    for i, child in enumerate(root):
        v = alphabeta(child, alpha, beta, False)
        if v > best_val:
            best_val = v
            best_index = i
        alpha = max(alpha, best_val)
    return best_val, best_index

# Example tree: root (MAX) has 3 MIN children. Each MIN child has 2 MAX children with leaves.
# Represented as nested lists; leaves are integers.

tree = [
    [[3,5], [6,9]],   # child 0
    [[1,2], [0,-1]],  # child 1
    [[7,4], [5,8]]    # child 2
]

value, move = best_move(tree)
print("Best value:", value)
print("Best move index at root:", move)

Sample output when the program runs exactly as above:

Best value: 7 Best move index at root: 2

(Explanation: child 2 yields minimax value 7; alpha–beta pruning avoids some leaf evaluations during the search.)

Common mistakes

  • Forgetting to alternate MAX and MIN roles at each ply.
  • Assuming alpha–beta always reduces work by half; pruning depends on child ordering — worst-case no pruning.
  • Returning the wrong value type (e.g., returning a pair at non-root nodes) when implementing recursively.
  • Confusing depth (plies) with moves: one ply = one player's move, one full move in chess = 2 plies.

For your exam

Kinds of questions:

  • Definitions: define alpha, beta, cutoff, and minimax.
  • Short notes: explain assumptions, advantages, and limitations.
  • Derivations: derive worst-case and best-case time complexities and explain the role of node ordering.
  • Diagrams: draw a small tree and perform alpha–beta pruning step-by-step.
  • Programs: write pseudocode or simple recursive code for alpha–beta.

What a full-marks answer includes:

  • Clear definition of all terms (bold if writing by hand), statement of assumptions (zero-sum, perfect info, deterministic), and the correctness claim.
  • Pseudocode or clean Python with correct alpha/beta updates and pruning conditions.
  • Complexity analysis using branching factor b and depth d with explicit best- and worst-case statements and explanation of impact of child ordering.
  • One worked example with a drawn tree showing alpha and beta at each node and indicating pruned nodes with a reason.

Quick check

  1. What does alpha represent in alpha–beta pruning?
  2. In which case does alpha–beta reduce time from Θ(b^d) to about Θ(b^{d/2})?
  3. What initial values should alpha and beta have at the root?

Answers: 1) The best (highest) value MAX can guarantee so far (a lower bound). 2) In the best case with perfect move ordering (best moves examined first). 3) alpha = −∞, beta = +∞.

Finished this topic? Mark it so your progress, study plan and readiness keep up.

Stuck on something here?