The GATE Grind

GATE 2024 DA – Question 25

Artificial Intelligence · Search: informed, uninformed and adversarial · 1 mark · Multiple choice

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?

  1. (m) = highest, (n) = highest
  2. (m) = lowest, (n) = highest
  3. (m) = highest, (n) = lowest
  4. (m) = lowest, (n) = lowest

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (C) (m) = highest, (n) = lowest

Explanation

$\alpha$ is the best (highest) value that MAX can already guarantee along the path, and $\beta$ is the best (lowest) value that MIN can already guarantee. A branch is pruned when $\alpha \ge \beta$.