Top
Free Shipping On Orders Over $35!
Get Rewarded for Ordering Your Textbooks! Enroll Now
Customer Reviews Read Reviews
Write a Review
| Preface | vii | ||||
| Acknowledgments | xi | ||||
| Chess Notation | xv | ||||
| Prologue | |||||
|
3 | (6) | |||
| Carnegie Mellon | |||||
|
9 | (11) | |||
|
20 | (26) | |||
|
46 | (23) | |||
|
69 | (21) | |||
|
90 | (15) | |||
| Intermezzo | |||||
|
105 | (20) | |||
| IBM | |||||
|
125 | (18) | |||
|
143 | (19) | |||
|
162 | (24) | |||
|
186 | (18) | |||
|
204 | (57) | |||
| Epilogue | |||||
|
261 | ||||
| Appendixes | |||||
|
277 | ||||
|
292 | ||||
|
297 |
The New copy of this book will include any supplemental materials advertised. Please check the title of the book to determine if it should include any access cards, study guides, lab manuals, CDs, etc.
The Used, Rental and eBook copies of this book are not guaranteed to include any supplemental materials. Typically, only the book itself is included. This is true even if the title states it includes any access cards, study guides, lab manuals, CDs, etc.
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?
An Office of Troublemakers
"Your office is an office of troublemakers!" Kung exclaimed, with a resigned look. Kung was Professor H T Kung, my faculty advisor at Carnegie Mellon University in Pittsburgh. He was a tall, well-built man in his 40s. I was a graduate student in the Computer Science (CS) Department. We had just had a long private conversation in his office.
It was the autumn of 1987. Professor Kung had been my advisor during my entire stay at Carnegie Mellon. I had a great deal of respect for him, not just because he was a good advisor to me, but also because of the deeds that he did in private. Professor Kung was a direct descendent of Confucius and took great pride in doing whatever he could to assist the technical and economic developments of Chinese societies around the world. I was not having trouble with Professor Kung. My troubles were with another faculty member in the department.
At the time of the conversation, there were two computer chess teams at Carnegie Mellon. Dr Hans Berliner headed the Hitech team. The competing ChipTest team was a group of freewilled, mostly unsupervised graduate students, of which I was one. I had some light faculty supervision from Professor Kung, while my team members worked on ChipTest almost purely for fun. The competition between the two teams had been friendly, but it was about to turn into an intense rivalry.
In hindsight, the rivalry was inevitable. There had been some friction between the two teams. The ChipTest team was not happy with the frequent and incorrect public portrayal that Dr Berliner was supervising us or that we were his students. To a great extent this portrayal was the result of Dr Berliner's existing fame in computer chess, which led reporters automatically to assume 1 that he led all computer chess efforts at Carnegie Mellon. This characterization was somewhat insulting to the ChipTest team, but it alone would not have caused the immediate escalation of the contention.
The escalation was triggered by, of all things, an invitation for the ChipTest team to play in a chess tournament. The Hitech team happened to be going to the same tournament and Berliner had made his case to Kung on why ChipTest should skip the event.
My conversation with Professor Kung was precisely on what to do with the chess invitation. Kung was supportive of the ChipTest team and saw no reason why we should not play. However, to avoid further problems, the ChipTest team had already decided to honor Dr Berliner's suggestion prior to the conversation.
Professor Kung was relieved that the issue seemed to be resolved, but when he made his remark about the "troublemakers", he must have had a sense of déjà vu. Two years before, in 1985, we had had another conversation, also on an issue related to Dr Berliner. That other conversation was a critical part of the chain of events that led to the creation of ChipTest and, eventually, Deep Blue.
The real seed of the Deep Blue project can be traced back even further. It all began with Professor Kung's "troublemakers" ...
First Year Graduate Students
The Computer Science (CS) Department at Carnegie Mellon was the Department of the university. Several others ranked among the top ten in their disciplines, but CS was ranked among the top three, the other two being the ones at MIT and Stanford. Depending on personal preferences, some would even say that the CS Department at Carnegie Mellon was the best. The Department had its own unique atmosphere, and the graduate students had a great deal more say in their own research directions than at other schools. The fact that the Department offered only a PhD program (no BS or MS program) probably gave the faculty the chance to experiment and come up with the unique system.
In part because of the unusual system and in part because of the diverse background of the incoming students, the entire first month of each fall semester was designated the "immigration Course". For the incoming students, it was a time to learn about the environments, tools, projects, and people, and generally to have a good time. The older students would spend time demonstrating their projects, helping the new students to adapt, and of course, generally having a good time themselves. Near the end of the Immigration Course, the annual Department "Reception" would be held, usually at some fancy location in Pittsburgh. I have a fond memory of pigging out at the Reception as a starving graduate student. The Immigration Course was also the time the "Marriage" process took place. During the Immigration Course, the new students sought out the faculty whose research interested them, and decided whom they wanted as their faculty advisors. The faculty, of course, also observed the new students, deciding whether they wanted a particular student. As in real life, the Marriages were not final, and "divorces" between faculty members and students did occur sometimes, made possible partly by the fact that the funding sources for the students were not necessarily tied to specific projects. Faculty members controlled their advisees mainly through the respect that their advisees had for them. Other than course work, faculty members had very little hold over nonadvisee students.
In 1982, the year I "immigrated" into the Department, the acceptance rate of the admitted students was higher than expected, and there was a space crunch. Normally when offices were assigned, it was considered preferable to mingle the incoming students with older students. As a result of the space crunch I ended up in an empty office together with three other incoming students, Mike Browne, Andreas Nowatzyk and Tony Stentz. In the end, the four of us came out all right, but along the way the faculty probably wished that they had done otherwise. The next year, Tony moved to another office, and for several years only Mike, Andreas and I occupied the office, becoming close friends. Professor Kung's remark on troublemakers probably did not include Tony.
Mike was probably the first American with whom I had a real conversation, which took place on my first day on the Carnegie Mellon campus. It was also only my third day in the United States. When I opened the door to my newly-assigned office, I found a bearded man inside. This was Mike. Because of his beard, I could not tell quite how old he was, but he turned out to be one of the younger students in the incoming class. Born in New Jersey, but growing up in Allentown, Pennsylvania, Mike finished his undergraduate degree at Lehigh University in just three years. In our conversation Mike described himself as a "hacker", which he defined as someone who could churn out computer programs. That is, someone who creates, although in a specialized domain. This definition is still in use today, although the more common definition used by the media is someone who damages or exploits computer systems through virtual means. The newer definition describes a destructive person. Mike was obviously very smart, but he was also surprisingly self-effacing. He attributed his accelerated college schooling entirely to his ability to do well in multiple-choice tests. "I just happened to be good at taking multiple-choice tests," he said, suggesting that he had no other useful talent.
While Mike was one of the younger incoming students, Andreas and I were among the older ones. In my case, this was because in Taiwan, where I came from, boys were required to serve two years in the military after college. Andreas was older because he had spent one extra year to get two tough undergraduate degrees: physics and computer science. He hailed from Germany, was a graduate of the University of Hamburg, and had been one year into his PhD program in Germany before he decided to make the move to Carnegie Mellon. Mike was an extremely good programmer, and Andreas was not too shabby either. Besides being a top-notch programmer, Andreas turned out to be a man with many technical skills. He never ceased to amaze me while we were at Carnegie Mellon. I had a dogged belief that I could be good at anything technical if I put my mind to it. Andreas seemed to be already good at everything technical.
Both Mike and I were somewhat playful in our early years at Carnegie Mellon, while Andreas was all business from day one. Andreas and I did not really become close friends until much later when we found that we shared many common technical interests. The friendship, however, was not really symmetrical. I can remember many instances of Andreas helping me in areas where I was lacking. But he was so self-sufficient that I don't recall ever doing anything to in any way help him.
Andreas, Mike, and I all had some prior contact with chess, or computer chess, before arriving in Carnegie Mellon. Mike used to be a serious tournament chess player when he was in high school. Andreas did not play chess seriously, but he had been keenly interested in computer chess. He had once helped to referee a World Microcomputer Chess Championship tournament in Germany while an undergraduate student. My earlier contacts with computer chess were mainly from reading technical journals and books. During our immigration both Andreas and I checked out the existing computer chess research in the Department. We were both interested in Very Large Scale Integration (VLSI) chip design and Carl Ebeling, a graduate student in the VLSI group, was designing a VLSI-based chess machine.
Continues...
Excerpted from Behind Deep Blue by Feng-hsiung Hsu Copyright © 2002 by Princeton University Press
Excerpted by permission. All rights reserved. No part of this excerpt may be reproduced or reprinted without permission in writing from the publisher.
Need Help? Copyright © 1999-2025
