How a random bug in Deep Blue may ultimately have led to Kasparov's defeat

http://www.washingtonpost.com/blogs/ezra-klein/wp/2012/09/26/nate-silvers-the-signal-and-the-noise/

by prajjwal • 14 years ago

185 50 14 years ago

As learned in CLRS ... when you're stuck, randomize. That turned out to be a great solution in way more problems than I had anticipated.

lloeki• 14 years ago

Making a choice (any choice) is often better than making no choice at all, although not choosing at all is itself an often overlooked valid choice ("A strange game. The only winning move is not to play"). There's an oxymoronic french expression reflecting that often overlooked possibility, especially in dire situations: "Il est urgent d'attendre" which could be translated as "it is most pressing to wait".

Robin_Message• 14 years ago

There's also the phrase by Dr. Linda A. Lewis: "Don't just do something, stand there!" to exhort careful consideration even in face of a crisis.

cbsmith• 14 years ago

It's not even that really: if you are stuck, that means as near as you can tell, all candidate moves are equally good. Picking any one of them (at random, or through any other heuristic) can only be a bad move if there is something you missed about their relative value.

riffraff• 14 years ago

contrast: Buridan's Ass http://en.wikipedia.org/wiki/Buridan%27s_ass

orjan2• 14 years ago

Amazon seems to have two different Kindle editions of this, with different prices:

1. For $19.54 you get this: http://www.amazon.com/The-Signal-Noise-Predictions-ebook/dp/... (The Penguin Press)

2. And for $13.79, you get this: http://www.amazon.com/The-Signal-Noise-Prediction-ebook/dp/B... (Allen Lane)

I have no idea if there is any difference in the editions besides the price. Page numbers differs but that means nothing

EDIT: grammar.

Stratoscope• 14 years ago

When I follow your links I see the Penguin edition for $14.99 and the other edition "not available".

orjan2• 14 years ago

Might be an Amazon territory thing, then. I'm in Europe.

d0mine• 14 years ago

I see $17 and $12 correspondingly for the kindle editions.

bluelu• 14 years ago

I have twice $19.81 here for both editions (Luxembourg)

Devilboy• 14 years ago

44...Rd1 http://www.youtube.com/watch?v=8guNB96rVgw See 3:10. Deep Blue resigned at move 45.

kqr2• 14 years ago

From the article:

  Kasparov had concluded that the counterintuitive play must 
  be a sign of superior intelligence. He had never considered
  that it was simply a bug.

Does anyone know the source for that? Game 2 was definitely pivotal, but I couldn't find any reference to indicate that he gave up because of the random move in Game 1.

Regarding Game 2, from http://www.washingtonpost.com/wp-srv/tech/analysis/kasparov/...

  In that game, Deep Blue made a series of brilliant moves 
  but then failed to anticipate one Kasparov could have made 
  -- but didn't -- to force a tie. Kasparov, who didn't 
  notice the possible move until it was pointed out to him 
  after the game, said: "I still don't understand how the 
  machine couldn't see that."

jc1233• 14 years ago

Agree this all sounds apocryphal. In a losing position there were not too many choices and 44...Rd1 seems reasonable even though it may not have been the best move to prolong the game the longest.

brindle• 14 years ago

I read an article years back and I think it was in the Wall Street Journal. My understanding was that an unexpected grandmaster-level move at a point where Kasparov was expecting to see a different move occurred.

Kasparov suspected user intervention. Unfortunately the event was sponsored by IBM, so ther was potential for a conflict of interest.

He requested to see the source code and the game logs which was denied by IBM. IBM also disassembled the computer immediately after the match to re-purpose the computer for protein folding.

I think this book is rewriting history. Kasparov was devastated.

T-hawk• 14 years ago

I remember that incident as well; it was the next game after the random rook move and Kasparov was already unsettled about the computer's capabilities. By my memory, it went like this:

In a complicated midgame, Kasparov moved a pawn to a square under attack. He intended to sacrifice it for positional gain, opening up his attack lines and compromising the opponent's defensive structure. Kasparov expected that a computational chess engine would seize the calculable material gain and not see the deeper positional subtleties. (Deep Blue 'only' searched ahead about 10 to 15 moves, not nearly as deep as today's computers.) Deep Blue did in fact decline the pawn sacrifice, causing Kasparov to accuse IBM of intervention, that only a human grandmaster would see the response.

This Wikipedia article mentions Kasparov setting a trap that the computer did not fall for, but it doesn't mention the details. http://en.wikipedia.org/wiki/Game_Over:_Kasparov_and_the_Mac...

