The Signal and the Noise

by Nate Silver

  Kasparov tried to exploit the blind spots in Deep Blue’s heuristics by baiting it into mindlessly pursuing plans that did not improve its strategic position. Computer chess programs often prefer short-term objectives that can be broken down and quantized and that don’t require them to evaluate the chessboard as a holistic organism. A classic example of the computer’s biases is its willingness to accept sacrifices; it is often very agreeable when a strong player offers to trade a better piece for a weaker one.

  The heuristic “Accept a trade when your opponent gives up the more powerful piece” is usually a good one—but not necessarily when you are up against a player like Kasparov and he is willing to take the seemingly weaker side of the deal; he knows the tactical loss is outweighed by strategic gain. Kasparov offered Deep Blue such a trade thirty moves into his first game, sacrificing a rook for a bishop,* and to his delight Deep Blue accepted. The position that resulted, as shown in figure 9-3a, helps to illustrate some of the blind spots that result from the computer’s lack of strategic thinking.

  FIGURE 9-3A: POSITION AFTER KASPAROV’S 32ND MOVE IN GAME 1

  Kasparov and Deep Blue each had their own ways of simplifying the position shown in figure 9-3a. Computers break complicated problems down into discrete elements. To Deep Blue, for instance, the position might look more like what you see in figure 9-3b, with each piece assigned a different point value. If you add up the numbers in this way, Deep Blue had the equivalent of a one-pawn advantage over Kasparov, which converts to a win or draw the vast majority of the time.28

  FIGURE 9-3B: DISCRETE EVALUATION OF POSITION

  Humans, instead, are more capable of focusing on the most important elements and seeing the strategic whole, which sometimes adds up to more than the sum of its parts. To Kasparov, the position looked more like what you see in figure 9-3c, and it was a very good position indeed. What Kasparov sees is that he has three pawns advancing on Deep Blue’s king, which has little protection. The king will either need to move out of the way—in which case, Kasparov can move his pawns all the way to Deep Blue’s home row and promote* them to queens—or it could potentially be mated. Meanwhile, Kasparov’s queen and his bishop, although they are in the lower left-hand corner of the board for now, are capable of moving diagonally across it with relatively little obstruction; they are thus adding to the pressure the vulnerable king already faces from the pawns. Kasparov does not yet know exactly how Deep Blue’s king will be mated, but he knows that faced with such pressure the odds are heavily in his favor. Indeed, the strength of Kasparov’s position would soon become apparent to Deep Blue, which would resign the game thirteen moves later.

  FIGURE 9-3C: HOLISTIC EVALUATION OF POSITION

  “Typical computer weakness,” Kasparov later said. “I’m sure it was very pleased with the position, but the consequences were too deep for it to judge the position correctly.”29

  “Human Outcalculates a Calculator,” trumpeted the headline in the New York Times,30 which published no fewer than four articles about the game the next day.

  But the game had not been without a final twist. It was barely noticed by commentators at the time, but it may have altered chess history.

  The Beginning of the End

  In the final stage of a chess game, the endgame, the number of pieces on the board are fewer, and winning combinations are sometimes more explicitly calculable. Still, this phase of the game necessitates a lot of precision, since closing out a narrowly winning position often requires dozens of moves to be executed properly without any mistakes. To take an extreme case, the position illustrated in figure 9-4 has been shown to be a winning one for white no matter what black does, but it requires white to execute literally 262 consecutive moves correctly.*

  FIGURE 9-4: A WIN FOR WHITE . . . IN 262 MOVES

  A human player would almost certainly not solve the position in figure 9-4. However, humans have a lot of practice in completing endgames that might take ten, fifteen, twenty, or twenty-five moves to finish.

  The endgame can be a mixed blessing for computers. There are few intermediate tactical goals left, and unless a computer can literally solve the position to the bitter end, it may lose the forest for the trees. However, just as chess computers have databases to cover the opening moves, they also have databases of these endgame scenarios. Literally all positions in which there are six or fewer pieces on the board have been solved to completion. Work on seven-piece positions is mostly complete—some of the solutions are intricate enough to require as many as 517 moves—but computers have memorized exactly which are the winning, losing, and drawing ones.

  Thus, something analogous to a black hole has emerged by this stage of the game: a point beyond which the gravity of the game tree becomes inescapable, when the computer will draw all positions that should be drawn and win all of them that should be won. The abstract goals of this autumnal phase of a chess game are replaced by a set of concrete ones: get your queenside pawn to here, and you will win; induce black to move his rook there, and you will draw.

  Deep Blue, then, had some incentive to play on against Kasparov in Game 1. Its circuits told it that its position was a losing one, but even great players like Kasparov make serious blunders about once per seventy-five moves.31 One false step by Kasparov might have been enough to trigger Deep Blue’s sensors and allow it to find a drawing position. Its situation was desperate, but not quite hopeless.

  Instead, Deep Blue did something very strange, at least to Kasparov’s eyes. On its forty-fourth turn, Deep Blue moved one of its rooks into white’s first row rather than into a more conventional position that would have placed Kasparov’s king into check. The computer’s move seemed completely pointless. At a moment when it was under assault from every direction, it had essentially passed its turn, allowing Kasparov to advance one of his pawns into black’s second row, where it threatened to be promoted to a queen. Even more strangely, Deep Blue resigned the game just one turn later.

  What had the computer been thinking? Kasparov wondered. He was used to seeing Deep Blue commit strategic blunders—for example, accepting the bishop-rook exchange—in complex positions where it simply couldn’t think deeply enough to recognize the implications. But this had been something different: a tactical error in a relatively simple position—exactly the sort of mistake that computers don’t make.

  FIGURE 9-5: DEEP BLUE’S PREPLEXING MOVE

  “How can a computer commit suicide like that?” Kasparov asked Frederic Friedel, a German chess journalist who doubled as his friend and computer expert, when they studied the match back at the Plaza Hotel that night.32 There were some plausible explanations, none of which especially pleased Kasparov. Perhaps Deep Blue had indeed committed “suicide,” figuring that since it was bound to lose anyway, it would rather not reveal any more to Kasparov about how it played. Or perhaps, Kasparov wondered, it was part of some kind of elaborate hustle? Maybe the programmers were sandbagging, hoping to make the hubristic Kasparov overconfident by throwing the first game?

  Kasparov did what came most naturally to him when he got anxious and began to pore through the data. With the assistance of Friedel and the computer program Fritz, he found that the conventional play—black moving its rook into the sixth column and checking white’s king—wasn’t such a good move for Deep Blue after all: it would ultimately lead to a checkmate for Kasparov, although it would still take more than twenty moves for him to complete it.

  But what this implied was downright frightening. The only way the computer would pass on a line that would have required Kasparov to spend twenty moves to complete his checkmate, he reasoned, is if it had found another one that would take him longer. As Friedel recalled:

  Deep Blue had actually worked it all out, down to the very end and simply chosen the least obnoxious losing line. “It probably saw mates in 20 and more,” said Garry, thankful that he had been on the right side of these awesome calculations.33

  To see twenty moves ahead in a game as complex as chess
