3.2. THE GAME OF TIC-TAC-TOE
We will use this simple game to illustrate how computers are programmed to play games. We start by assuming that the computer plays first. There are nine squares on the board, so it seems that there are nine initial moves but because of the symmetry of the board we only need to consider three initial positions: center (Fig. 3.2.1a), corner (Fig. 3.2.1b), and side (Fig. 3.2.1c).
 |
 |
 |
| (a) | (b) | (c) |
| Figure 3.2.1: The three possible first play positions in tic-tac-toe, each with an army of ants ready to explore possible plays | ||
If the computer plays the center its opponent has two possible responses, corner (Fig. 3.2.2a) or side (Fig. 3.2.2b).
 |
 |
 |
| (a) | (b) | (c) |
| Figure 3.2.2: (a) and (b) The two possible responses to the computer playing the center. The army of ants has divided itself to follow the plays resulting from each of the two positions. (c) Numbering of the squares of the board for reference in the play descriptions. | ||
We consider the computer response to the position of Figure 3.2.2a. Playing at corner No. 6 is clearly not a good idea because it does pose any threat to the opponent. That leaves corners 0 and 8 and because of symmetry we need consider only one of them, say, 0. Such a move forces opponent to play at the opposite corner, otherwise the computer will win in the next move. The configuration is shown in Fig. 3.2.3a.
 |
 |
 |
(a) |
(b) |
(c) |
| Figure 3.2.3: Possible plays following the position of Fig. 3.2.2a. | ||
In this case the computer must play position 5 and that, in turn, forces the opponent to play position 3 with the result shown in Fig. 3.2.3b. That leaves three possible plays marked with their numbers in Figure 3.2.3c. Position 7 is clearly better because it blocks the opponent from lining up in the bottom row and the game must end in a draw.
We consider now the possibilities for the arrangement of Figure 3.2.2b. Playing at the corners adjacent to the opponents play has the advantage of blocking a lineup and, because of symmetry, it does not matter what corner we play, so let us chose 0. That in turn forces the opponent to play at 8, so we have the arrangement at the top of Fig. 3.2.4a. The next play must be at 3 (shown at the bottom of Fig. 3.2.4a) because that ensures a win. If the opponent plays at 5, the computer plays at 6 and if the opponent plays at 6, the computer plays at 5.
 |
 |
 | |
(a) |
(b) |
| Figure 3.2.4: (a) Follow-up of the arrangement of Figure 3.2.2b. Playing at 3 ensures a win for the computer. (b) Graph of possible plays following a play at the center. | |
Fig. 3.2.4b summarizes what we have covered so far. Starting at the position of Fig. 3.2.1a we go to either the arrangement of Fig. 3.2.2a or the arrangement of Fig. 3.2.2b. The rest of the moves are either forced or have a clear advantage over their alternatives.
If the computer plays at a corner there are eight possible plays for its opponent, but three pairs of positions are symmetric, so we have only five of possibilities. These are shown in Figure 3.2.5.
 |
| Figure 3.2.5: Alternative moves when the computer plays at a corner. |
Figure 3.2.6 shows the graph of possible plays when the computer plays at a corner in its first move and its opponent plays at the center. The leftmost configuration of Figure 3.2.6 is the same as the leftmost configuration of Figure 3.2.5. We have switched to showing successive board position along the horizontal rather than the vertical direction because most of the subsequent moves are forced.
 |
| Figure 3.2.6: The graph of sequences of plays when the computer plays first at a corner and its opponent takes the center. |
If the computer plays at the middle of a side there eight possible plays for its opponent, but three pairs of positions are symmetric, so we have only five of possibilities. These are shown in Figure 3.2.7.
 |
| Figure 3.2.7: Alternative moves when the computer plays at the middle of a side. |
We observe that the leftmost board in Figure 3.2.7 is the same as the board of Figure 3.2.2b with the players switched. That position led to a computer win, so playing on the side may lead to a loss and that move is to be avoided.
Therefore we have a strategy (and, in effect, a computer program design):
First move: If the center is open play there. (It may lead to a win and it will do no worse than a draw according to Fig. 3.2.4.) Otherwise play at a corner. (It will do no worse than a draw according to Fig. 3.2.6.)
Next move after first move was at the center: If the opponent plays at a corner follow the moves shown in the upper path of Figure 3.2.4b. Otherwise follow the moves shown in the lower path of Figure 3.2.4b.
Next move after first move was at the corner: Depending upon the opponent's play follow the moves shown in one of the paths of Figure 3.2.5.
In order to reach a strategy that will do no worse than a draw, we had to consider fewer than 25 moves (count the boards shown in Figures 3.2.4b through 3.2.7). We could write a program that does this search while playing.