May 18, 1997
What Deep Blue Learned From Grandmasters
By BRUCE WEBER
hree months ago, the computer scientists at IBM discovered a bug in their now-famous chess machine, Deep Blue. For some reason, as the computer searched way out along the lines of possibilities in examining certain moves, it began seeing a queen where there wasn't one, a kind of computer hallucination.
"All over the place, Deep Blue was thinking there was an extra queen on the road," said Joe Hoane, a scientist on the Deep Blue team.
In 15 months, the IBM team redesigned the hardware, doubled the calculating power and took Deep Blue to chess school.
The alarming discovery came during the home stretch in the preparation of the computer for its rematch with Garry Kasparov, the world chess champion, who had roundly defeated it in February 1996.In 15 months of work, which began almost immediately after Kasparov's victory, the team redesigned some hardware, doubled the computer's calculating power and, most critically, took Deep Blue to "chess school," teaching it tricks that grandmasters would be proud of and that would so flummox the champion that he questioned its very soul.
But in February, there was this invisible queen.
The culprit, it turned out, was a newly designed chip linking Deep Blue's powerful multiprocessors with its chess software. It took two weeks to adjust the software and fix the bug, the mention of which still sends the chip designer, Feng Hsiung Hsu, into a fit of guilt.
The image of a magically appearing queen nicely represents the accomplishments of Deep Blue, which a week ago made history by whipping Kasparov in a six-game match. Deep Blue sees things, at least on occasion, that no other machine, or human, can see. Unlike the queen, most of them are really there.
The match ended in an atmosphere of hostility and suspicion, and Kasparov expressed his frustration again and again in terms that had to do with the machine's magic. During the match, he attributed one move to "the hand of God." In an interview on Friday, in which he challenged Deep Blue to a third match, the word he used was mystery.
I don't know what the computer did wrong or right. It's a mystery.
Garry Kasparov
"It's very difficult to analyze the results of the match," Kasparov said. "I know what I did wrong. But I don't know what the computer did wrong or right. It's a mystery."What particularly irks Kasparov is his sense that it was not Deep Blue's awesome calculating ability -- it can examine 200 million moves per second -- that defeated him. It was its ability to evaluate those positions. It seemed, he said, to understand complexities of chess that no other computer has come close to duplicating. The Deep Blue team agreed that this was the main element in the computer's improvement (though the extra speed didn't hurt), but it is something Kasparov has had trouble accepting.
"If that is the case," he said, "then they have to explain it to the rest of the world. Tell us how you accomplished it, because it's far beyond anyone's understanding. I met something I couldn't explain. People turn to religion to explain things like that. I have to imagine human interference, or I want to see an explanation."
The Deep Blue team, clearly offended by Kasparov's intimations, would not commit themselves to a third match.
"There are a lot of great chess players," Hoane said, when asked whether he was inclined to go at Kasparov again.
Frederick Friedel, Kasparov's computer adviser, said their own computer, Fritz -- capable of sophisticated evaluation but 1,000 times less powerful than Deep Blue -- duplicated 80 percent of Deep Blue's moves during the match within a minute or so of analysis. Most of the other 20 percent were duplicated after letting Fritz search for six or eight hours. But a handful of moves, maybe 1 percent, Fritz could never duplicate at all, even after Friedel and Kasparov gave it substantial clues.
Frederick Friedel,
Kasparov's computer adviser
"So it's not the 200 million positions per second," Friedel said, with some exasperation. "It's the programming. There's something in there. I would like to understand. And I would like to have it for Fritz."That, Hoane said, "is a great compliment." His team members added that improving the computer's chess knowledge was the focus of their work almost since the last match ended.
"Last year, Garry said quantity began to feel like quality," Feng said. "This year the quality got in before the quantity started to apply."
It was in early March 1996, just a couple of weeks after the first match, that C.J. Tan, the Deep Blue project manager for IBM, made a list of ways in which the computer could be improved.
The list, about one and a half single-spaced pages, included scrutiny of the computer's hardware, the increase of databases dealing with chess endgames, the augmentation of the computer's opening repertory, the creation of a more powerful and sophisticated evaluation function for chess positions, the hiring of additional grandmasters to work with the team and the development of a strategy to exploit an opponent's time trouble and to disguise the computer's own strategy on the board.
From the start, they knew they could make the computer faster, so they concentrated on making it smarter. But it was not entirely clear how to do that. Some things were tried and discarded.
There was an aborted attempt to adapt a program called Flash, which detects similarities in genetic patterns among humans and other creatures, to chess. The idea was that if the computer could recognize a situation on a chessboard that recalled a game previously played by a grandmaster, perhaps it would be able to apply the grandmaster's logic.
It did not work. A chess game has so many variations and nuances -- a difference on a single square can mean uncountably different possibilities -- that defining similarity turned out to be too daunting.
"Chess is just too chaotic," Hoane said.
Kasparov knew that the opening can be particularly tricky for a computer.
Each team member had a specialty. Tan oversaw both the scientific work and the negotiations with Kasparov for the rematch. Jerry Brody, an engineer, made adaptations on the machine hardware. Murray Campbell, the team member with the greatest chess expertise, was responsible for integrating chess knowledge into the system.And Feng designed the new accelerator chip -- "think of it as the innermost loop of the chess program," Tan said -- which was the lead priority for the first six months.
Joel Benjamin, a grandmaster, joined the team full-time in August, in the latter stages of the chip design. He spent his time playing position after position against Deep Blue, filling up notebooks with observations and trying to locate as many situations as possible in which the computer evinced weaknesses. Hoane then had the responsibility of translating Benjamin's observations into computerspeak.
"It's a problem of articulation," Hoane said, "which is my strength as a programmer."
The computer's added processing power was ready in January, and it was in tests with the new processors that Feng's chip began revealing the phantom queen. That problem was corrected by mid-March, and shortly afterward, grandmaster help began arriving for Benjamin.
For the last two months, he was joined by Miguel Illescas of Spain and John Fedorovich and Nick De Firmian, both New Yorkers, who worked on the machine's opening strategies. For a computer, the opening can be particularly tricky. With many undeveloped pieces on the board, the computer's understanding is simply not as good.
This was something that Kasparov did foresee; he prepared openings that he figured the computer (and its handlers) would not anticipate, to force the computer to play in unfamiliar territory as early in the game as possible. The weakness of this strategy was that it forced Kasparov to play against his own better instincts, which he said in the interview was a mistake. But it was not part of the mystery. He understood it.
The mystery is the computer's ability, at least at some points, to play positional chess.
The heart of the mystery lies, apparently, in Benjamin's earlier contributions. In examining situation after situation, he was trying to determine the occasions during which the computer's sense of a chess position was incomplete or unsophisticated."For example," Benjamin said, "I noticed that whenever Deep Blue had a pawn exchange that could open a file for a rook, it would always make the exchange earlier than was strategically correct. Deep Blue had to understand that the rook was already well placed, and that it didn't have to make the exchange right away. It should award evaluation points for the rook being there even before the file is opened."
This gets at Kasparov's frustration. The so-called mystery is the computer's ability, at least at some points, to play what is called positional chess, a concept that is difficult to define.
Positional chess, as opposed to tactical chess, involves a situation in which there are no clear objectives on the board, no obvious squares to be commandeered, no threats to be made. It is a kind of jockeying, with the two sides maneuvering for position, from which to begin long-term plans. It is the kind of chess that grandmasters generally say they play better than machines, because the power of individual moves is subtle, deeply resonant, rather than calculable.
Friedel tried to explain it with an anecdote about the development of Fritz. He once asked grandmaster Walter Browne about a particular position in which each side had the same number of pawns and pieces and the same number of controlled squares.
"Any amateur would have said the position was a draw," Friedel said. "I said, 'Walter, who is better here?' And he said, 'White is winning.' I said, 'Why?' and he said white controls more space." When Friedel pointed out that in fact each side controlled exactly the same number of squares, Browne continued, "Oh, these squares here don't count. They aren't important."
How to tell important squares from unimportant squares? Friedel didn't understand.
"But two years later," he said, "I was driving with the former world champion, Max Euwe, and I had the position in my pocket, and I asked him, and he said: 'White's winning. White's better. It controls more squares.' I counted them for him. And he said, 'Oh, these squares are not important.' "
The point, Friedel said, is that this information is too subtle to program. "Watch grandmasters at the board," he said. "It doesn't matter if they speak the same language. They look at each other and communicate. They understand these things."
Evidently, Deep Blue understands some of these things too.
"Garry didn't believe we were doing what we said we were doing," Tan said. "Garry prepared to play against a computer. But we programmed it to play like a grandmaster."
To that, Kasparov would agree.
"I have to pay tribute," he said. "The computer is far stronger than anybody expected. I wasn't ready to take on such a challenge in this match. Now I am ready to play a challenge that is threatening to my very existence. This match wasn't frightening enough for me, I guess.
"You talk about American fair play?" he said. "Rubber match."
