Information Technology Reference
In-Depth Information
influence the value of a position. These include factors such as the power of
each piece and its possible mobility, control of the center of the chess board,
and the safety of the king. A program therefore needs to find strategies that
optimize moves for the player MAX, at the same time assuming that the
opponent, MIN, will make an optimum move in response. Such a strategy is
provided by the
minimax algorithm
, a procedure that minimizes the risk for a
player. Because the number of moves that need to be examined by the mini-
max algorithm grows at an increasingly rapid rate with the depth of the tree,
computer chess programs can only afford to evaluate several moves ahead,
not all the way to the final result node. In their 1958 chess program dubbed
NSS from their initials, Allen Newell and Herbert Simon from Carnegie Mellon
University and Cliff Shaw from the RAND Corporation introduced an optimiza-
tion technique called
alpha-beta pruning
(
Fig. 13.9
) for the minimax search algo-
rithm. Alpha-beta pruning decreases the search time by stopping evaluation
of a move when at least one possibility has been found that proves the move
to be worse than a previously examined move. In this way, several branches
of the search tree can be “pruned” and the search time devoted to deeper
exploration of more promising branches. In addition to such pruning tech-
niques, modern chess programs also include tables of the standard openings
and endgames.
The first computer versus computer chess match featured the Kotok-
McCarthy program written by Alan Kotok, John McCarthy, and their colleagues
from MIT pitted against the Russian ITEP program written by scientists at the
Institute of Theoretical and Experimental Physics in Moscow (
Fig. 13.10
). Playing
by telegraph in 1967, the match ended in a 3 to 1 victory for ITEP. In the same
year, MIT's Mac Hack, written by Richard Greenblatt and colleagues, became
the first chess program to play in a tournament with humans. Its Elo rating was
1400, well above the novice level of 1000 on the chess rating system developed
by the Hungarian-born physicist Árpád Élő. In 1968, the international chess
master David Levy made a famous bet with John McCarthy that no computer
would beat him at chess in the next ten years, saying:
max
2
min
A
2
≥
6
≥
5
4
max
prune
prune
3
4
5
2
1
6
B
C
Fig. 13.9. In this example of alpha-beta
pruning, the moves of the game are
represented by a binary min-max tree.
The algorithm traverses the tree starting
from the bottom left and chooses the
maximum of the first two values. The
algorithm then moves to the red branch
and finds that the first value is six. Thus
what must be passed on to the min node
must be more or equal to six. Because
we already know that there is a lower
value of two at the min node we do not
need to evaluate branch B of the red
node because the algorithm will never
use this part of the tree. We proceed in
the same way to eliminate branch C.
Clearly, I shall win my … bet in 1978, and I would still win if the period were
to be extended for another ten years. Prompted by the lack of conceptual
progress over more than two decades, I am tempted to speculate that a
computer program will not gain the title of International Master before the
turn of the century and that the idea of an electronic world champion belongs
only in the pages of a science iction topic.
14
Levy played his 1978 match against the Chess 4.7 program, the strongest com-
puter chess program of the time, written by Larry Atkin and David Slate from
Northwestern University. Levy won by 4.5 to 1.5 but he said later, “I had proved
that my 1968 assessment had been correct, but on the other hand my opponent
in this match was very, very much stronger than I had thought possible when
I started the bet.”
15
In 1980, the celebrated MIT computer scientist Ed Fredkin offered prizes
for successive milestones in computer chess. The smallest prize of $5,000 went
to Ken Thompson, inventor of the Unix operating system, and Joe Condon,
when their Belle chess program earned a U.S. Master rating in 1983. Belle was
the first computer chess system to use custom-designed chips, and it won the
Fig. 13.10. A photograph of the Institute
of Theoretical and Experimental Physics
in Moscow.
Search WWH ::
Custom Search