Slaughter on 7th Avenue
|
|
The world's number one is still licking his wounds after IBM's chess computer
beat him last month.But is Kasparov right to feel so hurt by the
defeat?
Donald Michie
"I'M NOT AFRAID to say that I'm afraid,"
said Garry
Kasparov last month after his fifth game against
Deep Blue
2. The match between man and machine was all square as Kasparov spoke
to the watching chess aficionados and world press
assembled at the Equitable Center on New York's Seventh Avenue.
It was a chilling moment for all of us, raising to an extraordinary pitch
the tension surrounding the final game next day.
Then it came.
On his seventh move, sixth game, Kasparov played the wrong
pawn in a well- known opening. Deep Blue's immediate knight sacrifice sprung
a trap from which there is little escape. Kasparov's face on the big screen
in the auditorium stared in horror. Then he buried his head in his hands.
After Deep Blue had played its 19th move, Kasparov resigned the game -the
shortest losing game of his career-and the match.
Kasparov has an unprecedented chess rating of 2805. Grandmaster
Joel Benjamin, who worked with the IBM team that put Deep Blue 2 together,
rates the machine at 2700. According to the statistics of the rating system,
this kind of lead should allow Kasparov to win twice as many games over Deep
Blue as he loses. Chess masters had expected that a week of his usual confident
superchess would be enough to destroy Deep Blue. How then did catastrophe
overtake the greatest chess player that the world has ever seen?
This was a battle between two different ways of playing chess.
Deep Blue plays chess like no human on Earth. Kasparov was eager to learn
more about the machine's foibles. He had shocked the chess world in February
1996 by losing the first of six games to an earlier version of Deep Blue,
and word from the IBM camp before last month's match was that the latest
incarnation was beating its predecessor. This time round, Kasparov set aside
two months for intensive pre-match preparation. Unfortunately, because this
was the new Deep Blue's public debut, no samples of its play were available.
Eventually, he went into the match blind-something he would never do against
a human.
So how do humans play chess? Psychological research shows
that the critical skill for human chess players is pattern recognition. A
pattern is any feature, simple or complex, that can be spotted "at a glance".
The stronger the player, the larger the range and complexity of patterns
he or she can recognise and interpret
("A game
for life", New Scientist, 4 September 1993, p 23). Studies have also
shown that a grandmaster holds around 100 000 patterns in his or her head.
Not, of course, that grandmasters sift through these patterns one at a time.
Rather, the patterns are brought to bear much as a writer can assemble learnt
words, phrases or whole sentences to carry a story to its denouement.
One can broadly distinguish two components of chess
capability-search and evaluation. Search is about following different lines
of play; "what if I do A, and my opponent does B, followed by my doing C,
or alternatively my opponent might reply D, and then I might do E, F or ...
." This method produces a "tree" of possibilities (see
Diagram).
Evaluation, on the other hand, is not just a matter of spotting
the material value of a position-a rook, for example, is worth about one
bishop plus one pawn. From long experience, humans can recognise geometrical
patterns indicating future threats and opportunities, and can weigh these
against each other. This largely intuitive skill is highly developed in
grandmasters. By comparison, machines are weak at evaluating a position's
long-term, or strategic, merit (see Grabbing a
poisoned rook).
Quality, not quantity
Leading chess players tightly focus their searches-they tend to look at only
a few branches in the tree of possibilities, and only a few moves ahead.
Grandmasters famously compensate for this by using pattern recognition to
form judgements about the broad line that future play might take. An admirer
once asked the grandmaster Richard Reti how many moves he looked ahead. "One,"
he replied, "the right one." Reti was exaggerating, of course. But it is
true that a grandmaster does not ordinarily examine more than about thirty
positions in the tree, and rarely more than fifty. In some cases, however,
Deep Blue examines 50 billion or more.
This astounding search capability is Deep Blue's secret. It
makes up for strategic blindness with brute-force enumeration of tactical
possibilities. To decide its next move, it can probe the tree of possibilities
solidly to a depth of five to six moves ahead and can explore the future
still further along selected branches.
Deep Blue can evaluate twice as fast as its predecessor at
a colossal 200 million positions per second. To achieve this, the IBM team
has equipped the machine with 32 parallel processors, each with between six
and eight accelerator chips. More subtly, but more importantly; the team
has also improved the way Deep Blue chooses between potential positions.
The big calculation
At the heart of Deep Blue is a search method called the minimax principle.
This allows the computer to choose its next move from the tree of future
possibilities by comparing scores for positions that are back-calculated
from several moves ahead (see Tree of
possibilities). The scoring is done by a position-evaluator, which rates
each future position by checking it for several hundred stored patterns.
These patterns, or attributes, are hard- wired into Deep Blue's
accelerator chips -a few hundred against the 100 000 in Kasparov's head.
They include ways to recognise the safety of the king and to check how much
room for manoeuvre a position leaves other pieces. These patterns are very
primitive compared with those that Kasparov can recognise: they are like
words to his phrases. And while he uses his stored patterns to think
strategically about huge classes of future positions, Deep Blue applies its
patterns to just one position at a time.
Tree of future possibilities |
||||||||||||||||||||||||||||||
|
||||||||||||||||||||||||||||||
A CHESS COMPUTER cannot reason about
the broad consequences of a move. Instead, it calculates billions of nitty-gritty
possible futures and chooses between them using the minimax principle. Take, for example, the tree of possibilities in the diagram. The machine, playing white, must choose between the three positions A, B and C, by applying a position-evaluation formula to assign scores to each one. If the machine looks only one move ahead, then it compares the face values (in circles) of A, B and C. These are 150, -20 and -10. The obvious choice is to go for the highest score, called the "max", which in this case is move A.
But suppose that the machine has time to take into account
black's possible responses and the options for its own next move. The machine
assumes that lust as white prefers the move with the maximum score, black
will choose the move with the minimum score (called the "min"). So start
at the 17 possible positions at the bottom-at what is called the lookahead
horizon-and work upwards.
These 17 possible positions are generated by the seven groups
of options open to white directly above the lookahead horizon. White wants
to know the move with the maximum score in each of these seven groups, which
is entered as the "backed-up value" in a rectangle. On the far left, for
example, white must choose between -20 and 40 and will opt for 40, which
becomes the backed-up value.
In similar fashion, in the tier above, black has three groups
of options. For each group, it chooses the move with the minimum backed-up
value, which becomes its backed-up value. On the far left again, black must
choose between 40 and 10 and will choose 10. This brings the machine back
again to white's original move. This time, though, it looks at the backed-up
values, rather than the face values. This second, deeper analysis changes
white's preferred move from its original choice, move A, to move B (see Table).
Generalise this to 12 tiers rather than three and you have Deep Blue. This task is made feasible thanks to a process called alpha-beta pruning, devised in the 1950s by the American Arthur Samuel, author of the first highly capable computer draughts player. His method discards whole chunks of the tree on the fly, without further ramifications. Most of the tree, in fact, remains unexplored without affecting the values backed up to top level. |
The machine scores each position by evaluating the degree to
which each attribute (a1, a2, a3 . . .)
is present, and giving each a weighting (w1, w2,
w3) that reflects its relative importance. To decide the total
score for a position, the machine then performs a calculation
(a1w1
+a2w3+a3w3.. .) This sum, often
called a "scoring polynomial" also takes into account the values of the machine's
pieces and its opponent's. The aim is chose the highest score which then
dictates the next move.
The IBM programmers have increased the number of attributes
that Deep Blue's position-evaluator recognises and have tuned the weights
given to each one. They have also improved the machine's ability to change
the weightings according to the "phase" of the match.
This stems from an idea of Claude Shannon, the founder of information theory.
In 1950, he pointed out that the importance of pieces, and certain patterns
of pieces, changes throughout a game. A pawn, for example, can become much
more valuable in the closing phases of a game because it might be possible
to promote it into a queen, while a "Chinese wall" of pawns in an end game
can be invaluable. Deep Blue can now recognise a large number of different
phases and adjust the attribute weightings accordingly.
Grabbing a poisoned rook |
WHAT stands out as obvious
to a human player can be invisible to a machine. In the position above, one
of Deep Blue's ancestors, Deep Thought 2, has the white pieces. After lengthy
searching (not reasoning) the machine captures the black rook with its pawn.
To any player with a sense of danger, such short-sighted greed seems infantile.
The computer sees that "in the end" it will have
gained a rook, conventionally worth 5 points, minus 1 point to allow for
the fairly immediate capture of its adventurous pawn. But this tactical
evaluation misses the point. Deep Thought 2 has no way of seeing that white's
only salvation is the pawn-barrier between the white king and black's extra
pieces.
The barrier is recognisable to a human as a pattern
in which interlocked white and black pawns form a "Chinese wall", impregnable
so long as white does nothing to breach it. White's greedy capture allows
a hole in the wall, making the penetration inevitable. How far in the future
lurks the nemesis? Working this out would mean looking ahead more than 50
moves, according to the British grandmaster David Norwood. "Who cares?" asks
the human player. "Just give me the telltale pattern and a little common
sense reasoning!"
|
Yet for all its skilled play, Deep Blue has very little
intelligence. It doesn't learn from experience. It cannot tell chess sense
from nonsense, and it is blind to what a chess position or chess game is
really about. No automated development tools were used, and its
position-evaluator was handcrafted. It can offer no useful analysis of why
it made some apparently deeply calculated move. Forget artificial intelligence.
Deep Blue is a product of the sustained application of human intelligence
to modern computing technologies.
Mind-reading machine
Given all those disadvantages, how did Deep Blue beat Kasparov? From knowledge
of Deep Blue's inner workings, together with a close study of Kasparov's
face through the closing games, I am in no doubt. Deep Blue came across to
Kasparov as being able to read his mind, and this slowly wore him
down. Deep Blue's speed means that it can make calculations during the time
allocated to its opponent to consider and make a move, as well during as
its own. So, say Kasparov took 15 minutes to elaborate a deeply laid plan.
Finally, he moves. During this time, Deep Blue has calculated a branching
tree of several hundred billion possibilities. According to Deep Blue's
programmers, the machine had predicted Kasparov's moves in about half the
cases so it could reply instantly.
Imagine the effect on Kasparov when a succession of his deeply
pondered moves are answered without delay. When this happened he grimaced.
In addition to the "spooky" effect, an instant response in a complex and
difficult position applies a very peculiar form of time pressure not
characteristic of human play. It gives no pause for the human player to relax.
These uncanny effects slowly unstrung the man before our eyes. It was not
Deep Blue that destroyed Kasparov. It was Kasparov.
So where does all this leave us? For the
artificial
intelligence community the real action lies elsewhere: in the developing
world of chess machines which are being sold not so much for their playing
performance, but for their ability to tutor human opponents.
With this new generation, sheer skill must take second place to something
more complex, usually called "expertise". Cognitive scientists define this
as the capacity to handle novel situations, to reconsider and explain the
validity of rules, and to reason from first principles. To qualify, machines
must do better than just beat world champions. They must also hold their
own at the press conference afterwards as they explain their winning strategy.
This task is way beyond Deep Blue. The complex of phase-specific
scoring polynomials in its position evaluator is unstructured and opaque.
This became clear from a curious episode in game 2, which Kasparov eventually
resigned. On move 36 of that game, Deep Blue played a pawn rather than the
obvious queen move. This choice led, in still unfathomed ways, to the collapse
of Kasparov's position in that game.
He issued the first ever high-profile challenge to a computer
to explain its decision or be under suspicion of improper human intervention.
He insisted that the Deep Blue team seal the printed log of the machine's
thought processes during this game. After the match, when Kasparov and his
team unsealed the log, they found voluminous tree-search calculations. But
no thought processes.
Intriguingly, while the Kasparov match unfolded, across town
another contest was under way. This was the annual Loebner prize for the
most human-like conversation sustained by a machine with a panel of examiners.
The winner was Converse, a program developed by London-based Intelligent
Research, which is headed by the international master David Levy.
In 1970, the same David Levy laid a bet with me and others that he would be undefeated by a chess machine for at least 10 years. He won his bet, but was finally vanquished in 1990. He now returns to triumph in a larger domain of discourse than anything Deep Blue could begin to conceive.
Author Donald Michie is emeritus professor of machine intelligence at the University of Edinburgh. |
Chaos | Quantum | Logic | Cosmos | Conscious | Belief | Elect. | Art | Chem. | Maths |