Did a bug in Deep Blue lead to Kasparov's defeat?

[Sean Evans]

Did a bug in Deep Blue lead to Kasparov's defeat?

[hyatt]

Where does that nonsense come from? Who would program a chess engine to choose a "random" move under some circumstance? Not me. Not Hsu. No idea where that might originate.

[syzygy]

Who would program a chess engine to choose a "random" move under some circumstance?

That's why they refer to it as a "bug". The move would probably not be generated on purpose by a random generator, but be the result e.g. of a 1-ply search or of whatever the move generator spits out.

I have no way of verifying whether the story is true or not, but bugs do happen.

[hyatt]

Who would program a chess engine to choose a "random" move under some circumstance?

That's why they refer to it as a "bug". The move would probably not be generated on purpose by a random generator, but be the result e.g. of a 1-ply search or of whatever the move generator spits out.

I have no way of verifying whether the story is true or not, but bugs do happen.

Such a bug in a program that had been playing for years? Suddenly spitting out a purely random move?

Possible? certainly. Probability? similar to flipping a coin, calling "edge", and winning.

Sounds like idle speculation, as I'd think something like that would certainly show up in Hsu's book...

[ernest]

Such a bug in a program that had been playing for years?

Well, apparently this guy (Nate Silver) is speaking about DB's move 44...Rd1 (strange indeed) in the game:

[Event "Kasparov v Deeper Blue"]
[Site "New York"]
[Date "1997.05.03"]
[Round "1"]
[White "Kasparov, Garry"]
[Black "Deep Blue"]
[Result "1-0"]
[ECO "A07"]
[PlyCount "91"]
[EventDate "1997.05.??"]

1. Nf3 d5 2. g3 Bg4 3. b3 Nd7 4. Bb2 e6 5. Bg2 Ngf6 6. O-O c6 7. d3 Bd6 8. Nbd2
O-O 9. h3 Bh5 10. e3 h6 11. Qe1 Qa5 12. a3 Bc7 13. Nh4 g5 14. Nhf3 e5 15. e4
Rfe8 16. Nh2 Qb6 17. Qc1 a5 18. Re1 Bd6 19. Ndf1 dxe4 20. dxe4 Bc5 21. Ne3 Rad8
22. Nhf1 g4 23. hxg4 Nxg4 24. f3 Nxe3 25. Nxe3 Be7 26. Kh1 Bg5 27. Re2 a4 28.
b4 f5 29. exf5 e4 30. f4 Bxe2 31. fxg5 Ne5 32. g6 Bf3 33. Bc3 Qb5 34. Qf1 Qxf1+
35. Rxf1 h5 36. Kg1 Kf8 37. Bh3 b5 38. Kf2 Kg7 39. g4 Kh6 40. Rg1 hxg4 41. Bxg4
Bxg4 42. Nxg4+ Nxg4+ 43. Rxg4 Rd5 44. f6 Rd1 45. g7 Kh7 46. f7 1-0

4r3/8/2p2PPk/1p1r4/pP2p1R1/P1B5/2P2K2/8 b - - 0 44

[hyatt]

I ran this on Crafty and it changed its mind quite frequently. Score keeps inching up for white. Rd1 might have been the best move DB saw since anything is losing pretty badly (worse than +3.5).

[ernest]

anything is losing pretty badly (worse than +3.5).

Agreed, but when using Houdini or Crafty 23.00, I find that ...Rd1 immediately gets +8 or more, while other Black moves (...Rg8) are "limited" to +4 or less.

[marcelk]

Who would program a chess engine to choose a "random" move under some circumstance?

That's why they refer to it as a "bug". The move would probably not be generated on purpose by a random generator, but be the result e.g. of a 1-ply search or of whatever the move generator spits out.

I have no way of verifying whether the story is true or not, but bugs do happen.

The story is not new. This Rd1 move, the bug that caused it and the resulting confusion in Kasparov's camp are all well-described in Hsu's 2002 book. In fact Hsu describes the bug as "causing it to play a random move". So that is where the "nonsense" comes from.

[BB+]

From the 2002 interview with Hsu (promoting his book, in some sense -- I don't have the book at hand, and can't find any relevant text on Google(tm) Books): http://www6.chessclub.com/resources/art ... bird2.html

SJLIM: ophir : it was described by Mr. M. Campbel that DB lost game 1 in 1997 becuase of a "random move" - what does that really mean?
CrazyBird: argh. it was lost to begin with. a bug terminates the game early and caused the kasparov camp to spent all night analyzing why.
CrazyBird: they reached the conclusion that it saw a very deep mate:).
SJLIM: thats hilarious =)
SJLIM: what kind of bug?
CrazyBird: it was something related to move selection, some data structure problem, i think.
SJLIM: I see.. moving along.. quickly.
CrazyBird: which caused the program to essentially play a random move.

And from page 149-50 of Newborn's book (Deep Blue: An AI Milestone):
On its 44th move, a devilish bug suddenly surfaced, causing a random, totally illogical move! Campbell later confided, The move was incredibly bad. Deep Blue's score dropped about 300 points, the equivalent of three pawns. The bug started showing up in 1996, early 1997. It showed in a game with Larry Christiansen, where Deep Blue gave away a pawn when it played 13 ... f5, though it was able to eventually draw the game. [See Game One between Deep Blue Junior and Larry Christiansen in Appendix I]. The bug was fixed then --- almost. It turned out that the bug could arise in five ways, and only four of the five ways had been eliminated; the fifth was overlooked and sure enough, it came up here! The logs confirmed the presence of the bug, and that evening Hoane worked to eliminate it.

According to Campbell, the move was of great consequence, because, Kasparov saw this move and asked his own team why Deep Blue made it. They didn't know. They looked at alternatives, and found they lost also. So they conjectured that Deep Blue had looked 30-40 levels ahead at the alternatives --- they were overestimating Deep Blue's talents here --- and saw that all the moves lost, and that it didn't matter what was played, so it played a random move. Now, of course, this wasn't the case at all, but it perhaps gave Kasparov a false impression about what Deep Blue could do. Campbell felt that this might have been a factor in the next game where, in the final position, Kasparov overestimated Deep Blue's strength.

[syzygy]

Sounds like idle speculation, as I'd think something like that would certainly show up in Hsu's book...

Say again?

First you take the story way too literally, as if the Deep Blue team put in a routine that under circumstances deliberately selects a random move, while a reasonable interpretation of the story would be that Deep Blue had a bug that when triggered resulted in an essentially random move selection (very different).

Then when this is pointed out, you can't simply accept that the story might not be "nonsense", so you backpedal slightly into the position that it is virtually impossible (a coin landing on its edge) that Deep Blue had a serious bug! Oh wow, how many engines are there that have no serious bug that only pops up once every hundred or thoussand games or so? Clearly your new position is absolutely untenable, and I'm sure you would never haven taken this position in the first place, if you had not started by declaring the story "nonsense". But you did start like that, so you have to cement yourself in...