How Computers Play Games - Robots Unlimited: Life in a Virtual Age - page 74

P 0

r a5-a6 r a5-a7 r a5-a8 r a5xa4

P 1 P 2 P 3 P 4

Figure 19. A Chess tree for a position in which White has four possible moves (originally
printed in the author's topic Chess and Computers (Computer Science Pr, Rockville, MD,
1976))

five positions and four branches make up a small tree, whose depth is
one half-move, 5 also called one ply . By evaluating all the positions at the
lower extremities of the tree (called the leaf positions) the program can
decide which move to make. In this example the decision is simple—the
score for position P 3 is beyond the values of the other three positions
(P 1 ,P 2 and P 4 ) because the move by the white rook to a8 is checkmate;
the capture of the black pawn on a4 gains one unit of material; whereas
neither of the other moves gains any material. Clearly the correct choice
of move is that of the white rook to a8.
Now let us grow a slightly larger tree (see Figure 20 ) in order to see
how a program looks ahead more than one half-move. Each Chess posi-
tion on a diagram of a look-ahead tree is represented by a large dot. 6
This tree has been grown to a depth of two half-moves. The program
is thinking about which move to choose from the root position P 0 .Itcan
move to position P 1 , when its opponent will have the choice of moving
to P 11 ,P 12 or P 13 , or the program could move from the root to position
P 2 , when its opponent will have the choice of moving to P 21 ,P 22 or P 23 .
Associated with each of these six positions at a depth of two-ply there is a
score, obtained from the evaluation function, that measures how good or

5 A half-move in Chess program parlance means a move by one player, White or Black.
6 In computer parlance this is called a node.