Coursify

Alpha-Beta Pruning: Why Minimax Gets Faster

Alpha-Beta Pruning: Why Minimax Gets Faster

Verified Sources
Nov 4, 2026

Minimax searches a game tree to choose the optimal move under worst-case play, but its brute-force complexity grows exponentially with depth. alpha-beta pruning improves minimax by using bounds—alpha\\alpha for the best value MAX can guarantee and beta\\beta for the best value MIN can guarantee—to eliminate branches that cannot possibly influence the outcome. This corresponds directly to option (ii) Ignoring non-optimal branches.

A key result from classic analysis is that alpha-beta pruning can reduce the effective number of nodes searched. With good move ordering, the number of terminal evaluations can drop from the naive O(bd)O(b^d) toward O(bd/2)O(b^{d/2}), which is often described as enabling roughly twice the depth for the same time budget. This matches option (i) Increasing the depth (under the usual assumption of good ordering and fixed computation time) rather than option (iii). 2

Mermaid intuition (pruning occurs when bounds cross):

Correct choices (conceptually): (i) and (ii), while (iii) and (iv) are not the mechanism. Alpha-beta does not “double the search time” or “reduce the score of nodes”; it avoids exploring irrelevant subtrees while preserving the correct minimax value. 3

Key terms:

  • Minimax
  • Alpha
  • Beta
  • Pruning

