A Look Back at Deeper Blue vs. Kasparov, 1997/Game 2

Remember the second match between Deep(er) Blue and Garry Kasparov? This is the one where computers supposedly proved their superiority to human beings in chess. Kasparov had defeated its predecessor the year before by a relatively comfortable 4-2 score, but the rematch in 1997 went differently. Kasparov opened with a comfortable win, but then lost game 2 in what turned out to be controversial style, drew the next three games (though coming close to victory in games 4 and 5), but then had a complete breakdown in the last game, getting crushed in just 19 moves. Thus Kasparov lost the match 3.5-2.5, and the popular media widely broadcast that this was the end of humanity's reign over the royal game. This was almost surely false, but like the old joke goes, we're just haggling over the price; there's absolutely no doubt at this point that decent programs running on decent home computers are far stronger than even the best humans on their best day.

But back to the match. Game 2 was a huge turning point, and not just because the computer won. Kasparov was playing the Closed Ruy - not exactly one of his main openings with the black pieces - and was getting impressively outplayed. A first move that shook up Kasparov was 37.Be4. To human eyes, it's really obvious. Black has no counterplay anywhere, but would if he could play ...e4. Prevent it, and the world is White's oyster. The problem was that 37.Qb6 seems like a simple win of material. The standard view of computers was that they would take free material in all but the most obvious cases where doing so would be wrong, but here it didn't.

But if that bothered Kasparov a bit after the game, that was nothing compared with what happened later. The computer apparently continued rolling along with its positional masterpiece, and when Deep Blue played 45.Ra6 Kasparov threw in the towel. Anyway, analysis later that night seemed to show that in the final position Kasparov missed a draw with 45...Qe3, with an inevitable perpetual check. As the line wasn't even too terribly long, especially for a computer calculating 300 million positions per second, it really seemed to Kasparov that the hand of human intervention was at work. If 37.Be4 was the sort of move where typically human judgment is better than that of a materialistic computer's, then 44.Kf1 is a moment where human judgment falls short relative to the computer's. The engine can work things out to the bloody end; humans can't.

And yet...Deep Blue didn't. How was this possible? After and even during the match, Kasparov requested - or rather, demanded - the logs displaying the computer's evaluation. (Unless I'm badly mistaken, the Deep Blue team claims that they were given shortly after the match, as promised (and even published publicly), but for some reason I haven't been able to ascertain Kasparov continued to insist on their release.) Logs or no logs, it still seemed surprising that Deep Blue missed the perpetual.

But did it? There has been a lot of analysis of the ending since then, and if anything has become clear it's that if there is a draw, it isn't a trivial one. Whether it's a draw at all is an interesting question in its own right, but it's a very different issue from that of the alleged perpetual check. Also, importantly, this non-perpetual line is also relatively obvious for the computer; that is, it's plausible and well within its search horizon. It's clear that White - Deep Blue - is better in the resulting position, but this doesn't settle all the doubts either.

Did Deep Blue spot the perpetual check variations? IF it did, then it would have had to assess the non-perpetual variations as better for it than the endgame after 44.Kh1 Rb8 45.Qc6 Qxc6 46.dxc6. Contemporary engines prefer 44.Kh1, but did Deep Blue?

I've culled material from various Web sources: Ken Regan recently addressed the topic, Wikipedia has a decent introductory survey on the issue, and there are various analytical suggestions in the thread devoted to the game on ChessGames.com. For a historical look back readers may wish a look at this ChessBase article. Finally, I've amassed the analysis from the listed sites and added some of my own here, which you can replay and download. Doubtless there are mistakes in my analysis - I ran it on an older computer, for one thing - so I hope that those of you with access to souped-up hardware will find some improvements.

Regan on Draws and IPRs in the Anand-Gelfand Match

(And more.) The blog's favorite computer scientist with an IM title, Ken Regan, offers some reflections on draws in relation to the world championship match and in comparison with computer chess, in this recent blog post. As usual with his work - when it's accessible to laypeople (and in this case, it is), it's worth your time.

In Defense of Rajlich and Rybka

In early 2011, Vasik Rajlich was accused by the International Computer Games Association (ICGA) of plagiarism in writing his famous chess program Rybka, he was stripped of the world championship titles won with Rybka from 2007 to 2010, and banned for life from ICGA events. (Other than that, I think they liked him.)

It has been quite a while now, but there's a new and vigorous defense of Rajlich by one Dr. Søren Riis against what the author considers ICGA overreach. Two parts are out now (there's a third part coming soon), and they can be read here and here. He makes some interesting points, and it's good that Rajlich has someone defending him.

Thoughts?

Rybka Disqualified and Banned from Computer World Championships

Some time ago I mentioned the accusations that Vas Rajlich, Rybka's programmer, had based his program on the chess engine "Fruit". Since then the International Computer Games Association (ICGA) has investigated the claims, and concluded in a 5-0 decision that Rajlich was guilty not only of improperly taking code from Fruit but from Crafty as well. They write that

We are convinced that the evidence against Vasik Rajlich is both overwhelming in its volume and beyond reasonable question in its nature. Vasik Rajlich is guilty of plagiarizing the programs Crafty and Fruit, and has violated the ICGA’s tournament rules with respect to the World Computer Chess Championships in the years 2006, 2007, 2008, 2009 and 2010.

As a result, Rajlich is banned for life from the World Computer Chess Championship and all other ICGA events, and Rybka's championships in 2007-2010 are vacated, along with the Rybka predecessors's =2nd finish in 2006. Strong punishment, but appropriate if they are right about the evidence.

Much more, here.

TCEC Season 3 is Underway

For fans of computer-computer matches, the third season of Martin Thoresen's TCEC (Thoresen Chess Engines Competition) is underway. Information on how this season's competition is arranged is here, while the live broadcast (and a list of the participating computers, their ratings and their scores) is here.

Rybka vs. Houdini

For those who like to follow computer vs. computer matches, Rybka and Houdini will have a match to close the second season of engine competitions on Martin Thoresen's TCEC website. The fun starts Tuesday at 14:00 Central European Time.

The Rybka Controversy in the Mainstream Media

At least the mainstream German media. There's a report on the Rybka controversies (Fruit-to-Rybka, and Rybka-to-Ippolit-to-Houdini) in Der Spiegel (in German, but you can see what Google Translate has done it with it, here). Nothing new, really, but as so often happens chess generally makes the news in the West only after something strange, scandalous or salacious has occurred.

An Open Letter from Programmers on the Rybka-Fruit Issue

You can find it here, and it's not good news for Vas Rajlich and the Rybka side. There are some big names among the signatories (maybe they're all big names, but even I as an outsider to that community recognize some of the names), and I doubt that they can all be dismissed on the grounds of professional jealousy or something like that. Nevertheless, it must be emphasized that this letter does not constitute legal proof. All the same, I wonder: what's the best program out there that doesn't have some sort of direct or indirect taint?

David Levy on Cloned Chess Engines

Here. Levy condemns the practice, takes an inconclusive look at some of the controversies around Rybka, and then calls for help in setting up a forum to investigate claims of cloning.

A Look at Rybka 4 - Houdini 1.5a, Game 1

A while ago I reported that the free program Houdini 1.5a defeated the king of the commercial programs, Rybka 4, by a 23.5-16.5 score in a recent match. Many people, both on my blog and elsewhere, were especially impressed by Houdini's play in the first game of that match, and I can't blame them! Houdini sacrificed three pawns for play, and the end result was an overwhelming initiative. You can have a look at the game, with my comments, here.