Mig 
Greengard's ChessNinja.com

Log Jam: Deep Blue and Kasparov

| Permalink | 37 comments

In Part 1 of my March interview with Garry Kasparov, he repeated his well-known suspicions and accusations about human interference in the 1997 match with Deep Blue. He repeated his demands for evidence that DB was "real." This business as usual was fresher because of his retirement and the recent distribution of the movie "Game Over: Kasparov vs the Machine," which focuses on these suspicions.

The refrain "why don't they release the logs?" was a significant part of the conspiracy battle cry. Kasparov asked for them during the match (which would have been anti-competitive, at least for him to have access instead of his technical advisor or arbiters). This was reiterated right after the match, when IBM team leader CJ Tan said the logs would be published "in the near future."

That turned out to be years later, although the precise date isn't clear. The earliest reference I can find to the game and log page at the IBM site is May 1, 2000 in a Usenet post from Taiwan. For something of such apparent importance, it received astonishingly little attention. There are only a handful of links to the page and the logs, but it seems clear that they were available by May 1, 2000, almost exactly three years after the match. [It now seems that March 2, 2000 is the earliest date tracked. See below.]

Deep Blue designer Feng-Hsiung Hsu said in a 2002 interview on the ICC (coinciding with the release of his book), that "Kasparov received all the relevant log [sic] he asked for right after the match." (More on that in the NY Times here).

Yesterday Kasparov said he had not been not aware that the logs were available until I told him and that he is eager see them analyzed and the evaluations compared with those of Deep Junior and Deep Fritz. His ignorance of the logs' availability would seem improbable, except that I didn't know about them either, at least not in such a complete form. (Some segments were given to the NY Times a while back.) This is more than a little embarrassing because it would have been nice to go through this with him while he was here. I also feel stupid "breaking" five-year-old news.

