How a random bug in Deep Blue may ultimately have led to Kasparov's defeat(washingtonpost.com)
washingtonpost.com
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/
14 comments
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.
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.
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
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
It was a little different from what you recall. 37. Be4 (instead of 37. Qb6) is the move that really made Garry suspect human intervention. Be4 is a much more positional move than Qb6.
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.)
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.)
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
http://www.chessbase.com/columns/column.asp?pid=146
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.
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.
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.
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.
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.
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?
Now I'm wondering, which happened first -- that TV show episode, or the Kasparov game?
Cheers ended in 1993. The first Kasparov v. Deep Blue match was in 1996.
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.
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".
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.
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.
contrast: Buridan's Ass http://en.wikipedia.org/wiki/Buridan%27s_ass
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.
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.
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"
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"
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.
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.
When I follow your links I see the Penguin edition for $14.99 and the other edition "not available".
Might be an Amazon territory thing, then. I'm in Europe.
I'm in the UK and I get "pricing information unavailable) for both of them.
EDIT: Using UK amazon I get this (http://www.amazon.co.uk/The-Signal-Noise-Prediction-ebook/dp...) which shows £14.99 for me.
This is what pisses me off about ebooks. I understand that they can't be dirt cheap because you still need editors and proofreaders and setters and authors, and all those people need paying, but $15 = £9. (£15 = $24).
Amazon UK charges a 20% sales tax (VAT) for UK ebooks. (I have no idea if Amazon actually pay their tax or if they're the type of company using vigorous avoidance schemes.)
EDIT: Using UK amazon I get this (http://www.amazon.co.uk/The-Signal-Noise-Prediction-ebook/dp...) which shows £14.99 for me.
This is what pisses me off about ebooks. I understand that they can't be dirt cheap because you still need editors and proofreaders and setters and authors, and all those people need paying, but $15 = £9. (£15 = $24).
Amazon UK charges a 20% sales tax (VAT) for UK ebooks. (I have no idea if Amazon actually pay their tax or if they're the type of company using vigorous avoidance schemes.)
I have no idea if Amazon actually pay their tax or if they're the type of company using vigorous avoidance schemes.
My understanding is that for eBooks and other digital downloads, they do. They get around VAT for DVDs and similar items by subbing out to companies on the Channel Islands, which are not in the EU VAT zone, and shipments below a certain value are not subject to import VAT. This is why if you buy 10 DVDs on Amazon, you get 10 distinct shipments and invoices (and your bank might block your credit card because of 10 separate transactions happening simultaneously… I speak from experience).
As far as I know, it would be highly illegal for them to charge VAT and not actually pass it on to HMRC.
My understanding is that for eBooks and other digital downloads, they do. They get around VAT for DVDs and similar items by subbing out to companies on the Channel Islands, which are not in the EU VAT zone, and shipments below a certain value are not subject to import VAT. This is why if you buy 10 DVDs on Amazon, you get 10 distinct shipments and invoices (and your bank might block your credit card because of 10 separate transactions happening simultaneously… I speak from experience).
As far as I know, it would be highly illegal for them to charge VAT and not actually pass it on to HMRC.
The game itself, replayable online: http://www.chessgames.com/perl/chessgame?gid=1070912
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?
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?
Essentially never, if the top player knew it was a possibility.
> 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.
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.
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.
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.
> 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 ..
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 ..
But why did he conclude the computer has seen a very complicated sequence that Kasparov himself can't even begin to see?
The reason is rather obvious, IMO. Kasparov assumed, with good reason, that a computer is not likely to make tactical mistake. Especially in an end game the computer can see x moves deep perfectly. Computers historically are far weaker strategically -- doing things like creating good pawn structures.
So when Kasparov saw a move that appeared to be a tactical flaw his first belief wasn't, "Oh, must be a bug in the program, that was a random move." He thought, "There's an attack vector here I'm not familiar with."
It would be like sitting with John Carmack in a coding session and suddenly he deletes a function that seems like it would be useful to you. Your first thought would be, "Oh, John must have realized this function isn't useful. He's smarter than me. I just don't know the whole story." You likely won't think, "Must be a bug in John's brain that on occassion he will randomly delete a function."
The reason is rather obvious, IMO. Kasparov assumed, with good reason, that a computer is not likely to make tactical mistake. Especially in an end game the computer can see x moves deep perfectly. Computers historically are far weaker strategically -- doing things like creating good pawn structures.
So when Kasparov saw a move that appeared to be a tactical flaw his first belief wasn't, "Oh, must be a bug in the program, that was a random move." He thought, "There's an attack vector here I'm not familiar with."
It would be like sitting with John Carmack in a coding session and suddenly he deletes a function that seems like it would be useful to you. Your first thought would be, "Oh, John must have realized this function isn't useful. He's smarter than me. I just don't know the whole story." You likely won't think, "Must be a bug in John's brain that on occassion he will randomly delete a function."
The imagery of pair programming with Carmack was just too rich. Thank you for the laughs, mate.
So what you're saying is that, because Kasparov assumed the move was anticipated further than he could see, chess's "nature" is inferior to go, because in go–you implỵ–this wouldn't have happened.
Please be more clear with what you're saying.
Please be more clear with what you're saying.
No, according to this theory, it is because Deep Blue has a completely alien mind, and of the nigh-impossible to count ways in which that alien mind could work, it behaved in one of the many ways that Kasparov failed to consider.
Now, it might about the game if complete randomness is a valid strategy in Go.
Now, it might about the game if complete randomness is a valid strategy in Go.
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...
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...
> 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.
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.
What's funny is that you make the same mistake you are mocking: assuming that Go players are so close to perfect that they could never make a mistake.
Unless that professional athlete has been replaced by a machine, the same bio-logic remains. All humans are error prone. This isn't something you can remove with practice. It's built in so to speak.
What you talk about in Go is probably more in line with dispelling the "Fear aura" that happens on higher level.
What you talk about in Go is probably more in line with dispelling the "Fear aura" that happens on higher level.
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
It makes chess more interesting in my opinion
this may be a bit pedantic, but does it really say much about /chess/ itself as a game, or the chess ...culture?
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.
I just sent a LinkedIn InMail to Kasparov (0 connections on LinkedIn) trying to gain attention of this thread.
"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.
and that is how we humans come undone: we worry too much.
Except that this exact situation had happened in earlier games - see cube13's link: https://news.ycombinator.com/item?id=4583135
The pattern-recognition engine in the human brain is overcranked.
44...Rd1
http://www.youtube.com/watch?v=8guNB96rVgw
See 3:10. Deep Blue resigned at move 45.
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/...