was once thought to be impossible for both human beings and computers. Kasparov’s proudest moment, he once claimed, had come in a match in the Netherlands in 1999, when he had visualized a winning position some fifteen moves in advance.34 Deep Blue was thought to be limited to a range of six to eight moves ahead in most cases. Kasparov and Friedel were not exactly sure what was going on, but what had seemed to casual observers like a random and inexplicable blunder instead seemed to them to reveal great wisdom.

  Kasparov would never defeat Deep Blue again.

  Edgar Allan Kasparov

  In the second game, the computer played more aggressively, never allowing Kasparov into a comfortable position. The critical sequence came about thirty-five turns in. The material was relatively even: each player had their queen, one of their bishops, both of their rooks and seven of their pawns. But Deep Blue, playing white, had slightly the better of it by having the next move and a queen that had ample room to maneuver. The position (figure 9-6) wasn’t quite threatening to Kasparov, but there was the threat of a threat: the next few moves would open up the board and determine whether Deep Blue had a chance to win or whether the game was inevitably headed for a draw.

  FIGURE 9-6: DEEP BLUE’S OPTIONS IN 36TH MOVE OF GAME 2

  Deep Blue had a couple of moves to consider. It could move its queen into a more hostile position; this would have been the more tactical play. Or it could exchange pawns with white, opening up the left-hand side of the board. This would create a more open, elegant, and strategic position.

  The grandmasters commenting on the match uniformly expected Deep Blue to take the first option and advance its queen.35 It was the somewhat more obvious move, and it would be more in character for Deep Blue: computers prefer busy, complex, computationally demanding positions. But after “thinking” for an unusually long time, Deep Blue instead chose the pawn exchange.36

  Kasparov looked momentarily relieved, since the pawn swap put less immediate pressure on him. But the more he evaluated the position, the less comfortable he became, biting his knuckles, burying his head in his hands—one audience member thought he caught Kasparov crying.37 Why had Deep Blue not elected to press forward with its queen? Its actual move was not manifestly inferior—indeed, it’s a move he could have imagined one of his flesh-and-blood rivals, like his longtime nemesis Anatoly Karpov, trying under the right conditions. But a computer would need a good tactical reason for it—and he simply couldn’t figure out what that reason was. Unless his suspicion was correct—Deep Blue was capable of foreseeing twenty or more moves down the road.

  Kasparov and Deep Blue played out about eight more turns. To the reporters and experts watching the game, it had become obvious that Kasparov, who had played defensively from the start, had no chance to win. But he might still be able to bring the game to a draw. Then to the surprise of the audience, Kasparov resigned the game after the forty-fifth move. The computer can’t have miscalculated, he thought, not when it could think twenty moves ahead. He knew that Deep Blue was going to win, so why deplete his energy when there were four more games left to play?

  The crowd in the auditorium burst into robust applause:38 it had been a well-played game, much more so than the first one, and if Deep Blue’s checkmate did not seem quite as inevitable to them as it had to Kasparov, it was surely because they hadn’t thought about the position as deeply as he had. But they saved their real admiration for Deep Blue: it had played like a human being. “Nice style!” exclaimed Susan Polgar, the women’s world champion, to the New York Times.39 “The computer played a champion’s style, like Karpov.” Joel Benjamin, a grandmaster who had been assisting the Deep Blue team, agreed: “This was not a computer-style game. This was real chess!”

  Kasparov hurried out of the Equitable Center that night without speaking to the media, but he had taken his fellow grandmasters’ comments to heart. Perhaps Deep Blue was literally human, and not in any existential sense. Perhaps like the Mechanical Turk two centuries earlier, a grandmaster was working surreptitiously to pull its gears behind the scenes. Perhaps Benjamin, a strong player who had once drawn with Kasparov, had not just been coaching Deep Blue but actually intervening on its behalf during the games.

  With their minds so powerfully wired to detect patterns, chess champions have a reputation for being slightly paranoid. At a press conference the next day, Kasparov accused IBM of cheating. “Maradona called it the hand of God,” he said of the computer’s play.40 It was a coy allusion to the goal that the great Argentinean soccer player Diego Maradona had scored in an infamous 1986 World Cup match against England. Replays later revealed that the ball had been put into the net not off his head, but instead, illegally, off his left hand. Maradona claimed that he had scored the goal “un poco con la cabeza de Maradona y otro poco con la mano de Dios”—a little with the head of Maradona and a little with the hand of God. Kasparov, likewise, seemed to think Deep Blue’s circuitry had been supplemented with a superior intelligence.

  Kasparov’s two theories about Deep Blue’s behavior were, of course, mutually contradictory—as Edgar Allan Poe’s conceptions of the Mechanical Turk had been. The machine was playing much too well to possibly be a computer—or the machine had an intelligence so vast that no human had any hope of comprehending it.

  Still, quitting the second game had been a mistake: Deep Blue had not in fact clinched its victory, as Friedel and Yuri Dokhoian, Kasparov’s most trusted assistant, sheepishly revealed to him over lunch the next day. After playing out the position on Fritz overnight, they had found a line which in just seven more turns would have forced Deep Blue into perpetual check and given Kasparov his tie.* “That was all?” Kasparov said, staring blankly at the traffic on Fifth Avenue. “I was so impressed by the deep positional play of the computer that I didn’t think there was any escape.”41

  Although at 1-1 the match was still even, Kasparov’s confidence was deeply shaken. He had never lost a competitive chess match in his life; now, he was on the ropes. And making matters worse, he had committed a chess sin of the highest order: resigning a game that he could have played to a draw. It was an embarrassing, unprecedented mistake. The journalists and grandmasters covering the match couldn’t recall the last time a champion made such an error.

  Kasparov resolved that he wouldn’t be able to beat Deep Blue by playing the forceful, intimidating style of chess that had made him World Champion. Instead, he would have to try to trick the computer with a cautious and unconventional style, in essence playing the role of the hacker who prods a program for vulnerabilities. But Kasparov’s opening move in the third game, while unusual enough to knock Deep Blue out of its databases, was too inferior to yield anything better than a draw. Kasparov played better in the fourth and fifth games, seeming to have the advantage at points in both of them, but couldn’t overcome the gravity of Deep Blue’s endgame databases and drew both of them as well. The match was square at one win for each player and three ties, with one final game to play.

  On the day of the final game, Kasparov showed up at the Equitable Center looking tired and forlorn; Friedel later recalled that he had never seen him in such a dark mood. Playing the black pieces, Kasparov opted for something called the Caro-Kann Defense. The Caro-Kann is considered somewhat weak— black’s winning percentage with it is 44.7 percent historically—although far from irredeemable for a player like Karpov who knows it well. But Kasparov did not know the Caro-Kann; he had rarely played it in tournament competition. After just a few moves, he was straining, taking a long time to make decisions that were considered fairly routine. And on his seventh move, he committed a grievous blunder, offering a knight sacrifice one move too early. Kasparov recognized his mistake almost immediately, slumping down in his chair and doing nothing to conceal his displeasure. Just twelve moves later—barely an hour into the game—he resigned, storming away from the table.

  Deep Blue had won. Only, it had done so less with a bang than an anticlimactic whimper. Was Kasparov simply exhausted, exacerbating his p
