Behind Deep Blue: Building the Computer that Defeated the World Chess Champion

by Feng-hsiung Hsu

Overview

On May 11, 1997, as millions worldwide watched a stunning victory unfold on television, a machine shocked the chess world by defeating the defending world champion, Garry Kasparov. Written by the man who started the adventure, Behind Deep Blue reveals the inside story of what happened behind the scenes at the two historic Deep Blue vs. Kasparov matches. This is also the story behind the quest to create the mother of all chess machines. The book unveils how a modest student project eventually produced a multimillion dollar supercomputer, from the development of the scientific ideas through technical setbacks, rivalry in the race to develop the ultimate chess machine, and wild controversies to the final triumph over the world's greatest human player.


In nontechnical, conversational prose, Feng-hsiung Hsu, the system architect of Deep Blue, tells us how he and a small team of fellow researchers forged ahead at IBM with a project they'd begun as students at Carnegie Mellon in the mid-1980s: the search for one of the oldest holy grails in artificial intelligence—a machine that could beat any human chess player in a bona fide match. Back in 1949 science had conceived the foundations of modern chess computers but not until almost fifty years later—until Deep Blue—would the quest be realized.


Hsu refutes Kasparov's controversial claim that only human intervention could have allowed Deep Blue to make its decisive, "uncomputerlike" moves. In riveting detail he describes the heightening tension in this war of brains and nerves, the "smoldering fire" in Kasparov's eyes. Behind Deep Blue is not just another tale of man versus machine. This fascinating book tells us how man as genius was given an ultimate, unforgettable run for his mind, no, not by the genius of a computer, but of man as toolmaker.

Product Details

ISBN-13:	9780691118185
Publisher:	Princeton University Press
Publication date:	02/15/2004
Edition description:	With a New Afterword by the Author
Pages:	320
Product dimensions:	6.00(w) x 9.25(h) x (d)

About the Author

Feng-hsiung Hsu is the founding father of the Deep Blue project. He began it in 1985 as a graduate student at Carnegie Mellon University. From 1989 to 1997 he worked as the system architect and chip designer for the Deep Blue Chess machine at IBM's T. J. Watson Research Center. He is now a senior researcher at Microsoft Research Asia.

Read an Excerpt

COPYRIGHT NOTICE: Published by Princeton University Press and copyrighted, © , by Princeton University Press. All rights reserved. No part of this book may be reproduced in any form by any electronic or mechanical means (including photocopying, recording, or information storage and retrieval) without permission in writing from the publisher, except for reading and browsing via the World Wide Web. Users are not permitted to mount this file on any network servers.

Chapter 1

Show Time!

In late April 1997, posters for an unusual chess event were appearing on the streets of New York. They showed a somber and pondering gentleman in his early 30s peering over a chess set at the viewers. The small caption under his chin said, "How do you make a computer blink?" The gentleman on the poster was the World Chess Champion Garry Kasparov, possibly the strongest chess player who has ever lived.

Off the street, in the basement of the Equitable Building, I was staring at the blank screens in an empty auditorium. In a few days, the auditorium would be filled with an overflowing crowd; TV cameras would be entrenched at vantage locations and the three huge projection screens at the front would come to life. The left screen would be showing a live image from a TV studio on the 35th floor of the building, serving as the game room. The live image would usually show the two contestants sitting across a specially designed playing table. The contestant on the left would be Garry Kasparov. The contestant on the other side would be one of my two colleagues, Murray Campbell and Joe Hoane, or me.Garry's real opponent was the chess computer, Deep Blue, that the three of us had designed and programmed. During the games we acted merely as extensions of Deep Blue and made moves for it on the physical chessboard. In the auditorium itself, three chess commentators, sometimes with a guest commentator or two, would be using the center screen to show their analysis of the ongoing game. The right screen would be displaying the overhead shot of the chessboard. This way, the audience in the auditorium would have a clear view of the present game position.

It had taken me almost twelve years to reach this point. When I started, Garry was not the World Champion; it was a few months yet before he was crowned. For the past eleven years, since 1986, my partners and I had been building successively more powerful chess computers. Our eventual goal was to beat the World Chess Champion, whoever he or she was.

