IAE Academy

GATE 2026 DA Q.30: solution and answer

GATE 2026 · DAQ.30 · 1 mark · NAT

Consider the game tree for a two-player turn-taking minimax game as shown in the figure. The value of a terminal node represents the utility of the game state if the game ends there. The numbers written next to the edges denote the strategies.

There are two players MAX and MIN. At any particular state of the game, MAX prefers to move to a state of maximum value. On the other hand, MIN prefers to move to a state of minimum value.

Suppose MAX starts the game at the root and has three strategies: 1, 2 and 3. Next, MIN plays and also has three strategies: 1, 2 and 3. The game ends there. Both players always take optimal strategies throughout the game.

At the root, the best strategy for MAX is ____________ . (Answer in integer)

GATE 2026 DA question 30: A three-level game tree.Tap to open full size
Figure from the GATE 2026 DA paper. It is part of the question.
Figure description

A three-level game tree. The root is a MAX node (upward triangle). It has three edges labelled 1, 2 and 3 (left to right) leading to three MIN nodes (downward triangles). Each MIN node has three edges labelled 1, 2, 3 (left to right) leading to terminal nodes (upward triangles). Terminal values under the first MIN node (edge 1 from root): 8, 6, -1. Under the second MIN node (edge 2): 1, 5, 7. Under the third MIN node (edge 3): -4, -3, -12. Level labels MAX (root) and MIN (middle) are written at the left.

Answer and solution

ANSWER

The best strategy for MAX at the root is strategy 2, which gives a game value of 1.

Official answer: 2Source: Official answer key, GATE 2026 DA (IIT Guwahati)

  1. MIN moves at the second level and picks the smallest value among its children, so first back up the value of each MIN node.

  2. Left MIN node (reached by root strategy 1): .

  3. Middle MIN node (reached by root strategy 2): .

  4. Right MIN node (reached by root strategy 3): .

  5. MAX at the root picks the largest backed-up value: .

  6. The value comes from the middle MIN node, which is the child reached by the edge labelled .

  7. So the best strategy for MAX is strategy , and the game value is .

KEY IDEA

In minimax, back up values from the leaves. MIN nodes take the minimum of their children and MAX nodes take the maximum. The question asks for the edge label (the strategy), not the game value.

WATCH OUT FOR

Giving the game value (1) instead of the strategy number (2). The other slip is taking the maximum at the MIN level, which would pick strategy 1 (leaf 8 beats 7 and -3).

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

More Search questions