More bizarre is that as far as I recall, no mention of the log availability is made in "Game Over." (Amusingly, I wasn't sent a review copy of the US DVD release. I'm in the film, but am not a member of the "Chess Journalists of America," whose members got review copies. From all I've ever been able to tell, the CJA exists to give itself awards (a comical 40 categories) and, we can now add, get the occasional free DVD.) They talked with members of the IBM team, so why didn't this come up? Didn't Benjamin or someone else tell them the logs were available online? It's either a glaring error or an intentional omission so as not to deflate the conspiratorial tone of the film. I'll ask the director and maybe Joel can chip in here or by email.

You can't say "everybody knows" they are available because it's clear that's not true. The release of the logs received very little coverage, as Google attests. Feng-Hsiung Hsu says he wouldn't read the Khodarkovsky book on the match, so it's not surprising Kasparov doesn't read Hsu's stuff. Still, this is rather much considering the film and the jihad Kasparov has waged.

I hope this will finally put the nail in the human interference coffin for Kasparov. IBM behaved badly, possibly even with intent to provoke Kasparov's paranoia. But we can't confuse sharp practice with OTB cheating. The human interference angle has been dead to me for years since today's programs emulate Deep Blue's play, even the moves that in 1997 were acclaimed as human-like. DB was simply five or six years ahead, hardly a surprise.

Of course if you think IBM cheated at chess, doctoring the logs would be a relatively minor charge. Let's hope it doesn't go that far. I'd still like to know when they were first released, why it took so long, and who finally authorized it. Have they ever been comprehensively analyzed?

37 Comments

Mig,

I'm in CJA, and have a copy at home, if you need it for any reason. :)

Heh. Win any awards this week? Perhaps a lifetime achievement? I have a few copies of the UK version, just too lazy to reset my DVD software region to go through it looking for log references.

The first of what I'm sure are many interesting things in the logs. One of Garry's examples about of the current programs' superiority is the rook endgame in game four. According to Benjamin, Deep Blue thought it was never in danger of losing. First human analysis and then computers showed White was lost.

Apparently Deep Blue suffered some sort of crash at exactly the move before Kasparov made the mistake that let it off the hook. (Move 43, with ..Kc4 or ..d4 instead of ..Rf1+?) The log shows DB predicting the inferior ..Rf1+ and then, for only the second time I can find in the logs other than at the end of a game, there comes a "stop" and reset language. Deep Blue Screen of Death?

The eval before that was -.40, but it must have been a bad crash because the log shows DB considering opening moves at move 43!

The movie was clearly allowing the Kasparov argument just to make itself more meaningful. Yo can't blame the filmmakers I suppose, and it was a very well made doc, but I wasn't convinced by any of GK's arguments about cheating. I know it's the one thing he struggles to deal with rationally - getting beaten - but he really should let this one lie. And we keep hearing it - he lost Game 6 because they cheated on Game 2 (although he held it together inbetween). Just as we now hear that Topalov's bad results in Melody Amber are PROOF that he is was riding his luck in Linares!

(*I don't consider myself a GK basher - especially by this blog's standards - but he gives his critics so much ammunition with every goddamn interview it does annoy me.)

It wasn't just GK in the film though - one particular sleazeball journalist was trying so damn hard to sound like he was in the X-Files it was embarrassing. (Not the tall bald bloke!!!) Still, it was a superb film for all that. I'm not suggesting that everyone involved in documentaries wants to break into Hollywood, but the director & editor if this piece deserve good projects. I wish them well.

Incidentally, I didn't notice it first time round, but if you pay attention during the rapidly edited finale, the filmmakers are putting the blame firmly at Karpov's door as the human interventionist.

I don't know much about the production history of the film, but I get the impression that it is 'Kasparov product' as opposed to a film he just featured in. It was certainly being sold that way in the UK with his recent book tour.

From my view, the only conceivable reason for a company like IBM, representing many billions on the Sotck Exchange, to allow itself to seem guilty by implication by destroying the evidence and then to compound the problem by remaining mum about the issue for so many years, is that they were doing something shameful. They probably had human assistance, they also had programming difficulties and Kasparov's suspicions were too much for them to handle. They were afraid of the negative publicity and were hoping for the issue to disappear by itself. Maybe the programmers were forced into this by some hot shot executive and the whole thing backfired...

Can someone explain to me what form the cheating was supposed to take? I do remember Garry complaining about a change in how the computer evaluated something (the value of a bishop, maybe?), but that's not cheating, any more than someone changing opening strategy is.

No, this was about direct input of moves on several occasions (two specifically mentioned). These moves were deemed by Kasparov as suspiciously un-computerlike.

Game 2: 37.Be4 is a move often sited by Kasparov as a suspicous move. Everyone extpect Qb6 at some point to snatch a pawn. Instead DB went positional on Kasparov and surprised him. Indeed, at the time no program could reproduce it. However, several current commercial programs find this "suspicous" human-like move after a reasonable search period. You can finds lots on it with the google search--->
"deep blue" 37.Be4 human

Move 36.axb5, also instead of 36.Qb6, is tougher for computers, for similar reasons. Few of today's programs today prefer it, but it's definitely near the horizon. They think they can play 36.Qb6 Rd8 37.Be4, with the same idea as Deep Blue. But Black can play 36...Qe7! with defensive chances. But it's close enough in evaluation for it to be clear that comps are capable of the Be4 idea and the move.

I always wondered why Kasparov kept on complaining that he didn't have access to the logs. I'd read about them years ago on the Chess-Computer Club message board. I'd love to see him go through them thoroughly and hear his thoughts.

It's been up since at least March 2, 2000. See the Internet Archive:

http://web.archive.org/web/*/http://www.research.ibm.com/deepblue/watch/html/c.html

Feng-Hsiung Hsu even mentions this in his book (see Appendix C: Further Reading).

There are numerous posts about this on the Computer-Chess Club message board:

http://talkchess.com

They have a transcript of an interview that Hsu gave in October 2002 where he mentions that the entire logs had been posted on IBM's site several years before. See the bottom of the transcript at:

http://chessprogramming.org/cccsearch/ccc.php?art_id=260244

If you poke around at the postings you'll see them discussing how to interpret the logs. There's a lot of flaming going on where various programmers argue that Deep Blue is weaker than today's programs. Look out for the posts by Robert Hyatt (he's the guy who wrote the chess programs Cray Blitz and Crafty). They tend to be the most informative.

The idea that Kasparov didn't know about them until know is laughable. Does he want us to believe that, when they have been discussed for years and referenced to everywhere? Even I knew about them and I'm not even particularly interested in the case. I just read Hsu's book.

Although if he actually didn't know about them, what would that tell us about him?

"until now"

Laughable? Where is this "everywhere" they are referenced? You think Kasparov read Hsu's book or spends his time in computer chess message boards? As I said, *I* didn't know about them, and I read Hsu's book two days after it came out. (I remember reading it on my way to Bahrain for Kramnik-Deep Fritz.) As I said in the post, they received almost no publicity outside of computer chess circles. You can tell this just by googling the links. I definitely should have known about them, and am embarrassed about that. But if I heard word of them at the time I certainly didn't follow it up because I'd never seen them before last week.

