CSE 472/572, Spring 2002
CHESS
-
Marsland, T. Anthony
(1992), "Computer Chess and Search", in
Stuart C. Shapiro
(ed.) (1992),
Encyclopedia of Artificial
Intelligence, 2nd edition (New York:
John Wiley): 224-241.
- Seirawan, Yasser; and Simon, Herbert A., & Munakata,
Toshinori (1997),
"The
Implications of Kasparov vs. Deep Blue",
Communications
of the ACM
40(8):
21-25.
-
Zobrist, Albert L. (2000), "Computer Games: Traditional", in
Anthony Ralston, Edwin D. Reilly, &
David Hemmendinger (eds.),
Encyclopedia
of Computer Science,
4th edition
(New York:
Grove's Dictionaries):
364-368.
- Also discusses Nim and Tic-Tac-Toe
From Zobrist 2000: 367:
[S]ince all possible chess games can be expressed in a tree ..., it is
known that there is a perfect strategy for chess that guarantees a win
or a draw for one player. Of course, the strategy has never been found.
It is the combinatorics of game playing that prevent the discovery of
perfect strategies. In chess, when it is a player's turn to move, that
player has, on the average, 30 legal moves resulting in 30 different
positions. If the opponent also has 30 replies to each of those moves,
then 900 positions result. This sort of calculation gives an estimate
of 10^125 as the size of the lookahead tree for chess (the number of
paths from the top of the tree to the terminal positions). If a
computer could examine a billion positions per second, it would still
take 10^108 years to examine the entire lookahead tree to determine the
optimal strategy. It should be mentioned that the number of board
positions is far smaller, approximately 10^42, so it is theoretically
possible to store all positions together with their optimal moves in a
large table. Storing one board position on an element the size of an
atom would necessitate a memory of about the size of the earth.
Copyright © 2002 by
William J. Rapaport
(rapaport@cse.buffalo.edu)
file: 572/S02/chess.05fb02.html