World's Best Chess Engine Outlawed and Disqualified

An anonymous reader writes "Rybka, the winner of the last four World Computer Chess Championships, has been found guilty by a panel of 34 chess engine programmers of plagiarizing two open-source chess engines: Crafty and Fruit. The governing body of the WCCC, the International Computer Games Association, is even demanding that Rybka's author — the international chess master and MIT graduate Vasik Rajlich — returns the trophies and prize money that he fraudulently won. Rybka will no longer be allowed to compete in the World Championships, and the ICGA is asking other tournaments around the world to do the same."

Comments

The obvious question

[elrous0]

If he was just ripping off two other engines, why did his win?

Sounds like he at least made improvements to them, and isn't that what open source is supposed to be all about? In fact, the article even acknowledges "ICGA isn’t even disqualifying Rybka because it copies Fruit — rather, it’s simply upset that Rajlich claims his engine is original, and refuses to give credit where it’s due." Okay, so maybe he should have given the other coders credit, but why should that disqualify him from winning? He still won. He didn't cheat. He didn't steal the code from the other engines (it was open source). His biggest offense is denying the other coders credit.

I think he should have to share the prize with the other coders (since they contributed code to the final product). But it still doesn't take away from the fact that his fork won. It doesn't justify taking away the win, as if he had cheated. His engine is still the best, open source code and all.

And, nothing against FOSS, but why on earth would you even release code designed for competition as open source, BTW? Aren't you essentially unzipping your fly and telling you competitors all your secrets? Couldn't releasing the source code wait until after the software was "retired" from competition?

Re:The obvious question

[h4rr4r]

Because he committed plagiarism, plain and simple.

Re:The obvious question

[Un pobre guey]

He didn't steal the code from the other engines (it was open source).

If he refused to disclose that he used open source code then he most likely violated the terms of the open source license and therefore did indeed cheat. Open Source is not the same as Public Domain.

Re:The obvious question

[cultiv8]

Unfortunately, Rybka’s source code has never been available, so reverse engineering and straight-up move-evaluation comparison was used to analyze the originality of Rajlich’s chess engine.

I don't see how anyone can claim plagiarism if they haven't seen source code.

Re:The obvious question

[El_Muerte_TDS]

Nothing wrong with reusing other people's work with permission. But claiming that you made it (i.e. plagiarizing) isn't.

Also, Fruit 2.1 was released as GPL 2. Rybka is not, so it's a violation of copyright. And Crafty's license also doesn't permit the way Rybka used its source.

Re:The obvious question

[devnull17]

The same way that Google caught Bing ripping off search results a while ago: find some idiosyncratic behaviors (e.g. bugs) that serve no practical purpose and are highly unlikely to end up in two independent projects, and demonstrate the same weirdness in each.

Re:The obvious question

[JustinOpinion]

He didn't steal the code from the other engines (it was open source). His biggest offense is denying the other coders credit.

Well, it seems that Fruit is open-source in the sense that people can look at the codebase, but it is not FOSS. The license text (see, e.g. readme in this tarfile) says:

All right reserved. Fruit and PolyGlot may not be distributed as part of any software package, service or web site without prior written permission from the author.

Indeed it looks like a commerical product that you are meant to pay for. Rajlich's engine is closed-source and also commercial. He is not making his code available, so even if Fruit were, say, released under the GPL, he would be in violation of the license. But in fact Fruit is "all rights reserved" so if Rajlich took code from it then he is blatantly violating copyright, and thus breaking the law.

I would think that the competition has a blanket ethics rule that says that you cannot win by breaking the law. So Rajlich, if he did indeed appropriate code, doesn't deserve the wins. (Yes, he obviously did ~something~ to improve upon Fruit, but he still cheated.)

Re:The obvious question

[Moryath]

FTFA:

To come to this rather epic and libelous conclusion, the ICGA assembled a 34-person panel of programmers who have competed in past championships to analyze Rybka. Unfortunately, Rybka’s source code has never been available, so reverse engineering and straight-up move-evaluation comparison was used to analyze the originality of Rajlich’s chess engine. The panel unanimously agreed that newer versions of Rybka are based on Fruit — and worse, that the early beta versions were based on Crafty, another open-source chess engine.