I used to spend some time at the CCC, mostly when I was researching various comp chess articles. I used to work closely with Shay Bushinsky (half of the Junior team) and of course know the Fritz/ChessBase guys very well. If anyone had made a big deal out of these logs, I think I would have known about it.

It's bizarre to say that Kasparov knew about them and would say they didn't exist when it's easy to demonstrate they do. It makes him look silly, as it will when I run Part 2 of the interview pointing it out. (I also look dumb, equally deservingly. I hadn't really expected so much on Deep Blue and hadn't prepared it for our interview time.)

Inside computer chess circles, those logs are indeed well known since many years. For example, they were referenced to in many endless discussions, if up-to-date pc computers are stronger or still not as strong as D.B. was. When you simply enter "kasparov deep blue" into Google, IBM's match page is the top search hit. I compile a list with the most important computer chess links for a german magazine: The link to the logs is in the CSS Netguide since three or more years. See "Lesestoff" category.

http://www.computerschach.com/index.php?option=com_bookmarks&Itemid=51
(new layout, but it was already there among the old pages too)

It's all history anyway. - Nowadays, when "cheating" is talked referring to computer chess and online chess, it is meant that a computer chess engine has helped a human player, not vice versa...

Hello Mark. I gave a Q&A at the CSS site a few years ago, during the Kasparov-Deep Fritz match, I think. I think I annoyed the faithful by saying that when it came to playing humans, all the top engines were about the same!

What was interesting to me is that when you google "deep blue kasparov logs" you DON'T get that IBM log page. When you search for a link to it, you get one or two that aren't from the IBM site itself. But this is partially a search engine discrepancy and a reflection of how most message boards aren't indexed for Google and other search engines.

In a few weeks this thread will probably be the top link!

Hi again :) It's just bad luck with the search words: "logs" does not appear on IBM's page, "log" does...

I remember your fine Q&A, Feb. 2003. Unfortunately it seems that the postings are too old to be accessible in the online archives, still.

Since the days of Deep Blue and in recent years also, big progress has been made again in terms of strength and style in computerchess. I have read several quotes which seem to indicate that there are considerable differences between chess programs visible now - even from a Grandmaster's viewpoint.

What are some of the best examples of moves contemporary chess programs play that are demonstrably superior to Deep Blue moves?

@JT: This is difficult to answer, because Deep Blue is not here anymore for comparison. So, any very difficult move of a contemporary program (i.e. a very deep winning sacrifice) is a candidate to demonstrate that... The famous knight sacrifice Nxf7 in one of the Bahrain games Kramnik - Fritz would make a good example too - but that was played by the human, not by the computer. :-)

Mig: No, not everyone knew about them, but if you had an interest above average in the case, you most probably did. That Kasparov of all people, with his direct role in it and with all his contacts, never got told until now, is maybe not impossible but at least to me extremely implausible.

But if he somehow didn't know it just shows that he never even bothered to do a quick and easy search and still kept accusing them.
----

"It's just bad luck with the search words: "logs" does not appear on IBM's page, "log" does..."

Yes.
Google for
"Deep Blue" log
and the first hit is http://www.research.ibm.com/deepblue/watch/html/c.html

Google for
IBM chess log
and you get the same, etc.

Although just google for the simple
"Deep Blue"
and the first hit is the match site http://www.research.ibm.com/deepblue/ too.

Surely - if contemporary programs really are stronger than Deep Blue was as it is often claimed - there are at least a few examples of moves contemporary programs produce when you let them analyze the six 1997 games that are superior to the moves Deep Blue actually played. So I have to repeat my question: what are some of the best examples of these moves that demonstrate this superiority?

so, the excuse that u cant google for it is wrong.
for me the situation is clear:

1. kasparov indeed didnt know about the log-files BUT he also DID NOT really searched for it. he just reapeat that log-thingy in his endless intervies over and over again.

2. the most people just believe what kasparov says without verifying it. if kaspy says the logs are not available - then they are not availabe for most interviewers.

==> if someone really wanted to see the log (not including me, i just dont care) he could have done so bye phoning/mailing to IBM or using google&friends.

JT - I'm not sure there are "superior moves." However, you can say in general that most new programs will play moves once totally shunned by Comps. They will sometimes play exchange sacrifices, sac pawns or pass up material for positional reasons now. Occasionally you will even see a piece sac for attacking chances without a concrete win on the horizon. In short, all the ideas no computer would even consider in 1997 when Deep Blue did, is now common fare for the best dozen or so programs. In 1997 it was grounds to suspect cheating. Now we know DB was just way ahead of its time.

