GATE DA 2025 | Question 43

MCQ · 2 marks · −0.66

Consider game trees Tree-1 and Tree-2 as shown. The first level is a MAX agent and the second level is a MIN agent. The value in the square node is the output of the utility function.

Tree-1 (left): MAX root A has a square leaf 2 and a MIN child B, whose square leaves are x and 1, with the edge from B to 1 drawn dotted. Tree-2 (right): MAX root C has MIN children D (square leaves 5 and y) and E (a square leaf 2 and, by a dotted edge, a subtree drawn as a triangle).

For what ranges of \(x\) and \(y\), the right child of node \(B\) and the right child of node \(E\) will be pruned by alpha-beta pruning algorithm?

  1. Option A: \(x \in [1, \infty)\) and \(y \in (-\infty, 2]\)
  2. Option B: \(x \in (-\infty, 2]\) and \(y \in (-\infty, 5]\)
  3. Option C: \(x \in (-\infty, 2]\) and \(y \in [2, \infty)\) (correct)
  4. Option D: \(x \in [1, \infty)\) and \(y \in (-\infty, 5]\)

Answer

(C)

Explanation

Alpha-beta pruning skips the remaining children of a MIN node once its value \(\beta\) can no longer beat the value \(\alpha\) that MAX is already sure of, that is, once \(\beta \le \alpha\).

  • Tree-1: after the leaf 2, MAX at A has \(\alpha = 2\). At B, the leaf \(x\) gives \(\beta = x\). The leaf 1 is pruned when \(x \le 2\), because B is then worth at most 2 and cannot raise A above 2. So \(x \in (-\infty, 2]\).
  • Tree-2: D is searched fully, so \(\alpha = \min(5, y)\) at C. At E, the leaf 2 gives \(\beta = 2\), and the triangle is pruned when \(2 \le \min(5, y)\), i.e. \(y \ge 2\). So \(y \in [2, \infty)\).

Only option C has both ranges.

Answer: C