A Gross Miscarriage of Justice in Computer Chess (part one)

A Gross Miscarriage of Justice in Computer Chess

By Dr. Søren Riis

Søren Riis is a Computer Scientist at Queen Mary University of London. He has a
PhD in Maths from the University of Oxford. He used to play competitive chess (Elo 2300).

Summary

Introduction
In June 2011 it was widely reported in the global media that the International Computer Games Association (ICGA), headed by Dr. David Levy, had found chess programmer Vasik Rajlich in breach of the ICGA’s annual World Computer Chess Championship (WCCC) tournament rule related to program originality. In the ICGA’s accompanying report it was asserted that Rajlich’s chess program Rybka contained “plagiarized” code from Fruit, a program authored by Fabien Letouzey of France. Rajlich, who cruised to victory in four consecutive WCCC tournaments in 2007, 2008, 2009 and 2010, was retroactively stripped of all titles he had won in competition and was slapped with a lifetime ban. In response, Rajlich claimed complete innocence and made it clear that he found the ICGA’s investigatory process and conclusions to be biased and unprofessional, and the charges baseless and unworthy. He refused to be drawn into a protracted dispute with his accusers or mount a comprehensive defense.

History
On December 4, 2005 a free, downloadable chess program named Rybka 1.0 Beta was initially released and took a sizable lead on all then-existing chess program strength ranking lists, surpassing all commercial programs. Rybka then proceeded to rapidly widen its lead with subsequent versions. Rybka went on to become a commercial engine in 2006. Working with Grandmaster Larry Kaufman, one of the world’s leading position evaluation specialists, Rajlich issued the seminal Rybka 3 in 2008. Rybka 3 was over 100 Elo points stronger than Rybka 2, an enormous improvement in what was already the leading commercial program. The latest public edition of Rybka (Rybka 4.1) is more than 300 Elo points stronger than the top competitors that existed in late 2005 on comparable hardware.

The ICGA’s investigation and outcome

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. They requested that the ICGA investigate their charges and, implicitly, take punitive action on the grounds that Rajlich had violated WCCC tournament rules. At this point over five years had elapsed since the alleged offense, and four consecutive world computer chess championships had been decisively won in head-to-head competition by Rybka.

In response to the accusing letter the ICGA formed a committee consisting of 34 experts, some with genuinely distinguished CVs, for their investigation. Judging from the Wiki which they used during their investigation, approximately seven of these 34 experts actively participated in the discussions. Three of the experts wrote a report wherein they argued that Rybka 1.0 Beta had plagarized large parts of Fruit. None of the actual Rybka versions that participated in the four WCCC tournaments were investigated, although a very close version (Rybka 2.3.2a) was examined following a laborious process of reverse-engineering.

The ICGA committee found that Rybka 1.0 Beta had violated Rule 2 of the ICGA-organized WCCC, and published extensive findings in support of its action. It is argued within the paper that this rule is vague on key points and become obsolete for several reasons, and that the overarching reason it has passed into obsolescence is that there has been a paradigm shift in computer chess programming in the past decade which the rule does not take into account.

---

Introduction

In June 2011 it was widely reported in the global media that the International Computer Games Association (ICGA) had found chess programmer International Master Vasik Rajlich in breach of the ICGA’s annual World Computer Chess Championship (WCCC) tournament rule related to program originality. In the ICGA’s accompanying report it was asserted that Rajlich’s chess program Rybka contained “plagiarized” code from Fruit, a program authored by Fabien Letouzey of France.

Rajlich, who cruised to victory in four consecutive WCCC tournaments in 2007, 2008, 2009 and 2010, was retroactively stripped of all titles he had won in competition and was slapped with a lifetime ban. Some of the headlines reporting the charges and ruling in the media were “Computer Chess Champion Caught Injecting Performance-Enhancing Code”, “Computer Chess Reels from Biggest Sporting Scandal Since Ben Johnson” and “Czech Mate, Mr. Cheat”, accompanied by a photo of Rajlich and his wife at their wedding.

In response, Rajlich claimed complete innocence and made it clear that he found the ICGA’s investigatory process and conclusions to be biased and unprofessional, and the charges baseless and unworthy. He refused to be drawn into a protracted dispute with his accusers or mount a comprehensive defense. In his only public statement on the matter to date he said:

Rajlich added that the ICGA’s action would not deter him from continuing to improve Rybka and sell it commercially, as he has done successfully for the past five years, and that his program would be willing to compete in a match or tournament with any worthy challenger.

This article re-examines the case. With the support of an extensive technical report by Ed Schröder, author of chess program Rebel (World Computer Chess champion in 1991 and 1992) as well as support in the form of unpublished notes from chess programmer Sven Schüle, I will argue that the ICGA’s findings were misleading and its ruling lacked any sense of proportion. The purpose of this paper is to defend the reputation of Vasik Rajlich, whose innovative and influential program Rybka was in the vanguard of a mid-decade paradigm change within the computer chess community.

