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)

Hint:

Evaluate each MIN node first by taking the minimum of its children, then let MAX pick the largest of those results.

Answer 1

Correct Answer: 2

Step 1: Understand the tree structure.
MAX moves first at the root with three choices, labelled strategies 1, 2 and 3, each leading to a MIN node. Each MIN node then has three choices, also labelled 1, 2 and 3, each leading to a terminal (leaf) node with a fixed utility value.

Step 2: Evaluate the MIN node reached by MAX's strategy 1.
Its children have values 8, 6, -1 (for MIN's strategies 1, 2, 3). MIN always picks the move with the minimum value, so this node's value is \(\min(8, 6, -1) = -1\).

Step 3: Evaluate the MIN node reached by MAX's strategy 2.
Its children have values 1, 5, 7. MIN picks the minimum: \(\min(1, 5, 7) = 1\).

Step 4: Evaluate the MIN node reached by MAX's strategy 3.
Its children have values -4, -3, -12. MIN picks the minimum: \(\min(-4, -3, -12) = -12\).

Step 5: Back up the values to the root and let MAX choose.
The root now sees three backed-up values: -1 (from strategy 1), 1 (from strategy 2), and -12 (from strategy 3). MAX always picks the move with the maximum value: \(\max(-1, 1, -12) = 1\), which is reached through strategy 2.

Final Answer:
The best strategy for MAX at the root is strategy 2, which guarantees a game value of 1. \[ \boxed{2} \]