Grand Challenge in Chip Design
January 30, 2003
Computer scientist Feng-Hsiung Hsu, one of the creators of Deep Blue, shakes hands with reigning world chess champion Gary Kasparov shortly before the opening of the 1997 match in which Deep Blue made history by defeating Kasparov. From Behind Deep Blue.
Book Review
James Case
Behind Deep Blue: Building the Computer that Defeated the World Chess Champion, Feng-Hsiung Hsu, Princeton University Press, Princeton and Oxfordshire, 2002, 320 pages, $27.95.
On May 11, 1997, the IBM computer known as Deep Blue defeated Garry Kasparov--the reigning world chess champion and arguably the most skillful player in history--in a six-game match. It is remembered as the second of their two matches, although Deep Blue was completely rebuilt after the first. Whereas the contests themselves were extensively chronicled, little has been written about the twelve-year campaign to construct a computer and program that could achieve such a victory. Here is a blow-by-blow account of that extraordinary quest for technoglory, written by a man who participated in every phase of it.
By building both a winning program and a machine capable of running it, the IBM team realized a dream dating back at least to 1956, when many of the founding fathers of artificial intelligence gathered at Dartmouth College to discuss long-range research objectives. In the belief that such an achievement would penetrate "to the very core of human intellectual endeavor," they included the development of a chess program strong enough to defeat the reigning world champion on their list of challenge problems. Several computer pioneers, including Germany's Konrad Zuse, predicted that the feat would be accomplished within fifty years. Herbert Simon, later to win the Nobel Prize in Economics, asserted in 1957 that it would be done in ten!
Feng-Hsiung Hsu arrived in the computer science department at Carnegie Mellon University in August 1982. He was 23 years old, and fresh from what he describes as a mind-numbing two-year hitch in the Taiwanese army. He already had some exposure to computer chip design and meant to obtain more, the Taiwanese government having announced its intent to develop a domestic integrated circuit industry. He had chosen computer science at CMU over electrical engineering at Stanford because CMU offered a generous research assistantship and its CS department was rated among the top three in the country.
By the spring of 1985, Hsu had completed the course requirements for a PhD and was gathering material for a thesis on laser printers. Canon had recently announced a new low-cost printer engine--soon to spawn personal laser printers priced below $3000--and Adobe's page-description language PostScript was well on its way to becoming the electronic lingua franca in which such machines are wont to address one another. Yet because PostScript and its original competitors were unable to process Chinese, Japanese, and other East Asian characters, there existed a window of opportunity to produce a custom VLSI printer controller capable of printing pages of ideograms at high speed. Could such a project fail to produce a successful start-up, leading to financial independence?
Literature on printers, computer fonts, and the like was already beginning to accumulate on Hsu's desk when Hans Berliner asked him to delay his thesis work long enough to participate in the redesign of a chess machine called Hitech. Hsu had known about Hitech since his first seminar at CMU, but--not being a particularly gifted or enthusiastic chess player--had taken no part in the project. Berliner wanted to improve Hitech's "evaluation function," which assigns a numerical value to each board configuration. The one in place was a 64-chip design, in which each chip corresponded to a particular square on the 8 � 8 board.
A chess machine has three main components: a move generator, which identifies the moves possible in a particular game situation; an evaluation function, which judges the strength (or vulnerability) of the board configuration reached after a given sequence of moves; and a search control, which chooses the move sequences that are worth further investigation. All three can be realized either in hardware or in software, with the hardware version enjoying perhaps a hundredfold speed advantage. When computer chess aficionados speak of a "chess machine," they are typically referring to a construct equipped with at least a hardware move generator and a hardware evaluation function. Hitech, as Hsu first encountered it, had 64-chip versions of each. He says that all the chess machines he has ever designed are capable of looking ahead 128 plies (meaning 64 moves by each player), although the vast majority of search paths are abandoned far sooner.
After about a week spent looking into Berliner's request, Hsu was unable to convince himself that 64 chips were really needed for the construction of move generators and evaluation functions. In 1983, a chess machine known as Belle (because it was built at Bell Labs) had become the first chess machine to play at the U.S. National Master level. The designers had written a paper describing the basic architecture of their machine, and Hsu had a copy at home. He quickly understood from it that the Belle design was too large to fit onto a single chip, but that the information it obtained from the "disable-stack" was available elsewhere, raising the possibility that something very like Belle's move generator--and presumably its evaluation function as well--could be mounted on a single chip. He observed further that the number of long wires in the design could be reduced from 384 to 48 by incorporating something called a Future Bus, about which he had recently read in an IEEE magazine.
Sometimes, says Hsu, you just have to be in the right place at the right time. Had he not been at CMU, surrounded by computer chess aficionados, and had his apartment not contained copies of both the Belle paper and the IEEE article describing the Future Bus, he probably would not have discovered a way to mount an entire chess machine on a single chip. Had he figured out the same thing five years earlier, the technology needed to exploit his vision would not have been available. Five years later, existing technology would have enabled realization of the original Belle design on a single chip, in which case someone else would almost surely have done it first. It was largely by accident that--in a single fateful evening--he was able to chart the course that eventually led to Deep Blue's historic victory.
After inspiration comes perspiration. Within a month, the circuit design (down to the transistor-switch level) was complete, along with a working simulator. Then came the physical layout, showing every wire and transistor. Nowadays, such a task would be performed automatically with commercially available computer-aided design tools. But the electronic tools available in 1985 weren't up to the job, meaning that virtually the entire task had to be performed manually. Two full months were required, and Hsu found the experience "hellish." His announced purpose was simply to build and test a very fast machine. The one he built turned out to be about twenty times faster than Belle, and more than a thousand times more cost-effective. He gradually realized, in the course of writing up a summary tech report for the benefit of colleagues at CMU, that he was looking at the basic blueprint for the Mother of all Chess Machines.
Doubts about the efficacy of his chips continued even after tests had shown the best of them to work as designed. To demonstrate the soundness of the design, Hsu resolved to adapt an existing chess program to use his new chip. He was fortunate in that a fellow graduate student had written a rudimentary chess program for his own amusement, and was willing to incorporate the new chip into it. The result was able to search about 30,000 chess positions per second--as compared with about 100,000 for the fastest computer chess programs and machines then in existence--and managed to win the very first game it played against a local expert. This was encouraging, but failed to reveal how fast the new chip could operate without overheating. It was therefore decided to assemble a team of graduate students to design a more demanding program, called ChipTest, that would compete in the Association for Computing Machinery's 1986 Computer Chess Championship in Dallas. ChipTest won two games, lost two, and drew one at that tournament, while searching some 300,000 chess positions per second. An improved version won the 1987 ACM tournament without losing a game; able to search nearly 400,000 chess positions per second, it was arguably the strongest computer chess player the world had yet seen.
But ChipTest did not seem strong enough to perform at the Grand Master level over a series of 25 games against human competitors, as would be necessary to claim the second of three Fredkin Intermediate Prizes. Edward Fredkin had established the prizes during the late 1970s to stimulate the development of more capable chess-playing computers and programs. The Belle team had claimed the first such prize during the early 1980s by performing at the Master level. Hsu and his team captured the second Fredkin prize by constructing yet another chess-playing computer, known as Deep Thought. The third and final Fredkin Prize of $100,000 awaited the first computer to defeat the world chess champion.
All this is recounted in the first four chapters of the book. The next eight chronicle--in a chatty nontechnical manner--the final assault on this particular intellectual Everest. These twelve are followed by an epilogue and three appendices, the first of which ("A Lad From Taiwan") is biographical. The bulk of the work on Deep Blue was done at IBM by a three-man team made up of Hsu, Joe Hoane, and Murray Campbell. On July 29, 1997--a mere 80 days after Kasparov surrendered--the three split the final Fredkin Prize of $100,000 evenly. Together, they had devoted some 28 man-years to the project, including 12 for Hsu, nine for Campbell, and seven for Hoane. Hsu and Campbell had been associated with the project from its beginning at CMU; Hoane was already at IBM Research when the project moved there. Others, including a variety of human chess experts, IBM project managers, and CMU faculty members, played essential--if supporting--roles in the drama. Hsu mentions them all by name, and describes their contributions to the campaign, along with the hurdles they helped surmount.
In his epilogue ("Life After Chess"), Hsu describes Kasparov's churlish behavior at the postmatch press conference, IBM's efforts to schedule a rematch, and his own new life as a research scientist at the Western Research Lab of Compaq Computer, Inc. He wants, he says, to "do something practical for a change." He voices in passing the opinion that Kasparov would probably now be crushed by any state-of-the-art chess-playing computer, as "computers can get better much faster than he can." He also opines that either of the current pretenders to the world champion's throne, namely Vladimir Kramnik and Vishwanathan Anand, are tougher opponents for computers than Kasparov, whose playing strength lies mainly in his tactical play, which happens also to be the forte of chess-playing computers.
Hsu also mentions that Kramnik was scheduled to play an eight-game match against the Deep (parallelized) version of Fritz, one of the world's leading commercial chess-playing programs, in October 2002. But the book went to press before that match could take place. (It ended in a draw.) Kasparov himself--whose current chess rating of 2838 is still the highest in the world--is scheduled to play a man-machine match of his own against the Deep (parallel) version of Junior, another highly successful commercial chess package. Their match is to take place in New York City, beginning January 23. It seems only a matter of time before the best human players have no chance at all against the strongest chess-playing machines.
James Case writes from Baltimore, Maryland.
