3.1. GAME STRATEGIES
In a game, such as chess, that does not involve chance, there is strategy that, in theory, can determine a way for playing that will not lose the game, or win it (if that is possible). One can start with all possible moves by one player, then, for each one, consider all possible moves by the second player, and so forth. When all possible sequences of moves have been considered we look for an opening move that leads to a win (a mate in chess) no matter what the opponent does. If such an opening does not exist we look for one a move that leads to a draw. We play that move and depending on the opponents move, we pick up the most advantageous move from one of the sequences we have constructed.
You can think of am army of ants that at each position divides itself into parts equal to the number of possible moves. For a simple game like Tic-Tac-Toe one third of the ants is going to follow a play at the center, another third a play at a corner, and the last third a play at a side. The group that follows the play at the center will divide again into parts, one for a play at a corner and another for a play at a side. Figure 3.1.1 shows some of the initial subdivisions of the army of ants.
 |
 |
|
 |
|
 |
|
||||||||||
 |
|
 |
 |
|
 |
|
 |
 |
|
 |
|
 |
||||
| .... | .... | .... | .... | .... | .... | .... | .... | |||||||||
Figure 3.1.1: An army of ants following different plays for the game of Tic-Tac-Toe. We show only a few of the possible plays. |
||||||||||||||||
Eventually the ants reach the end of the play and report back the result. Amongst there may be a path that leads to a win for the first player, no matter what the opponent does. If such a path does not exist there should be a path that leads to a draw by the first player, no matter what the opponent does. The moves of the best path are saved for future plays, or in the case of a computer playing the game, included in the game program.
This exhaustive search strategy can be used in a simple game like Tic-Tac-Toe because the number of possible plays is small. There are 9 possible first moves, 8 possible second moves, 7 possible third moves, etc, so that the number of possible sequences is 9x8x7x6...x2x1 or 362,880. Because of the symmetry of the board the number of moves that are not forced is much smaller, about 25. Section 3.2 describes in detail the exhaustive search strategy for Tic-Tac-Toe that leads to the conclusion that whoever plays the center of the board ensures at least a draw.
The trouble with such an exhaustive search strategy is that for most games the number of possible move combinations is too large for either a human or computer search. For example, in chess, the number of positions that need to be examined by looking 30 moves ahead exceeds 1060, or 1 followed by 60 zeros. (There are probably no more than 1015 ants on earth, so we have to import them from other planets.) Human players play by eliminating most of the possible moves and considering only the most promising sequences. Before 1970 computer programs for chess (and other games such as checkers) tried to emulate the human strategy without much success.
All this changed when Ken Thompson (then at Bell Labs) hit upon a different idea. Because computers are much faster than humans it would be feasible to consider all combinations of possibilities for at least a few moves. Such brute force approach could look a few moves ahead and the resulting positions would be given scores according to known chess practice. The play that led to the best position would then be chosen. Such limited exhaustive search strategies proved very useful and eventually led to the chess machine Deep Blue that beat the human world champion Garry Kasparov in 1997. We will return to computer chess in Section 3.4 after discussing first some simpler games.
Checkers is the most complex game for which the exhaustive search strategy has been carried to its completion. This was announced in 2007 after many years of computations. We describe that effort in Section 3.3.
Computers have also been programmed to play other games besides board games such as chess and checkers.
Scrabble® is a game with incomplete information where each player does not know the tiles the other player has. In addition, the play must rely on information from a dictionary of legitimate words and the latter feature makes it quite different than board games such as chess and checkers. ADD
The most ambitious project to computerized a game based on knowledge is Jeopardy. ADD