[Next] [Up] [Previous]

The Game of Quadripawn

Let us examine in more detail how game playing by search operates. We will not use chess simply because to show even a tiny part of a chess game tree would take too much space. Rather we shall adopt a small game based on chess, called quadripawn. It is played on a board with 3 files and 3 ranks (or 3 columns and 3 rows if you prefer), using two white pawns and two black pawns. The starting position is shown at the top of figure 4.6.

  [IMAGE ]
Figure 4.6: Part of the game tree for quadripawn.

White moves first, and players take turns, moving one of their own pieces on each move. On any move a piece may either be moved forward one square, if there is nothing in the way, or it may take an opponent's piece that is diagonally in front of it. An opponent's piece directly in front cannot be taken, and acts as a block. The winner is the first player to move one pawn to the far side of the board, or to take both the opponent's pawns, or to prevent the opponent from moving on the next turn.

Figure 4.6 shows the game tree for 2 moves from the start. To illustrate the idea of heuristic game playing, we will suppose our program is restricted to look ahead only 2 moves. (Real chess programs look much further ahead than this.) The program is playing white, and its first problem is to choose one of the two possible starting moves. We need an evaluation function to apply to the boards on the lowest level of the tree. The following simple example will serve, though other functions are possible. Starting from 0

 

• for each white pawn on the middle rank that is not blocked add 1,
• for each black pawn in this state subtract 1,
• if it is white's turn, for every black piece that can be taken on the next move add 1, and
• if it is black's turn, for every white piece that can be taken on the next move subtract 1.

Thus the value may become negative; positive values are good for white, negative ones bad. Figure 4.7 shows how the static value for one of the board states is calculated. In this case there is a white pawn, not blocked, on the middle rank, and the total score is +1. You should confirm that the values assigned to the other board states in the bottom row of figure 4.7 are correct.

  [IMAGE ]
Figure 4.7: A calculation of the static value for a board state.

Now we are in a position to work back up the tree to see what to do on white's first move. From the left-hand state in the middle level, black has a choice of 3 moves, and we guess that the black player would choose the move that is worst for white: the one labelled 0. From the right-hand state, black has a choice of 2 moves and we guess that the choice would be to the one labelled -1. Thus if white takes the left-hand move, the expected value is 0, but for the right-hand move it is -1, so the program's choice should be for the left-hand move with a value of 0. Note that the `good' state labelled +2 plays no part, since we do not expect black to allow the program the opportunity to exploit it. The expected value, calculated by looking ahead and propagating the static values back up the tree, is called a dynamic value.

The strategy is called minimax, and the name comes from the fact that if we think of a move to a board state with a lower value as a loss, then black will always try to maximize the program's loss. The program must seek to minimize its loss -- thus it must choose a move to minimize the the maximum loss that black can inflict.

Powerful chess playing programs are essentially based on a minimax strategy. However, they incorporate many extra ploys to increase their effectiveness, such as avoiding searching branches of the tree that can rapidly be identified as unproductive, and searching deeply in regions where a promising sequence of moves is found. An enormous amount of attention also goes into devising their evaluation functions. Furthermore, they often use specially designed computers to make the generation of possible future board states much faster.

It is unlikely that human chess players work the same way. They do not seem to look ahead as far as the programs, but may depend more heavily on recognizing patterns on the board and remembering successful lines of play that can develop from these patterns. They are probably much more capable of taking advantage of their opponent's characteristic weaknesses in play. Whilst it is possible that chess playing programs may be able to beat all humans in the not too distant future, it is unlikely that they will be simulating the cognitive processes of even a modest human chess player.

[Next] [Up] [Previous]