GATE 2024 DA Q.25: solution and answer

GATE 2024 · DAQ.25 · 1 mark · MCQ

Consider the following statement:

In adversarial search, $α$ - $β$ pruning can be applied to game trees of any depth where $α$ is the (m) value choice we have formed so far at any choice point along the path for the MAX player and $β$ 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?

(A)
(m) = highest, (n) = highest
(B)
(m) = lowest, (n) = highest
(C)
(m) = highest, (n) = lowest
(D)
(m) = lowest, (n) = lowest

See the question in the paper

Tap to open full size

Answer and solution

ANSWER

The correct choice is (C): (m) = highest and (n) = lowest.

Official answer: CSource: Official answer key, GATE 2024 DA (IISc Bengaluru)

In alpha-beta pruning, $α$ is the value of the best choice found so far along the path for MAX. MAX wants the largest value, so the best choice is the highest value. Hence $α$ can only increase as the search proceeds, and (m) = highest.
$β$ is the value of the best choice found so far along the path for MIN. MIN wants the smallest value, so the best choice is the lowest value. Hence $β$ can only decrease as the search proceeds, and (n) = lowest.
Check against the pruning rule. At a MIN node, once a child value is $\leq α$ , MAX already has a better option elsewhere (a value of at least $α$ ) and will never choose this branch, so the remaining children are pruned. At a MAX node, once a child value is $\geq β$ , MIN already has an option no larger than $β$ and will never allow this branch, so the remaining children are pruned. In both cases pruning happens exactly when $α \geq β$ . This only makes sense if $α$ is the highest value MAX can guarantee and $β$ is the lowest value MIN can force.
Option (A) makes $β$ a highest value, which is not what MIN seeks. Option (B) swaps the two roles. Option (D) makes $α$ a lowest value, which is not what MAX seeks. Only (m) = highest, (n) = lowest describes each player's best guarantee, so the answer is (C).

KEY IDEA

$α$ is the highest value MAX can already guarantee along the path, and $β$ is the lowest value MIN can already force. A branch is pruned as soon as $α \geq β$ .

WATCH OUT FOR

Reading "best choice for MIN" as the highest value. Best for MIN is the lowest value, so $β$ tracks the lowest value and only decreases. Mixing up the two bounds also flips which comparison ( $\leq α$ at MIN nodes, $\geq β$ at MAX nodes) triggers pruning.

From the GATE 2024 DA paper. Every question of this paper · Download the full paper · All 7 Search questions, with notes

GATE 2024 DA Q.25: solution and answer

Answer and solution

More Search questions