CHESMAYNE
HAL-9000
by Carmelo Coco
The diagram shows the move played from Frank Poole, the
astronaut of the Discovery, and Hal-9000, the computer of the space-ship, in a
sequence of the movie ‘2001: A space Odyssey’ by
ROESCH - SCHLAGE Willi
1.e4 e5
2.Nf3 Nc6
3.Bb5 a6
4.Ba4 Nf6
5.Qe2 b5
6.Bb3 Be7
7.c3 0-0
8.0-0 d5
9.exd5 Nxd5
10.Nxe5 Nf4
11.Qe4 Nxe5
12.Qxa8 Qd3
13.Bd1 Bh3
14.Qxa6 Bxg2
15.Re1 Qf3 0-1
The final position is the same played in the movie.
In
It is
strange to note how in the
KOTELNIKOV - GELLER Efim
Moscow 1979 - C86
1.e4 e5
2.Nf3 Nc6
3.Bb5 a6
4.Ba4 Nf6
5.0-0 Be7
6.Qe2 b5
7.Bb3 0-0
8.c3 d5
9.exd5 Nxd5
10.Nxe5 Nf4
11.Qe4 Nxe5
12.Qxa8 Ne2+
13.Kh1 Qd3
14.Re1 Ng4
15.Qf3 Qd6
16.g3 Nxf2+
17.Kg2 Bg4 0-1
Ritorna all'indice della sezione Cinema
Willi Schlage
=
Hal9000
by Carmelo Coco
The diagram above
shows the move
played from Frank Poole, the astronaut of the Discovery, and Hal9000,
the computer of the space-ship, in a sequence of the movie '2001: A space
Odyssey' by
The game went on with 1. Qxa6 Bxg2 2. Re1 and the checkmate
was introduced from Hal9000, through the sentence: ' I' m sorry Frank maybe you
escaped Qf3, Bxf3, Nxf3 mate'.
In the opinion of many critics, the start position
seemed artificial and created on purpose.
Yet, how is possible not to take into account the scrupulous
Kubrick' s attention for the particulars and his perfectionism?
Now, we can state that the move was not original but it was
taken from a game actually played in 1910 during the famous tournament in
Hamburg:
ROESCH - SCHLAGE Willi
Hamburg 1910 - C86
1.e4 e5 2.Nf3 Nc6 3.Bb5 a6 4.Ba4 Nf6 5.Qe2 b5 6.Bb3 Be7 7.c3 0-0
8.0-0 d5 9.exd5 Nxd5 10.Nxe5 Nf4 11.Qe4 Nxe5 12.Qxa8 Qd3 13.Bd1 Bh3 14.Qxa6
Bxg2 15.Re1 Qf3 0-1
The final position is the same played in the movie.
<BR<
It
is strange to note how in the Moscow tournament, in 1979, Geller reached the
same position used from Hal9000/Schagel at the twelfth move.
Yet, he chose to check by the Knight in e2. What a pity!.
KOTELNIKOV - GELLER Efim
Moscow 1979 - C86
1.e4 e5 2.Nf3 Nc6 3.Bb5 a6 4.Ba4 Nf6 5.0-0 Be7 6.Qe2 b5 7.Bb3 0-0 8.c3 d5
9.exd5 Nxd5 10.Nxe5 Nf4 11.Qe4 Nxe5 12.Qxa8 Ne2+ 13.Kh1 Qd3 14.Re1 Ng4 15.Qf3
Qd6 16.g3 Nxf2+ 17.Kg2 Bg4 0-1
(20/12/1999)
(Traduzione in inglese di B.S.)
To be continued
Ritorna alla Home Page
Ritorna all'indice della sezione Cinema
The chess scene in 2001
is just one example of the genius behind Clarke and Kubrick’s screenplay. Although the game between HAL and astronaut
Frank Poole is shown for only about thirty seconds, it conveys a great deal of
information about HAL and the relationship between Frank and HAL. The fact that HAL can beat Frank at one of
the world’s oldest and most difficult games is clearly intended to establish
HAL as an intelligent entity. But is
this a correct conclusion? Does a
machine need to be intelligent to play chess?
The question of whether HAL’s
chess ability demonstrates intelligence
boils down to a question of how
HAL plays chess. If, on the one hand,
HAL plays chess in the “human style” employing explicit reasoning about move
choices and large amounts of chess knowledge the computer can be said to
demonstrate some aspects of intelligence.
If, on the other hand, HAL plays chess in the computer style that is,
if HAL uses his computational power to carry out brute-force searches through
millions or billions of possible alternatives, using relatively little
knowledge or reasoning capabilities then HAL’s
chess play is not a sign of intelligence.
This chapter attempts to resolve this question by
examining in detail how HAL plays chess and by comparing HAL with Deep Blue, the world’s
current premier chess computer. I and
my colleagues, Feng-hsiung Hsu and A. Joseph Hoane, Jr., developed Deep Blue at IBM’s T. J. Watson
Research Labs. It was the first machine
in history to beat the
human world
champion, Garry
Kasparov, in a regulation chess game.
The chapter also examines the strengths and weaknesses of computer-style
chess by looking at some of the games between Kasparov and Deep Blue. Finally, we discover that HAL’s
first error
occurred in the chess game with Frank.
Before we analyze how HAL plays chess, we need to put
his game with Frank into perspective by understanding the history of
man-machine chess matches. What is the
significance of a machine beating a human at a game like chess?
Frank versus HAL; Man versus Machine
HAL
claims to be “foolproof and incapable of error”. But, as we witness only one isolated game
between Frank and HAL, how do we really know that HAL plays well? The answer
can be determined, not so much by the game itself but by Frank’s reaction to
it.
Poole: Umm ... anyway, Queen takes pawn.
HAL: Bishop takes Knight’s Pawn.
HAL: I’m sorry, Frank. I think
you missed it. Queen to Bishop
Three. Bishop takes Queen. Knight takes Bishop. Mate.
Poole: Ah ... Yeah, looks like
you’re right. I resign.
HAL: Thank you for an enjoyable game.
Having personally witnessed scores of amateur chess
players lose to computers, I
found Frank’s reaction to losing to HAL extremely realistic. After HAL announces mate, Frank’s pause is brief. This brevity is significant, because it
demonstrates that Frank assumes HAL is right.
He trusts that HAL has the details of the checkmate correct and does not
take the time to confirm them for himself.
Instead, Frank resigns immediately.
Moreover, it is obvious from his tone of voice or perhaps I should say
from his complete lack of tone that he never expected to win. In fact, Frank would have been utterly
stunned if HAL had lost. No, playing
chess with HAL is simply a way for Frank to pass the time on the eighteen-month
journey to Jupiter. (As HAL is running virtually every aspect of
the ship, there is little for the two, nonhibernating
astronauts to do.) It is also clear from
the dialogue, as well as from Frank’s body language, that this is not a game
between two competitors but one between two conscious entities one of whom is
vastly superior in intelligence to the other.
Clearly, Frank does not feel bad about losing to a
computer, any more than a sprinter would feel bad about being outrun by a race
car. Nor do we, the viewers, feel
particularly sorry for Frank’s loss. We
don’t mind HAL winning, because at this stage in the film we like HAL. The human relationship with chess computers
hasn’t always been so amicable though.
In many recent human-machine matches, the mood has been
decidedly pro-human and anti-computer.
In the first encounter between the human world champion (Kasparov) and
the computer world champion (Deep Thought, Deep Blue’s predecessor) in 1989,
there was definite hostility toward the computer. When Kasparov pulled out the victory, the
audience breathed an audible sigh of relief.
In gratitude for “saving human pride,” onlookers gave Kasparov a
standing ovation.
Kasparov couldn’t, however,
save humanity’s pride indefinitely. In
1995 he lost a game of speed chess to a computer program called GENIUS3. Burying his head between his hands, Kasparov could not hide
his despair; he stormed off the stage, shaking his head in disbelief. The loss, reported by newspapers and magazines around the
globe, shocked the multitude of those players and nonplayers
alike who believed that the strongest player in the
history of the game would never suffer defeat at the hands of “a silicon
monster”. Although Kasparov was badly
shaken by this upset, it was, after all, only speed chess - a game in which
decisions are made within severe time constraints. (Speed chess allows each player only
twenty-five minutes for the entire game, whereas players in regulation chess
each have two hours to complete forty moves.)
In February of 1996, Kasparov played Deep Blue in a
six-game, full-length regulation match sponsored by the Association for
Computing Machinery in celebration of the fiftieth anniversary of the
computer. Before the match, Kasparov was
quoted as saying, “To some extent this is a defense of the whole human race”.
When he lost the first game, his computer adviser, Frederick Friedel, openly acknowledged that Kasparov was devastated (see
figure 5.1). Even though he rebounded to win the match, Time magazine called the first-game
defeat an event larger than “world historical.
It was species-defining”.
Other grandmasters refuse to
play against computers at all. Why? Perhaps because the idea of computer
superiority in an arena as cerebral as chess is so disorienting; in Western
culture, many consider chess the ultimate test of the human intellect. (It is interesting that Kubrick originally
filmed the “chess scene” with a five-in-a-row board game called pentominoes but chose not to use it, believing that viewers
would better appreciate the difficulties involved in a chess game.) Mathematicians have estimated that there are
more possible chess positions than there are atoms in the universe. Therefore, skilled chess players must possess
the ability to make
difficult calculations and recognize a seemingly infinite number of patterns. Yet excellent chess play also requires imagination, intuition, ingenuity, and
the passion to conquer. If a machine can beat a man at a game
requiring as much creativity as chess does, what does that say about our
“unique” human qualities?
For now, at least, we can rest assured that even though
the best computers are better at chess than 99.999999 percent of the
population, they do not actually play chess the way humans do. In the history of man’s rivalry with
machines, only one grandmaster-level computer has appeared to play like a human
and that computer is our fictitious friend HAL.
How HAL Plays Chess
By analyzing
the game between Frank and HAL, we can uncover a number of clues about how HAL
plays chess. As I explain in more
detail below, HAL appears to play chess the way humans do. Even more important perhaps, the game
reveals that HAL is not simply mimicking the way humans play; he actually
understands how humans think.
The game in the screenplay is a real one played by two
undistinguished players in
Evans makes the crucial point in his article that HAL
should have said “Queen to Bishop six”
(not three). HAL used the so-called descriptive notation
system that describes moves from the viewpoint of the moving player. This contrasts with the algebraic-notation
system used in the game score (see Appendix to chapter), in which moves are
described from White’s
viewpoint. HAL used the incorrect
viewpoint when giving his fifteenth move.
Was the notation error a deliberate foreshadowing of the machine’s
fallibility or merely a writer’s oversight?
This is a question only Kubrick can answer. If
To better understand how HAL chooses to play against
Frank, it is important to have some sense of Frank’s chess background. Although the movie does not disclose his
chess rating, it is easy
enough to speculate about his skill level. He is a highly educated man who holds a
doctoral degree, most likely in a field such as aerospace engineering or robotics. We can surmise that, as second in command on
a top-secret space mission of unprecedented importance, Frank is well above
average intelligence. Because he is a
full-time astronaut, it is unlikely that he would have time to compete in
professional chess tournaments; yet he clearly knows something about chess, for
his game with HAL follows opening
theory for eleven moves (see Appendix for a complete account of the game). Frank’s chess rating may be in the expert
range, making him strong enough to engage in an interesting game but certainly
not experienced enough to handle HAL.
(See figure 5.2 for an explanation of the rating scale.)
In the game itself, Frank plays White and HAL is Black. Frank chooses an unusual but perfectly sound variation of the
well-known Ruy
Lopez, or Spanish
opening. HAL responds with very
aggressive play, creating a situation that makes it very difficult for Frank to
find the best moves. By the time the
movie picks up the game, Frank has already made the losing move, and he goes
down without much of a fight.
The game provides sufficient evidence that HAL plays
chess the way humans play chess. Early
in the game HAL uses an apparently nonoptimal but
very “trappy”
move. The choice creates a very complex
situation in which the “obvious” move is a losing blunder. If Frank had been able to find the best
move, he would have gained the advantage over HAL. In leading Frank into this trap, HAL appears
to be familiar with Frank’s level of play, and we can assume that HAL is
deliberately exploiting Frank’s lack of experience.
The interesting point here is that present-day chess
programs do not normally play trappy chess. They are almost always based on the minimax principle, which assumes that the
opponent always makes the best move. (I
discuss this principle in more detail later in the chapter.) A machine like Deep Blue, therefore, would
only play the optimal move found in its search. The ability of HAL to play trappy moves is a sign of a sophisticated player who is
familiar with the opponent’s strengths and weaknesses.
A second interesting point in the game occurs on move
13. The move played by HAL is clearly a
winning move, but Deep Blue would have found a move that forces checkmate one
move sooner. Current programs always
prefer the shortest checkmate.
Thus, either HAL is not able to calculate as deeply as Deep Blue does or he
chooses a move based on “satisficing” criteria; that
is, HAL saw that the move guaranteed a win, and so did not bother to search for
a better move. Human chess players
commonly follow this practice, which is another piece of evidence pointing to HAL’s human style of play.
So how do we now that HAL understands how humans
think? When HAL plays his spectacular
fifteenth move, he surmises, undoubtedly correctly, that Frank had overlooked
this move. Further, HAL did not point
out to Frank the other possible variations to checkmate only the most
interesting line, the one that Frank would most appreciate. Although Frank need not have accepted HAL’s queen sacrifice, a prosaic
checkmate would have followed shortly anyway.
HAL’s ability to play chess human
style is what computer scientists in the 1960s might have expected. When 2001
was produced, the majority of artificial intelligence researchers probably
believed that computers should play the way humans play:
by using explicit reasoning about move decisions and applying large amounts of pattern-directed
knowledge. It wasn’t until the 1970s,
after years of much hard work and little progress, that chess
programmers tried a new strategy,
which is still utilized in the 1990s. A
brief history of computer chess and some of its key components is relevant to
understanding how machines play today.
Perhaps we should start with an even more basic question: Why develop a chess machine in the first
place?
A Brief History of Computer Chess: The
Early Days
In 1950, Claude Shannon, the
founder of information theory, proposed that developing a chess machine would
be an excellent way to work on issues associated with machine intelligence. In his article, “A Chess-Playing Machine,”
Shannon states the case for developing such a machine: “The investigation of
the chess-playing problem is intended to develop techniques that can be used
for more practical applications. The
chess machine is an ideal one to start with for several reasons. The problem is sharply defined, both in the
allowed operations (the moves of chess) and in the ultimate goal
(checkmate). It is neither so simple as
to be trivial nor too difficult for satisfactory solution. And such a machine could be pitted against a
human opponent, giving a clear measure of the machine’s ability in the type of
reasoning”.
In fact, the practical applications that could result
from development of a world-class chess machine are numerous. Complex tasks that may be solved by
technologies derived from Deep Blue include problems in chemical modeling, data
mining, and economic forecasting.
Fascination with the idea of a chess-playing machine,
however, began more than two centuries ago, long before anyone thought of using
a computer to solve large-scale problems.
In the 1760s Baron
Wolfgang von Kempelen toured
The first documented discussion of computer chess is in
‘The Life of a Philosopher’ by
Charles Babbage (1845). Babbage, whose
remarkable ideas in mathematics and science were far ahead of his time,
proposed programming his Analytical Engine a precursor of the computer to
play chess. A century later, Alan M. Turing, the British
mathematician and computer scientist, developed a program that could generate
simple moves and evaluate
positions. Lacking a computer with
which to run his program, Turing ran it by hand. Konrad
Zuse, a German computer science pioneer, in his Der Plankalkuel
(1945), described a program for generating legal chess moves. He even developed a computer, although he did
not actually program it to play chess.
In spite of these earlier precedents, it was Shannon’s
efforts that laid the groundwork for actual research, and he is generally
considered the “father of computer chess”.
Shannon’s work was based, in turn, on the findings of John von Neumann
and Oskar Morgenstern, game theorists who devised a minimax
algorithm by which the
best move can be calculated.
Key Components of a Chess Program
The minimax algorithm can be
thought of as consisting of two parts: an evaluation function and the minimax rule. An evaluation function for any chess
position produces a number that measures the “goodness” of the position. Positions with positive values are good for White, and negative values are
good for Black. The higher the score, the better it is for
White, and vice versa. The minimax rule allows the evaluation function
values to be used. It simply states
that, when White moves, White chooses the move that leads to the maximum value,
and when Black moves, Black chooses the move that leads to the minimum
value.
In theory, the minimax
algorithm allows one to play “perfect” chess; that is, the player always makes
a winning move in a won position or a drawing move in a drawn position. Of course, perfect chess is just a fantasy;
chess is far too vast a game for perfect play, except when there are only a few
pieces on the board. In practice, chess
programs examine only a limited number of moves ahead typically between four
and six.
Although minimax
is very effective, it is also quite inefficient. In the opening position in a chess game,
White has twenty moves, and Black has twenty different replies to each of these
- thus there are four hundred possible positions after the first move. After two moves there are more than twenty
thousand positions, and after five moves the number of potential chess
positions is into the trillions. Even
today’s fastest computers cannot process this many positions. The alpha-beta
algorithm improves the minimax rule by
greatly reducing the number of positions that must be examined. Instead of
exploring trillions of positions after five moves, the computer only needs to
analyze millions.
The Modern Era of Computer Chess
The
principles of the minimax and alpha-beta algorithms
were well understood in the 1960s. When
2001 made its screen debut in
1968, however, the very best computer chess program was only as strong as the
average tournament
player. Still, many computer scientists
believed that building a world-class chess machine was a fairly straightforward
problem, one that would not take long to solve.
The earliest approach to solving it involved emulating
the human style of play. It is now clear that this was an extraordinarily
difficult way to tackle computer chess. Even though chess seems to be a simple
and restricted domain, people use many different aspects of intelligence in
top-level play, including calculation of possible outcomes, sophisticated
pattern recognition and evaluation, and general-purpose reasoning. Significant progress in computer chess did
not occur until 1973, when David Slate and Larry Atkin
wrote a well-engineered brute-force chess program called Chess 4.0. Since then, almost all good chess programs
have been based on their work.
The Slate/Atkin program
remained the best chess-playing computer program throughout the 1970s; it
gained in strength with each new, faster generation of computer hardware. It was observed in practice, and verified by
experiment, that every fivefold speedup in computer hardware led to a
two-hundred-point increase in the program’s rating as it approached the master
level. Subsequent chess-playing
machines pushed the computer chess ratings higher and higher in large part
due to faster hardware, although software was also improving rapidly. The Slate/Atkin
program reached the expert level (2,000) by 1979; in 1983 Belle, a machine from
AT&T Bell Labs, used specially designed chess hardware to reach the
master’s level (2,200); then came Cray Blitz, which ran on a Cray
supercomputer, and Hitech, which dedicated a
special-purpose chip to each of the sixty-four squares on a chessboard.
Recognizing this trend, Ray Kurzweil predicted that a
computer would beat the world champion around 1995. All these machines were finally surpassed by
Deep Thought, which began playing in 1988 (see figure 5.3). Designed and programmed by a group of
graduate students (myself included), Deep Thought was the first machine to
defeat a grandmaster in tournament play; it was capable of searching up to
seven hundred thousand chess positions per second. Deep Thought eventually led to Deep Blue,
still the world’s best chess-playing machine.
How Deep Blue Plays Chess
The objectives of the Deep Blue project were to develop
a machine capable of playing at the level of the human world chess
champion and to apply the knowledge gained in this work to solving other
complex problems. To accomplish these
goals, a significant increase in processing power was necessary. Today Deep Blue is capable of searching up
to two hundred million chess positions per second. Its ability to search such an extraordinary number
of positions prompted Kasparov to comment that |quantity had become
quality”. In other words, the computer
is able to search so deeply into a position that it can discover difficult and
profound moves. Although Deep Blue uses
a variety of techniques to achieve its high level of chess play, the heart of
the machine is a chess microprocessor
(see figure 5.4).
Designed over a period of several years, this chip was
built to search and evaluate up to two million chess positions per second. By itself, however, the chip cannot play
chess. It requires the control of a
general-purpose computer to make it work.
Deep Blue runs on an IBM SP2 supercomputer with thirty-two separate
computers (or nodes) that work in concert.
For the match against Kasparov, each SP2 node controlled up to eight
chess chips, while the entire SP2 system had about 220 chess chips that could
be run in parallel. The old saying
about too many cooks spoiling the broth is also applicable to parallel
computers. A lot of processors won’t do
much good unless they can all be kept busy doing useful work. In fact, parallelizing a chess program
efficiently has proven to be a very difficult problem. For the match with Kasparov, Deep Blue looked
at an average of close to one hundred million positions per second.
Nonetheless, a purely brute-force machine would have
little chance against a player like Kasparov.
Although grandmasters require very little actual calculation of
variations for most moves, there are typically a few key points in a game where
they must calculate the possible variations very
deeply. Often these calculations far
surpass what brute-force search could hope to attain. To overcome this problem, Deep Blue employs
a technique called selective extensions,
which enables the computer to search critical positions more deeply.
One of the questions most commonly asked about a chess
computer is, “How deep does it search?”
In the early days of the computer chess, most programs searched all
lines to roughly the same depth, and this question was relatively easy to
answer. The fact that Deep Blue employs
sophisticated selective searches complicates the issue considerably. When asked how deeply Deep Blue searches,
one can give at least three answers; minimum depth (six moves in typical middle
game positions); average depth (perhaps eight moves); and maximum depth (highly
variable, but typically in the ten-to-twenty-move range).
Yet, although Deep Blue’s
speed and search capabilities enable it to play grandmaster-level chess, it is
still lacking in general intelligence.
It is clear that there are significant differences between the way HAL
and Deep Blue play chess.
How HAL Compares with Deep
Blue
As we
mentioned earlier, there is considerable evidence that HAL plays chess in the
human style. In fact, given that
Kubrick and Clarke chose a game between two humans as the model for the Frank
Poole-HAL game, it would have been extraordinary if HAL had not played in the
human style. Deep Blue, on the other
hand, is a classic brute-force-based machine, albeit it has considerable search
selectivity. So a comparison between
HAL and Deep Blue must begin by comparing computer and human styles of chess
playing.
The difference is actually quite subtle and would
probably be detected only by persons experienced with computer play. A computer engaged in an electronic dialogue
is said to have passed the Turing test if the computer’s conversation is
indistinguishable from that of a human being.
At the present time, no computer has ever passed the Turing test. HAL, by comparison, would pass with flying
colors and later turn around and try to kill the person administering the
test!
Drawing on this analogy, one could devise a Turing test
for computer chess programs. That is, a
chess machine would pass the chess-restricted Turing test if the person playing
the machine could not determine whether or not he or she was playing against
another person or a machine. Most players
would find it difficult to discern whether or not a Deep Blue game was played
by a human or a computer. This was
proven in an informal experiment conducted by Frederic Friedel,
Kasparov’s computer adviser. Friedel showed
Kasparov a series of games in a tournament played by Deep Thought and several
grandmasters. Without identifying the
players, Friedel asked Kasparov to pick out the moves
made by the computer. In a number of
cases Kasparov mistook the computer’s moves for those of a human grandmaster,
or vice versa. In general, only chess
players who have considerable experience playing against computers can identify
computer moves.
A specific example demonstrates the difference between
the human style of play and the computer style of play: the fact that chess
programs exhibit a lack of understanding of the role of timing in chess. Concepts involving ‘never’, ‘eventually’, or ‘any
time’ can be very difficult for computer programs. For example, a weapon in the arsenal of most
strong human players is the idea of a fortress
- a position where a player who has fewer or less-powerful pieces, can create
an impenetrable position in which the opponent can never make progress (see figure
5.4). In the 1996 Kasparov-Deep Blue
match, Kasparov was able to clinch a draw in the fourth game by means of a sacrifice that created a
fortress (see figure 5.5). Although Deep Blue can be programmed to identify
many different specific ‘fortresses’, detecting the general case of a fortress
is still beyond its capabilities and presents us with a complicated
pattern-recognition problem worthy of further research.
Another difference between human and computer styles of
play can be seen by examining a position involving the ability to reason. At the conclusion of the historic match,
Kasparov visited our research lab and showed us a position from which he was
absolutely certain that Black would eventually checkmate. Kasparov could not say precisely how many
moves it would take, and he was curious to see how Deep Blue would analyze the
position. Even after several minutes of
search, however, Deep Blue did not see the checkmate. Sometimes search is a very poor substitute
for reasoning.
There is, of course, another obvious difference between
the human style (HAL) and the computer style (Deep Blue) of play: Humans have
emotion. One of the supposed advantages
of computers over humans in a game like chess is that computers lack
emotion. They are not embarrassed by
previous mistakes, they don’t slump dejectedly in their chairs when they get
into a bad position. One wonders, then, whether HAL’s emotional side possibly influenced his style of play
(see chapter 13).
When HAL thanks Frank for “an enjoyable game,” this is
more than simply a pleasing platitude entered into HAL’s
system by his programmers. Because he
possesses both emotion and general intelligence, HAL has the ability to enjoy a
good game of chess. Alas, while Deep
Blue is sometimes capable of playing magnificent, world-class chess, it is
unable to appreciate its own moves.
How, one might speculate, would Deep Blue fare in a
match against HAL? Deep Blue could find all the moves HAL plays to finish off
the game with Frank in a fraction of a second.
Clearly, both machines are tactically very strong. However, given HAL’s
general intelligence, one suspects it would be able to avoid most of the
typical computer mistakes to which brute-force machines like Deep Blue are
susceptible. On the other hand, Deep
Blue’s search strategy could be a strength; it might find counterintuitive
moves that would probably be dismissed by a humanlike search. I suspect it would be a very interesting
match, in which each computer would gain its fair share of wins.
The idea of HAL losing a
game, however, brings up an interesting point. Throughout the film, HAL
consistently asserts that he is “incapable of error”. Given the overwhelming complexity of the
game, it is not plausible for HAL to play perfect chess, as this would require
HAL to have solved all possible chess problems. So, if HAL does not play perfect chess,
there must be some winning positions in which HAL fails to play a winning move or
drawn positions in which he doesn’t find the drawing move. In the normal sense of the word, these would
constitute errors. HAL’s
own interpretation of the word error
remains mysterious.
Man versus Machine today
In
one six-game match, the 1996 Kasparov-Deep Blue “showdown” demonstrated both
the great strengths and the great weaknesses of 1990s computer chess machines.
The diagram in figure 5.6 illustrates how quantity can indeed become
quality.
This position was taken from Game-01 of the match. Deep Blue’s move-23 was P-Q5 (or d5 in algebraic notation). This strong move completed the demolition of
Kasparov’s pawn structure; all Black’s pawns were soon isolated and unable to
support each other. Kasparov knew that
23. P-Q5 was a strong move, but
he did not expect it from a computer, because it involved a pawn sacrifice
something computers are often reluctant to do.
However, Deep Blue, in analyzing the position, saw deeply enough to
realize that 23. P-Q5 was only a
temporary pawn sacrifice; that is, it saw that it would later win back the pawn
and retain all the other advantages.
As figure 5.7 illustrates, however, computers can
sometimes lack basic chess concepts that are understood even by amateur
players. The diagram shows the final
position in Game-06 of the match.
Although Deep Blue was actually a pawn ahead, its pieces were all trapped, or immobilized. Deep Blue had not recognized the danger in
this position many moves earlier, when there was still a chance to avoid
it. If Deep Blue had not resigned, Kasparov could have
won easily by, for example, opening up the kingside and attacking the
undefended king. The human ability to
reason about permanently trapped pieces was a deciding factor in this
game.
Although the competitive aspects of
human-versus-computer play attract considerable attention, cooperation between
man and machine is becoming more and more common. Many grandmasters use PC chess programs to
help them analyze chess positions. And
players can now learn more about chess endgames by studying
computer-generated endgame databases that demonstrate perfect play in positions
with five or fewer pieces on the board.
But, perhaps most notably, Kasparov feels that the 1996 match with Deep
Blue helped him understand more about chess.
This may be a sign of things to come.
The Future of Computer Chess
Early optimism in the field of artificial intelligence
led people to believe that the chess problem would be relatively easy to
solve. In the late 1950s, Herbert
Simon, one of the founding fathers of artificial intelligence, predicted that
it would take only ten years for a machine to become world champion. Despite his expertise in the field, Simon
was off by at least thirty years. After
Kasparov lost a regulation game to Deep Blue, many people mistakenly assumed
that the chess-playing problem had finally been solved. It is becoming more and more apparent,
however, that chess mastery requires an intriguing mixture of skills: pure
calculation, sophisticated evaluation, learning, and a generalized reasoning
capability. Although a machine like Deep
Blue excels in calculation, at present it still lacks many other skills essential
to consistent world-class chess play.
Until computers possess the ability to reason, strong human chess
players will always have a chance to defeat a computer-style opponent.
Given recent advances in hardware speed and algorithms,
I believe Kasparov’s loss to a machine in a regulation match was
inevitable. Kasparov still has the
advantage in that he has the ability to adapt quickly to weaknesses in a
computer opponent, a skill that current chess-playing machines lack. With continued progress, however, it is
likely that we will see the end of competitive matches between man and machine
sometime in the next century. Certainly
competitive chess will continue: man against man; machine against machine. Ultimately, though, the computer’s
superiority over human players will be so great that the only value in
man-versus-machine play would be the instructional benefit it provides human
players, or as in 2001 its
recreational use on journeys to faraway planets. The applications that have been, and will
continue to be derived from developing a world-class chess machine will advance
our use of computers as tools for solving other complex problems. Even so we are still decades away from
creating a computer with HAL’s capabilities.
Acknowledgments
I would like to acknowledge the other members of the Deep Blue team: Feng-hsiung Hsu, the principal designer of Deep Blue, and
A. Joseph Hoane, Jr. Other IBM Research staff that
supported the project include C.J. Tan and Jerry Brody. My thanks to tcrain@s2.sonnet.com for directing me to
the article by Grandmaster Larry Evans that includes the Frank Poole-HAL game
in its entirety.