The following is based on my memory of the "public face" of the match at the time. I'll have to look at the Hsu's book to see if it changes my perspective. That said:

What really bothers me about the K-DB match has nothing to do with Mr. Kasparov. It is the bait-and-switch pulled by the DB team: They played the front end as a research project in computer science with an interesting "test" and then as soon as they actually won they dismantled the machine and scuttled silently away. Three years to produce logs is just further insult.

One of my HUGE soap box issues is the misuse and abuse of scientific credibility, a practice that is trivial to get away with under these conditions. IBM went from open research project to a mode of closed, secretive corporate cash-in, and as far as I'm concerned this debased IBM and completely invalidated the match. I'm sure they cried all the way to the bank.

The existence and publishing of the logs was very well known by Frederic Friedel, who has been coaching Kasparov on computer chess for the last 10 years (and more...) and created the Chessbase company and the German computer chess magazine CSS.

The thing that is really surprising to me is that the person who made the Deep Blue Kasparov movie did not do any research to find out if the logs were posted on the internet. That was the first comment out of my mouth when I got out of the movie theatre when I saw the movie. I watched it in Denver with some fellow chess players, who did not know as much about the Deep Blue match as I did. That is really sloppy research. Maybe he did know this, but realized it made the movie a moot point. I remembered reading in Hsu's book that they were posted on the internet.

BTW I also got a free advance copy as a former CJA member (I was the editor of the Colorado Chess Informant magazine) which was a nice surprise. I was disappointed to see that there were no "extras" on the DVD at all. Just the movie, and that is it. It is still a good movie for any chess fan.

Cheers,
Tim

One question still unanswared : why Kasparov played this bad line of the Caro-Kahn in the 6th game in New-york ? Mistake ? Mismatch ? or the team judge Kasparov could beat a computer in this bad line ?

Mig, could you ask to Garry, please ?

As for myself not having attempted to verify the presence of the logs (too lazy) nor the chess acumen to validate specific moves (with or without a chess engine like Fritz), the movie did point out one other suspicious move in Game 2 of the match, and that was DB 44. Kf1 move, which the producers claimed presented GK a chance at a straightforward perpetual check if he went looking for it (which he did not, since a computer would not be expected to play such an obviously incorrect move). Is this move as suspicious as the movie claims?

@Terry: 44.Kf1 isn't simply "incorrect." Acoording to an analysis J.Nunn has given, the perpertual sequence could have started not earlier than 10 (!) plies later, with 48...Qc1+. And it is not a simple perpetual with immediate repetition, but White's king could walk around over a number of squares from e1 to h2, so it would take many more moves to calculate before a computer can see that repetition is inavoidable. It is absolutely nothing special when a comp misses such a deep thing, even for a machine like Deep Blue II was.

Are there some recent examples of programs missing perpetuals of similar depth?

@acirce: You can use the original position, to test current chess engines. Here is a result of Shredder 9.SE (which performs identical to the normal Shredder 9, latest top Chessbase engine, in that position):

Deep Blue - Kasparov,G, New York man vs machine 1997
R7/1r3kp1/1qQb1p1p/1p1PpP2/1Pp1B3/2P4P/6P1/6K1 w - - 0 1

Analysis by Shredder 9 SE (1.5 GHz, 128 MB hash tables):

44.Qxb6
² (0.41) Depth: 1/2 00:00:00
² (0.41) Depth: 1/2 00:00:00
44.Kh1
² (0.42) Depth: 1/3 00:00:00
² (0.42) Depth: 1/3 00:00:00
(...)
44.Kf1 Rb8 45.Ra6 Qe3 46.Qxd6 Re8 47.h4 h5 48.Bf3 Qc1+ 49.Kf2 Qd2+ 50.Be2 Qf4+ 51.Kg1 Qe3+ 52.Kh2 Qf4+ 53.Kh3 Qxf5+ 54.Kh2 Qf4+ 55.Kg1 Qe3+ 56.Kf1 Qc1+
± (1.09) Depth: 8/19 00:00:00 70kN
+- (1.57) Depth: 17/52 00:04:04 108795kN
44.Kh1 Rb8 45.Ra6 Qxc6 46.dxc6 Kf8 47.Ra7 Rc8 48.Rb7 Rc7 49.Rxb5 Ra7 50.g4 Ke8 51.Rd5 Ke7 52.b5
+- (1.58) Depth: 17/52 00:04:24 118209kN
+- (2.15) Depth: 18/46 00:04:45 128716kN