Before us, many pioneers, some famous and some not so famous, had made their contributions to the "Computer Chess Problem". In 1949, Claude Shannon made his proposal on how to program a computer to play chess. Since then, thousands of computer scientists, engineers, hobbyists, chess players, and even commercial organizations had worked on the problem. Some wanted to use chess as an experimental tool to find out how human intelligence worked. "If one could devise a successful chess machine, one would seem to have penetrated to the core of human intellectual endeavor," said Allen Newell, Cliff Shaw and Herbert Simon in one of the early computer chess papers. Other people viewed chess as a clear-cut, well-defined example of a complex problem. "Solving" chess could conceivably provide new techniques to solve other complex problems. The commercial entities did it for profit, of course, and some people, especially the hobbyists, did it just for fun.

We approached the problem from a different direction. We, or at least I, viewed the problem as a purely engineering one. Since the late 1970s, it had been established that chess computers became stronger as their hardware speed increased. By 1985, when I started my small project that eventually become Deep Blue, the extrapolation from the experimental data indicated that a one thousandfold increase in hardware speed might be sufficient to produce a World Champion-class chess machine. Our project began with a simple goal, namely, to find out whether a massive increase in hardware speed would be sufficient to "solve" the Computer Chess Problem. Building this "Mother of all Chess Machines" was an interesting problem by itself. Of course, it would be an added bonus if our machine could indeed defeat the World Champion.

The previous version of Deep Blue, lost a match to Garry Kasparov in Philadelphia in 1996. But two-thirds of the way into that match, we had played to a tie with Kasparov. That old version of Deep Blue was already faster than the machine that I conjectured in 1985, and yet it was not enough. There was more to solving the Computer Chess Problem than just increasing the hardware speed. Since that match, we rebuilt Deep Blue from scratch, going through every match problem we had and engaging Grandmasters extensively in our preparations. Somehow, all the work caused Grandmaster Joel Benjamin, our chess advisor, and one of the best chess players in the US, to say, "You know, sometimes Deep Blue plays chess." Joel could no longer distinguish with certainty Deep Blue's moves from the moves played by the top Grandmasters.

The press covered this new match with much anticipation. If the new Deep Blue won the match, then it would be a momentous occasion in the long history of men as toolmakers. It would also be the completion of a long-sought-after milestone for computer scientists and artificial intelligence researchers. It was almost certain that this match would be bigger than any World Chess Championship match, with possibly the sole exception of the Fischer vs. Spassky match in 1972. If we did win, perhaps not even that Fischer vs. Spassky match would compare.

The new Deep Blue was much improved, but would it be enough? Would the journey begun by my partners and me so many years ago finally be over?

Table of Contents

	Preface	vii
	Acknowledgments	xi
	Chess Notation	xv
	Prologue
Chapter 1	Show Time!	3
	Carnegie Mellon
Chapter 2	An Office of Troublemakers	9
Chapter 3	Taking the Plunge	20
Chapter 4	The Chess Machine That Wasn't	46
Chapter 5	The Race for First Machine Grandmaster	69
Chapter 6	"Knock, Knock. Who's There?"	90
	Intermezzo
Chapter 7	First Date with History	105
	IBM
Chapter 8	We Need a New Name	125
Chapter 9	Bringing Up the Baby	143
Chapter 10	A Living Mount Everest	162
Chapter 11	Retooling	186
Chapter 12	The Holy Grail	204
	Epilogue
Chapter 13	Life after Chess	261
	Appendixes
Appendix A	A Lad from Taiwan	277
Appendix B	Selected Game Scores	292
Appendix C	Further Reading	297

What People are Saying About This

From the Publisher

"Feng-hsiung Hsu, who masterminded Kasparov's match play defeat by a computer, tells his story. A nerdy book might be expected, delving into arcane topics (computer chip design, programming, chess), but instead we have something more like 'Indiana Jones and the Holy Grail.' No specialist knowledge is demanded. The author's adventures with phantom queens, etc. are fascinating. His will-to-win matched that of the legendary Kasparov."—Ken Whyld, Editor of the Oxford Companion to Chess

"I don't play chess; never have. Most research, as Edison said, is 90% perspiration and 10% inspiration—not exciting to watch. Thus, I did not have high hopes for Behind Deep Blue. Wrong! It's a page-turner! Even if you don't follow the technical details of chip design or chess, Hsu has captured the very human dimension exquisitely! It's a great story!"—William A. Wulf, President of the National Academy of Engineering, AA&M Professor of Computer Science, University of Virginia

Ken Whyld