So in other words:
- They empaneled as the "jury" a bunch of assholes who were predisposed to want Rajlich banned from competition (he kept beating them, four competitions in a row).
- They based their decision on "move evaluation", a decidedly touchy subject given that in any Chess situation, it should be theoretically possible to find an optimal move and the more optimal the engines, the more optimal moves they'll make.

So, people with a motive to try to force Rajlich into a no-win situation got a chance to... hey look, a no-win situation!

It’s a tricky situation, though: with Rybka now outlawed from the WCCC, and with the ICGA asking other tournaments to block its entry, the only real way Rajlich and the rest of the Rybka team can clear their names is to show their source code — a financially untenable move. In short, Rybka is stuck between a rock and a hard place.

ICGA fucked up royally. What they SHOULD have done is demanded a closed-doors, clean-room evaluation of the Rybka source code. Instead, they're playing the "burn him at the stake" card, banning him from ever competing again and demanding he "come clean" when for all they know, his source is original and just plays better chess than the other, also-highly-optimized (and likely to make the same "optimal moves" on basic chess theory for the most part) competitors.

Re:The obvious question

[Arlet]

Cheating, in this case, means violating the rules of the championship:

18th WORLD COMPUTER CHESS CHAMPIONSHIP TOURNAMENT RULES

2. Each program must be the original work of the entering developers. Programming teams
whose code is derived from or including game-playing code written by others must name all
other authors, or the source of such code, in the details of their submission form

Re:The obvious question

[canajin56]

Read the fucking report. An analysis of the binary code revealed 60% similarity. So about 60% of the binary was completely identical. Most of the evaluation functions which are unique to Fruit (AKA not done in other algorithms) were mostly identical, usually with only some constants changed. These are functions that not only are unique in their purpose to those in Fruit, but which have the exact same binary code, the same local variables, declared in the same order. That much duplication is absolutely beyond the pale. In earlier versions of Rybka, they found that obsolete functions from the Crafty codebase were in there. So, you are claiming that not only did he magically duplicate most of the functions, he even had the same useless functions just sitting there not being called. And the exact same unit tests for those unused functions. So, there is a long history of blatant copy and pasting, some of it even completely mindless (copying unused functions). Additionally, he was offered the chance to be on the panel and offer his own input without having to release his sourcecode. He refused to respond whatsoever in his own defense.

Re:The obvious question

[Moryath]

First off: would it kill you to learn some basic HTML? Hard to separate out your comments when you're too lame to even italicize.

I know a lot of competitors and they don't want people who beat them banned.
Idle speculation and ad homs help nothing.

Empanel the losers from the competition on a witch hunt against the winner. Sounds like a dick move to me. Definitely doesn't pass the smell test.

They could get a third party to analyze and compare.

Why, precisely, should the Rybka team have to pay for that? It's the ICGA that should have been the ones doing this. FIRST.

And there are striking similarities in behavior.

You can walk into any chess tournament and see "striking similarities in behavior" between members of the same chess club/team, or between players of equal skill. Chess is a logical game, relying on logical formulations. Eventually, like Checkers and Othello were, it'll be solved. The closer the programs get to solving it, the more moves alike they'll make. "Similarities in behavior" of mathematical problem-solving prove nothing. If anything, the fact that his program beat - rather than drew to - the other programs ought to prove that he was NOT using their source code.

by your argument, opening moves in chess would have been the same for hundreds of years.

Funny you should mention that.
There are a grand total of 10 logical chess opening moves (8 pawns, 2 knights). Opening with knights has been derided as downright silly for centuries; the only "variation" there comes when it's immediately followed by a pawn push alongside, putting it back into "standard" opening land of a Kingside or Queenside gambit. Openings that begin with the A,H,B,G pawns are rightly derided as virtually useless. Even opening with the C and F pawns is viewed as akin to suicide, since it allows the opponent to open straight into the middle virtually uncontested.

Queen's Gambit openings, of various sorts, have dominated the arena since the early 1400's. The Italian opening was the favorite kingside method for over 300 years, until the Ruy Lopez opening passed it up in popularity. The entirety of "Black Openings" in modern chess for the past 500 years have been attempts to devise responses to these three methods of attack.

So now that I've given you a lesson, run back to your checkers board. The grownups are discussing things.

