GATE DA 2026 | Question: 20

Question

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)

 

Answer 1

As per given tree,MAX moves first, then MIN moves.

Both play optimally.

 

Branch 1 (MAX chooses strategy 1)

Leaf utilities: 8, 6, -1

MIN chooses the minimum:
\[
\min(8, 6, -1) = -1.
\]

So value of Branch 1 is:
\[
-1.
\]

 

Branch 2 (MAX chooses strategy 2)

Leaf utilities: 1, 5, 7

MIN chooses:
\[
\min(1, 5, 7) = 1.
\]

So value of Branch 2 is:
\[
1.
\]

 

Branch 3 (MAX chooses strategy 3)

Leaf utilities: -4, -3, -12

MIN chooses:
\[
\min(-4, -3, -12) = -12.
\]

So value of Branch 3 is:
\[
-12.
\]

 

At the root, MAX chooses the maximum among:

\[
-1, \quad 1, \quad -12.
\]

 

\[
\max(-1, 1, -12) = 1.
\]

This corresponds to strategy 2.

 

Final Answer:
\[
{2}
\]