The maximizing player has already found a move guaranteeing a score of at least 7 (alpha = 7). While evaluating a different branch, it discovers the minimizing player can force a score of 5 from that branch. What should alpha-beta pruning do?
AContinue exploring remaining children of this branch to find the exact minimax value
BPrune the remaining children of this branch — the maximizer would never choose it over the guaranteed score of 7
CUpdate alpha to 5 and continue, since 5 is now the new best guaranteed outcome
DUpdate beta to 7, indicating the maximizer has a better option available
This is the core alpha-beta cutoff condition. The maximizer already has an option guaranteeing 7; this new branch lets the minimizer force 5, which is worse for the maximizer. No matter how good the remaining children of this branch might be, the minimizer would choose the 5-option or worse — so the maximizer would never prefer this branch over its guaranteed 7. Pruning the remaining children saves computation without changing the result. Option C is wrong — alpha represents a floor for the maximizer and should only increase, not decrease.
Question 2 Multiple Choice
In the best case, alpha-beta pruning reduces the effective branching factor of a minimax search from b to approximately:
Ab/2 — half the branches are pruned on average
Bb^(2/3) — a two-thirds reduction in branching factor
C√b — allowing the search to reach twice the depth in the same time
Dlog(b) — a logarithmic reduction corresponding to the tree depth
In the best case — when moves are examined in perfect order from best to worst — alpha-beta pruning reduces the effective branching factor to approximately √b. This means the algorithm can search to roughly twice the depth in the same time compared to plain minimax. For chess with branching factor ~35, this means reaching depth 10 instead of 5 with the same node budget. Achieving this best case requires optimal move ordering, which is why practical engines invest heavily in heuristics to examine the most promising moves first.
Question 3 True / False
Alpha-beta pruning always produces the same final move decision as plain minimax, regardless of how moves are ordered.
TTrue
FFalse
Answer: True
This is the key correctness guarantee of alpha-beta pruning. It is purely a computational optimization — it prunes branches that are provably irrelevant because no value from those subtrees could change the maximizer's or minimizer's decision. The cutoff condition (alpha ≥ beta) guarantees that any pruned subtree cannot contain a better option than what is already established. The final move decision is identical to what plain minimax would return; if it ever differed, that would indicate a bug.
Question 4 True / False
Alpha-beta pruning changes the move that minimax would select, which is why game-playing engines prefer it over plain minimax.
TTrue
FFalse
Answer: False
This is a fundamental misconception. Alpha-beta pruning produces exactly the same optimal move as plain minimax — it does not change the result at all. Its advantage is purely computational: it reaches the same answer while examining far fewer nodes, allowing deeper searches within the same time budget. Deeper searches produce stronger play, which is why engines prefer alpha-beta. But the algorithm is not finding a different or better move than minimax would find at the same depth — it is finding the exact same move, faster.
Question 5 Short Answer
Why does move ordering dramatically affect alpha-beta pruning efficiency, and how do practical game engines exploit this without changing the underlying algorithm?
Think about your answer, then reveal below.
Model answer: Alpha-beta cutoffs occur when the current node's value is provably outside the range that could matter (when alpha ≥ beta). If the best moves are examined first, alpha and beta bounds tighten quickly, enabling cutoffs early and often — large subtrees get pruned. If moves are examined worst-first, bounds tighten slowly, cutoffs are rare, and performance degrades to plain minimax. Practical engines improve move ordering through iterative deepening (using results from shallower searches to order moves in deeper ones), killer move heuristics (trying moves that caused cutoffs at sibling nodes), and history tables (tracking which moves have historically been effective). All of these remain within the alpha-beta framework — they only rearrange which children are examined first.
The insight that the same algorithm's performance varies dramatically with input ordering is a general lesson in algorithm design. Alpha-beta is an extreme case: best-case and worst-case performance differ by a factor of b (the branching factor), depending entirely on move ordering. This is why move ordering is as important as the pruning algorithm itself in practical implementations.