Robotics Reference
In-Depth Information
an evaluation function is, the slower it will be in its computation of the
score for a position. Determining the best balance when faced with such
choices is one of the factors that makes games programming such a chal-
lenging and interesting task.
How Computers Look Ahead
Just as human Chess players look ahead when they are planning their
strategy and trying to defend against their opponent's plans, so a Chess-
playing computer program needs to “think ahead”, to analyse the future
consequences of its choice of moves. Otherwise the program may well
make a move which appears superficially to be quite strong but which,
in fact, is easily refuted by an even stronger counter-move that the op-
ponent could play in reply. When a human Chess grandmaster looks
ahead, his whole analytical search rarely encompasses much more than
100 positions. His expertise is such that he can immediately discard
from his thought processes almost all of the possible moves in any posi-
tion, knowing from experience that they cannot possibly be relevant. He
can do this because his own evaluation function, i.e., his instinct, allows
him to concentrate on only those moves that might be fruitful.
The device employed by many game playing programs to look ahead
is called a search tree.
4
Computer trees are not peculiar to game-playing
programs but are used to help solve a variety of decision-making com-
putational problems. Like the arborial variety, computer trees have roots
and branches, but traditionally they are drawn as growing downwards
rather than up towards the sky.
The position in which the program is considering its move is the root
of the tree. Each branch of the tree represents one legal move, and the
position at the lower end of that branch arises on the Chessboard when
the move corresponding to that branch is made. A simple tree is shown
in Figure 19.
Here the position P
0
, the root of the tree, is the one from which the
program must select a move. If the program follows the branch that
represents the move of its rook from the square a5 to the square a6, then
it will reach position P
1
. If it chooses the branch representing the move
of its rook to the square a7, then it will reach position P
2
,
and similarly
for the move by the rook to the square a8 (position P
3
) and the capture
by the rook of the black pawn on the square a4 (position P
4
). These
4
The word “tree” reflects its branching nature.
