A Gross Miscarriage of Justice in Computer Chess

January 6, 2012 6:20 AM

On December 4, 2005, the computer chess community was astonished by the initial release of a free, downloadable chess program named Rybka 1.0 Beta, which within days took a sizable lead on all then-existing chess program rankings, surpassing all commercial programs, including renowned engines Shredder, HIARCS, Fritz and Junior.

[snip]

In early 2011 sixteen chess programmers, many of whose programs were direct competitors of Rybka, signed a letter wherein they asserted that Rajlich copied programming code from another engine, Fruit, authored by Fabien Letouzey and released to the public in June 2005, about six months before Rybka 1.0 Beta.

A four part analysis of the International Computer Games Association decision. (full paper in pdf)

Next, an observer comments on a spectacular positional win over Deep Sjeng: The first part of Rybka’s win over Deep Sjeng from 2009 is played like Petrosian on steroids, while the second part is played like nothing I have ever seen in human chess. From my limited human standpoint it looks crazy as Rybka is sacrificing two pawns and allows black to get a strong pawn center apparently without getting much in return.

(note: quotes for description were pulled out of order)

posted by rider (47 comments total)

I was going to add for the uninitiated that Rybka is the 800 pound gorilla of chess software. As in "could give noogies to Kasparov until he cried for mama".

But on checking the latest rating chart, I see that its former dominance seems to have been successfully challenged by something called Houdini.
posted by Trurl at 6:31 AM on January 6 [1 favorite]

OK, Rybka is a little fishy.

But the program beats all other programs (except maybe this Houdini), including the programs whose code it uses?
posted by pracowity at 6:36 AM on January 6 [2 favorites]

Playing millions of games to gain aggregate insights is such an obvious approach to me - pure genetic programming stuff - that I wonder why it was ever considered a trade secret.
posted by Leon at 6:51 AM on January 6 [2 favorites]

Seriously? 'Borrowed code' is a huge scandal? I guess I'd just never known that "computer chess" was a whole sport, really.
posted by koeselitz at 7:04 AM on January 6 [1 favorite]

I have no idea if the first version of Rybka copied Fruit's code without attribution (which would be a GPL violation among other things), but I do think the rule as written is definitely problematic if using algorithms learned from other chess programs results in a complete banning. From the wording of the rules it seems that even if none of Fruit's code was used in the versions that actually competed in the tournaments, the fact that the Rajlich learned things from Letouzey's code would be enough for a ban, which to me as a programmer is completely insane. If you're writing a chess program, of course you're going to read through every piece of chess program code you can find for things you can use. And of course after years and years of people writing chess programs, the top chess programs are going to converge on the algorithms that work the best. The idea that someone could write a top level chess program completely from scratch without learning anything from anyone else is laughable. Rybka may have stolen ideas from Fruit, but every top level chess program today steals ideas from Rybka, just like Java stole ideas from Smalltalk, GNOME stole ideas from Windows, etc. Banning Rybka for something like this is like banning the next human world chess champion because he learned strategies from analyzing Kasparov's play.
posted by burnmp3s at 7:06 AM on January 6 [20 favorites]

(Meant to say – this is incredibly interesting; thanks, rider.)
posted by koeselitz at 7:06 AM on January 6

Nice game here of Rybka (White) vs. Houdini (that Trurl mentioned).

I'm no chess expert, but the commentator seems very impressed at how Houdini's algorithms are happy to sac pawns in order to empower its stronger pieces with greater attack area. Fun to watch.
posted by anthill at 7:14 AM on January 6 [5 favorites]

I don't think genetic programming has much to do with this, but I haven't read the full article. (And I probably won't, I don't really care enough about the scandal to plow through all that, and my free time is already being savaged by my online correspondence chess games).

It's worth mentioning, I suppose, that Chessbase sells a licensed version of Rybka, in addition to their own chess program, Fritz. It's not clear to me what their relationship is to the author of this defense of Rybka's programmer. Did they commission this study? Or are they just publishing links to an independent rebuttal? It may be that Rybka did get railroaded, but I think it's worth pointing out that Chessbase, indirectly, is a party to this controversy.
posted by thelonius at 7:15 AM on January 6 [1 favorite]

Chessbase, indirectly, is a party to this controversy