Feng-hsiung Hsu, who masterminded Kasparov's match play defeat by a computer, tells his story. A nerdy book might be expected, delving into arcane topics (computer chip design, programming, chess), but instead we have something more like 'Indiana Jones and the Holy Grail.' No specialist knowledge is demanded. The author's adventures with phantom queens, etc. are fascinating. His will-to-win matched that of the legendary Kasparov.
— Ken Whyld, Editor of the "Oxford Companion to Chess"

Wulf

I don't play chess; never have. Most research, as Edison said, is 90% perspiration and 10% inspiration--not exciting to watch. Thus, I did not have high hopes for Behind Deep Blue. Wrong! It's a page-turner! Even if you don't follow the technical details of chip design or chess, Hsu has captured the very human dimension exquisitely! It's a great story!
— William A. Wulf, President of the National Academy of Engineering, AT&T Professor of Computer Science, University of Virginia

Editorial Reviews

"Mr. Hsu manages to make seemingly dry, technical material vivid and gripping, even for readers without a background in chess or computers. And his story is a fascinating study, of men as well as machines."—-Christopher F. Chabris, The Wall Street Journal

"Hsu's account is written in an easy, flowing style, and, as he says, it is rather light-hearted. . . . The point that Hsu makes is that building and programming a computer that can calculate 2 million chess moves a second is not frivolous . . . All science is a kind of play, in the sense of a play of mind. . . . Most of Behind Deep Blue is Hsu's tale of encountering and overcoming obstacles in the design and programming of the computer to enable it to play chess like a human being. The technical aspects of both computers and chess will be fully comprehensible only to those with the appropriate experience and skill. The human story, though, is clear and exciting: dversity encountered, challenges met, all with the human elements of pride and anxiety and triumph. And the human elements, too, of anger and resentment."—-Anthony Day, Los Angeles Times

"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."—-Tony Hoare, Times Higher Education Supplement

"A chess-playing machine rather than a mere program, Deep Blue drew its awesome power from chips designed by Hsu to do nothing but play chess. The IBM team put 256 of these processors into a supercomputer, allowing it to analyze at least 100 million chess positions a second."—-Nell Boyce, U.S. News and World Report

"A fascinating account of the IBM computer and the match, written by its programmer."—-Lubomir Kavalek, The Washington Post

"This is a fascinating insight into the machinations and science that went into the now dismantled chess program which defeated Kasparov in 1997."—-Raymond Keene, The Spectacle

From the Publisher

"This is a story of the search for one of the oldest holy grails in artificial intelligence—a machine capable of beating any human chess player in a bona fide match. . . . It also exquisitely captures the very human dimension and is a page-turner not to be missed."

Choice

[A] vivid, intimate portrayal of personal toil and triumph. Behind Deep Blue is warm, humorous and insightful. . . . Hsu . . . shows the reality of scientific exploration, warts and all, chronicling the obsessiveness, competitiveness and costly mistakes that mark most research (along with, of course, the thrills, fun and camaraderie).

" American Scientist athan Schaeffer

Mr. Hsu began trying to solve "The Computer Chess Program" in 1985 while a graduate student at Carnegie Mellon University. His narrative of those early days is as riveting as the details of the victory over Mr. Kasparov. It is not easy to make a discussion of computer chip design palatable to non-nerds. But the electronic intricacies of Mr. Hsu's rewiring of Deep Blue's hardware are explained in the context of university and chess world politics. By blending technical descriptions into the real-life daily dramas confronting the project, Mr. Hsu makes the trip exciting.

The Dallas Morning News - Doug Bedell

