Robotics Reference
In-Depth Information
P
0
(S
0
)
Depth 1
P
1
(S
1
)
P
2
(S
2
)
Depth 2
P
11
(S
11
)
P
13
(S
13
)
P
12
(S
12
)
P
21
(S
21
)
P
22
(S
22
)
P
23
(S
23
)
Figure 20.
A Chess tree of depth two half-moves (originally printed in the author's topic
Chess and Computers
(Computer Science Pr, Rockville, MD, 1976))
bad that position is from the perspective of the program. These scores are
indicated in Figure 20 as S
11
,S
12
,S
13
,S
21
,S
22
and S
23
.Iftheprogram's
opponent had to choose a move from position P
1
, and if it chose its best
option, it would move to whichever of P
11
,P
12
and P
13
carried with it
the best score from the opponent's point of view. This would be the
minimum (lowest score) of S
11
,S
12
and S
13
, and this is the score (S
1
)
associated with position P
1
because it is the best score the program can
hope for, assuming correct play by the opponent, if it chooses the move
from the root position to P
1
.
Similarly, if the program's opponent had to choose a move from po-
sition P
2
, and if it chose its best option, the opponent would move to
whichever of P
21
,P
22
and P
23
carried with it the best score from the op-
ponent's point of view. This would be the minimum score of S
21
,S
22
and S
23
, and this is the score (S
2
) associated with position P
2
because it
is the best score the program can hope for, assuming correct play by the
opponent, if it chooses the move from the root position to P
2
.
Clearly, when searching the tree to find its best move, and assuming
correct play by both sides, a program should choose to move to whichever
of the positions P
1
and P
2
has the highest score, so once it knows the
scores S
1
and S
2
it chooses the maximum of these two and makes the
corresponding move. The maximum of S
1
and S
2
becomes the score
(S
0
) associated with the root position P
0
and represents how well or badly
the program's evaluation function thinks the program is doing in the root
position, assuming best play by both sides. This process of choosing the
maximum of the minimums (of the maximums of the minimums ...)
is called, not surprisingly, the
minimax
method of tree searching. The
score for the root position is called the backed-up or minimax score.