Excellent observation. Though Chessbase.com is only a news organization en passant, as it were. Advertorials for their products are regularly featured there. So that they have a direct financial interest in promulgating the view they've published here makes it more the rule than the exception.
posted by Trurl at 7:22 AM on January 6 [1 favorite]

> I guess I'd just never known that "computer chess" was a whole sport, really.

The whole idea of computer chess as an organized endeavor is one layer of abstraction too far for me. In terms of my level of understanding it might as well be wizards holding a spell-casting competition.
posted by The Card Cheat at 7:25 AM on January 6 [5 favorites]

Is this a dupe, or was the original deleted ? I swear I read this earlier on the blue.
posted by k5.user at 7:35 AM on January 6

IIRC, Chessbase didn't report on the June 29 decision at all, on their news page. I remember checking, thinking, wow, they have to at least MENTION this. They may have eventually published something sometime in July; I find it hard to believe that they really would have just ignored the scandal last summer.

Anyway, if anyone wants to go neck-deep in this stuff, here's a link to coverage of the Rybka ban from another chess site, with links to the technical documents that the 4-part rebuttal disputes:

ChessVibes article
posted by thelonius at 7:35 AM on January 6 [1 favorite]

The chart of p. 25 is just mind blowing. How many comments per day do the top 100 Metafilter users average? Now, imagine making all those comments on one issue, day after day. That's some serious switch to decaff Thorazine behavior right there.
posted by Kid Charlemagne at 7:50 AM on January 6

Yeah, because Chessbase SELLS a version of Rybka, it was really crappy they didn't report on any of this. Rybka was only free for awhile--once it started winning, they started selling it for $60+ depending on which version you bought.

Rybka's championships were anulled (and at least a few sponsors want their trophy AND money back).

These days the standard Houdini and Stockfish (open source) are better than standard Rybka. As far as I know, you can only download the early versions of Houdini for free, but Stockfish is still free.

While they're both poweful, Rybka and Fritch 13 both have a lot more functions to help with studying games & positions. From the "Grand-Prix" analysis of Chessbase-Rybka to the "Let's Check" feature of Fritz 13.
posted by whatgorilla at 7:55 AM on January 6 [2 favorites]

Ugh. Second "Stockfish" link goes to Houdini.
posted by whatgorilla at 7:58 AM on January 6

The chess world is too small to have an independent press, or an independent association for that matter. Nobody's impartial. Thus I am not surprised to read, on one hand, that the author of the reigning computer chess program has received a lifetime ban for cheating, and on the other hand, that a detailed defense of the railroading and manufactured evidence exists.

I don't trust anybody in this. Certainly not Chessbase, and I have skepticism of the ICGA too.

The only thing to do if you want to understand the decision is unfortunately to read through the evidence directly.
posted by cotterpin at 7:59 AM on January 6 [1 favorite]

All of these engines are strong enough to beat grandmasters almost all the time, so I don't see any reason to pay $50+ for the commercial ones.

I don't even play against computers at all anymore, it's just demoralizing. It just whips your spirit; you end up learning that if you appear to have any attack at all, there must be something drastically wrong with it. Like many players, I use them to analyze completed games, check the soundness of ideas, etc.
posted by thelonius at 8:13 AM on January 6 [6 favorites]

I was really hoping the big discovery would be that it was a human grandmaster hidden in a cabinet.
posted by rokusan at 8:15 AM on January 6 [15 favorites]

Here is the game being described in the quote below the fold of the FPP. Really neat stuff.
posted by grog at 8:21 AM on January 6

What is curious to me, as a computer scientist, is that I don't see any mention of an attempt to compare the structure of the Rybka binary to Fruit. In the absence of Rybka source code, that's the first thing I'd do to try to establish plagiarism. Granted, I don't really know the state of the art in obfuscation; maybe it's possible to definitively baffle that kind of analysis, but I expect it is possible to make a good guess about whether or not a binary has been run though obfuscation.

All of the analysis presented as evidence seems to be behavioral ("Rybka behaves like Fruit"), and is not really very compelling. But the faked Rybka code from the ICGA report (shown in part 4) utterly destroys the credibility of the ICGA. What a sham.
posted by qxntpqbbbqxl at 8:28 AM on January 6 [7 favorites]

I really couldn't follow much of that at all, skimming until near about the end the "We just put some code in there that would look like Fruit and call it Rybka" should have been the deathblow to the anti-Rybka case.
posted by Slackermagee at 8:43 AM on January 6

