King toppled by knights in the quest for computing holy grail

Tony Hoare looks at the story of the computer scientists who created the supercomputer Deep Blue that beat world chess champion Gary Kasparov

In 1946, the electronic computer Eniac, built at the Moore School in Philadelphia, started to obey its first program of instructions.

In 1949, Claude Shannon, the father of information theory, made his proposal on how to program a computer to play chess. The construction of a successful chess machine was suggested by Alan Newell, Cliff Shaw and Herbert Simon as a milestone in the pursuit of artificial intelligence. Its achievement was expected to penetrate the core of human intellectual endeavour and show the way for computers to dominate in other areas of human intellectual activity.

On May 11 1997 in New York, Gary Kasparov, the reigning world chess champion, was playing the deciding game of a match sponsored by IBM.

His opponent was an IBM chess machine called Deep Blue. On move seven he advanced his king's rook pawn by one space, expecting the computer to decline the opportunity for a knight sacrifice. The computer made the sacrifice, and pressed home its advantage. Twelve moves later, the champion resigned.

Was this the triumph of the icy logic of a computer over the joyful exercise of the human intellect? The answer given by the author of this book is a resounding "no". It was an isolated victory of one skilled and practised team of human game players over another. Both teams used computers to help prepare for the match; but only one team undertook to use a computer during the match. The computer-assisted team happened to achieve a remarkable but narrow victory.

This book tells the gripping story of the construction, programming, preparation and use of the Deep Blue chess machine and its predecessors. It proves on every page the author's claim that computer scientists are human too, and they do like to have fun. The fun will be shared by the reader who has no prior knowledge of chess or of computer science; but there is enough technical explanation in the footnotes to convey to the amateur chess player or computer programmer the nature of the problems encountered and how they were solved.

The story begins in 1982, when Feng-hsiung Hsu arrived from Taiwan as a graduate student in the computer-science department at Carnegie Mellon University. At that time, a leading chess computer was Hitech, designed and built at CMU by Hans Berliner and his team. In 1985, as a side project from his main thesis work, Hsu was asked to design special-purpose hardware for evaluating the chessboard position. To fit in with the existing architecture, this had to use 64 chips, one for each square of the chessboard. But Hsu conjectured that the state-of-the-art in chip construction was sufficiently advanced to allow the whole job of move generation to be done on a single chip. In a magnificent design effort, he proved his point (but with no margin to spare). Evidently, no one had told him it was impossible.

Of course, his miniaturised architecture could not fit within the existing structure of Hitech, so Hsu decided to go it alone. He changed his thesis topic, and constructed (on a student budget - $0 in principle, but $500 or about £300 in practice) a hardware interface and test environment for the chip. He entered it for the 1987 ACM Computer Chess Championship under the name Chiptest, and to everybody's astonishment it won the $2,000 prize.

The next target date was to play human opponents at the Fredkin Masters Open Championship in May 1988. For this, a completely new chip was designed with a proper evaluation function built in. Hsu recruited his friends Andreas Novatzyk, Murray Campbell and Mike Brown to give software support and the essential benefit of chess-playing experience. The new device was called Deep Thought, named after the computer in The Hitchhiker's Guide to the Galaxy . It beat several human players and came equal second in the Open Championship.

Deep Thought then travelled the world, playing matches and tournaments against grandmasters from many countries. Hsu describes vividly the excitement of each game. Every evening, the program was extended to incorporate lessons learnt from that day. Its program grew to 100,000 lines.

In 1989, IBM recruited Hsu, with Campbell, to embark on a project that was to bring fame and unprecedented publicity to IBM. They built a new chess chip, and incorporated 24 of them in a new machine Deep Thought II (also known as Deep Blue prototype). It was controlled by 5,000 lines of new software, written by Hsu himself. It won all its games in the 1991 ACM Computer Championship. It toured the world between 1991 and 1995, picking up further experience from its human opponents.

But the ultimate goal was a match with Kasparov, planned for February 1996.

For this, a new chip again was designed and built, to search more than 1 million chess positions a second. More than 200 of the chips were connected to a 36-processor IBM supercomputer. It had been working only two weeks when the match started. Yet it won its very first game. After this shock, Kasparov took the challenge more seriously, and by the last two games he had learnt to win consistently.

For the return match in 1997, the chip set and the machine were again redesigned from scratch. The new machine had 480 chips and 30 work-station processors, and could scan hundreds of millions of positions a second.

Three grandmasters were employed to assist in planning the opening moves.

Large numbers of top games were input into its memory, and used to tune the weightings of the evaluation function for each chess position. All this took place in great secrecy to prevent the preparation of counter-measures by Kasparov and his team. The actual match is described in thrilling detail, including the changes made to the program overnight and during the rest days to prevent further exploitation of each detected weakness.

Equally thrilling is the account of the engineering, managerial and personal problems encountered in the many designs and redesigns. The whole story is a lesson in the advantages of repeatedly throwing away everything that has come before and starting again from scratch. When the investment in a project gets too large, this is no longer possible and all subsequent progress becomes mere routine.

In his preface, Hsu explicitly mentions the model for writing his book as James Watson's personal account of the discovery of the structure of DNA, The Double Helix . Hsu has achieved his aim of matching the excitement of that book. I would have welcomed a chronology and an index to the book and also an account of the progress of computer chess since 1997, when Deep Blue was disassembled, never to play again. Perhaps the holy grail of computer chess, like other inspiring grand challenges, turns out after its achievement to be little more than a byway in the broad history of the advancement of science.

Sir Tony Hoare is senior researcher, Microsoft Research, Cambridge.