Page 1 of 1

Brief Q&A about Rybka 1.0 Beta and Fruit 2.1

Posted: Tue Dec 14, 2010 4:57 am
by BB+
This is the product of some comparison work with Rybka 1.0 Beta and Fruit 2.1. I have deliberately avoided issues that can be contentious, and have stuck with more inarguable items.

Q. What are the principal similarities between Rybka 1.0 Beta and Fruit 2.1?
A. I will simply stress the evaluation functions, as the search functions have more differences. Both use exactly the same features (for every piece). Mobility and nothing else for minors, additionally 7th rank for queens, all this and (half-)open files for rooks, blocked bishops/rooks --- it's all the same, as is the criterion for king attacks, the method for passed pawns (including the 10:30:60:100 scaling on every sub-feature), and much of the pawn evaluation.

More examples are the identical "flags" in the material tables, giving the same criterion for when to use king safety, and similarly for when to halve the eval score in an opposite bishop ending. There is also the exact same internal scaling (in all 8 or 9 cases) in the piece-square tables, with the only structural difference in the whole PST process being a minor difference in bonuses for central pawns.

I do not think there is any possible way one could argue that the evaluation function(s) of Rybka 1.0 Beta are remotely "independent" of those of Fruit 2.1 according to the traditional standards of computer chess. A comparison of Fruit 2.1 with Crafty or Glaurung (or Pepito, or Gerbil, or Faile, or Phalanx, or likely any other pre-Fruit engine) will indicate that this is not within the realm of coincidence.

Q. What are the principal differences between Rybka 1.0 Beta and Fruit 2.1?
A. Rybka 1.0 Beta uses bitboards, has an extensive material imbalance table, and does not have the history pruning which Fruit 2.1 made prominent, but has a more vanilla approach that only considers the location in the move list. The values/weightings of the evaluation features are also of course different.

The search function of Rybka 1.0 Beta follows that of Fruit 2.1 in a vague sense, but seems not to be as mature; for instance, Rybka 1.0 Beta simply announces mate and does not try to minimise the distance to it (which can lead to overly lengthy mating chases). The principal "new idea" in search seems to me to be the passage beyond the strict cutoff values used in AEL pruning with respect to futility.

These add up to about 75-100 elo improvement on a 32-bit machine, comparable to the amount that Fruit itself gained over the second half of 2005.

Rybka 1.0 Beta also lacks underpromotions, which is quite odd for such a strong engine. One can note that the "predecessor" Rybka 1.5.32 from March/April 2004 included at least rook underpromotions, playing one against Taktix in Round 3.2 of the Top 200 of Le Système du Suisse (season 3), and also one against Chess System Tal II in Round 8.3 of ChessWar V E.