Footnotes

  1. Wikipedia - Alpha–beta pruning (https://en.wikipedia.org/wiki/Alpha%E2%80%93beta_pruning) - Overview and pruning condition/cutoff and complexity discussion. ↩ ↩2

  2. Stanford CS221 (MIT OCW notes/lectures) style references on alpha-beta complexity and depth effect (https://stanford.edu/class/cs234/notes/cs234-notes4.pdf) - Discusses pruning effect and complexity assumptions like move ordering; supports best-case reductions and depth gains. ↩ ↩2

  3. Wikipedia - Minimax and Alpha–beta correctness intuition (https://en.wikipedia.org/wiki/Minimax) - Background on minimax decision rule and how pruning preserves minimax-correct choices. ↩

Alpha-Beta Pruning (Minimax Optimization) Tutorial

How Alpha-Beta Prunes Non-Optimal Branches

  1. 1
    Step 1

    At the start of a MAX node, set α=−∞\alpha=-\infty; at a MIN node, set β=+∞\beta=+\infty (or use appropriate initial values).

  2. 2
    Step 2

    As you evaluate children, update α\alpha at MAX nodes and update β\beta at MIN nodes based on the child values.

  3. 3
    Step 3

    At any node, if α≥β\alpha \ge \beta, further exploration of remaining sibling children cannot change the ancestor’s decision.

  4. 4
    Step 4

    Stop exploring the rest of that subtree (do not evaluate those nodes), returning the best value found so far for that node.

  5. 5
    Step 5

    "Despite skipping work, the returned value equals the minimax value because pruned branches are guaranteed not to affect the final choice."

    Key terms:

    • Cut-off
    • Search tree
    • Correctness

Naive Minimax vs Alpha-Beta (Typical Effect)

Node growth comparison (qualitative): alpha-beta can drastically reduce evaluations, especially with good move ordering.

Mapping the multiple-choice statements

We can classify each option by whether it reflects the mechanism (bounds + pruning) or an unrelated effect.

(ii) Ignoring non-optimal branches — TRUE (core mechanism).
When alphagebeta\\alpha \\ge \\beta, the algorithm proves that further descendants cannot improve the current best decision at an ancestor. Thus it prunes those branches without affecting the minimax result. 2

(i) Increasing the depth — TRUE (typical consequence under fixed time).
Alpha-beta reduces the number of nodes evaluated; for a fixed computation budget, this often allows deeper search (frequently summarized as effectively searching to about twice the depth in the best case).

(iii) Doubling the search time — FALSE (wrong direction).
Alpha-beta aims to reduce work for the same result; it does not double runtime as its purpose. Any “increase in depth” happens because the saved computation can be re-invested in searching deeper, not because the algorithm inherently runs longer. 2

(iv) Reducing the score of nodes — FALSE (doesn’t alter values).
Alpha-beta does not modify state utility values to “reduce scores.” It only skips evaluating subtrees whose values cannot affect the final minimax decision. Returned values remain consistent with minimax.

Key terms:

  • Utility value
  • Move ordering
  • Evaluation function

Footnotes

  1. Wikipedia - Alpha–beta pruning (https://en.wikipedia.org/wiki/Alpha%E2%80%93beta_pruning) - Overview and pruning condition/cutoff and complexity discussion. ↩ ↩2

  2. Wikipedia - Minimax and Alpha–beta correctness intuition (https://en.wikipedia.org/wiki/Minimax) - Background on minimax decision rule and how pruning preserves minimax-correct choices. ↩ ↩2

  3. Stanford CS221 (MIT OCW notes/lectures) style references on alpha-beta complexity and depth effect (https://stanford.edu/class/cs234/notes/cs234-notes4.pdf) - Discusses pruning effect and complexity assumptions like move ordering; supports best-case reductions and depth gains. ↩ ↩2

Why (i) and (ii) go together

"When you prune many branches (ii), you evaluate fewer leaves. With the same time budget, you can often search deeper (i). The exact “how much deeper” depends strongly on move ordering." 2

Footnotes

  1. Stanford CS221 (MIT OCW notes/lectures) style references on alpha-beta complexity and depth effect (https://stanford.edu/class/cs234/notes/cs234-notes4.pdf) - Discusses pruning effect and complexity assumptions like move ordering; supports best-case reductions and depth gains. ↩

  2. Wikipedia - Minimax and Alpha–beta correctness intuition (https://en.wikipedia.org/wiki/Minimax) - Background on minimax decision rule and how pruning preserves minimax-correct choices. ↩

Best-case vs worst-case behavior

"In the worst case, alpha-beta pruning may prune very little, and performance can approach naive minimax (O(bd)O(b^d)). The large gains are typically expected when move ordering is good." 2

Footnotes

  1. Wikipedia - Alpha–beta pruning (https://en.wikipedia.org/wiki/Alpha%E2%80%93beta_pruning) - Overview and pruning condition/cutoff and complexity discussion. ↩

  2. Stanford CS221 (MIT OCW notes/lectures) style references on alpha-beta complexity and depth effect (https://stanford.edu/class/cs234/notes/cs234-notes4.pdf) - Discusses pruning effect and complexity assumptions like move ordering; supports best-case reductions and depth gains. ↩

Common Confusions about Alpha-Beta

From Minimax to Alpha-Beta (Conceptual Roadmap)

Minimax baseline

Step 1

Evaluate the entire relevant game tree assuming optimal opponent play."

Add bounds

Step 2

Maintain α\alpha (best for MAX so far) and β\beta (best for MIN so far)."

Cut-off / prune

Step 3

When α≥β\alpha \ge \beta, prune remaining children of that node."

Reinvest saved computation

Step 4

With fewer evaluated nodes, search deeper under the same time budget."

Alpha-Beta Quick Checks

1 / 4
Question · Term

What triggers pruning in alpha-beta?

Click to reveal
Answer · Definition

When α≥β\alpha \ge \beta at a node, the remaining children cannot affect the final minimax decision.

Knowledge Check

Question 1 of 3
Q1Single choice

Alpha-beta pruning improves minimax primarily by:

Explore Related Topics

1

Shortest Paths in Unweighted Graphs: Why BFS Wins

2

When A* Performs Worse Than Uninformed Search: A Poor Heuristic Case Study

3

Handle Pruning: Its Role in Predictive Parsing (and How It Differs from Other Parsing Paradigms)

Browse all research articles