Information Technology Reference
In-Depth Information
Thus, the number of possible move sequences is an exponential
function of the number of plies considered. This number increases
very quickly, so chessplaying programs can never hope to consider
all possible consequences of every particular move; if a typical game
involves about 50 moves, this analysis suggests that a computer
would have to consider roughly 20
50
different move sequences be
fore it could choose the best response to the first move by an oppo
nent. The combinatorial explosion is at work.
Consider for a moment that scientists estimate that the age of
the universe is between 10 and 20 billion years. Assuming we began
a chess game 20 billion years ago, a computer evaluating 20
50
possi
ble move sequences would have had to analyze about 1.3 10
47
chess moves per second to respond by now to an initial move made
at the birth of the universe. In contrast, the fastest modern comput
ers can perform only about 10
7
to 10
8
instructions per second, and
there is no prospect that increases in computer speed will have much
real impact on this problem. Even major revolutions in computer
processing speed would likely have little effect on problems dealing
with huge numbers like this one.
Because the numbers related to chess playing and analysis are so
large, modern chess playing programs must restrict what moves are
considered in order to be somewhat effective. A particularly com
mon approach is to look ahead only a specified number of plies. For
example, several of the best programs currently available may look
ahead eight or nine plies. Other programs may consider only some
possible moves instead of all of them. Libraries of common board
positions may also allow the machine to restrict the number of
moves it must consider. Regardless of how the range of chess moves
is restricted, computer chess programs are a particularly good ex
ample of the limitations that arise due to the combinatorial explo
sion. Each additional ply increases the number of moves to be con
sidered by a factor of about 20. The consequences are parallel to
what the king encountered in the fable. Any completely successful
approach to playing chess will not be able to look at all possible
moves, but rather will have to proceed differently (e.g., the king
may abdicate). In Chapter 16, we will talk more about chess and the
way it is played by both people and computers.