[Hsu's] conversational narrative takes us from school days in Taiwan through his graduate studies at Carnegie-Mellon University to his team's triumph in Deep Blue's second match against Garry Kasparov. . . . Hsu spins an intriguing behind-the-scenes tale of how he and his Deep Blue team prevailed.

San Francisco Times - Lee Gaillard

This is a fascinating insight into the machinations and science that went into the now dismantled chess program which defeated Kasparov in 1997.

The Spectacle - Raymond Keene

A fascinating account of the IBM computer and the match, written by its programmer.

The Washington Post - Lubomir Kavalek

A chess-playing machine rather than a mere program, Deep Blue drew its awesome power from chips designed by Hsu to do nothing but play chess. The IBM team put 256 of these processors into a supercomputer, allowing it to analyze at least 100 million chess positions a second.

U.S. News and World Report - Nell Boyce

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.

Times Higher Education Supplement - Tony Hoare

Hsu's account is written in an easy, flowing style, and, as he says, it is rather light-hearted. . . . The point that Hsu makes is that building and programming a computer that can calculate 2 million chess moves a second is not frivolous . . . All science is a kind of play, in the sense of a play of mind. . . . Most of Behind Deep Blue is Hsu's tale of encountering and overcoming obstacles in the design and programming of the computer to enable it to play chess like a human being. The technical aspects of both computers and chess will be fully comprehensible only to those with the appropriate experience and skill. The human story, though, is clear and exciting: dversity encountered, challenges met, all with the human elements of pride and anxiety and triumph. And the human elements, too, of anger and resentment.

Los Angeles Times - Anthony Day

Mr. Hsu manages to make seemingly dry, technical material vivid and gripping, even for readers without a background in chess or computers. And his story is a fascinating study, of men as well as machines.

The Wall Street Journal - Christopher F. Chabris

By building both a winning program and a machine capable of running it, the IBM team realized a dream dating back to at least 1956.. . . Here is a blow-by-blow account of that extraordinary quest for technoglory, written by a man who participated in every phase of it.

SIAM News - James Case

Hsu's enthusiasm and expertise allow him to ease into the role of storyteller, and his personal narrative is colored with details that make, surprisingly, for a thrilling page turner.

Christian Science Monitor - Elizabeth Armstrong

[Hsu's] conversational narrative takes us from school days in Taiwan through his graduate studies at Carnegie-Mellon University to his team's triumph in Deep Blue's second match against Garry Kasparov. . . . Hsu spins an intriguing behind-the-scenes tale of how he and his Deep Blue team prevailed.
— Lee Gaillard

San Francisco Times

By building both a winning program and a machine capable of running it, the IBM team realized a dream dating back to at least 1956.. . . Here is a blow-by-blow account of that extraordinary quest for technoglory, written by a man who participated in every phase of it.
— James Case

SIAM News

This is a fascinating insight into the machinations and science that went into the now dismantled chess program which defeated Kasparov in 1997.
— Raymond Keene

The Spectacle

Mr. Hsu got my attention and kept it, though, bringing this strange story to life with a fluent, modest style, some side excursions into academic politics, a dash of wit, and riveting accounts of the games—and the gamesmanship—that led up to the May 1997 victory. . . . Part of this book's particular charm is that Mr. Hsu is level-headed about what he and his colleagues accomplished.

New York Sun - John Derbyshire

Mr. Hsu got my attention and kept it, though, bringing this strange story to life with a fluent, modest style, some side excursions into academic politics, a dash of wit, and riveting accounts of the games—and the gamesmanship—that led up to the May 1997 victory. . . . Part of this book's particular charm is that Mr. Hsu is level-headed about what he and his colleagues accomplished.
— John Derbyshire

New York Sun

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.
— Tony Hoare

Times Higher Education Supplement

Hsu's enthusiasm and expertise allow him to ease into the role of storyteller, and his personal narrative is colored with details that make, surprisingly, for a thrilling page turner.
— Elizabeth Armstrong

Christian Science Monitor

A chess-playing machine rather than a mere program, Deep Blue drew its awesome power from chips designed by Hsu to do nothing but play chess. The IBM team put 256 of these processors into a supercomputer, allowing it to analyze at least 100 million chess positions a second.
— Nell Boyce

U.S. News & World Report

[A] vivid, intimate portrayal of personal toil and triumph. Behind Deep Blue is warm, humorous and insightful. . . . Hsu . . . shows the reality of scientific exploration, warts and all, chronicling the obsessiveness, competitiveness and costly mistakes that mark most research (along with, of course, the thrills, fun and camaraderie).

American Scientist

A fascinating account of the IBM computer and the match, written by its programmer.
— Lubomir Kavalek

The Washington Post

Mr. Hsu manages to make seemingly dry, technical material vivid and gripping, even for readers without a background in chess or computers. And his story is a fascinating study, of men as well as machines.
— Christopher F. Chabris

The Wall Street Journal

Mr. Hsu began trying to solve "The Computer Chess Program" in 1985 while a graduate student at Carnegie Mellon University. His narrative of those early days is as riveting as the details of the victory over Mr. Kasparov. It is not easy to make a discussion of computer chip design palatable to non-nerds. But the electronic intricacies of Mr. Hsu's rewiring of Deep Blue's hardware are explained in the context of university and chess world politics. By blending technical descriptions into the real-life daily dramas confronting the project, Mr. Hsu makes the trip exciting.
— Doug Bedell

The Dallas Morning News

"A fascinating story."

Booklist

A chess-playing machine rather than a mere program, Deep Blue drew its awesome power from chips designed by Hsu to do nothing but play chess. The IBM team put 256 of these processors into a supercomputer, allowing it to analyze at least 100 million chess positions a second.
— Nell Boyce

U.S. News and World Report

Hsu's account is written in an easy, flowing style, and, as he says, it is rather light-hearted. . . . The point that Hsu makes is that building and programming a computer that can calculate 2 million chess moves a second is not frivolous . . . All science is a kind of play, in the sense of a play of mind. . . . Most of Behind Deep Blue is Hsu's tale of encountering and overcoming obstacles in the design and programming of the computer to enable it to play chess like a human being. The technical aspects of both computers and chess will be fully comprehensible only to those with the appropriate experience and skill. The human story, though, is clear and exciting: dversity encountered, challenges met, all with the human elements of pride and anxiety and triumph. And the human elements, too, of anger and resentment.
— Anthony Day

Los Angeles Times

"Hsu . . . was the system architect for Deep Blue. He makes an exciting tale of computer chess evolution and the Kasparov match."

Scientific American

Hsu spins an intriguing behind-the-scenes tale of how he and his Deep Blue team prevailed.
—San Francisco Chronicle

Mr. Hsu manages to make seemingly dry, technical material vivid and gripping, even for readers without a background in chess or computers. And his story is a fascinating study, of men as well as machines.

Wall Street Journal

In 1997, a computer developed by a team of researchers at IBM shocked the world by defeating world chess champion Gary Kasparov in a six-game match. Hsu began developing Deep Blue, the first computer to achieve such a feat, as a graduate student at Carnegie Mellon University. Here he focuses on the events in his career that led to his involvement with the project. He tells the story of how the basic technical ideas took shape in the computer science department and describes the further evolution and culmination of the project at IBM. Not merely a rehashing of the engineering that was poured into creating the "mother of all chess machines," Hsu's account goes beyond the typical man vs. machine angle and attempts to capture the true essence of the contest between men in two distinct roles: Kasparov as performer and Hsu's team as toolmaker. The result is an intelligent, well-written account of a milestone in the history of computer science that stands out from the other books on Deep Blue. Recommended for general readers attracted to the history of chess and computing.-Joe J. Accardi, William Rainey Harper Coll. Lib., Palatine, IL

Library Journal

A byte-by-byte account of the successful effort of IBM computer scientists to create a machine that could defeat a genius. Hsu, who left IBM in 1999 to write and to pursue non-chess-related interests, brings a unique perspective to this task: It was he and his colleagues (first in Carnegie Mellon's Ph.D. Computer Science program and then at IBM) who designed the hardware and software that ultimately defeated Garry Kasparov in a highly publicized six-game match in 1997. Hsu insists that this was not a case of John Henry versus the steam engine; instead, it was man-as-toolmaker defeating man-as-performer. Hsu portrays himself, also, as a reluctant warrior who initially resisted the Call to Adventure and entered the fray only when the engineering issues began to intrigue him (at the outset, he knew little chess). In his chronicle of increasingly fierce Carnegie Mellon academic politics, a competitor, Prof. Hans Berliner, doesn't come off well as his chess-playing computer (Hitech) falls behind the system designed by Hsu et al. Hsu gives ample credit to his colleagues and tries to be generous with Kasparov-though the latter emerges as somewhat arrogant, petulant, pampered, and petty, not to mention a sore loser. Hsu strives admirably to avoid geek-speak (he tells us what cursors and pawns are), and readers who speak neither computer-ese nor chess-ian can still enjoy the building tension. Born in Taiwan, Hsu appends some autobiographical material-as if to certify that he is no cyborg (he seems reluctant to accept much blame for computer failures, which, invariably, he attributes to "bugs" or to time's wingéd chariot hurrying near). A strange, inaccurate index lists some people by first name,some by last. A real-life Revenge of the Nerds, the tale captures some of the excitement of the day when a machine took a man to the woodshed. (20 halftones)

Kirkus Reviews

"A fascinating story."

Booklist