In my view Mark Watkins and Zach Wegner, two members of the ICGA investigative panel who served as technical investigators, provided a series of documents that are accurate in a number of respects. In addition, those on the ICGA panel who supported the finding of plagiarism against Rybka included some rigorously honest and distinguished people. That said, I do quarrel with much of the evidence the ICGA presented and, based on the evidence I will lay out over the course of this paper, I must emphatically reject the conclusion that the similarities between Rybka and Fruit are so overwhelming that Rajlich must have copied Fruit code. It is clear that Rybka is an original program by any reasonable standard.

Based on the evidence I will present, a person can form a very credible alternative conclusion: that the implementation of similar evaluation concepts and algorithms in a computer chess program will inherently lead to code similarities even if no code is copied. Thus, the statement “Rybka implements concepts and algorithms learned from Fruit” appears to be the most correct and accurate formulation—a semantically subtle difference that nonetheless completely overturns the ICGA’s conclusion. It is important to understand that the implementation of ideas and algorithms learned from other programs is universal practice in chess programming as well as many other types of programming. The issue in contention in this case is whether source code was copied from one program to the next.

Here’s the main point: to convict and sentence a man due to his presumed ethical failings and then attempt to ruin him on a world stage you need a very high standard of evidence. The ICGA claims its evidence is of a high standard. We shall explore the veracity of that claim.

---

History of Rybka

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. Starting from this top perch, Rybka then proceeded to rapidly widen its lead with subsequent versions. Rybka went on to become a commercial engine in 2006.

Working with Grandmaster Larry Kaufman, one of the world’s leading position evaluation specialists, Rajlich issued the seminal Rybka 3 in 2008. Rybka 3 was over 100 Elo points stronger than Rybka 2, an enormous improvement in what was already the leading commercial program. When Rybka 3 was released Rajlich also converted the Rybka 2 series of releases into licensed freeware. In retrospect this was the moment of Rybka’s greatest dominance in computer chess: two Rybka editions held the #1 and #2 slots, with the #2 program free, yet stronger than any commercial rival.

The emergence of Rybka meant that affordable personal computers were now capable of exhibiting unprecedented chess playing strength which easily surpassed all human grandmasters. The implications of this were not lost on professional players, whose preparation methods became more reliant on computers than ever. As a result, Rybka enabled the development of considerable new opening theory and much reassessment of past certitudes. To take just one example, Garry Kasparov’s multi-volume My Great Predecessors could hardly have been the monumental work it is without pervasive utilization of the best available computer chess software.

Not least among its impacts, though few admit it, Rybka directly or indirectly had the effect of improving its competitors. They learned from Rajlich’s innovative search and evaluation techniques which enabled systematic performance tuning, as well as his emphasis on fast searching, as opposed to inefficiently loading up a program with CPU-consuming “chess knowledge”. However many view Rajlich’s description of his incrementalist program-testing methodology as his single most significant innovation. Dann Corbit, an American programmer and computer chess expert, remarks:

Rybka maintained unbroken supremacy on the chess engine rating lists for five years. However its performance in dozens of competitive tournaments held all over the world was, if anything, even more spectacular. Rybka did not merely win nearly every tournament it entered; it won them with a near-90% success rate. It is difficult to overstate the degree of superiority that the Rybka team exhibited in these years in chess software, mastery of hardware, and even in opening theory.

Going from one innovation to another, the Rybka team during this period developed the strongest chess-playing entity in the history of mankind up to the present day: the Rybka Cluster. The cluster, owned by Lukas Cimiotti, a German physician and member of the Rybka team, marshals the power of 300 late-model computer processors and plays chess at a hitherto unmatched and as-yet undefeated level.

Before Rybka it was rare to witness a computer program playing brilliant games with deep, beautiful combinations. Rybka was the first chess program to routinely produce highly artistic masterpieces of chess while avoiding a great many pointless “computer” moves that for many years had been a source of ridicule among strong human players.

For the sake of those not familiar with Rybka’s tournament play it might be helpful to study a few of its most stunning games. In the following example the Rybka Cluster demolishes chess program Shredder (winner of 13 WCCC titles) with a series of remarkable moves.

Next, an observer comments on a spectacular positional win over Deep Sjeng:

Finally, another brilliant game wherein the Rybka Cluster on 260 cores defeats chess program Jonny running a super-cluster of 800 Intel i7 cores located at the University of Bayreuth:

The latest public edition of Rybka (Rybka 4.1) is more than 400 Elo points stronger than the top competitors that existed in late 2005 on comparable hardware (who, at the time, were themselves approximately as strong as the world’s top grandmasters).

