GATE 2025 DA – Question 43
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.
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?

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)$.
More Search: informed, uninformed and adversarial questions
- GATE 2025 DA Q44
- GATE 2024 DA Q23
- GATE 2024 DA Q25
- GATE 2024 DA Q44
- GATE 2026 DA Q13
- GATE 2026 DA Q30
All Search: informed, uninformed and adversarial questions →