Kasparov versus Deep Blue: The Re-match

Prelude

For the third time, the computer chess community was privileged to witness a match between the human world chess champion, Garry Kasparov, and IBM's Deep Blue chess machine. In 1989, Kasparov easily defeated the program -- then named 'Deep Thought' -- in a two-game, fast-play match. The Deep Blue team spent seven long years preparing for a return match with Kasparov, which they eventually got in 1996.

Last year's Kasparov - Deep Blue match was played in Philadelphia in February. The six-game match, played under tournament conditions, was contested for a prize fund of $500,000. The very first game produced a stunning surprise, as Kasparov stumbled in an unbalanced position and went on to a historic defeat. For the first time under tournament conditions, the world chess champion had lost to a computer. After the match, Kasparov identified the first game as a critical wakeup call for him. He studied the program's play, identified weaknesses in it, and used this to win three of the remaining five games (with two draws) to score a convincing match victory. The consensus afterwards was that Kasparov grew in strength as the match progressed. Were the match to continue, the expectation was that his dominance over Deep Blue would only grow.

The 1996 match reportedly generated over $250 million of "free favorable advertising" for IBM (to quote IBM). With that kind of media presence, it was inevitable that there would be a re-match. It would be another six-game event, played under similar conditions to the previous match. The prize fund was set at the staggering amount of $1.1 million, $700,000 to the winner.

Pre-match predictions were decidedly in Kasparov's favor. Kasparov's dominance at the end of the 1996 match convinced most experts to predict the champion to score four or more points out of six. In addition, Kasparov was coming off a superb performance at the Linares tournament, where he scored 8.5/11 against the world's elite grandmasters, including wins against the number 2 through 6 finishers in the event. In the past year, Kasparov's results have been improving, pushing his rating to an all-time high of 2820.

While much is known about Kasparov's activities during the past year, the same cannot be said for Deep Blue. After the Philadelphia loss, the Deep Blue team retreated to their laboratory just north of New York City and did extensive secret preparations. (Although it must be said that Deep Blue Junior, a small version of its big brother, toured the country and played many exhibition games.) The Deep Blue team consisted of Feng-hsiung Hsu and Murray Campbell, veterans from the Chip Test and Deep Thought days at Carnegie Mellon University, and IBM additions C.J. Tan, Joseph Hoane, and Jerry Brody.

Prior to the match, only two things were known about the new Deep Blue (affectionately called Deeper Blue): their chess-playing VLSI chip had been re-fabricated, presumably to make it faster and add extra evaluation function capabilities, and Grandmaster Joel Benjamin was hired to work full-time since August 1996 on testing and developing the chess knowledge. The new hardware consisted of a 32-node SP-2 computer with 512 chess chips. IBM said that the new configuration was twice as fast as the previous year, evaluating roughly 200 million positions per second.

The match was held May 3-11 at the Equitable Center in downtown Manhattan. The actual games were played on the 35th floor of the building, but the audience was in an auditorium on the ground level, watching the game via closed circuit television. The auditorium accommodated up to 500 people, most of whom paid $25 per game for the privilege of watching. Five of the six rounds were sold out.

