1 This exercise considers two-player MDPs that correspond to zero-sum, turn-taking games. Let the players be A...

1 This exercise considers two-player MDPs that correspond to zero-sum, turn-taking games.

Transcribed Image Text:

Let the players be A and B, and let R(s) be the reward for player A in state s. (The reward for B is always equal and opposite.) a. Let UA(s) be the utility of state s when it is A's turn to move in s, and let UB(s) be the utility of state s when it is B's turn to move in s. All rewards and utilities are calculated from A's point of view (just as in a minimax game tree). Write down Bellman equations defining UA(s) and UB(s). b. Explain how to do two-player value iteration with these equations, and define a suitable termination criterion. c. Consider the game described in Figure 17 of the chapter "Adversarial Search." Draw the state space (rather than the game tree), showing the moves by A as solid lines and moves by B as dashed lines. Mark each state with R(s). You will find it helpful to arrange the states (SA, SB) on a two-dimensional grid, using SA and SB as "coordinates." d. Now apply two-player value iteration to solve this game, and derive the optimal policy.