Re:The obvious question

[LoveMuscle]

Not necessarily, most Open Source Software (OSS) licenses (eg. GPLv2, EPL, etc.) only kick in on redistribution since you need the license to not be in violation of someone's copyright. You can USE all the OSS you want without complying with the license if you don't redistribute it. On top of that some OSS Licenses don't require that you disclose that there is OSS in your redistributable nor do they require you to provide source. (eg. 3-clause BSD).

In this case however, he's clearly distributing the binaries. Fruit appears to be LGPLv2.1 and Crafty has some goofball custom pseudo-oss license that requires attribution. So if he did copy the code and redistribute he's not complying with the licenses and in violation of copyright law.

I don't find it all that unusual that 2 different good chess programs might make similar decisions, and they don't have the source to compare so unless someone is going to sue and do discovery the claim of plagiarism is (IMO) premature.

The courts exist to settle just these sorts of conflicts, and banning him on supposition is questionable.. IANAL....

Re:The obvious question

[GooberToo]

Open source does not mean free of copyright. Furthermore, many open source licenses depend on copyright enforcement. Furthermore, claiming someone else's create as your own is fraudulent at best.

Re:The obvious question

[ArsonSmith]

Right in main.c

  Crafty, copyright 1996-2010 by Robert M. Hyatt, Ph.D., Associate Professor
  of Computer and Information Sciences, University of Alabama at Birmingham.

  Crafty is a team project consisting of the following members. These are the people involved in the continuing development of this program, there are no particular members responsible for any specific aspect of Crafty.

  * Michael Byrne, Pen Argyle, PA.
  * Robert Hyatt, University of Alabama at Birmingham
  * Tracy Riegle, Hershey, PA.
  * Peter Skinner, Edmonton, AB Canada.
  * Ted Langreck

  All rights reserved. No part of this program may be reproduced in any form or by any means, for other than your personal use, without the express written permission of the authors. This program may not be used in whole, nor in part, to enter any computer chess competition without written permission from the authors. Such permission will include the requirement that the program be entered under the name "Crafty" so that the program's ancestry will be known.

  Copies of the source must contain the original copyright notice intact.

  Any changes made to this software must also be made public to comply with the original intent of this software distribution project. These restrictions apply whether the distribution is being done for free or as part or all of a commercial product. The authors retain sole ownership and copyright on this program except for 'personal use' explained below.

Personal use includes any use you make of the program yourself, either by playing games with it yourself, or allowing others to play it on your machine, and requires that if others use the program, it must be clearly identified as "Crafty" to anyone playing it (on a chess server as one example). Personal use does not allow anyone to enter this into a chess tournament where other program authors are invited to participate. IE you can do your own local tournament, with Crafty + other programs, since this is for your personal enjoyment. But you may not enter Crafty into an event where it will be in competition with other programs/programmers without permission as stated previously.

Re:The obvious question

[h4rr4r]

As someone who is no chess master but can count, you are wrong. Those horsies move in Ls and each one has two possible Ls he could move into . Plus the pawns can move one spot or two spots. So that is 8 more moves. Up to 20 already. There might be more, but I am too busy playing Go to count.

Best chess engine

[Arlet]

No Rybka, but Houdini:

http://www.cruxis.com/chess/houdini.htm

Rybka/Houdini played a 40-game match recently, and Houdini won by a wide margin of 23.5-16.5. You can see the match here:
http://livechess.chessdom.com/site/ (Check for TCEC S1 Elite Match)

Rybka ... Or Skynet?

[WrongSizeGlass]

Now that it isn't distracted by chess this poor little computer will have nothing else to do except plot its revenge against man.

Should be easy to prove innocence

[JustinOpinion]

TFA points out that Rajlich could exonerate himself by showing the source code, but then says that this isn't possible:

It’s a tricky situation, though: with Rybka now outlawed from the WCCC, and with the ICGA asking other tournaments to block its entry, the only real way Rajlich and the rest of the Rybka team can clear their names is to show their source code — a financially untenable move. In short, Rybka is stuck between a rock and a hard place.