Q. Is there any code from Fruit 2.1 in Rybka 1.0 Beta?
A. I would say yes, and this is particularly clear in various parts of the UCI parsing. One example (in the position UCI command) is given here and in the following discussion. However, there is various mis-information around concerning the extent of any copying of UCI parsing, as for instance [url=http://ct_chess.pagesperso-orange.fr/Fruit-Rybka/start_go.html]this[/url] purports to give a "side-by-side" comparison of the "go" parser, but the Rybka 1.0 Beta order of parsing is re-ordered to fit the conclusion (it is not alphabetical [binc, btime, depth...] as with Fruit 2.1). Rick Fadden gives the Rybka 1.0 Beta disassembly and a more proper C translation here.

What makes this all the more strange is that the predecessor Rybka 1.5.32 was already a UCI engine, and thus it would be more logical to re-use that code rather than "borrow" from Fruit 2.1. The occurrence of "0.0" (as per Fruit 2.1) in the otherwise integer-based time management code of Rybka 1.0 Beta is another piece of evidence that is hard to dismiss, even if one demands a "copy/paste" standard rather than one akin to "plagiarism" for code copying.

Q. Is there chess-specific Fruit 2.1 code in Rybka 1.0 Beta?
A. I do not know of any direct evidence of this, such as would occur when (say) local variables are allocated in an identical manner by a compiler. The use of bitboards would preclude any mechanical copying of the evaluation function in any event. If you consider "data structures" to be code, then the identical use of the first 64 bits of the hash entries [lock(32), move(16), depth(8), date(8)] would be one point of non-independence, with again other open source engines notably differing so as to deflect any cry of "coincidence" (e.g. Faile uses [hash, depth, score, move] with differing bit widths; even Fruit 1.0 differs, having a 64-bit lock).

Here is a high-level comparison of the root search (see ZW's analysis)

Code: Select all

[b]Fruit 2.1[/b]                        [b]Rybka 1.0 Beta[/b]
generate legal moves                    generate legal moves
limit depth to 4 if #moves is 1         limit depth to 4 if #moves is 1       
setup setjmp                            setup setjmp
list/board copy
reset/start timer                       start timer
increment date and date/depth table     increment date and date/depth table
reset killers then history (sort_init)  reset killers then history
copy some Code()/UCI params
score/sort root list                    score/sort root list
Here are the comparative operations and their ordering in Phalanx XXII (for example): generate legal moves, init killers/history, increment Age, setup time limits, sort root moves, start timer, return move if forced (there are various bits about book/learning that I omit). The Fruit/Rybka overlap would already likely meet a "plagiarism" standard, for instance as used in the detection of non-original work in academia and/or book publishing. I really can't answer the question of how much weight to attach to this.

Q. What is your conclusion about Rybka 1.0 Beta and Fruit 2.1?
A. Rybka 1.0 Beta contains too much that is unique to Fruit 2.1 to consider it to be truly "independent" by the traditional standard of computer chess. This seems to have remained true until the evaluation was rewritten in Rybka 3 (the eval of Rybka 2.3.2a has only minor differences from that of Rybka 1.0 Beta, and various of the remnants of the internal PST scaling also remain). The Fruit-facets that still remain are fairly pedestrian, such as the 1:2:4 phase scaling with linear interpolation in the evaluation.

Rybka 1.0 Beta also likely violated the Gnu GPL by copying part of the UCI parser code of Fruit, though by now this seems moot, and it would be the prerogative of Fabien Letouzey to pursue this. The question of "intellectual property" is dismissed by Letouzey in an email to Dann Corbit (see here) though he does note that "Tournament organisers might think differently."

Re: Brief Q&A about Rybka 1.0 Beta and Fruit 2.1

Posted: Tue Dec 14, 2010 11:50 am
by kingliveson
It might be safe to say most people appreciate the honest effort to present data from an objective point of view. Also Zach W. analysis speaks for itself. This topic only continues to be an issue in the sense that to some like myself, there is an obvious double standard -- it does pay when your friend or friend of a friend runs the tournaments and so-called official rating's list.

Re: Brief Q&A about Rybka 1.0 Beta and Fruit 2.1

Posted: Tue Dec 14, 2010 1:27 pm
by notyetagm
kingliveson wrote:It might be safe to say most people appreciate the honest effort to present data from an objective point of view. Also Zach W. analysis speaks for itself. This topic only continues to be an issue in the sense that to some like myself, there is an obvious double standard -- it does pay when your friend or friend of a friend runs the tournaments and so-called official rating's list.
Yep.

Fruit is to Rybka as Ippolito is to Houdini.

Fruit => Rybka
Ippolito => Houdini

Deal with it.

Re: Brief Q&A about Rybka 1.0 Beta and Fruit 2.1

Posted: Sun Jan 02, 2011 11:14 am
by BB+
I ran across two bits from VR on CCC in late 2005. Both of these regard the Fruit/Rybka issue.

The first was in response to Daniel Mehrmann, who within a week had run some tests, and found that the mobility and PST in Rybka 1.0 Beta was a lot like that of Fruit 2.1 (he later apologetically retracted this).
Subject: Re: Rybka - How much Fruit is inside ?
From: Vasik Rajlich
Message Number: 469187
Date: December 12, 2005 at 03:34:15
[...]
The Rybka source code is original and pre-dates all of the Fruit releases.
[...]
Perhaps the intent of the phrase "source code" is in dispute here. If he means something limited, like the bitboard internals, it seems reasonable (if not particularly answering the question in context). However, I would take "source code" to include the search mechanism (and the UCI code for that matter), and thus the exact match of the common root search order (gen legal moves, limit depth to 4 if move is forced, setup setjmp, start timer, increment date and table, reset killers and history, score/sort root list) appears to belie that this "pre-dates all of the Fruit releases."

Then to Andrew Wagner a few days later (emphasis added):
Subject: Re: Unmasking the Secrets of Rybka and Fruit
From: Vasik Rajlich
Message Number: 470751
Date: December 16, 2005 at 03:42:44

>A very good question. If I were able to ask Vasik one question, which I doubt he would have time to answer at the moment, it would be whether he did anything radically different (different heuristic(s), algorithms, etc.), or if he just did what everyone else is doing, better than they did it.

Andy,

I will just end up teasing you by answering this. :)

As far as I know, Rybka has a very original search and evaluation framework. A lot of things that have been dismissed by "computer chess practice" can in fact work.
Here the word "framework" appears to be tendentious -- for instance, I would say that Rybka 1.0 Beta and Fruit 2.1 have an almost identical "framework", though perhaps VR envisioned that the material imbalance table made the evaluation framework original.

Re: Brief Q&A about Rybka 1.0 Beta and Fruit 2.1

Posted: Mon Jan 03, 2011 10:09 pm
by gaard
BB+ wrote:This is the product of some comparison work with Rybka 1.0 Beta and Fruit 2.1. I have deliberately avoided issues that can be contentious, and have stuck with more inarguable items.

Q. What are the principal similarities between Rybka 1.0 Beta and Fruit 2.1?
A. I will simply stress the evaluation functions, as the search functions have more differences. Both use exactly the same features (for every piece). Mobility and nothing else for minors, additionally 7th rank for queens, all this and (half-)open files for rooks, blocked bishops/rooks --- it's all the same, as is the criterion for king attacks, the method for passed pawns (including the 10:30:60:100 scaling on every sub-feature), and much of the pawn evaluation.

More examples are the identical "flags" in the material tables, giving the same criterion for when to use king safety, and similarly for when to halve the eval score in an opposite bishop ending. There is also the exact same internal scaling (in all 8 or 9 cases) in the piece-square tables, with the only structural difference in the whole PST process being a minor difference in bonuses for central pawns.

I do not think there is any possible way one could argue that the evaluation function(s) of Rybka 1.0 Beta are remotely "independent" of those of Fruit 2.1 according to the traditional standards of computer chess. A comparison of Fruit 2.1 with Crafty or Glaurung (or Pepito, or Gerbil, or Faile, or Phalanx, or likely any other pre-Fruit engine) will indicate that this is not within the realm of coincidence.

Q. What are the principal differences between Rybka 1.0 Beta and Fruit 2.1?
A. Rybka 1.0 Beta uses bitboards, has an extensive material imbalance table, and does not have the history pruning which Fruit 2.1 made prominent, but has a more vanilla approach that only considers the location in the move list. The values/weightings of the evaluation features are also of course different.

The search function of Rybka 1.0 Beta follows that of Fruit 2.1 in a vague sense, but seems not to be as mature; for instance, Rybka 1.0 Beta simply announces mate and does not try to minimise the distance to it (which can lead to overly lengthy mating chases). The principal "new idea" in search seems to me to be the passage beyond the strict cutoff values used in AEL pruning with respect to futility.

These add up to about 75-100 elo improvement on a 32-bit machine, comparable to the amount that Fruit itself gained over the second half of 2005.

Rybka 1.0 Beta also lacks underpromotions, which is quite odd for such a strong engine. One can note that the "predecessor" Rybka 1.5.32 from March/April 2004 included at least rook underpromotions, playing one against Taktix in Round 3.2 of the Top 200 of Le Système du Suisse (season 3), and also one against Chess System Tal II in Round 8.3 of ChessWar V E.

Q. Is there any code from Fruit 2.1 in Rybka 1.0 Beta?
A. I would say yes, and this is particularly clear in various parts of the UCI parsing. One example (in the position UCI command) is given here and in the following discussion. However, there is various mis-information around concerning the extent of any copying of UCI parsing, as for instance [url=http://ct_chess.pagesperso-orange.fr/Fruit-Rybka/start_go.html]this[/url] purports to give a "side-by-side" comparison of the "go" parser, but the Rybka 1.0 Beta order of parsing is re-ordered to fit the conclusion (it is not alphabetical [binc, btime, depth...] as with Fruit 2.1). Rick Fadden gives the Rybka 1.0 Beta disassembly and a more proper C translation here.

What makes this all the more strange is that the predecessor Rybka 1.5.32 was already a UCI engine, and thus it would be more logical to re-use that code rather than "borrow" from Fruit 2.1. The occurrence of "0.0" (as per Fruit 2.1) in the otherwise integer-based time management code of Rybka 1.0 Beta is another piece of evidence that is hard to dismiss, even if one demands a "copy/paste" standard rather than one akin to "plagiarism" for code copying.

Q. Is there chess-specific Fruit 2.1 code in Rybka 1.0 Beta?
A. I do not know of any direct evidence of this, such as would occur when (say) local variables are allocated in an identical manner by a compiler. The use of bitboards would preclude any mechanical copying of the evaluation function in any event. If you consider "data structures" to be code, then the identical use of the first 64 bits of the hash entries [lock(32), move(16), depth(8), date(8)] would be one point of non-independence, with again other open source engines notably differing so as to deflect any cry of "coincidence" (e.g. Faile uses [hash, depth, score, move] with differing bit widths; even Fruit 1.0 differs, having a 64-bit lock).

Here is a high-level comparison of the root search (see ZW's analysis)

Code: Select all

[b]Fruit 2.1[/b]                        [b]Rybka 1.0 Beta[/b]
generate legal moves                    generate legal moves
limit depth to 4 if #moves is 1         limit depth to 4 if #moves is 1       
setup setjmp                            setup setjmp
list/board copy
reset/start timer                       start timer
increment date and date/depth table     increment date and date/depth table
reset killers then history (sort_init)  reset killers then history
copy some Code()/UCI params
score/sort root list                    score/sort root list
Here are the comparative operations and their ordering in Phalanx XXII (for example): generate legal moves, init killers/history, increment Age, setup time limits, sort root moves, start timer, return move if forced (there are various bits about book/learning that I omit). The Fruit/Rybka overlap would already likely meet a "plagiarism" standard, for instance as used in the detection of non-original work in academia and/or book publishing. I really can't answer the question of how much weight to attach to this.

Q. What is your conclusion about Rybka 1.0 Beta and Fruit 2.1?
A. Rybka 1.0 Beta contains too much that is unique to Fruit 2.1 to consider it to be truly "independent" by the traditional standard of computer chess. This seems to have remained true until the evaluation was rewritten in Rybka 3 (the eval of Rybka 2.3.2a has only minor differences from that of Rybka 1.0 Beta, and various of the remnants of the internal PST scaling also remain). The Fruit-facets that still remain are fairly pedestrian, such as the 1:2:4 phase scaling with linear interpolation in the evaluation.

Rybka 1.0 Beta also likely violated the Gnu GPL by copying part of the UCI parser code of Fruit, though by now this seems moot, and it would be the prerogative of Fabien Letouzey to pursue this. The question of "intellectual property" is dismissed by Letouzey in an email to Dann Corbit (see here) though he does note that "Tournament organisers might think differently."
Long story short, you agree with Robert Hyatt, who stated that Vasik's claim that Rybka is and always has been 100% original at the source code level, is a lie?

Re: Brief Q&A about Rybka 1.0 Beta and Fruit 2.1

Posted: Tue Jan 04, 2011 2:52 am
by BB+
Long story short, you agree with Robert Hyatt, who stated that Vasik's claim that Rybka is and always has been 100% original at the source code level, is a lie?
I would say that such a claim is mealy-mouthed, perhaps even duplicitous. If he would elucidate what he means by it, I could say more. In particular, "100% original at the source code level" is not the same standard as "plagiarism" --- with the latter, as ZW has noted more than once, any border between "code" and "ideas" has become so fuzzy that it all depends on what standard is being used. My own preference is to adjudge the matter by the precedent standards of computer chess, though in the above I've striven to enumerate the evidence in such a way that others can pursue their own purposes. As I noted above (following the evidence of others), even the "100% original" source code claim could be contra-indicated via things like the UCI parsing of "position", though maybe that's not part of "Rybka", or maybe it is "original" because it was re-typed rather than copy/pasted.

[Not to drag IPPOLIT into the picture, but it again could be said to be "100% original at the source code level", yet I would hardly expect this to be the primary element of any debate regarding it as original for the purposes of computer chess].

Re: Brief Q&A about Rybka 1.0 Beta and Fruit 2.1

Posted: Tue Jan 25, 2011 12:00 am
by BB+
Detecting clones in game-playing software
Not the greatest paper in the world (and likely not freely available), but it does couch the issues somewhat well, and mentions Rybka, Strelka and Fruit. For Rybka/Fruit the comment is:
The decompiling efforts are, as of the time of writing, substantially inconclusive and may not ever conclude at all. Reports of uncommon practices in non-AI code, similar terms and analogous policies in certain areas have been offered, but there is no smoking gun.
The main technique of the paper is to detect plagiarism (via token counts and other methods) between source codes, even if various transformations (renaming variables for instance, or interleaving with random junk) have been performed.

Re: Brief Q&A about Rybka 1.0 Beta and Fruit 2.1

Posted: Tue Jan 25, 2011 9:04 pm
by Howard E
While I am not chess programming savy enough to contribute to the topic here I very much enjoy reading what those in this field have to share. So when I logged in just now I was hoping for a lively discussion with Fabien, Bob and others. So I am a bit disappointed that questions posed about Fruit/Rybka/Strelka are not
brought to the surface. My gut feeling is that the questions raised by Fabien would find some resolve in this thread. Anyway, thanks BB for once again giving us some substantial reading.

Re: Brief Q&A about Rybka 1.0 Beta and Fruit 2.1

Posted: Wed Jan 26, 2011 12:27 am
by Ron Murawski
BB+ wrote:Detecting clones in game-playing software
Not the greatest paper in the world (and likely not freely available), but it does couch the issues somewhat well, and mentions Rybka, Strelka and Fruit. For Rybka/Fruit the comment is:
The decompiling efforts are, as of the time of writing, substantially inconclusive and may not ever conclude at all. Reports of uncommon practices in non-AI code, similar terms and analogous policies in certain areas have been offered, but there is no smoking gun.
The main technique of the paper is to detect plagiarism (via token counts and other methods) between source codes, even if various transformations (renaming variables for instance, or interleaving with random junk) have been performed.
The following is a 3-part article on a methodology to detect clones...

Dr Dobb's
Finding Binary Clones with Opstrings & Function Digests
Part 1 http://www.drdobbs.com/184406152
Part 2 http://www.drdobbs.com/184406203
Part 3 http://www.drdobbs.com/184406247
By Andrew Schulman, July 01, 2005

Ron