ACJ Extra

The Last Human Champion?

Chess Computer Gains Ground Bit by Bit

Christopher Chabris

"It felt like we were mission control in Houston when the Eagle was landing." That's how grandmaster Joel Benjamin described the mood backstage after IBM's Deep Blue computer system won the first game of its February chess match against world champion Garry Kasparov. "We were whooping it up, yelling and screaming," said Benjamin, who served as the IBM team's full-time chess consultant during the match and two months beforehand.

The celebration was justified, for Deep Blue had played some marvelous moves to upset the human being widely considered the greatest player in the history of chess. Although Kasparov had lost "speed chess" games to other programs in 1994, this was the first time a computer had ever defeated a reigning world champion under the standard match time limit of forty moves in two hours.

The historic game began with Kasparov as Black choosing his favorite Sicilian Defense, and Deep Blue countering with the same Alapin variation its predecessor Deep Thought had tried without success in their first encounter, a 1989 mini-match in New York that Kasparov easily won by a 2-0 score. This time, with Benjamin helping with opening selection (in effect, Deep Blue's handlers tell it how to play the first few moves of the game, much as Kasparov begins by consulting his own vast memory of previously studied opening theory), the computer was well-prepared and reached a position with much better prospects than Deep Thought had had in 1989.

In the middle game Kasparov took on weaknesses in his pawn structure but gained attacking chances in compensation-- exactly the kind of tradeoff that human intuition typically judges well but computers often miscalculate. But at the key point, Deep Blue played "a wonderful and extremely human move," as Kasparov later described it. The computer gave up a pawn in order to shatter Kasparov's pawns and work its queen into enemy territory, where it could terrorize the black forces from behind the lines. Kasparov immediately launched a counterattack against the white king, but the computer calmly captured pawns and defended with nerves of silicon against an offensive that would have frightened most human players. When the dust had settled after 37 moves, Kasparov's attack had come up short and he was two pawns behind, with his king on the run in a hopeless position. He resigned.

Many commentators attributed the computer's victory to poor defense by Kasparov. Yasser Seirawan of Inside Chess asked, "How could Garry play such a horrible game?" But the champion himself offered a much more charitable assessment: "A real masterpiece." After Deep Blue's 23rd move, Kasparov said later, "I was lost; it played beautiful, flawless chess the rest of the way."

The truth probably lies somewhere in between, but Deep Blue and its developers had clearly achieved what computer scientists could only dream about during most of the 50 years since the first digital computer was switched on. The question before Game 1 of the man-versus-machine encounter was whether the machine could make a contest of the six-game match; the question after it was whether the man could.

Since the 18th century, when the fraudulent chess automaton "The Turk" traveled across Europe, humanity has been fascinated with the idea of an artificial device that could play chess, a game that represented like no other a challenge to man's unique intellectual powers. The Turk was eventually destroyed by a fire in Philadelphia, where later a similar device known as "Ajeeb" was exhibited at the Convention Hall in the 1930s as part of a U.S. promotional tour.

Automatic chess left the province of hucksterism and became a science in the late 1940s, when computer pioneers Alan Turing and Claude Shannon described how the new digital computers could be programmed to actually play legal moves and complete games without human direction. Shannon foresaw the two contrasting approaches a computer could follow: "selective" versus "exhaustive" search. Human players decide which move to make by considering a few alternatives, how the opponent might reply to each, how they might counter those replies, and so on, then mentally compare the resulting board positions in order to judge which line of play is most favorable (or least unfavorable) to them. This process is called searching. But chess is such a complex game, with so many possible moves in any position (on average, 30 to 40), that the human brain can search only a tiny fraction of them in the allotted time.

Shannon correctly noted that it would be difficult to program a computer to equal human judgment and intuition in selecting promising moves to examine and discarding irrelevant ones. Computers, on the other hand, are fast calculators that never become confused or forget what they are doing, and thus could implement a search of every possibility for each side as far ahead as time permits. However, Shannon concluded that this exhaustive approach would fail in the face of the immense complexity of chess, which he estimated to contain about 10^120 different possible 40-move games.

What his analysis didn't anticipate was the subsequent explosive growth in computer speed and the development of clever mathematical tricks for reducing the amount of analysis necessary to complete an exhaustive search several moves deep. But even with these and a host of other advances, it was not until 1983 that Belle, developed by Ken Thompson and Joe Condon at Bell Labs, became the first computer chess master. One of the key innovations in Belle was the design of customized computer chips to perform some of the calculations involved in playing chess. Adapting not only the computer's programming, or software, but also its hardware to a single task enabled deeper searches to be conducted in even less time. Grandmaster playing strength, a level achieved by only a few hundred people in the world, was now within the computer's reach.

The first computer to play at the grandmaster level was Deep Thought, developed by Feng-Hsiung Hsu, Thomas Anantharaman, Murray Campbell, and several other graduate students at Carnegie Mellon University beginning in 1985. After receiving their computer science doctorates and seeing their machine trounced by Kasparov in the 1989 New York exhibition match, the trio was soon hired by IBM Research. They continued the project with the goal of building a machine so fast it could take revenge on Kasparov, who had by then been world champion for four years. This new computer would take advantage of special-purpose hardware and the nascent technique of parallel processing (the use of multiple computers to work simultaneously on solving a single problem) on an unprecedented scale.

Early plans called for a computer with 1,000 speedy chess processors to be ready for Kasparov by 1992, but this turned out to be too ambitious a schedule for a team of three people. (Anantharaman left in late 1990 and Joe Hoane joined in 1991.) But while working on the ultimate machine, which had been named Deep Blue after a company-wide contest, the team developed Deep Thought II (sometimes known as Deep Blue Prototype), which could carry up to 24 chess chips and could analyze 3 million to 5 million moves per second. This figure surpassed Shannon's "very optimistic" estimate of 1 million per second. Combined with sophisticated search methods and techniques for evaluating positions, this record speed yielded solid grandmaster-level play in events in 1993 and 1994, including victories over prominent Danish players and the young Hungarian star Judit Polgar.

Meanwhile, the chess world was growing impatient with the failure of the Deep Blue team to deliver on its promise of a machine at Kasparov's level. (Indeed, the project had more than once been perilously close to cancellation.) Programs running on personal computers had become strong enough to challenge grandmasters and even Kasparov at fast games, and the aging Deep Thought II was upset by a PC program at the May 1995 world computer championship in Hong Kong. But at the conclusion of the event, IBM stole the show by announcing that contracts had been signed for the new Deep Blue to play six games under world championship match conditions (but not for the title, which apparently is reserved for humans) against Kasparov in Philadelphia in February 1996.

Preparations for the match had begun as early as November 1994, when the team started a final push to finish the new chess chip, which Hsu had been working on by himself for years. In December the match was proposed to Kasparov, and by February 1995 the parties had agreed in principle. In July 1995 the completed chip design, with over a million transistors, was sent to the manufacturer. In September the first batch was received at the team's lab in IBM's Watson Research Center in Westchester County, New York.

At the same time, just 50 miles south at New York's World Trade Center, Kasparov was defending his championship against the Indian challenger Viswanathan Anand. At first the match was difficult for Kasparov, and with the score 5-4 in Anand's favor after nine games, some wondered whether Anand would be a better opponent for Deep Blue come February. But Kasparov won four of the next five games to take a decisive lead. By early October he had convincingly retained his title for the fifth time.

The Deep Blue team had also cleared a significant hurdle by getting the chip up and running and splitting a pair of Beijing exhibition games with then-women's world champion Xie Jun of China. Unfortunately, the machine's loss was caused by a serious bug that required a second version of the chip to be made before the complete machine could be assembled.

While this was under way, three leading American grandmasters, all of whom had experience playing against computers, were brought in to play secret two-game training matches with the prototype. Only Joel Benjamin, who had already gone undefeated in two consecutive Harvard Cup man-versus-machine tournaments, won his match. He was soon hired to help Campbell (who at master level was until then the strongest player on the team) develop Deep Blue's general chess knowledge and opening theory.

Like the training matches, Benjamin's work was kept secret so that Kasparov would have as little information as possible about the computer's preparation for the match. In this information vacuum, the intensely curious Kasparov assumed that an entire team of grandmasters was helping in the preparations, but besides Benjamin there were only two others, who provided part-time assistance.

Indeed, to coordinate the work of many more assistants would have been an impossible task for the already overloaded (and underslept) Deep Blue team. Joe Hoane, who was largely responsible for moving the system's 500,000 lines of program code to the new, $2.5-million SP2 parallel supercomputer that would coordinate the efforts of about 200 of the now bug-free chips, worked 12 to 14 hours a day, seven days a week, for over two months just to get the machine running.

By January, with just weeks to go before the match, Kasparov had learned through a leak that two more test games had been played in early December. (In a quick two-game morning match, the prototype got some revenge on Benjamin with a win and a draw.) Through an intermediary he asked for the moves of the games; he also asked to see any other training games played by the new system, and even demanded to play some test games himself. C.-J. Tan, the manager of the IBM team since 1992, politely rebuffed all of Kasparov's overtures.

About two weeks before the February 10 date for Game 1, the team was finally able to use the complete resources of the SP2 computer and began to wind down the programming effort. There was time for just one semiformal test to make sure the program could get through a complete game; it still tended to fail about once every four hours. As late as four days before the match, Hoane was still reworking the main routines to squeeze out extra speed, and even during the match he continued to work on improving the system's reliability. "We did six months of work in just two months," says Hoane. On the chess preparation side, Benjamin added that "we were only able to scratch the surface of teaching it chess knowledge." By the start of the match, Deep Blue was examining about 100 million chess positions per second, with a peak speed of up to 400 million in special situations. This was better than the 50 million per second forecast three months earlier, but would it be enough?

The truth is that after more than 10 years of research, including almost 25 man-years of development at IBM, the project was deep into uncharted territory. Nobody knew how strong, or weak, Deep Blue would be. While few predicted a Deep Blue sweep, expert assessments ranged from 4-2 for the machine all the way to the not uncommon hope for a 6-0 Kasparov victory.

By the start of Game 2 a media frenzy was under way, with over 100 reporters, writers, photographers, and camera crews descending on the Philadelphia Convention Center on a Sunday in the middle of a terrible winter to cover the growing story. By the end of the match the sponsoring body, the Association for Computing Machinery (ACM), estimated that the event had attracted free publicity in the U.S. worth over $125 million in advertising. IBM saw its technological achievements recognized worldwide, and its stock price even went up 4.5% during the week of the match. An unprecedented number of fans around the world followed the action via the Internet and regular newspaper and television updates.

After a reported sleepless night following his loss in the first game, Kasparov came back with an elegant six-hour win that showed that Deep Blue was not his equal in long-range strategic planning. This time he sacrificed a pawn for an attack and kept the game under control, winning back the pawn and clamping down on the computer's chances. Although his play was not perfect, he was never in danger of losing, and his eventual victory was well-deserved.

The match, which before it began had received surprisingly little publicity, was now a top story around the world. Games 3 and 4 were drawn; in both games Deep Blue was under the kind of pressure that might cause a human player to defend halfheartedly or blunder, but the computer found ingenious maneuvers to escape unscathed, and in Game 4 it even managed to turn the tables before Kasparov saved himself with a perceptive sacrifice. After four games the match was tied, 2-2.

On the final day off the Deep Blue team members appeared relaxed, if still busy and a bit nervous. Already they had achieved their goals: a victory over the world champion and a credible showing in a series of games.

In "mission control" before the fifth game the atmosphere was calm; everything at last seemed to be working well. Glitches that affected Deep Blue's play earlier had been solved, and Hoane had finally finished testing the program code. Benjamin and Campbell had continued to prepare diligently for Kasparov's Sicilian Defense.

But when the game began, Kasparov chose the Petroff Defense, an opening he had ventured only twice before in serious games. Benjamin had anticipated this possibility during the prematch work, however, and Deep Blue effected a deft transposition, or a shift in the opening, to the Scotch Game, which leads to the type of open, tactical situations computers are thought to excel in. As in Game 1, the crucial moment came at move 23. This time it was not Deep Blue taking control, but Kasparov abruptly offering a draw.

In man-versus-machine matches, a human operator normally intervenes only to physically execute the computer's moves on the standard chessboard. But the operator or his team is fully responsible for resigning the game or responding to draw offers. In this case, Hsu, at the board, picked up the special "hotline" phone to call the team for advice. During the long delay before the machine's next move, the commentators and spectators who were following the action on projection screens in a nearby auditorium, and were unaware of Kasparov's draw offer, thought the computer might have crashed. The only other explanation for the delay would be consideration of a draw offer. But why would Kasparov offer a draw and force a high-wire showdown in the final game (Kasparov explained after the game that he offered the draw because trying to win would be risky and he was running low on time, which had nearly cost him the previous game), and if he had, why would the Deep Blue team even think of refusing?

All along, fearful of a potential backlash should the computer somehow win the match, or of questions about whether building a chess-playing machine was serious business, IBM had been portraying the match more as a scientific experiment than a sporting event. "Whatever the result," said C.-J. Tan, "it will be a triumph for human ingenuity." And in fact, Deep Blue is such a complex machine that although its human developers can read every line of its program and trace every pathway in its chips, they can rarely predict how it will play in a given position, let alone what it will do over the course of several moves. If they could, there would be no need to test out Deep Blue in a match against Kasparov, and nothing demonstrated this more clearly than the draw offer. After much debate, and even though the computer evaluated the board position as slightly favorable for Kasparov, the match-as-experiment view won out and the Deep Blue team declined the draw offer, preferring to play the games out and learn more about the machine. When the game finally resumed, the computer immediately played a series of weak moves, letting its pieces become tied up and its king become vulnerable. Kasparov mopped up in professional style and took a 3-2 lead.

Did Deep Blue's creators learn anything from this defeat (other than that if they wanted to score points, they should have accepted the draw)? One of their main goals was to identify types of situations in which the computer's prodigious calculating ability paradoxically gets it into trouble, and then to adjust the computer's knowledge base to solve the problem. In fact, through many practice games with Benjamin, they found more ways to improve the program than they had time to implement. But losing Game 5 was a painful way to discover one more. For all its calculating strength, "Deep Blue still doesn't play chess that well," according to Benjamin. "I'd like to actually try to teach it the game and see what the results are."

Before the lessons could resume, though, Game 6 offered Deep Blue a final chance to tie the match and make history for a second time that week. But now, almost as though it was disheartened by its own poor performance in Game 5, Deep Blue played its worst game of the match. Kasparov as White was in total control of the board from start to finish. In the final position Deep Blue still had an extra pawn, but its forces were so boxed in that they could barely move. After the crushing victory in Game 6, Kasparov's former challenger Anand mused, "I wonder what we were all worried about. I'll take my five positions per second any day, thank you." The Deep Blue team may be wondering, too, about what it can do to forestall future losses of this sort, which are not obviously connected to any single piece of missing chess knowledge or any specific scenario the machine can be taught to avoid.

For his victory Kasparov took home a $400,000 prize. The $100,000 loser's share went to IBM. As usual, Kasparov was a charismatic public figure throughout the match, giving lengthy post-game commentary for the audience and making a gracious acceptance speech at the awards banquet following the last game.

Kasparov seemed intrigued by the question of whether Deep Blue was "intelligent," even though its developers have carefully avoided associating the project with the somewhat checkered tradition of research in artificial intelligence. Kasparov claimed that the computer's vast search capacity had turned "quantity into quality," enabling it to achieve aspects of chess understanding that people accomplish with pattern recognition, thinking by analogy, intuitive judgment, and even "gut feelings." During the match, he added, he felt that he was sensing "a new kind of intelligence across the chess table." The debate over whether skill at chess reflects intelligent thinking has tended to assume that intelligent thinking equals human-style thinking, but Deep Blue's performance and the very legitimacy of its challenge should remind us that computer-style thinking, often derided as "brute force," is an equally valid approach to many interesting problems, perhaps in realms beyond chess.

Kasparov's comeback did, at least temporarily, lay to rest the doomsday predictions that inevitably surfaced after Game 1. But what will happen to chess in the future when, as most computer experts and grandmasters still believe, Kasparov or his successor is finally, comprehensively, defeated? Will interest in the game suddenly disappear? Joel Benjamin, once the youngest human chess master and now the trainer of the youngest silicon grandmaster, has strong opinions about the influence of machines. "Computers will never replace humans in chess because we will always admire the games of Kasparov more than the games of Deep Blue," he explains. "The aesthetic and competitive aspects of chess will always be human, and computers will amplify human creativity. Working on Deep Blue was as rewarding a challenge as anything else I've done as a chessplayer."

Deep Blue's immediate future will probably include an early-1997 rematch with Kasparov, who has publicly expressed his willingness. With plenty of time to improve the machine, Joe Hoane thinks that he and Hsu can optimize it to search up to five times more positions per second than the Philadelphia version did. And with Benjamin and Campbell "teaching" Deep Blue new knowledge of the game, Kasparov may find himself pushed to the wall.

Christopher Chabris was Editor in Chief of American Chess Journal. This article appeared originally in Games magazine, July 1996, pp. 10-12, 14, 63.

This page last modified on 28 April 2018.
Copyright (c) 1995-2018 Christopher F. Chabris. All rights reserved.