Does pruning change the root minimax value?

Correct alpha-beta pruning preserves it for the same tree and evaluation rules.

Does it always examine fewer nodes?

No. Poor move ordering can leave little or no opportunity to prune.

Does it prove a depth-limited move is globally optimal?

No. It preserves the result of that limited search, including its evaluation assumptions.

AI Glossary / Graphs and symbolic AI / Intermediate

Alpha-beta pruning

Definition

Alpha-beta pruning is an optimization of minimax search that skips branches proven unable to improve the relevant decision. It maintains bounds on achievable values while exploring a game tree. With correct implementation, it preserves the minimax value at the root for the same tree and evaluation rules while potentially examining fewer positions.

What it means

Minimax models one player, MAX, as seeking a higher score and an opposing player, MIN, as seeking a lower score. It evaluates possible moves by accounting for the opponent's best response.

Alpha-beta pruning avoids completing parts of that calculation when enough is already known to reject them. It does not discard a branch simply because the branch looks unpromising. The current bounds must establish that further examination cannot improve the decision that matters.

The classic setting is a deterministic, two-player, zero-sum game with known rules and perfect information. Variants and extensions exist, but the basic guarantee should not be transferred unchanged to hidden-information games, chance outcomes, or unrelated business decisions.

How it works

Search the tree while carrying two bounds. Alpha records a value MAX can already secure through alternatives considered along the search path. Beta records a corresponding upper bound supplied by MIN's alternatives.

At a MAX node, newly examined children can raise alpha. At a MIN node, they can lower beta. When the bounds meet or cross, remaining children of the relevant node need not be examined for the current decision. Equivalent implementations express the stopping condition using the node's current value and the inherited bound.

Move ordering strongly affects how early useful bounds appear. Examining strong candidate moves first can permit more pruning, while unfavorable ordering may leave little to prune. Ordering changes the work required, not the underlying minimax value of a fixed tree.

If search stops at a depth limit, leaf values come from an evaluation function. Alpha-beta preserves that limited-tree result; it does not turn approximate position evaluations into a proof of the full game's outcome.

Three practical examples

1. A board-game program evaluates candidate moves and avoids fully exploring an opponent response that already makes one candidate inferior to a previously evaluated option.

2. A teaching tool displays the same small game tree under different move orders. Students can see why node counts differ while the root minimax value remains unchanged.

3. A simulator for a precisely specified two-sided competitive task uses pruning within a minimax model. Its conclusions remain conditional on the modeled actions, scores, and opponent assumptions.

Think of it this way

Think of comparing offers where an opponent chooses your final outcome within each offer. Once one offer lets that opponent force a result worse than an alternative you already have, examining all its remaining possibilities cannot make it attractive.

The analogy is limited to the minimax decision structure. In ordinary shopping or negotiation, an opponent may not control the outcome in this exact way. Pruning is justified by the formal bounds, not by a general intuition that you have already seen enough.

Worked example

Consider an original toy tree. MAX chooses between moves L and R. Each leads to a MIN node. L has terminal values 7 and 9, so MIN chooses 7. After fully evaluating L, MAX has an available value of 7, establishing alpha = 7 at the root.

Now examine R. Its first terminal value is 4. Because MIN chooses the smaller available value, R's final value can be no greater than 4, whatever its remaining child contains. Thus R cannot beat L's 7, and its remaining child can be pruned.

If that hidden child were 12, R's exact value would be 4. If it were −3, R's value would be −3. Either way, MAX still prefers L. Ordinary minimax would inspect all four leaves, while this ordering needs only three. The example demonstrates one safe cutoff; it does not promise that every tree loses the same proportion of work.

Illustrative case study

Fictional case: Clover Games compares a plain minimax engine with an alpha-beta version on small positions whose full trees can be checked. One test returns a different root score. The team discovers that a bound from one unrelated search was incorrectly reused in another.

After correcting the bound handling, the two versions agree on the tested root values. The team separately evaluates deeper-search behavior and move ordering. This invented case illustrates verification of the preservation property, not a claim that matching a few tests proves every implementation correct.

Common misconceptions and mistakes

Pruning does not mean the skipped branch is impossible or has no value. Its exact value is simply unnecessary for the current minimax decision.

The algorithm does not guarantee a fixed speedup. Its benefit depends on the tree and move order. It also need not choose the same move among several equally valued alternatives unless tie handling is matched.

Do not confuse a cutoff bound with an exact subtree value. Caching or reporting bounds as exact scores can cause errors. Finally, depth-limited minimax remains dependent on its evaluation function and search horizon, even when pruning itself is mathematically sound.

Business use

The practical value is efficient evaluation of a particular adversarial decision model. The saved work can sometimes support searching deeper within the same time budget, but that benefit should be measured on relevant positions.

When reviewing an implementation, compare it with unpruned minimax on manageable test trees and inspect cutoff conditions, score conventions, and tie behavior. Keep claims about speed separate from claims about decision quality. Faster calculation of a mismatched opponent model does not make that model appropriate for the real task.

Check your understanding

MAX already has a move worth 8. A competing MIN branch has revealed a child worth 5. Can unexplored children raise that MIN branch above 8?

Answer: No. MIN can already choose 5, so the branch's final minimum cannot exceed 5. Its remaining children cannot make it preferable to the available 8.

Related terms

Learn next

Next, trace alpha and beta through a small tree in two different move orders. Compare the root value, visited leaves, and values known exactly versus only bounded after a cutoff.

Sources

Russell and Norvig, official alpha-beta algorithm, Figure 6.7: https://aima.eecs.berkeley.edu/global-algorithms.pdf

University of California, Berkeley, CS188 textbook, Minimax and alpha-beta pruning: https://inst.eecs.berkeley.edu/~cs188/textbook/games/minimax.html

Primary algorithm and teaching explanation were read. All numerical trees and scenarios here are original.

Previous: ALOPEX Next: Alpha blending (feathering)