Consider the game of Tic-Tac-Toe (also called Noughts and Crosses), which is played by two players, an “X” player and an “O” player who alternate putting their symbol in a blank space on a $3\times 3$ game-board. A player’s goal is to win by placing three symbols in a row, column, or diagonal; the game ends when a player wins or the board is filled. In the game shown below, player O has just made its third turn. It is X’s turn to make its fourth move. The playing agent needs to decide intelligently which of the available 3 moves X should choose next: X1, X2, or X3. We have started the search tree, with three branches for the three possible moves for X:

Draw the rest of the game tree. Assume the value of the tree is +1 for an X win, $-1$ for an O win, and 0 for a draw. Show how the values are backed up to give a value for each of the nodes. What should $X$ do? Is it likely to win, lose or draw?

Could $\alpha$-$\beta$ pruning prune any of the tree?

For the hawk–dove game of Example 11.11, where $D>0$ and $R>0$, each agent is trying to maximize its utility. Is there a Nash equilibrium with a randomized strategy? What are the probabilities? What is the expected payoff to each agent? (These should be expressed as functions of $R$ and $D$). Show your calculations.

Which of the following games in normal form have a Nash equilibrium made up of pure strategies? For those that do, specify the pure strategy Nash equilibria. For those that do not, explain how you know there is no pure strategy Nash equilibrium.

1. (a)

   		Player 2
   		a2	b2
   Player 1	a1	10,10	110,0
   	b1	0,110	100,100

2. (b)

   		Player 2
   		a2	b2
   Player 1	a1	10,10	11,20
   	b1	0,11	20,1

3. (c)

   		Player 2
   		a2	b2
   Player 1	a1	10,20	5,10
   	b1	7,11	20,12

In Example 11.12, what is the Nash equilibrium with randomized strategies? What is the expected value for each agent in this equilibrium?

Consider the following normal-form game where the row player can choose action $A$, $B$ or $C$ and the column player could choose action $D$, $E$, or $F$:

where the pairs give the value of the outcome for the row player followed by the value for the column player.

1. (a)

   When eliminating dominant strategies, what strategies (if any) can be eliminated? Explain what is eliminated, and what cannot be eliminated.

2. (b)

   Specify a Nash equilibrium for this game. (For a randomized strategy, give just the actions that are randomized; you do not need to give the probabilities). Explain why it is a Nash equilibrium.

3. (c)

   Is there more than one Nash equilibrium? If so, give another one. If not explain why there is no other one.

4. (d)

   If the agents could coordinate, could they get a better outcome than in a Nash equilibrium? Explain why or why not.

Answer the same questions as in the previous exercise for the following games:

1. (a)

2. (b)

Consider the sequential prisoner’s dilemma.

1. (a)

   Suppose the agents play for a fixed number of times (say three times). Give two equilibria if there are two or more, otherwise give the unique equilibrium and explain why there is only one. Hint: Consider the last time first.

2. (b)

   Suppose there is a discount factor of $\gamma$, which means there is a probability $\gamma$ of stopping at each stage. Is tit-for-tat a Nash equilibrium for all values of $\gamma$? If so, prove it. If not, for which values of $\gamma$ is it a Nash equilibrium?