The GATE Grind

GATE 2025 DA – Question 43

Artificial Intelligence · Search: informed, uninformed and adversarial · 2 marks · Multiple choice

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.

[Figure: Tree-1 has the MAX root A with a leaf of value 2 on the left and a MIN node B on the right. B has the leaf x on its left and the leaf 1 on its right (dotted). Tree-2 has the MAX root C with two MIN nodes D and E. D has the leaves 5 and y. E has the leaf 2 on its left and an unexplored subtree on its right (dotted).]

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?

Diagram for GATE 2025 DA question 43
  1. $x \in [1, \infty)$ and $y \in (-\infty, 2]$
  2. $x \in (-\infty, 2]$ and $y \in (-\infty, 5]$
  3. $x \in (-\infty, 2]$ and $y \in [2, \infty)$
  4. $x \in [1, \infty)$ and $y \in (-\infty, 5]$

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (C) $x \in (-\infty, 2]$ and $y \in [2, \infty)$

Explanation

In Tree-1 the root $A$ already has the value 2 from its left child, so $\alpha = 2$. At $B$ (a MIN node) the first child is $x$, so $B \le x$. The remaining child of $B$ can be pruned once $B$ cannot beat $\alpha$, that is $x \le 2$. In Tree-2, node $D$ gives the root the value $\min(5, y)$, so $\alpha = \min(5, y)$. At $E$ the first child is 2, so $E \le 2$, and the right child of $E$ is pruned when $2 \le \alpha = \min(5, y)$, which means $y \ge 2$. So $x \in (-\infty, 2]$ and $y \in [2, \infty)$.