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)
Show Hint
Evaluate each MIN node first by taking the minimum of its children, then let MAX pick the largest of those results.
Minimax works from the leaves upward: figure out what each MIN node will do first, since MIN moves right after MAX, then let MAX pick the best of those outcomes.
List the three MIN nodes with the leaf values under each:
MAX's move
Leaf values under that MIN node
MIN picks (smallest)
Strategy 1
8, 6, -1
-1
Strategy 2
1, 5, 7
1
Strategy 3
-4, -3, -12
-12
MIN always wants to steer the game toward the lowest possible utility for MAX, so each MIN node's value is just the smallest of its three children. That gives $-1$, $1$, and $-12$ for MAX's three options.
Now step up one more level. MAX gets to choose which of these three backed-up values to walk into, and MAX always wants the largest one. Comparing $-1$, $1$, and $-12$, the largest is $1$, coming from strategy 2.
So playing optimally, MAX should choose strategy 2 at the root, since every other strategy leads to a worse (smaller) guaranteed outcome once MIN responds optimally.
