Information Technology Reference
In-Depth Information
that the search does not have to continue below C , since it cannot affect the result.
Therefore perform an alpha cutoff , and jump immediately to node E , which may turn
out to affect the value at A .
An analogous situation holds on the right of figure 10.18. In this case, the search is
for a value for A , a node for Min. After it has been determined that B has value 4 and
D has value 8, it is clear that C cannot get a value smaller than 8, since Max chooses a
maximum. Since Min chooses a minimum at A , and the value of B is already smaller
than 8, perform a beta cutoff , and jump immediately to node E , which may still affect
the value at A .
The alpha and beta cutoffs allow deciding what moves to make (for Max or for
Min) without examining an entire tree all the way to the leaves. These cutoffs can be
very significant, especially if they happen high up in the game tree.
10.3.3 The application to chess
A minimax game player is able to decide on a best next move without looking at
all the game states up to the end of the game. To use it, however, one needs to be
able to estimate the values of states where the game is not over. (This is not unlike
estimating the distance to the goal during planning in section 9.3.2.) So in addition to
the four predicates player , initial_state , legal_move , and game_over , a fifth one
is needed:
estval( state , player , v )
This says that if it is the turn of player in state , then the number v is the estimated
measure of how good the state is, from the point of view of Max.
Different games have different methods of estimating how well or how poorly Max
is doing at nonfinal states of the game. For a game like chess, a typical estimate is
something like
(
material advantage
+
positional advantage
)
. The material advantage is of
the form 9
P , where Q , R , N , B , and P represent the
advantage in queens, rooks, knights, bishops, and pawns, respectively. The positional
advantage is much harder to quantify but usually includes things like mobility, control
over squares, early development of pieces, and so on.
How well does this work for chess? Although chess-playing programs have existed
for a long time, the first one to win against a world chess champion was Deep Blue ,
which won against Garry Kasparov in 1997. Here are some details on it:
·
Q
+
·
R
+
·
N
+
·
B
+
5
3
3
It used minimax with alpha-beta cutoffs, but on a special computer to speed up
the generation of moves and the evaluation of states. (It was able to consider a
staggering 200 million board positions per second.)
 
Search WWH ::




Custom Search