Consider the following statement:
In adversarial search, \(\alpha\)–\(\beta\) pruning can be applied to game trees of any depth where \(\alpha\) is the (m) value choice we have formed so far at any choice point along the path for the MAX player and \(\beta\) is the (n) value choice we have formed so far at any choice point along the path for the MIN player.
Which ONE of the following choices of (m) and (n) makes the above statement valid?
Answer
(C)
Explanation
Alpha–beta pruning carries two bounds down the game tree:
- \(\alpha\) is the value MAX can already guarantee along the path. MAX wants large values, so \(\alpha\) is the highest value found so far.
- \(\beta\) is the value MIN can already guarantee. MIN wants small values, so \(\beta\) is the lowest value found so far.
A branch is pruned as soon as \(\alpha \geq \beta\), because the player choosing above it already has a better alternative and would never let play reach it. The other options give MAX, MIN or both the preference of the opponent, so the bounds would no longer be values that player can guarantee.
Answer: C