K9APE’s BOOKSHELF
Shel Epstein
Beyond Deep Blue
By
Feng-Hsiung Hsu
In a previous issue, I reviewed
The Turk, which described Wolfgang von
Kempelen’s 1769 chess-playing hoax. That
apparatus continued to delight and intrigue spectators until it was destroyed
in an 1854 fire. While only a deception,
the Turk was an important spark for fuel to build a machine that could actually
beat a World Champion chess player. The
next major event in chess technology when Claude Shannon (father of
modern Information Theory and M.I.T. Professor) laid out the foundations of
modern chess computers in 1949. It would
take almost 50 years before a machine was built on that foundation that could
beat a Grand Master. That did not happen until 1997 when IBM’s Deep Blue
computer beat Gary Kasparov. Beyond
Deep Blue is not about chess; but, about the men who built it and played
against it – and especially about Feng-Hsiung Hsu, the
author.
Hsu’s
story begins with his 1985 acceptance as a graduate student in the Computer
Science Department of Carnegie Mellon University (CMU). He went there because of his interest in
learning to build Very Large Scale Integrated (VLSI) circuits and
Hsu’s
faculty advisor was Prof. H.T. Kung, who was noted for his work in VLSI
technology and whose students established an informal ChipTest team to
explore the limits of VLSI technology in applications including
chess-playing. CMU’s chess maven was
Prof. Has Berliner who established his HiTest team for the specific
purpose of building an unbeatable chess-playing machine. What started out as friendly rivalry between
the two teams turned to hostile competition when ChipTest technology was
able to beat HiTest technology.
Chess-playing programs have been divided into three sections; namely, a) a move generator that finds moves, b) an evaluation function that assesses the quality of positions found while the program looks ahead and c) a search control that guides analysis of move sequences searched by the program. Dr. Berliner asked Hsu to design a new circuit comprising 64 VLSI chips (one for each square) that would compute how well squares were controlled by pieces. Hsu wasn’t interested in the problem; but, he reluctantly agreed. After analyzing the problem, Hsu told Berliner that a 64-chip solution was not practical and that he had reduced the problem to a circuit that could fit on the die of one VLSI chip. Berliner rejected the proposal; but, Kung urged Hsu to proceed.
Beyond Deep Blue then details how Hsu and his two officemates, plus others, succeeded in building a series of chess-playing machines, named Deep Thought, that beat the HiTest machines and those from other universities. With each victory, the ChipTest team members become more committed to the goal of beating Berliner to the Fredkin International Prize, which they did in 1989. They learn along the way not only how to build better chess-playing machines; but, the politics and strategy of playing competition chess.
In 1989 with his Ph.D. in hand, Hsu was employed by IBM for the specific purpose of continuing his research to build a World Champion chess-playing machine. Deep Thought is renamed Deep Blue and IBM begins to draw public media attention as Deep Blue progresses higher and higher in tournament rankings.
At this point, Hsu’s book bifurcates along two paths; namely, a) strategies and politics of playing tournament chess and b) struggles in developing technology at IBM. You will particularly enjoy reading about the negotiations with Kasparov and his reactions to Deep Blue’s so-called human-like moves (was Hsu cheating?). I found Hsu’s description of technology development very interesting because –to my surprise– I was using several of the same development tools in our business and experiencing some of the same problems.
Having achieved the Holy Grail with victory of Kasparov in 1997, Hsu leaves IBM to work on other problems. He purchases from IBM rights to his chess player; however, he is not successful in commercializing a product. Chess-playing programs become common on PC-computers and even smaller machines. Hsu writes that today even a PDA-based program can beat a Grand Master.
In conclusion, I highly recommend Behind Deep Blue because it is an insightful look at chess and technology and – particularly – about one man who brought them together. It also left me thinking about whether there was still a better way of playing computer chess that did not require in-depth searching and evaluation of each potential move.
* * *
Subsequent to the publication
of Behind Deep Blue and my review of
it, Gary Kasparov played to a 3-3 game tie in a tournament against the Israeli Deep Junior chess playing computer. Kasparov wrote a letter about the experience
that appeared on the editorial page of the
Kasparov acknowledged that his defeat by Hsu’s Deep Blue computer was a milestone in a 50-year quest initiated by Alan Turing for a machine that could beat a human chess champion. However, he criticized IBM for abandoning the competition after its single victory.
Kasparov acknowledged that it was a battle to achieve a tie against Deep Junior; however, he felt that he was much better prepared for this contest than he was for the contest that he lost to Deep Blue. One reason was that he had an opportunity to study Deep Junior’s prior games and its programs. By contrast, Deep Blue’s engineers had the benefit of studying Kasparov’s prior games; but, everything about Deep Blue was held as a secret from Kasparov.
Kasparov is of the opinion that Deep Junior plays a more imaginative and better game that did Deep Blue. He attributes this to the work over the last 5½ years of enthusiasts who have developed better programs that overcome Deep Blue’s 100:1 speed advantage.
Kasparov concludes that we are now entering a new era in man versus machine chess. He looks forward to new sponsors and claims that far from ending the quest, we are just beginning to see new innovations in machine chess. Meanwhile, you can learn more about Kasparov versus Deep Junior at www.x3dworld.com .