As we see, S9.SE will play Kf1 too up to 4 minutes on that machine, later prefers Kh1. But it returns +1.57 as the last eval (not 0.00) for Kf1, so I guess it hasn't seen the draw either but changes it's mind for other reasons. Anyway, up to a Shredder 9 ply depth of 17 it wants to play the same move like Deep Blue II did.

Right!

Thanks, but isn't 44.Kf1 still better or winning, just much trickier? I got the impression the real blunder was 45.Ra6. How long does it take for Shredder to realize that 45.Ra6 only draws?

When I get all this correctly, Kf1(?) allows Black to draw.

Ok, I let run another analysis in the position AFTER 44.Kf1 Rb8 45.Ra6. The evaluation drops to +0.39 after 4:52, and later to +0.20 after 7:16 at ply 17.

Deep Blue - Kasparov,G, New York man vs machine 1997
1r6/5kp1/RqQb1p1p/1p1PpP2/1Pp1B3/2P4P/6P1/5K2 b - - 0 1

Analysis by Shredder 9 SE:

45...Qxc6 46.dxc6 Rc8 47.Ra5 Ke7 48.Rxb5 h5 49.Bd5
² (0.60) Depth: 1/2 00:00:00
+- (2.50) Depth: 14/28 00:00:06 3073kN
45...Qe3 46.Qxd6
+- (2.49) Depth: 14/42 00:00:19 8724kN
² (0.70) Depth: 19/54 00:13:26 367275kN

No 0.00 evaluation after 15 minutes yet. - Please keep in mind that this analysis is 3 plies later compared to the position where Deep Blue II moved the discussed move 44.Kf1.

It is possible that other engines see the draw quicker here; I didn't try more for now... Btw. the Kf1 variant in my previous posting already contains a repetition, just no 0.00 eval yet.

Somehow I wonder if Garry Kasparov reads these comments :-) In that case: Hello Champion! You see, that great match is still inspiring chess fans around the world. The Man versus Machine battle continues and is not decided yet.

Kasparov's and Mig's not knowing is a good lesson. We always suppose that even if we mortals don't, at least people of power(influence/brains/contacts/money...) know their stuff, know what they are meant or supposed to know. But who can blame them, it happens all the time. You are not told because those people who could tell you think you already know, and you don't ask the right specific question because you think if there's interesting stuff you would be told anyway.
This world is about flawed information networks in this age of information. It happens all the time in government, science, everywhere.

It does seem highly unlikely that GK didn't know of the publication of these logs when you consider how many contacts in the chess world he most certainly has. Perhaps he realized that once they were published the results could disprove his long held beliefs about the contest and that the only way to ASSURE that he could continue to convince himself of intervention would be to not examine them.

Of course he could "take lemons and make lemonade" by analyzing them for Part 1 of his next series: Garry Kasparov on My Great Successors. :)

Mig, could you ask Garry who was the actor he refers to toward the end of the film "Game Over: Kasparov and the Machine"? He mentions in the film that back in 1997 he got on the elevator of the hotel he stayed in for the match and telling the unnamed actor that he was seeking a rematch with IBM and Deep Blue. Garry then said that the actor said then that they would never give him a rematch. Just curious...thanks!

I think there are too many indicators to say that IBM were cheating among them:
- Kasparov was convinced certain moves couldn't possibly have been played by a computer. Conclusion: A human must have played them.

-IBM reserved the right to change code during play, this allowed grandmasters to change flaws in deep blues play that they had spotted during other matches.

- IBM retired Deep Blue without a rematch. Conclusion: IBM had something to hide.

Theres no reason to look guilty if your not?

I though i would also take this chance to mention the related forum: http://www.ai-stockmarketforum.com Its an Artificial Intelligence Forum with emphasis on neural networks and the stock market. Hopefully it might attract people that are already signed up to some AI forecasters, so we can all have a good idea of how accurate they are and what they are currently predicting.

Jonas, of course changing strategy inbetween games by grandmasters is cheating. Thats not a program. Thats a bunch of players going versus Kasparov.

Why hide the computer in another room during the match? Why not put the computer on stage with Kasparov while they play?

Because they were cheating. That's why.

Twitter Updates

    Follow me on Twitter

     

    Archives

    About this Entry

    This page contains a single entry by Mig published on April 9, 2005 11:49 PM.

    Friday Cat Blogging 2 was the previous entry in this blog.

    Anand Wins 2004 Oscar is the next entry in this blog.

    Find recent content on the main index or look in the archives to find all content.