The Bug in Deep Blue and Its Effect on Garry Kasparov

Nate Silver’s anticipated book, The Signal and the Noise: Why So Many Predictions Fail-but Some Don’tcomes out today. The Washington Post has a great excerpt from Silver’s book about the bug in Deep Blue that made Kasparov consider the machine super intelligent:

Nevertheless, there were some bugs in Deep Blue’s inventory: not many, but a few. Toward the end of my interview with him, [Murray] Campbell somewhat mischievously referred to an incident that had occurred toward the end of the first game in their 1997 match with Kasparov.

“A bug occurred in the game and it may have made Kasparov misunderstand the capabilities of Deep Blue,” Campbell told me. “He didn’t come up with the theory that the move it played was a bug.”

The bug had arisen on the forty-fourth move of their first game against Kasparov; unable to select a move, the program had defaulted to a last-resort fail-safe in which it picked a play completely at random. The bug had been inconsequential, coming late in the game in a position that had already been lost; Campbell and team repaired it the next day. “We had seen it once before, in a test game played earlier in 1997, and thought that it was fixed,” he told me. “Unfortunately there was one case that we had missed.”

In fact, the bug was anything but unfortunate for Deep Blue: it was likely what allowed the computer to beat Kasparov. In the popular recounting of Kasparov’s match against Deep Blue, it was the second game in which his problems originated—when he had made the almost unprecedented error of forfeiting a position that he could probably have drawn. But what had inspired Kasparov to commit this mistake? His anxiety over Deep Blue’s forty-fourth move in the first game—the move in which the computer had moved its rook for no apparent purpose. Kasparov had concluded that the counterintuitive play must be a sign of superior intelligence. He had never considered that it was simply a bug.

I’ve ordered the book on Amazon.

Link of the Day (01/25/10)

There is one article I want to highlight for today. It is so interesting that it deserves to stand on its own as the link of the day.

(1) “The Chess Master and the Computer” [New York Review of Books] – an incredibly well-written and thought-provoking piece by Garry Kasparov, perhaps the greatest chess player of all time. In the article, Garry Kasparov discusses his play against computers, from the 1980s to the showdown with Deep Blue in 1997 to playing against modern computer chess programs.

Most intriguing to me are Mr. Kasparov’s thoughts on the possibility of solving chess. Imagine this scenario: you make a move in chess, and the computer would be able to calculate the best move under the circumstances and predict the likelihood of achieving mate (and in how many moves it will occur). The concept of solving chess is something I have been thinking about for over ten years, so it’s refreshing to read a Grandmaster’s opinion:

Another group postulated that the game would be solved, i.e., a mathematically conclusive way for a computer to win from the start would be found. (Or perhaps it would prove that a game of chess played in the best possible way always ends in a draw.) Perhaps a real version of HAL 9000 would simply announce move 1.e4, with checkmate in, say, 38,484 moves. These gloomy predictions have not come true, nor will they ever come to pass. Chess is far too complex to be definitively solved with any technology we can conceive of today.

So Mr. Kasparov is not excluding the possibility of chess being solved one day; he simply argues that it is inconceivable to solve the game of chess with the hardware we have today. Mr. Kasparov goes on to explain:

The number of legal chess positions is 1040, the number of different possible games, 10120. Authors have attempted various ways to convey this immensity, usually based on one of the few fields to regularly employ such exponents, astronomy. In his book Chess Metaphors, Diego Rasskin-Gutman points out that a player looking eight moves ahead is already presented with as many possible games as there are stars in the galaxy. Another staple, a variation of which is also used by Rasskin-Gutman, is to say there are more possible chess games than the number of atoms in the universe. All of these comparisons impress upon the casual observer why brute-force computer calculation can’t solve this ancient board game.

If you are at all interested in chess, computer science, or algorithms, I highly encourage you to read the entire article.