Robotics Reference
In-Depth Information
games played by Chess masters and grandmasters are available on disk—
this is the twenty-first century form of openings topic most popular with
serious human players and is
de rigeur
as part of the openings arsenal of
the most competitive Chess players, man or machine.
Endgame Databases
In 1970 Thomas Strohlein created the first Chess endgame database for
his PhD project at Technische Hochschule Munchen, and within a few
years Ken Thompson
9
had pioneered the use of such databases in com-
petitive Chess programs.
Thompson realised that the number of possible Chess positions in
which there are very few pieces on the board is a manageable number in
terms of computer storage. For example, if we ignore the fact that some
positions will not be feasible for reasons connected with the rules of the
game, for the endgame in which one player has a king and a rook while
his opponent has only a lone king, this configuration can be represented
in fewer than 250,000 positions.
10
In fact the number of positions that
needs to be stored to represent this configuration completely is consider-
ably smaller, partly because of symmetry and partly because of consider-
ations relating to the rules of Chess, such as a position being illegal if the
side that just moved is in check.
Thompson's aim was to build a database of perfect knowledge about
Chess endgames in which there are very few pieces on the board. His
method was to back up from all positions in which one player has been
checkmated, in order to create a database of all the positions that are won
for the side with the extra rook, together with a note of how many half-
moves are required from each position to checkmate. Then, when faced
with any winnable position, the program simply looks into the database
and chooses a move that leads to a win in the smallest number of half-
moves.
In practical terms, using a database to win the ending of king and
rook versus a lone king is sheer overkill, since a relatively simple evalua-
tion function can be designed to win this ending, hardly surprising given
9
Thompson was one of the co-developers of the BELLE Chess computer that won the World
Computer Chess Championship in 1980. Thompson was also co-author of the Unix operating
system for computers, an accomplishment that earned him the U.S. National Medal of Technology
in 1999.
10
The rook can be on any of 64 squares, one player's king on any of the remaining 63 and the
other king on any of the remaining 62, hence 64
×
63
×
62.
