In a game of tic-tac-toe, the first player has three different choices at the first move: the…
In a game of tic-tac-toe, the first player has three different choices at the first move: the center square, a corner square, or a side square. The second player then has different alternatives depending upon the move of the first player. For instance, if the first player chooses a corner square, the second player can select the center square, the opposite corner, an adjacent corner, an opposite side square, or an adjacent side square. We can picture the possible outcomes for the game in a decision tree as follows:
Nodes ➀ correspond to decision points for the first player; nodes ➁ are decision points for the second player. The tree is constructed in this manner by considering the options available to each player at a given turn, until either one player has won the game (i.e., has selected three adjacent horizontal or vertical squares or the squares along one of the diagonals), or all nine squares have been selected. In the first case, the winning player receives 1 point; in the second case the game is a draw and neither player receives any points.
The decision-tree formulation of a game like that illustrated here is called an extensive form formulation. Show how the game can be recast in the linear-programming form (called a normal form) discussed in the text. Do not attempt to enumerate every strategy for both players. Just indicate how to construct the payoff tables.
[Hint: Can you extract a strategy for player 1 by considering his options at each decision point? Does his strategy depend upon how player 2 reacts to player 1’s selections?]
The remaining exercises extend the theory developed in this chapter, providing new results and relating some of the duality concepts to other ideas that arise in mathematical programming