Alpha-Beta Pruning Theory Guide

Rules & Common Mistakes

• Exam Trap: Use $\ge$ Not $>$ — They Are Not The Same

  The pruning condition is $\alpha \ge \beta$, not $\alpha > \beta$. When $\alpha$ and $\beta$ are exactly equal, the branch is still dead — MAX cannot do better than what MIN has already capped the path at. If you use strict inequality, you will evaluate nodes that should be pruned and lose marks on any tree where equal values appear at the boundary. This comes up constantly in exam questions specifically because professors know students get it wrong.
• Exam Trap: $\alpha$ and $\beta$ Are Passed Down, Not Shared Globally

  This is the most common source of cascading wrong values in a manual trace. $\alpha$ and $\beta$ are not global variables sitting on a whiteboard that every node reads from. Each node receives a copy of its parent's current bounds at the moment it is visited. When a sibling branch updates $\alpha$ at a MAX node, that updated value is passed down to the next child — it does not teleport back up to nodes you already evaluated. Trace the tree like a DFS call stack: each recursive call carries its own snapshot of the bounds.
• The Update Rule: MAX Raises the Floor, MIN Lowers the Ceiling

  This is the rule to write at the top of your exam trace. At a MAX node: compare the returned value against $\alpha$ — if it is higher, update $\alpha$. Then pass $\beta$ down to the next child completely unchanged. At a MIN node: compare the returned value against $\beta$ — if it is lower, update $\beta$. Then pass $\alpha$ down completely unchanged. Both values travel together at every node. The difference is which one each node type is responsible for tightening.
• Pro Tip: In Exams, Move Ordering Is Already Set For You

  Move ordering only affects *how many* branches get pruned — it never changes the final answer. In an exam question, the tree is given to you left-to-right and that order is fixed. Your job is not to reorder it; your job is to correctly identify every branch that gets cut given that order. If the best moves happen to be on the right side, you will prune less — that is intentional in harder exam questions designed to test whether you can trace a near-worst-case tree accurately.

Strengths, Weaknesses & When To Use It

When to use it:Use Alpha-Beta Pruning any time your exam question or implementation calls for Minimax — it is a strict upgrade, not an alternative. The only scenario where you would deliberately use plain Minimax instead is when a question explicitly asks you to demonstrate the unoptimized baseline, or when you need to count exactly how many nodes a full tree evaluation visits. In every real implementation context, Alpha-Beta is the default. There is no performance downside — worst case, it degrades gracefully back to standard Minimax behaviour.

Alpha-Beta Pruning vs. Standard Minimax

Most students treat Alpha-Beta Pruning and Minimax as two separate algorithms competing for the same job. They are not. Alpha-Beta is Minimax — with one surgical addition: a mechanism that recognises when a branch cannot possibly affect the root decision and stops searching it. Everything else is identical. Same recursion. Same player logic. Same final answer. The only question is how many nodes each version has to visit to get there.

• Node Evaluation: Minimax visits every single node in the tree — it has no mechanism to skip anything, regardless of what it has already found. Alpha-Beta tracks a running floor $\alpha$ and ceiling $\beta$ and stops expanding any subtree the moment $\alpha \ge \beta$. Minimax is unconditional. Alpha-Beta is conditional.
• Correctness Guarantee: Minimax derives its answer by evaluating every possible outcome, so its correctness is trivially guaranteed by exhaustion. Alpha-Beta skips entire subtrees yet returns the identical root value — because every pruned branch is mathematically proven unable to change the outcome. One is correct by brute force; the other is correct by proof.
• Performance Profile: Minimax has fixed, predictable performance — always $O(b^m)$, regardless of tree shape or move order. Alpha-Beta has variable performance: $O(b^{m/2})$ in the best case down to $O(b^m)$ in the worst. Minimax never wastes work, but it never saves any either. Alpha-Beta can save enormous amounts of work — but only if stronger moves appear early in the search.
• Real-World Applicability: Minimax becomes computationally unusable in games with high branching factors because it cannot skip anything. Alpha-Beta's halved exponent at best-case ordering means it can search to twice the depth in the same time — for a chess engine at $b = 35$, that is the difference between seeing 6 moves ahead and seeing 12. This is why every serious game-playing AI uses Alpha-Beta rather than raw Minimax.

Implementation Pseudocode

// alpha = guaranteed floor on this path — the best MAX can already secure from root to here
// beta  = guaranteed ceiling on this path — the best MIN can already secure from root to here
// Prune when alpha >= beta: the floor has met or crossed the ceiling — this branch is irrelevant