It happened in game 2 of the 1997 match, the moves of which are recorded here. I haven't got the time at the moment to find the position in the game but perhaps someone can. http://en.wikipedia.org/wiki/Deep_Blue_versus_Garry_Kasparov

QuantumGood• 14 years ago

Yup, there was an agreement in place that Kasparov could see the analysis that Deep Blue output. The outcome has never been decided, in my opinion, because of IBM violating the terms of the agreement.

When K requested it, he was put off. This went on, and I tracked it closely at the time, waiting for IBM to give it up. They kept saying they would, but never did to my knowledge.

Kasparov was concerned that IBM could encounter a bug, or simply a losing situation, and would have the chance to intervene with Deep Blue's calculations without anyone knowing. Deep Blue made more than one move that made Kasparov suspicious during the match. (Years later, humans interacting with computers was shown to produce much stronger results than just computers alone, even when the computers were much stronger at chess than the humans assisting them.)

Many Grandmasters have pointed out that at top-level matches, particularly world championships, psychology is the MOST important factor in deciding the outcome. This makes IBM's behavior all the worse, regardless of their reason.

(My friend Mike Valvo, now passed away, was the arbiter at the match http://www.computerhistory.org/chess/full_record.php?iid=stl... When I first met Mike, I said "There's something I always wanted to say to you!" He said "What's that?" and I said "e4" to which he responded "c5" and we proceeded to play a few moves of a Sicilian. Mike was one of a few people who had played and beaten Bobby Fischer in casual play.)

cube13• 14 years ago

Here's an article with quotes from Kasparov that supports the thesis. The site is a classic 90's setup, and Kasparov's reaction is about halfway down the page(search for "Suicide?" without the quotes).

http://www.chessbase.com/columns/column.asp?pid=146

dmlorenzetti• 14 years ago

The block quote from the book states, "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."

This suggests rather strongly that the author of the book interviewed Campbell, rather than relying on some secondary source. Campbell, of course, may be speculating, but this seems like pretty direct attribution. The only more direct source would be Kasparov himself.

jc1233• 14 years ago

From this source which looks credible and quotes Kasparov http://www.chessbase.com/columns/column.asp?pid=146

Sitting in front of the computer Garry started trying out other lines, beginning with 44...Rf5+. Then he turned to me (his "computer expert") and said: "How could Deep Blue play 44...Rd1 and lose immediately? 44...Rf5+ also loses, but it puts up much more resistance. How can a computer commit suicide like that?" I had no immediate answer, it did indeed look very strange. Garry continued to potter around with Fritz, and suddenly he found the solution himself.

The conclusion is that it was not a bug: "It probably saw mates in 20 and more", said Garry.

SagelyGuru• 14 years ago

"Kasparov had concluded that the counterintuitive play must be a sign of superior intelligence."

and that is how we humans come undone: we worry too much.

Florin_Andrei• 14 years ago

The pattern-recognition engine in the human brain is overcranked.

anthonyb2• 14 years ago

Except that this exact situation had happened in earlier games - see cube13's link: https://news.ycombinator.com/item?id=4583135

fts89• 14 years ago

Kindle version: http://www.amazon.com/gp/product/B007V65R54/ref=as_li_ss_tl?...

hasenj3• 14 years ago

> 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 think this says quite a bit about chess as a game.

That a top player can't recognize a bad move near the final stage of the game.

In contrast, the game of Go is rich with examples where one player makes a bad move and the opponent takes advantage of it; and I'm talking about top players; not amateurs.

Following the opponent and/or always responding to his moves is considered a typical sign of a weak player. One of the things you learn as you get better is to never assume that the last move of your opponent is necessarily a good move.

Imagining that your opponent has a threat you haven't yet figured out is one of the bad habits that weak players must get rid of before they can become stronger.

pessimist• 14 years ago

I'm not aware of the move in question, but you are overinterpreting wildly. Of course top chess players recognize obviously bad moves.

In this case though Kasparov was trying to defeat Deep Blue with an anti-computer style, he had a particular model in mind for how the computer would play and when it didnt, he thought it meant that the computer was more far-sighted than it actually was.

hasenj3• 14 years ago

> Of course top chess players recognize obviously bad moves.

I'm not talking about obviously bad moves.

I'm not trying to imply that Kasparov is a bad player either.

But why did he conclude the computer has seen a very complicated sequence that Kasparov himself can't even begin to see?

It's because of the nature of the game.

Remember, we're talking about a completely random move here ..

VMG• 14 years ago

It makes chess more interesting in my opinion

nchlswu• 14 years ago

this may be a bit pedantic, but does it really say much about /chess/ itself as a game, or the chess ...culture?

Ygg22• 14 years ago

No, it doesn't. What this episode tells us is that humans often have frequent false positives, when it comes to pattern matching. This is common in most animal, and is the part how we perceive the world. Our limbic, fast-acting system works like this, when it spots a pattern that matches some kind of known "threat" reacts to it quickly. This kind of pattern matching is flawed as evolution has optimized for numerous false positives over false negatives (e.g. the one time you mistake a bear for a tree is deadlier than when you confuse a rock with a poisonous snake). This kind of input is bad in cases where false negative are as bad as false positives.

This somewhat flawed system, supplies our rational system with said bad input. In other words, garbage in, garbage out. This would have happened regardless of game, as long as one opponent is human and under some pressure, he would make a faulty guess and make the same mistake. This happens in a variety of games, from Chess to Starcraft to Street Fighter. As long as game has some pattern matching, it will be affected. So I'm pretty sure it applies to Go as well.

When you move up the ladder in a game, you start understanding how opponent mind functions and you make certain optimizations. You don't want to mentally exert yourself in all matches so you pick up a routine, that doesn't task the brain much and use it to weed out the lesser opponents. From time to time someone will use a totally different pattern which is when you mentally turn yourself on and start analyzing their moves, to figure out their next move. The presumptions your mind makes can often be exploited by a totally new/random enemy which screws up your evaluation model. This explains why people new to game have that "begginer's luck" effect. They can't value moves right, so they use a completely foreign way to play. For example in Street Fighter you expect your opponent to attack you with his far range fireball, which are that character's best weapon, so your prepare to block, but instead the newbie mashes button and starts throwing you around like a ragdoll. Of course good players will spot the newbie and change their play accordingly, however it might take some time for that.

http://www.sirlin.net/ptw-book/the-invincible-and-the-beast....

http://www.sirlin.net/articles/yomi-layer-3-knowing-the-mind...

hasenj3• 14 years ago

> No, it doesn't. What this episode tells us is that humans often have frequent false positives, when it comes to pattern matching. This is common in most animal, and is the part how we perceive the world.

Yes but you must put this in context: we're talking about a professional here.

For example, a lot of people don't succeed at diet and exercise: they somehow give up or lose motivation. You can find all sorts of biological roots that explain this behavior, but it's not appropriate to apply this same reasoning to a top professional athlete.

In "Go", assuming that your opponent can see something that you can't see is one of the bad habits that gets beaten out of you as you become stronger (and if it doesn't, you'll continue to be a weak player).

It seems that this doesn't happen for chess players.

anthonyb2• 14 years ago

It wasn't imagined - check cube13's link for a good example of where this happened in a previous game: https://news.ycombinator.com/item?id=4583135

nicholassmith• 14 years ago

So we can add this to the incredibly small list of "it's not a bug it's a feature" where it's actually true.

JackpotDen• 14 years ago

There's an idea that richard garfield likes to bring up, which is that if a player plays random moves, they have a chance (a very small chance) of beating a grandmaster.

I wonder what would happen if you interjected very occasional random moves on purpose to extremely advanced chess AI. How often would it make a top player second guess themselves?

mcherm• 14 years ago

Essentially never, if the top player knew it was a possibility.

squirrel• 14 years ago

The game itself, replayable online: http://www.chessgames.com/perl/chessgame?gid=1070912

Tipzntrix• 14 years ago

Man, Kasparov has been salty about that loss for decades. This is probably the tenth article I've read about it. An interesting new theory though.

derekp7• 14 years ago

This story reminds me of an episode of the American TV show "Cheers", where the bar tender (Sam) was playing against an experienced player. However, since he wan't good at chess, he was cheating by having a computer play his moves, and having someone in another room give him directions over an earpiece. Inevitably, the computer crashed (or the earpiece failed, can't remember which), so he made a random move. This threw off his opponent, who over-analysed the situation, and ended up losing.

Now I'm wondering, which happened first -- that TV show episode, or the Kasparov game?

philodespotos• 14 years ago

Cheers ended in 1993. The first Kasparov v. Deep Blue match was in 1996.

wslh• 14 years ago

I just sent a LinkedIn InMail to Kasparov (0 connections on LinkedIn) trying to gain attention of this thread.

gxs• 14 years ago

This reminds me of when veteran professional poker players play complete novices. They often say that beating a brand new player is harder than beating a mediocre player, since a novice player will do things that make no sense seemingly randomly.

rograndom• 14 years ago

Or they try to do things that work in their "normal" games: bet sizing, giving off false tells, etc. that just go right over the head of the novice player.

There's a quote from probably Doyle Brunson or Amarillo Slim along the lines of "It's like trying to show a dog a magic trick"

How a random bug in Deep Blue may ultimately have led to Kasparov's defeat

Related Stories