This doesn't really hold up. Yes, Rajlich is trying to sell his software, so he can't open-source it to the world. But to exonerate himself he doesn't have to release the source-code to the world; he simply needs to arrange for the source code to be shown to the expert panel. As long as they can both confirm that: (1) the provided source compiles to the binary used in competition, and (2) there is no substantial overlap between the provided source and other known codebases, then he's in the clear. The expert panel doesn't have to retain copies of the source code beyond the review period (all copies could be destroyed).

So, really, it should be possible for Rajlich to demonstrate the originality of his code without releasing it or decreasing his commercial opportunities. The fact that he hasn't done this is strange. In that sense, it sounds to me like the ICGA made the right decision here.

Re:Should be easy to prove innocence

[vlm]

I have an honest question. I'm going to assume the program is compiled into an executable, and not a scripting language like python. How do they determine if code from an open source program was used from the binary program?

Compile it with debugging symbols and compare to the open source program compiled with debugging symbols and compare the symbol tables. How odd that so many functions are exactly the same length and have exactly the same arguments. Run both thru a profiler and notice any identical control flow loops. I suspect there's a way to ask the GCC optimizer to compare the psuedocode before it gets assembled. Heck, just rub the raw binaries against each other and look for matches. It would be hilarious to ask/force him to compile and/or link mixmaster style

Ask a "windows security researcher" dude how he identifies a file with a virus. If he says, "use norton" then fire him and repeat. Eventually you'll find someone who knows how to use the binary equivalent of "substr".

Re:Should be easy to prove innocence

[Unoriginal_Nickname]

The problem with looking at just algorithm similarities is that every modern chess bot uses some variant of the same algorithm so the executable code will superficially look similar (negamax.) Computers aren't powerful enough to search the entire game tree, so you have to stop after a certain number of levels (15, for instance) and use a heuristic to evaluate the strength of that position.

The main differences between chess bots are found in that heuristic.

According to the actual report the heuristic is obviously based on Fruit's, which is what they're really angry about.

Oblig.

[Bobfrankly1]

Checkmate?

Re:Come Clean

[TaoPhoenix]

What if someone made it financially tenable for him to show his code?

"Oh. You did in fact innovate. Okay, we're sorry. But we won't take back the reputation tsunami we unleashed on you."

Anyone see parallels with the whole DHS theme of accuse first and question later?

I think Samuel Johnson said it best

[idontgno]

"Your [chess program] is both good and original; but the parts that are good are not original, and the parts that are original are not good."

I dunno? Sensed a disturbance in the force?

[mschaffer]

This explains it, but without an exact source:
http://blog.chess.com/clizaw/did-ibm-cheat-kasparov

He did not combine them.

[HanClinto]

He didn't even do that, he combined two separate opensource engine making one better engine.

According to the allegations, he did not combine two open-source programs into a super-bot. They claim that the current version of his bot (Rybka) is a copy of Fruit, and an earlier version of his software was a copy of Crafty.

As you said, he closed-sourced them and claimed them as his own without giving attribution -- thereby breaking the software licenses of at least one of them (Fruit), which is GPL.

Re:Whether he improved on them is irrelevant

[Arlet]

since he didn't redistribute binaries he didn't need to provide the source

He's using a funny way of not redistributing binaries, then:

http://www.rybkachess.com/index.php?auswahl=Purchase+Rybka

Re:Whether he improved on them is irrelevant

[Fnkmaster]

A) As was already pointed out, he sells the binary engine, so he did redistribute it.

B) The rules of the competition require disclosure of any used third party libraries or components. Since he didn't disclose this usage, he violated the competition rules regardless of whether he was complying with the license conditions or not.

Re:Come Clean

[rtfa-troll]

Let's see, should we take the word of Ken Thompson (yes that one), who according to the fine article seems to have been on the investigative panel, or the word of a random slashdot troll? Duhhh...

Actually neither. We should Read The Fine Reports.

Beyond the plain expression of the program, there are lots if artifacts which come through from source to binary. Even if two progammers start in the same language to develop the same algorithm to solve the same problem they will normally end up with great differences. The exceptions are the stuff of legends, and we are talking about 20 line long assembly programs. One programmer will choose an integer because it's big enough, another a long because the variable will mostly be used with other longs. This choice will not be optimised out of existence.

Looking at the report, it seems they used various different artifacts and clearly showed similarity between the programs.