While the Rybka Cluster remains unsurpassed in the “unlimited hardware” category and by any standard of strength ought to be considered the reigning world champion of computer chess, a new program for the PC called Houdini, authored by Belgian Robert Houdart, surpassed Deep Rybka 4.1 on the rating lists in December 2010. His latest edition, Houdini 2.0c, is an impressive 60 Elo stronger. Rajlich has indicated that his next edition of Rybka (Rybka 5) will be issued in the first half of 2012. At this point it remains to be seen whether Rybka will retake the top spot among chess programs for the PC.

---

The ICGA’s investigation and outcome

In early 2011 sixteen chess programmers, many of whose programs were in direct competition with 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. They requested that the ICGA investigate their charges and, implicitly, take punitive action on the grounds that Rajlich had violated WCCC tournament rules. At this point over five years had elapsed since the alleged offense, and four consecutive world computer chess championships had been decisively won in head-to-head competition by Rybka.

In response to the accusing letter the ICGA formed a committee consisting of 34 experts, some with genuinely distinguished CVs, for their investigation. Judging from the Wiki which they used during their investigation, approximately seven of these 34 experts actively participated in the discussions. Three of the experts wrote a report wherein they argued that Rybka 1.0 Beta had plagarized large parts of Fruit. None of the actual Rybka versions that participated in the four WCCC tournaments were investigated, although a very close version (Rybka 2.3.2a) was examined following a laborious process of reverse-engineering.

The ICGA committee found that Rybka 1.0 Beta had violated Rule 2 of the ICGA-organized WCCC, and published extensive findings in support of its action.

Ed Schröder was one of the original sixteen signatories calling for an investigation. However, he later began to doubt the ICGA’s investigatory process and, ultimately, its findings. Eventually he had a complete change of heart and published his own investigation with the help of five other dissenting chess programmers.

WCCC Rule 2

The basis for the ICGA’s action was WCCC Rule 2, related to program originality.

Rule 2 has been invoked on a number of occasions. In the 9th World Microcomputer Chess Championship (Portoroz, 1989) the program QUICKSTEP was excluded when it was found to be an unauthorized version of another program. In the 11th WCCC the author of the program LIST was banned from the tournament, and in the 14th WCCC the program LION++ 1.5 was likewise excluded. The case of LION++ 1.5 was discussed by tournament director Jaap den Herik in his article “Interpretation of the Rules” in ICGA Journal Vol 29, p53-54, June 2006.

While no reasonable person can have any quarrel with Rule 2’s basic intention to exclude flagrant cheaters the rule nonetheless has some serious flaws which were not clarified in den Herik’s 2006 article.

For a non-specialist, including tournament directors and other ICGA board members, the flaws in Rule 2 might not be so obvious. However, to begin to understand the problem with Rule 2 one can start by acknowledging the truth contained within Rajlich’s remark on this topic:

Putting it bluntly, Rule 2 has become obsolete. It is completely vague or unrealistic on critical points that have emerged in recent years, or have always existed but were not as well understood in the past. Years ago, because of the way chess programs were traditionally developed, it was much easier to identify fraudulent entries and programmer-poseurs. Perhaps in that era Rule 2 was quite sufficient to expel entries not meeting originality standards. But, as will be shown, times have changed in computer chess and some of the old standards have been undermined or supplanted due to advances in information technology.

To make Rule 2’s absurdity as clear as possible, let me pose some straightforward questions:

• Given the great algorithmic overlap between modern chess programs, what is the definitional distinction between “original” and “non-original” work?

• A modern computer chess program can consist of tens of thousands of lines of code. Which of these lines can a programmer feel certain are in public domain and therefore exempt from Rule 2, and which are not?

• What exactly is meant by “game playing code” and on what basis does the ICGA make its distinction?

• What exactly is the definition of a “close derivative”? Is this phrase entirely a “we know it when we see it” construct, and if not, then what sensible, consistent, well-defined and articulated principles is such a determination based upon?

• Does Rule 2 require all competitors to maintain a copy of any source code they used in competition for an indefinite number of years?

• Can Rule 2 be invoked after tournaments are completed without any time limitation whatsoever? (In law, there is a defense called laches, which certainly applies to the Rajlich/Rybka case.)

• Finally, what safeguards exist to prevent ex post facto interpretations of rules which are not fully consistent with what competitors understood at the time the tournament took place?

It seems to me rather imperative that a tournament billing itself a “world championship” have crystal-clear rules. These rules should evolve in response to circumstances, contain well-defined procedures and credible enforcement mechanisms, and be designed to protect the integrity of the competition and the title.

To Part two ...

Earlier ChessBase article by Dr Søren Riis

• Computer analysis of world champions