GATE 2025 DA Q.43: solution and answer

GATE 2025 · DAQ.43 · 2 marks · MCQ

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?

GATE 2025 DA question 43: Two game trees. — Figure from the GATE 2025 DA paper. It is part of the question.

(A)
$x \in [1, \infty)$ and $y \in (- \infty, 2]$
(B)
$x \in (- \infty, 2]$ and $y \in (- \infty, 5]$
(C)
$x \in (- \infty, 2]$ and $y \in [2, \infty)$
(D)
$x \in [1, \infty)$ and $y \in (- \infty, 5]$

Answer and solution

ANSWER

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

Official answer: CSource: Official answer key, GATE 2025 DA (IIT Roorkee)

Pruning rule: at a MIN node, once its running value is $\leq α$ (the best value MAX can already guarantee on the path to the root), the remaining children are pruned, because MAX would never choose this node.
Tree-1: $A$ is MAX. Its left child is the leaf $2$ , so after the left branch $α = 2$ at $A$ .
$B$ is MIN and its left leaf is $x$ , so $B$ 's running value is at most $x$ . The right child of $B$ (the leaf $1$ ) is pruned exactly when $x \leq α = 2$ , that is $x \in (- \infty, 2]$ .
Tree-2: $C$ is MAX. Its left child $D$ is MIN with leaves $5$ and $y$ , so $D = min (5, y)$ and $C$ gets $α = min (5, y)$ .
$E$ is MIN. Its first leaf is $2$ , so $E$ 's running value is at most $2$ . The right child of $E$ is pruned exactly when $2 \leq α = min (5, y)$ .
$2 \leq min (5, y)$ holds only if both $2 \leq 5$ (always true) and $2 \leq y$ . So $y \in [2, \infty)$ .
Both pruning conditions must hold together: $x \in (- \infty, 2]$ and $y \in [2, \infty)$ , which is option (C).

KEY IDEA

A MIN node stops searching its remaining children as soon as its running value drops to $α$ or below, where $α$ is the best value MAX has already secured from earlier siblings. Pruning therefore needs the first child to be $\leq α$ .

WATCH OUT FOR

Comparing $x$ with the pruned leaf $1$ instead of with $α = 2$ , which gives $x \geq 1$ . Another slip is forgetting that $α$ in Tree-2 is $min (5, y)$ , not $y$ , and writing $y \leq 5$ or $y \leq 2$ .

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

GATE 2025 DA Q.43: solution and answer

Answer and solution

More Search questions