Robotics Reference
In-Depth Information
Samuel's program was extremely sophisticated for its time and played
a mean game of Checkers. It won a demonstration game played in the
summer of 1962 against Robert Nealey, a strong tournament player.
Chinook
It remains as a testament to Samuel that little new was achieved in com-
puter Checkers until Jonathan Schaeffer and his colleagues at the Univer-
sity of Alberta
19
developed the Chinook program. Schaeffer's goal with
Checkers was simply to “solve” the game. By this we mean to develop
a program that can play perfectly from any position, always winning
a winnable position in the shortest possible number of moves, always
putting up the stiffest resistance when faced with a lost position, and
never allowing a winning advantage to be dissipated or a draw to become
a loss. It was Thompson and Stiller's work on Chess endgame databases
that provided the inspiration for Schaeffer.
20
Schaeffer's idea was to create a Checkers endgame database so big that
it would allow his program to search, in effect, to the end of the game
tree, along all variations, from the very start of the game. His program
would conduct as deep a search of the game tree as was possible in the
time available for it to choose its move and then, instead of evaluating
the leaf positions on the tree using an evaluation function, Schaeffer's
program would look up the leaf positions in the database and assign the
corresponding score (win, draw or loss) to that position in the tree. This
approach would guarantee perfect play, provided that every leaf position
on the game tree could be found in the database. For this to be possible
the database would need to be huge and the program would need to be
able to search very deeply. The bigger the database, the shallower the
program could search, while still playing perfect Checkers.
19
Schaeffer heads a research group specializing in programming various strategy games. His team,
and a similar group at the University of Maastricht, in the Netherlands, is home to many of the
world's leading experts in this field. Schaeffer himself had long been one of the world's top Chess
programmers and had written the Sun Phoenix program that tied for first place at the 1986 World
Computer Chess Championship in Cologne, Germany.
20
While the number of possible Chess positions has been estimated at approximately 10
44
,the
estimate from Schaeffer's group of the corresponding number for Checkers was “only” 5 x 10
20
.To
be precise, Schaeffer has calculated it to be 500,995,484,682,338,672,639, and explains that “To
put a number this big into perspective, imagine the surface of all the earth's land mass as being
equivalent to the number of possible Checkers positions. Then one position is roughly equivalent
to one-thousandth of a square inch.” [1]
21
Because the match was played in the U.K. the anglicized name of the game was used in the
name of the event, the World Draughts Championship.