Game commentary was provided by Grandmaster Yasser Seirawan and International Master Maurice Ashley (reprising their roles from last year's match) with the welcome addition of International Master Mike Valvo. Mike, of course, is well known to the computer chess community, having been the tournament director for most of the major computer chess tournaments over the last 10 years. Seirawan and Ashley provided an analysis of the game in progress, while Mike provided insights into the computer chess side of the game. Mike's presence gave some counterbalance to the tendency of some of the commentators, audience, and press to extol the virtues of Kasparov's play, while finding flaws with Deep Blue.

The commentary was highly entertaining, as the commentators tried to keep the discussion at a level that everyone could understand. It featured a lot of humor, anecdotes, audience participation and guest appearances from members of the Deep Blue and Kasparov teams. Even if you did not know a lot about chess or computers (like most of the press) you could still enjoy the show.

The commentators job was made easier by Kasparov's antics over the board. Kasparov's face is very expressive during a game -- he does not hide his emotions. As the game progresses, you can read from his expression how well (or poorly) he is doing. He starts off by taking his watch off and placing it beside his score sheet. Whenever the watch goes back on his wrist, as far as he is concerned the game is over and he does not need to think further. Needless to say, this is an important event to watch for! Sometimes Kasparov would stare off into space; sometimes he would shake his head angrily. When he was upset, he got up from his chair and prowled around the playing room like an impatient animal. The commentators would closely watch Kasparov's face, trying to interpret the current game situation from his expression. Many human opponents of Kasparov's have criticized his antics at the board, accusing him of deliberately trying to disturb their concentration. Yet he is just as emotional against a computer as he is against a human opponent. If nothing else, it made for a very entertaining show.

The commentators were placed at the center of a long stage that had three large video screens. The right screen showed the output of a camera perched above the actual game board so that you could see when moves were played. The left screen had a live action feed from the playing room, continually zooming in on the participants, the clock, and Kasparov's watch. The center screen was used for analysis by the commentators. The 1995 World Computer Chess Champion Fritz was used to analyze the game in progress. An interesting feature was to compare Fritz's evaluation with that of the commentators and their chess guests (usually an assortment of Grandmasters, including Zsuzsa Polgar, the World Women's Chess Champion). Interestingly enough, particularly in game 1, Fritz's evaluation greatly differed from that of the experts (and, reportedly, of that of Deep Blue).

Media interest in the re-match was high. IBM's press room accommodated 90 people, but eventually over 300 press were accredited. The press room moved to occupy half of the 50th (top) floor of the building, commanding a majestic view of Manhattan. Visiting the press room was quite an experience. It was very busy, with lots of grandmasters analyzing (a who's who of U.S. chess was there, along with several strong grandmasters from other countries) and media people from around the world scrambling for stories from anyone claiming to be an "expert." The IBM publicity juggernaut milked this event for all it was worth.

The press generally covered the match as a man versus machine event, with Kasparov defending the honor of mankind against the onslaught of the machine (for example, Newsweek's cover story was titled "The Brain's Last Stand"). Chess being the intellectual game par excellence, many an article considered the event a test of human dominance in matters of intelligence. If the articles were to be believed, a Deep Blue victory would do irreparable damage to mankind's self image, comparable to the impact of Galileo's and Darwin's work. The press exaggerated this story out of proportion to create the false image of a technological monster, playing on their audience's fear of the unknown. Yes, beating the chess World Champion is an important milestone in artificial intelligence history, but it pales in comparison to the difficulty of important, real-world problems that artificial intelligence researchers are trying to solve. (Some jokes actually caught on to these problems. For example, David Letterman and Jay Leno, two popular U.S. talk show hosts, made fun of the things Deep Blue still couldn't do, such as jumping over a fence or having a date.)

Of course, a loss by Kasparov is not a defeat for mankind, but a triumph: man has found a way to master complex technology to create the illusion of intelligence. The press is the gullible audience which has been fooled by a sleight of hand; the Deep Blue team is Harry Houdini and IBM, his agent.

Like the Philadelphia match, this event was covered live on the World Wide Web. The IBM web site was very busy, making access occasionally problematic. It provided live coverage of the moves as they were played, a transcript of the commentary, and various pieces of background information on chess, Kasparov, Deep Blue, and IBM's computer technology. Apart from a few minor slips, such as stating that checkers was a trivial game like tic-tac-toe, the web site was impressive. The URL is http://www.chess.ibm.com.

The Match

Game 1

Kasparov started with the White pieces and tried a safe positional Reti, but was immediately put off guard by Deep Blue's second move. This demonstrated that the Deep Blue team had done a lot of work on their opening preparation.

Kasparov built up a small comfortable advantage. Just when you thought he would slowly use his positional superiority to squeeze Deep Blue, the program suddenly and unexpectedly blasted the position wide open, causing the commentators to start worrying about Kasparov's chances. Of course, all this concern was misplaced; Kasparov went on to demonstrate that he had seen through all the complications and he had everything under control. Kasparov sacrificed the exchange for a pawn to reach the kind of position where computers are notoriously weak: positional compensation for material. He exchanged pieces to reach a material-down endgame, where Deep Blue's pieces had no good squares, and Kasparov's connected passed pawns eventually triumphed. Of note is that in the entire game, none of Kasparov's pieces ever crossed the fourth rank.

An exuberant Kasparov came down to the auditorium after the game to answer questions from the commentators and the audience. He clearly reveled in the exultation accorded to him by the appreciative audience. Looking on was a sullen Deep Blue team, greatly disappointed by their prodigy's play.

The initial impression from the game was that Deep Blue played well, except for a couple of time-wasting moves and one poor positional move. Kasparov had to play precisely to beat the computer. After the game, it seemed as if everyone was predicting a Kasparov rout. Joel Benjamin, the chess player behind the electronic chess player, was quite disappointed with Deep Blue's play. From his testing, he was convinced that Deep Blue could play much better than it had shown in game 1.

The game illustrated several themes that were to repeat themselves in the match. First, Deep Blue was extensively booked up in the openings. This does not come as much of a surprise to chess programmers, since CDs containing hundreds of thousands of grandmaster games are commercially available. Nevertheless, it may have been a surprise to Kasparov. Second, Deep Blue still made "computer" chess moves -- moves that the commentators loved to poke fun at -- but the errors weren't as major as the ones seen in the previous match. Third, Kasparov wasn't afraid to give up material for positional gains. He believed that computers weren't capable of correctly assessing material imbalances properly.

As a postscript to the game, postmortem analysis revealed that Deep Blue could have drawn the game after the queens came off the board. Now, if only Deep Blue could search a few more ply...

Overall, Kasparov had to be very satisfied with the first game. He played well and Deep Blue's play exactly matched his expectations. Human superiority at chess seemed safe for another year.

Game 2

With the Black pieces, Kasparov surprised everyone by playing a passive line of the Ruy Lopez. Initially, it seemed like a good opening choice because of the closed nature of the position. Deep Blue prefers open positions (as do most chess programs) and was reputed to be much weaker in closed positions. Playing for this type of position as Black was part of Kasparov's strategy for defeating the computer.

In a stunning reversal of game 1, Deep Blue played outstanding positional chess to score a resounding victory against the human world champion. Kasparov played passively and never had any counter-play. Only briefly did two of his pieces cross the fourth rank; most of the game his pieces were huddled on the back two ranks. Kasparov never made an obvious error; rather his defeat seems to be the result of a series of passive moves.

If a game such as this were ever used for a Turing Test, few would peg the computer as playing White. In fact, most grandmasters would have been thrilled to played such a nice a game as White, regardless of who was playing the Black pieces.

Whereas Kasparov's victory in game 1 was treated rather nonchalantly by the media (after all this was his third straight defeat of Deep Blue going back to 1996), Deep Blue's victory unleashed an avalanche of media attention. The price of IBM stock went up over $4.

Whereas in 1996 people said that Deep Blue was lucky to win the first game of the match (Kasparov was not prepared and missed several good opportunities) this time around, there were no excuses. Kasparov was well-prepared, played well, and was soundly beaten. In the press conference after the game, a visibly pleased Joel Benjamin said that what we witnessed was a beautiful game of "chess", not "computer chess".

A week after the match, Kasparov expressed his admiration for Deep Blue's play in game 2:

The decisive game of the match was Game 2, which left a scar in my memory and prevented me from achieving my usual total concentration in the following games. In Deep Blue's Game 2 we saw something that went well beyond our wildest expectations of how well a computer would be able to foresee the long-term positional consequences of its decisions. The machine refused to move to a position that had a decisive short-term advantage -- showing a very human sense of danger. I think this moment could mark a revolution in computer science that could earn IBM and the Deep Blue team a Nobel Prize. Even today, weeks later, no other chess-playing program in the world has been able to evaluate correctly the consequences of Deep Blue's position.

Much has been made of Kasparov's missed opportunity. However, this distracts the discussion from the real issue: Deep Blue played a magnificent game. Who cares if there was a minor flaw in the game? Most classic games of chess contain many flaws. Perfect chess is still an elusive goal, even for Kasparov and Deep Blue.

Game 3

Everyone expected Kasparov to come out fighting in game 3 and, indeed, he quickly built up a dominating position. Many experts thought Deep Blue's position was nearly critical, when Kasparov unexpectedly decided to sacrifice a pawn. Although he had compensation for the slight material deficit, queens quickly came off the board and Kasparov never had serious winning chances. The game was drawn.

As was usual after a game that he did not lose, Kasparov would come down to the auditorium to answer questions from the commentators and audience. Rather than talk about the just-completed game, Kasparov was quite animated in his discussions of game 2. He admitted that he was stunned by Deep Blue's play in the game, even to the point of suggesting that human players might have been making the moves for Deep Blue. Kasparov kept repeating that he "knew" how computers played chess, and because of this he could not rationalize how Deep Blue was capable of playing the brilliant Be4 in game 2, a move that he claimed only the top players in the world were capable of finding, and yet it missed the "easy" draw at the end of the game. (Need we remind Kasparov, he too missed the draw, so maybe it wasn't so easy?)

The explanations for the anomaly is obvious to computer chess programmers. Deep Blue spent roughly 15 minutes on the Be4 move, well beyond its normal allotment of three minutes a move. In this case, the program had numerous Principal Variation changes and the original move, Qb6, failed low. Deep Blue saw it was winning material, but Kasparov got significant compensation for it. Be4 preserved the material gains, without the positional concessions. All this was in Deep Blue's search horizon. From the programmer's point of view, we marvelled at how well Deep Blue was able to properly evaluate the material/positional trade-offs and come up with a strong move. Kasparov just couldn't believe a machine was capable of this. In contrast, whereas Be4 was in Deep Blue's search horizon, the perpetual check was too deep for the program to find (just a few more ply...).

Needless to say, the suggestion of cheating dominated the next day's reporting of the match. Murray Campbell admitted that he was livid with Kasparov's suggestions. IBM did not take kindly to the unsubstantiated accusations. Nevertheless, that Kasparov would go to such extraordinary lengths to rationaize his defeat is perhaps the biggest compliment that he could give to the program!

Game 4

As Black, Kasparov again surprised experts by playing an opening that he has never before played in tournaments. He got a cramped position and people began to worry that there might be a repeat of game 2. However, Kasparov demonstrated his depth of understanding of the position by playing several "anti-positional" moves that lead to a pawn sacrifice, catching everyone off guard. It allowed Kasparov to place his pieces on good squares but, objectively, Deep Blue had nothing to fear. Some indecisive, planless-play by the computer gave Kasparov a large advantage. Short of time, Kasparov simplified into an endgame which looked to be winning. Deep Blue defended well and managed to draw, defying most of the expert's predictions. Post-game analysis showed that Kasparov missed at least one win; doubtless more will be discovered.

After the game, Kasparov came down to the auditorium as usual. But the Kasparov that showed up was a shadow of the supremely confident man we met after game 1, and the angry accuser after game 3. Instead we saw a quiet, reserved champion. When asked about missing possible wins in game 4, Kasparov quietly shrugged his head and admitted that he might have missed some wins. He displayed a surprising indifference to the missed golden opportunity of winning with Black. Here was a man who looked dejected and beaten. After four games, the match score was even, but watching Kasparov you had the feeling that in his mind it was already over.

Game 5

Game 5 was played after two days off for rest -- a welcome break for Kasparov. Everyone expected the champion to come out fighting, since this was his last opportunity with the White pieces. Instead, Kasparov's play lacked energy, as he failed to capitalize on some questionable moves by Deep Blue in the opening. The game simplified into equality. Deep Blue created its own difficulties by offering a strange queen trade that allowed Kasparov to get the better pawn structure and the initiative. The advantage grew from move to move, and many expected Kasparov to win the game (including the commentators and several well-known Grandmasters). In the end, Deep Blue held the draw by playing a series of spectacular moves that amazed many people. The program ignored Kasparov's advancing g-pawn and instead played for a minor piece attack that resulted in a perpetual check.

Again, the aftermath showed us a Kasparov that was respectful of his opponent. He conceded that Deep Blue played well to a draw. Kasparov showed none of the fire and passion that is his trademark.

On a less pleasant note, the Deep Blue team was greeted by the audience with a mixture of cheers and boos. Although Kasparov was the overwhelming sentimental favorite, there was no need to disparage the enormity of the Deep Blue achievement.

Game 6

What can one say about historic game 6? It was over just as it began. On his seventh move, Kasparov played a well-known opening blunder and ended up resigning in a mere 19 moves. The game lasted less than an hour but, in reality, it was all over in five minutes.

How does one explain such an incredible oversight by the world champion in one of the most important games of his life? Some people theorized that Kasparov deliberately went into this line, having a refutation up his sleeve. If so, then clearly Deep Blue refuted the refutation. In our opinion, this is unlikely. Kasparov made a mistake. The expression of horror on Kasparov's face when he realized what he had done spoke volumes for what really happened.

Kasparov has not commented on the critical move. On his seventh move, the normal move sequence is Bd6 followed by h6. The likely explanation for the champion's collapse is that he transposed moves, playing h6 before Bd6. After h6 he never had a chance to develop his pieces. Even if Kasparov's loss was an accidental transposition of moves, it does not excuse him for his choice of opening variations. Again he chose an opening variation that he rarely played against humans (the Caro-Kann). One commentator noticed an interesting pattern. Kasparov played opening lines as Black that were favorites of his great rival Anatoly Karpov. Both losses (games 2 and 6) came in openings that Karpov plays as Black, and that Kasparov had devoted considerable attention to playing with the White pieces. By inexplicably choosing openings for which he has little experience, Kasparov was asking for trouble.

After the game, a dejected Kasparov admitted at the press conference that he was embarrassed and ashamed of his performance. But he deflected the blame to IBM, again suggesting that they had cheated in game 2. To many observers, he came across as a bad loser and, to their credit, most of the media coverage of the final game ignored Kasparov's unsubstantiated claims.

Epilogue

A milestone in computing history was achieved with Deep Blue's triumphant 3.5 - 2.5 match victory against the World Chess Champion, Garry Kasparov -- a victory that was not (yet) expected by most of the computer chess community. The holy grail of computer chess has been won by the Deep Blue team. They have worked long and hard to earn it. The team, notably Feng-hsiung Hsu and Murray Campbell, deserve the hearty congratulations of the entire computer-chess community.

The victory went around the world. IBM estimated it received $500 million of free publicity from the match, and IBM stock prices went up over $10 to reach a new high for the company.

In looking at the match retrospectively, can we conclude that one chess computer (Deep Blue) is now better than the best that mankind has to offer? No, at least not yet. Two points come to mind. First, we believe that Kasparov played the better chess and failed to convert his opportunities. Second, IBM bought the right to play Kasparov; they did not earn it. By offering Kasparov a lot of money to play, Deep Blue could bypass the normal route for getting to play Kasparov, including the Candidate's Matches. Deep Blue has demonstrated that it can successfully compete with Kasparov; it has not yet demonstrated that it can beat the other top grandmasters in the world. The positional playing style, for example, of Anatoly Karpov might give Deep Blue trouble.

Why did Kasparov lose? A lot has been written about this, but to the computer chess experts watching the games in New York, several things were obvious. First, Deep Blue played much better than in 1996. The program made fewer errors, and the errors that it did make were less serious. In addition to the increased speed of the machine, it appeared that the extensive tuning by people such as Joel Benjamin played an important role. Second, Kasparov's preparation for the match was poor. He refused to believe that Deep Blue, with its impressive search depths and grandmaster tuning, was capable of playing much better than commercially available programs. Third, Kasparov made some poor choices of openings. He handicapped himself by not playing for the positions that he feels most comfortable in.

Kasparov writes about his preparation that:

Unfortunately, I based my preparation for this match ... on the conventional wisdom of what would constitute good anti-computer strategy. Conventional wisdom is -- or was until the end of this match -- to avoid early confrontations, play a slow game, try to out-maneuver the machine, force positional mistakes, and then, when the climax comes, not lose your concentration and not make any tactical mistakes.

It was my bad luck that this strategy worked perfectly in Game 1 -- but never again for the rest of the match. By the middle of the match, I found myself unprepared for what turned out to be a totally new kind of intellectual challenge.

IBM's total control of the site and the playing conditions underscored the vulnerability of the human player. I was the only player in this competition influenced by any sort of negative or hostile atmosphere. I think IBM's unwillingness to cooperate or give printouts of the computer's thought processes harmed that atmosphere. (As of today, I still have not received the complete printouts that I requested.) There were also many minor incidents, starting with the fact that the venue was created for the convenience of the machine -- with all these air-conditioning systems and dozens of people serving the machine -- not the human player.

I don't want anybody to look at this as an excuse. It's my fault. I accepted the conditions.

Now that the match is over, a few pieces of information about Deep Blue's preparations are beginning to emerge. Besides Grandmaster Joel Benjamin, Deep Blue was tested by several New York-based grandmasters as well as Spanish Grandmaster Miguel Illescas. Other researchers at IBM's T.J. Watson facility were apparently brought into the project. For example, Gerry Tesauro, best known for his program TD-Gammon (playing at a level on par with the best backgammon players), used his neural net technology to help tune Deep Blue's evaluation function. The biggest strides forward seemed to be in the evaluation function, where extensive efforts were spent trying to improve the program's play in positions where computers have a reputation for playing weakly in. As far as we can tell from a small sample of six games, the Deep Blue team have made significant strides here.

And of the future? At the time of this writing, Kasparov has been using every media opportunity to issue a challenge to Deep Blue to play a 10-game match in November:

I also think IBM owes me, and all mankind, a re-match. I hereby challenge IBM to a match of 10 games, 20 days long, to play every second day. I would like to have access in advance to the log of 10 Deep Blue games played with a neutral player or another computer in the presence of my representative. I would like to play it this fall, when I can be in my best form after a summer of vacation and preparation. And I'm ready to play for all or nothing, winner take all, just to show that it's not about money. Moreover, I think it would be advisable if IBM would step down as an organizer of the match. It should be organized independently.

Reference:

Kasparov quotes are taken from "IBM Owes Me A Rematch" by Garry Kasparov, Time Magazine, May 26, 1997.