function alphaBeta(node, depth, alpha, beta, isMaximizing):

    // BASE CASE: Reached a leaf or the depth limit — return the node's utility value
    if depth == 0 or node is a terminal node:
        return node.value


    // ── MAX'S TURN ──────────────────────────────────────────────────────
    if isMaximizing:

        // Start at absolute floor — so low that the first real value will always beat it
        bestValue = -Infinity

        for each child in node.children:

            // Recurse: pass current floor and ceiling down to the child
            childValue = alphaBeta(child, depth - 1, alpha, beta, false)

            // max(a, b): returns whichever value is higher — raises bestValue if child is better
            bestValue = max(bestValue, childValue)

            // max(a, b): raises the guaranteed floor if bestValue exceeds the current alpha
            alpha = max(alpha, bestValue)

            // BETA CUTOFF: floor has met or crossed the ceiling
            // MIN already holds a ceiling (beta) lower than MAX's guaranteed floor (alpha)
            // MIN will never allow the game to reach this node — prune all remaining children
            if alpha >= beta:
                break

        return bestValue


    // ── MIN'S TURN ──────────────────────────────────────────────────────
    else:

        // Start at absolute ceiling — so high that the first real value will always beat it
        bestValue = +Infinity

        for each child in node.children:

            // Recurse: pass current floor and ceiling down to the child
            childValue = alphaBeta(child, depth - 1, alpha, beta, true)

            // min(a, b): returns whichever value is lower — drops bestValue if child is better
            bestValue = min(bestValue, childValue)

            // min(a, b): lowers the guaranteed ceiling if bestValue falls below the current beta
            beta = min(beta, bestValue)

            // ALPHA CUTOFF: floor has met or crossed the ceiling
            // MAX already holds a floor (alpha) higher than MIN's guaranteed ceiling (beta)
            // MAX will never choose this path — prune all remaining children
            if alpha >= beta:
                break

        return bestValue


// ── INITIAL CALL (always start with widest possible window) ──────────
// alphaBeta(rootNode, maxDepth, -Infinity, +Infinity, true)

Time & Space Complexity

Alpha-Beta Exam Questions Students Always Get Wrong

• Will I get a different answer than Minimax if I prune branches? How do I prove I won't?

  You will get the identical answer — always, without exception. Here is the one-sentence proof you can write on an exam: every branch that Alpha-Beta prunes is one the opponent would never permit the game to reach, because a better option already exists for them elsewhere in the tree. A branch that can never be reached cannot influence the root value. If your examiner asks you to justify this, state it exactly that way: the pruned branches are strategically unreachable, therefore irrelevant, therefore safe to remove.

• I keep mixing up Alpha Cutoff and Beta Cutoff. Which one fires where?

  Anchor it to who raises the floor and who lowers the ceiling. A Beta Cutoff fires at a MAX node: MAX keeps raising the guaranteed floor $\alpha$ until $\alpha \ge \beta$. MIN already holds a ceiling lower than MAX's floor — MIN will never allow the game to reach this node. Prune the remaining children of that MAX node. An Alpha Cutoff fires at a MIN node: MIN keeps lowering the guaranteed ceiling $\beta$ until $\alpha \ge \beta$. MAX already holds a floor higher than MIN's ceiling — MAX will never choose this path. Prune the remaining children of that MIN node. The memory trick: the cutoff is named after the bound that gets *overrun*. In a Beta Cutoff, $\alpha$ rises until it overruns $\beta$. In an Alpha Cutoff, $\beta$ drops until $\alpha$ overruns it. Beta Cutoff — $\beta$ is the victim. Alpha Cutoff — $\alpha$ is the aggressor.

• What happens on my exam if the tree is ordered badly — worst moves on the left?

  Nothing breaks — the answer is still correct. What changes is how much work you have to show. With reverse ordering, $\alpha$ and $\beta$ bounds stay wide for the entire traversal because every node you visit is worse than the previous one. No cutoff condition ever triggers. You end up evaluating every single node — exactly like standard Minimax — and your working will show no pruned branches at all. If an exam question gives you a tree with weak moves on the left and asks 'how many nodes does Alpha-Beta evaluate?', the answer may simply be: all of them. That is not an error. That is the worst case, and recognising it is the correct answer.

• Do alpha and beta reset to $-\infty$ and $+\infty$ at every new node I visit?

  No — and this is the mistake that causes entire exam traces to collapse. $\alpha$ and $\beta$ are inherited from the parent node at the moment of the recursive call. Each node receives a snapshot of the bounds that were current when its parent visited it. They do not reset. Think of it as a phone call: when the parent calls the child, it passes its current $\alpha$ and $\beta$ as arguments. The child works with those values and may tighten them further — but it starts from where the parent left off, never from scratch.

• On an exam, what do I actually write when a cutoff fires?

  Three things, in this order. First, write the condition that triggered it: $\alpha \ge \beta$ with the actual numbers (e.g., $5 \ge 2$). Second, name the cutoff type correctly: a Beta Cutoff fires at a MAX node, an Alpha Cutoff fires at a MIN node. Third, cross out or clearly mark the remaining unevaluated children with a note like 'pruned' or 'not evaluated'. Do not leave it ambiguous — examiners need to see that you know *why* those nodes are crossed out, not just that you stopped there. A crossed-out branch with no label gets no marks for the pruning step even if the final root value is correct.