Actually, it was the use of identical variable names between Fruit and "Rybka" that got my haunches up. That stuff is compiled out immediately (this is very annoying).
posted by effugas at 8:54 AM on January 6

Actually, it was the use of identical variable names between Fruit and "Rybka" that got my haunches up. That stuff is compiled out immediately (this is very annoying)

It's actually worse than that. To explain it a little more simply for non programmers, the Rybka program and the Fruit program use something called Piece Square Tables or PSTs as part of their logic. The actual concept of using a PST was not invented by either programmer, it was an established method that had been around for years. The way these tables are used is that they are calculated ahead of time into big blocks of numbers, and during the game the program will refer to the numbers in the tables to find the specific value for a specific situation.

In the Fruit program, these tables were calculated as the program started up, so there was code for calculating them in the actual source code. For Rybka though, the tables were calculated ahead of time outside of the program, and the tables themselves were embedded in the program as just a big block of numbers. Even if the source code to the Rybka version being discussed was available, the code for calculating these values would not be present because the Rybka program does not need to do the calculations. The author of Rybka claims that he didn't even use the same programming language as Fruit and Rybka to calculate them, which is very plausible, he could have calculated them in Excel if he wanted to.

In the ICGA report, there are several side-by-side comparisons that show Fruit's code for calculating PST values next to extremely similar code labeled Rybka that calculate different PST values. Not only is the "Rybka" code not actually source code from Rybka, it's source code that could never exist in Rybka because those values were already calculated in advance. The copying of the extremely similar parts was done entirely by the person making the comparisons, there are many other ways to calculate the same values in any number of programming languages. It's more or less like finding out that someone calculated 2+2 and put 4 in their program, and accusing them of copying the code from your calculator program to do it, using the "proof" that if you plug 2 plus 2 into the calculator code it spits out 4.
posted by burnmp3s at 9:20 AM on January 6 [17 favorites]

burnmp3s,

So, outright fraud. Got it.
posted by effugas at 9:29 AM on January 6

Actually, it was the use of identical variable names between Fruit and "Rybka" that got my haunches up. That stuff is compiled out immediately (this is very annoying).

Yeah, regardless of what the facts actually are, from the outside it appears pretty clear that this is the act of people who have decided that Rybka's developer is or should be guilty (for reasons that are probably independent of much of the evidence they present), and have set out to convince others at any cost.
posted by advil at 10:12 AM on January 6 [1 favorite]

In one of the "evidence" documents they cite similarities in comment structure and placement, based on decompiled binaries!
posted by bonehead at 10:17 AM on January 6 [1 favorite]

Stockfish also has a dandy free iOS app, I've discovered.
posted by Trurl at 10:41 AM on January 6

thelonius: "I don't even play against computers at all anymore, it's just demoralizing."

I know what you mean. Is there an engine that is not necessarily the best, but has a more human-like style? Any suggestions appreciated.
posted by vanar sena at 12:02 PM on January 6

bonehead: Wait, the claims of "identical variable names" are talking about decompiler output??
posted by murphy slaw at 12:17 PM on January 6

The part of this story that caught my attention is this chart of program performance from part 2 of the series. The key thing here is how there's a new wave of innovation in late 2004. It's pretty much all attributable to the open source release of Fruit. It's not just that someone innovated, but they made that innovation open source and so a bunch of other developers could take those ideas and improve on them themselves.

In a nutshell, this is a graph of why open source is so great for innovation.

(Also could you imagine if computer chess were infected with patented algorithms? Oh god.)
posted by Nelson at 12:28 PM on January 6 [4 favorites]

The whole idea of computer chess as an organized endeavor is one layer of abstraction too far for me. In terms of my level of understanding it might as well be wizards holding a spell-casting competition.

We continue to calculate ever greater number of decimal places for pi - even though long ago the available knowledge far exceeded anything relevant to physical reality. Something in man always strives to squint a little further towards infinity.

