Adversarial Search

GATE DA previous year questions · 2 questions

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?

\(x \in [1, \infty)\) and \(y \in (-\infty, 2]\) \(x \in (-\infty, 2]\) and \(y \in (-\infty, 5]\) \(x \in (-\infty, 2]\) and \(y \in [2, \infty)\) \(x \in [1, \infty)\) and \(y \in (-\infty, 5]\)

Explanation

Answer: (C)

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

GATE DA 2024 | Question 25

MCQ · 1 mark · −0.33

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?

(m) = highest, (n) = highest (m) = lowest, (n) = highest (m) = highest, (n) = lowest (m) = lowest, (n) = lowest

Explanation

Answer: (C)

Alpha–beta pruning carries two bounds down the game tree:

\(\alpha\) is the value MAX can already guarantee along the path. MAX wants large values, so \(\alpha\) is the highest value found so far.
\(\beta\) is the value MIN can already guarantee. MIN wants small values, so \(\beta\) is the lowest value found so far.

A branch is pruned as soon as \(\alpha \geq \beta\), because the player choosing above it already has a better alternative and would never let play reach it. The other options give MAX, MIN or both the preference of the opponent, so the bounds would no longer be values that player can guarantee.

Answer: C