Robotics Reference
In-Depth Information
that there are only three pieces on the board. But where the database
technique becomes of real use is in some four-piece endings, such as king
and queen versus king and rook, which is not trivial to play, even for
some humans of master strength. And for endings with five pieces and
more, the endgame databases make a huge difference in computer ver-
sus human play, enabling programs to play these endings perfectly and
even teaching human grandmasters lessons in Chess. There is also an-
other reason why these databases are useful for a competitive program.
If the program sees, during its search of the game tree, that it can reach
a position stored in its endgame database, the program knows what the
result of the game will be if that position is reached, and uses the result
to decide whether or not it wishes to aim for that position. This factor
has been of enormous help in programming Checkers.
11
From Patzer to World Champion
It took almost 50 years from the time of Shannon's first publication on
computer Chess in 1950 until a program was able to defeat the human
World Champion in a match. Progress during most of that period was
painfully slow. Much of the research in computer Chess during the
1950s, 1960s and 1970s was carried out by academics who lacked the
resources to play many games between their programs and human oppo-
nents, and it is only by playing such games and studying printouts of the
resulting program analysis that programmers are able to make significant
strides.
Since Shannon's kick-start of research in this field, each decade has
been characterised in a way that reflects a quantum leap forward in un-
derstanding, if not results. The end of the 1940s and the whole of
the 1950s were notable for a small number of research efforts: hand-
simulations by Alan Turing and Donald Michie; a program developed at
the Los Alamos Scientific Laboratory for playing Chess on a 6 x 6 board
(omitting the bishops); the efforts of Allen Newell, Herb Simon and John
Shaw at Carnegie Institute of Technology; and the strongest, a program
developed by Alex Bernstein at IBM (see
Figure 22)
. None of these ef-
forts resulted in a program that could play well enough to challenge any
but the very weakest human players.
The biggest step forward of the 1960s, and the most publicized,
was the program MacHack VI, written by an MIT student, Richard
11
See the “Chinook” section later in this chapter.