But unlike pi, there may be an end to this exploration. Computers may someday "solve" chess into a force win for White. Or a force draw for Black. (At least I'm aware of no proof to the contrary.)

The game will lose some of its poetry that day. I'll miss it.
posted by Trurl at 1:12 PM on January 6

Computers may someday "solve" chess...

It's pretty easy to write a computer program that solves chess. Fortunately, computers aren't yet fast enough to run that program to completion, but if computer power continues to increase exponentially, it's only a matter of time. Then everybody will have to switch to Go.
posted by qxntpqbbbqxl at 1:41 PM on January 6

Interestingly Computer Go has gotten a whole lot better in the past few years. Zen19s is up to 5 dan on KGS and improving.
posted by Nelson at 1:48 PM on January 6 [1 favorite]

I MOVED A WHITE QUEEN THERE IN 1989 STOP COPYING MY MOVES
posted by obiwanwasabi at 2:51 PM on January 6

It's pretty easy to write a computer program that solves chess. Fortunately, computers aren't yet fast enough to run that program to completion, but if computer power continues to increase exponentially, it's only a matter of time.

There are literally not enough resources in the universe to solve the game of chess.
posted by dfan at 3:34 PM on January 6 [2 favorites]

dfan,

There aren't enough resources to precompute all possible games. There are enough resources, possibly, for a smart enough analysis of the game to always solve for a path to a game state that must be winnable. It is possible that this solution may even be from the initial state to a must-win state.

Solvers are crazy now. Our joke now is "just because it's NP-hard doesn't make it hard".
posted by effugas at 4:10 PM on January 6

There are literally not enough resources in the universe to solve the game of chess.

Yeah, by solve I mean "write a computer program that can play a perfect game of chess", not "enumerate the perfect move for all possible chessboards". You don't need much space to run a depth first search. Are you talking about the theoretical amount of computation the universe can perform before it dies a heat death?
posted by qxntpqbbbqxl at 4:49 PM on January 6

Playing millions of games to gain aggregate insights is such an obvious approach to me - pure genetic programming stuff - that I wonder why it was ever considered a trade secret.

Genetic programming wouldn't work very well. Depending on the level of abstractions, you'd have to play trillions (or possibly trillions of trillions of games), not millions to code a chess program from scratch.

If you think you can do better, why don't you try it and see how your results compare to the free stuff out there?
posted by delmoi at 4:50 PM on January 6

That was a difficult, and redundant, read. TLDR (it all.) Did the guy get all his shiny trophies back?
posted by Chuffy at 4:58 PM on January 6

it might as well be wizards holding a spell-casting competition.

Actually, more like wizards holding a golem, artificial construct or summoned creature fighting competition. Kind of like a fantasy-world BattleBots. Kind of makes me want to throw that in next time I run a D&D session.

There's actually a rich history of computer competition programs, going back to the days of Core War. And it's leaked over into the real world, manifesting in board games such as the awesome RoboRally, recently re-released by WOTC.
posted by formless at 5:52 PM on January 6

Oh yeah, and Nelson makes a wonderful point about the chart showing positive proof of the effects of open-source software and non-patent encumbered code on innovation in an industry. I'll need to remember that in the next thread on patents.
posted by formless at 5:56 PM on January 6

WIZARD BATTLE!!!!!!
posted by delmoi at 6:31 PM on January 6

Dr. Hyatt, the guy who posted the thousands of Usenet messages, was the pioneer in open source chess engines, with his free program Crafty.
posted by thelonius at 4:43 AM on January 8

Rebuttal by David Levy (president of the ICGA)
Rebuttal by Mark Watkins (one of the ICGA investigators)

Both are PDF files.
posted by dfan at 6:40 AM on January 8 [2 favorites]

Genetic programming wouldn't work very well. Depending on the level of abstractions, you'd have to play trillions (or possibly trillions of trillions of games), not millions to code a chess program from scratch.

For what it's worth I didn't literally mean to use GP or GA to evolve a chess program (although it would make a great undergrad project). I should have said that running a simulation many times and analysing the results in aggregate is a very common technique. Maybe chess programming is full of classic top-down AI people?
posted by Leon at 8:55 AM on January 8

Maybe chess programming is full of classic top-down AI people?

Chess programs got started during the 'classic' AI era, and I think most of them are made that way.
posted by delmoi at 12:15 AM on January 9

Computers may someday "solve" chess...

Assuming that this happens, what would be the implications for human enjoyment of the game? Would top-rated players be able to comprehend and memorize the solution, thus making world championships redundant, or would we just have separate categories for human and digital players? I'm guessing that very low-rated players like myself would still be able to enjoy a game -- i.e., chess wouldn't become as pointless as tic-tac-toe.
posted by Crane Shot at 6:51 PM on January 11