roblems by playing an opening line with which he had little familiarity? Or, as the grandmaster Patrick Wolff concluded, had Kasparov thrown the game,42 to delegitimize Deep Blue’s accomplishment? Was there any significance to the fact that the line he had selected, the Caro-Kann, was a signature of Karpov, the rival whom he had so often vanquished?

  But these subtleties were soon lost to the popular imagination. Machine had triumphed over man! It was like when HAL 9000 took over the spaceship. Like the moment when, exactly thirteen seconds into “Love Will Tear Us Apart,” the synthesizer overpowers the guitar riff, leaving rock and roll in its dust.43

  Except it wasn’t true. Kasparov had been the victim of a large amount of human frailty—and a tiny software bug.

  How to Make a Chess Master Blink

  Deep Blue was born at IBM’s Thomas J. Watson Center—a beautiful, crescent-shaped, retro-modern building overlooking the Westchester County foothills. In its lobby are replicas of early computers, like the ones designed by Charles Babbage. While the building shows a few signs of rust—too much wood paneling and too many interior offices—many great scientists have called it home, including the mathematician Benoit Mandelbrot, and Nobel Prize winners in economics and physics.

  I visited the Watson Center in the spring of 2010 to see Murray Campbell, a mild-mannered and still boyish-looking Canadian who was one of the chief engineers on the project since its days as Deep Thought at Carnegie Mellon. (Today, Campbell oversees IBM’s statistical modeling department.) In Campbell’s office is a large poster of Kasparov glaring menacingly at a chessboard with the caption:

  How Do You Make a Computer Blink?

  Kasparov vs. Deep Blue

  May 3–11, 1997