Robotics Reference
In-Depth Information
-3-
How Computers Play Games
In Chapter 1 we saw how the game of Nim can be programmed by
means of fixed rules—a method called an algorithm—that guaran-
tees to find the solution to a problem if a solution exists. Some other,
relatively simple games can also be played perfectly using algorithms de-
signed for the purpose. But for most interesting games, the problem of
finding the best move or even a good one is much too complex, and
the number of possibilities that need to be examined is too vast, for an
algorithmic method to provide a practical solution within a reasonable
amount of time. Instead it is necessary to use rules of thumb, called
heuristics, to enable a program to choose its move. Heuristics, unlike
algorithms, do not guarantee to find the solution to a problem. What
heuristics contribute is the means to make a hopefully intelligent guess
at which moves are good and which are less good, and to enable a pro-
gram to disregard certain moves from serious consideration. Chess is one
example of a game whose programming derives great benefit from the
use of heuristics.
The section that follows not only provides an account of how com-
puters play Chess, it also serves as an induction into some of the most im-
portant techniques employed to program many other two-person games.
Chess
The problem of how to program thinking games has attracted the interest
of computer scientists ever since the birth of computers, and even earlier.
In the world of Artificial Intelligence it has long been argued that, since
Chess is a game that requires intelligence to play it well, building a strong
Chess program is synonymous with the creation of an artificial intellect.
Charles Babbage thought about “programming” Chess on his ill-fated
Analytical Engine, and Konrad Zuse described the basis for program-
ming Chess in his
Plankalkul
. But it was not until Claude Shannon's
seminal paper in 1950, “Programming a Computer for Playing Chess”,
that anyone provided a lucid explanation of how the problem might be
