Behind Deep Blue

15 January 2018

Shiri Avni

“Behind Deep Blue: Building the Computer that Defeated the World Chess Champion” is a compelling 2002 autobiography by Feng-Hseing Hsu, retailing his development of the computer that beat Garry Kasparov in a world-televised series of chess matches. It’s a page-turning book that will captivate readers regardless of their affinity to the game (I myself do not play chess).

A Long, Accidental Road

One of the takeways from this book is that there are no shortcuts when it comes to accomplishing great things. While the famous Kasparov chess matches takes place in 1997, Hsu begins his computer chess saga in 1985 as a PhD student at Carnegie Mellon. In sum, he dedicates a full 12 years to this quest. Hsu actually gets involved in computer chess by accident, and I refer you to his book to find out how it happened!

deep blue creator hsu

Hsu playing Garry Kasparov in 1996, with Hsu making the moves decided upon by the computer he'd developed.
Photo from NBCnews.

Man vs. Man

I often hear from non-computer people about fears of AI and dread about machines taking over the world. While some computer scientists hype up these misplaced claims, I appreciate Hsu’s candor and his continuous emphasis that “intelligent” machines are really just machines reflecting intelligent design by humans. In his book, Hsu states:

The “man versus machine” angle apparently sells well for chess books, but it does not capture the true essence of the content. The contest was really between the men in two different roles: man as a performer and man as a toolmaker… Deep Blue is not intelligent. It is only a finely-crafted tool that exhibits intelligent behavior in a limited domain.

Indeed, after newspapers spread false puff that Hsu’s chess machine could be used for AI purposes in warfare, Hsu quoted Ken Thompson (renown developer of Unix) to say that:

the only military application…[of such a chess machine] is to drop it from an airplane and kill someone.”

So what is it that Hsu set about to accomplish? Hsu’s main focus throughout both his PhD and his computer chess quest was on building a physical computer in a way so that it would make chess calculations quickly. In other words, Hsu was interested in determining the best arrangement of thousands of transistors on a small chip such that that a physical computer could evaluate more chess positions per second, and increase the depth in the search space (see photo below). In this way, Hsu’s computer would be better able to determine which move to make during the rounds of a match.

tic tac toe space search

Search space for the game of tic-tac-toe. The search spaces grows exponentially in the search depth, and moves are evaluated according to the viewpoint of player X, with a score of 1 given to a move resulting in X winning. The search space for chess is similar, but grows much more quickly at every level due to the (generally) larger number of choices per turn.
Courtesy of wikimedia.

Reverse Psychology

Hsu’s ability to garner colleagues to join his cause was impressive, and often times humorous. In 1986, Hsu finished up a prototype of a new chip, but he wanted to avoid the pain of writing the software that would interface with his hardware. Hsu had written a test program that checked that his finished chip was working as designed (verification), but this is different from checking that the chip design itself is actually correct (validation). To validate the hardware, actual chess software would need to be developed to interface with the chips, but Hsu was uninterested in spending the long time needed to create such a program.

So, Hsu, aware of a student at Carnegie Mellon called Thomas who wrote chess programs for fun, took the chip test program he’d developed, and

placed the source of the test program in a public place that Thomas could access… Then I got back to my simulation on how to parallelize the search, pretending to ignore Thomas for the moment. A few days later, Thomas informed me that he had adapted his chess program to use the chess chip, just as I had secretly planned. Thomas was able to get his program… to search about 30,000 positions/second.

Amusement at Computer Chess Tournaments

As Hsu became more involved in his accidental chess quest, he started attending computer chess tournaments. These tournaments were not mere competitions, rather, they were meeting places for computer researchers to discuss ideas.

The state of computer chess in the 1980s led to amusing results at such events. At times, computer programs got caught in inconsistent states and decided on chess moves that were completely illegal (the referee would usually let the researchers restart their computer program at this point).

The programs described in the book all rely on the computer simulating several moves ahead and evaluating each scenario. However, as the search space grows exponentially with the search depth level, the computers back then were limited to searching only a few moves ahead. This resulted in a well-known problem called the horizon effect, in which a move that appears good if evaluated steps ahead, is actually disastrous, and this would be seen if the search depth were deeper.

In a 1986 tournament that Hsu attended, two of the top teams came across this horizon effect, and due to the fact that both teams had the same search depth capability, this comical situation ensued:

[At a certain point in the game,] neither program had any idea about who would come up ahead in the end. Both sides just kept playing… until, suddenly, both programs realized that [Team B] …was a dead loss.

To discover how such buggy, limited computers ended up being advanced enough to beat the best chess players of the world, I strongly recommend this delightful read. Suspense, drama, and laughs are guaranteed.

Relevant Posts:

The Moment of Lift (Melinda Gates)
Revolution for Dummies: Laughing Through the Arab Spring