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. Choose Your Next Move Face Value Minimax Score Preferred Back-up score move Preferred move MoveA 150 Best 10 Worst Move B -20 Worst 120 Best Move C -10 Middle 40 Middle 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 (a₁, a₂, a₃ . . .) is present, and giving each a weighting (w₁, w₂, w₃) that reflects its relative importance. To decide the total score for a position, the machine then performs a calculation (a₁w₁ +a₂w₃+a₃w₃.. .) 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.

'For all its skilled play, Deep Blue has very little intelligence. It doesn't learn and it cannot tell chess sense from nonsense'

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.