Fabien's open letter to the community

Discussion of anything and everything relating to chess playing software and machines.

Moderators: hgm, Harvey Williamson, bob

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
bob
Posts: 20344
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Fabien's open letter to the community

Post by bob » Wed Jan 26, 2011 6:19 pm

Xann wrote:
SuneF wrote:I took a brief at look at Fruit v2.1.2 and compared it to Strelka 2.0, there are many differences though.

* Strelka is all bitboard Fruit is not.
* Strelka has multiple specialized search routines for check and null windows, Fruit does not.
* Evaluation and move selection looks quite different.
Looks are not so important.

Several experts that possibly don't want to be mentioned plus myself concluded that Strelka contains a large amount of Fruit algorithms.
Ryan, however, did not see Fruit in Strelka.
Anthony concluded that it was perhaps a modified version of Fritz 5.
Anthony is most certainly an expert.

How are these differences possible?
It's because I, and I assume some others as well, look "through" the code all the way to what it computes (the mathematical function that the code implements).
And we compare what Strelka computes with what Fruit computes.
"What", not "how".
And we find a match.

Bob, does this makes sense to you?

Fabien.
Yes and No.

Yes, in that comparing outputs is one way to detect similarity. But it doesn't guarantee that one is a derivative or cousin of the other. But it makes you think. The harder process is the one several of us undertook, led by Zach, to actually compare pieces of Rybka binary, de-compiled by hand back to C, against pieces of the Fruit source. That was more eye-opening.

bob
Posts: 20344
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Fabien's open letter to the community

Post by bob » Wed Jan 26, 2011 6:29 pm

JuLieN wrote:
bob wrote:Let's take Crafty. Which was, originally a bitboard version of Cray Blitz. And to further complicate it, it was ported from FORTRAN to C. The first step was FORTRAN to C, then from mailbox to bitboard. Is that a "rewrite" Hardly. That is a translation, just as converting from German to English is not a "rewrite".
Allow me to ask a question that might look naive, Robert (I'm not a computer scientist), but isn't a translation from a computer language to another called a "compilation"? (Compilers do take a listing in a language and translate it to another, usually assembly language). Though maybe this can't be called "compilation" when it's done by hand?
The terms are a bit vague. Traditionally, a compiler takes a high-level language and converts it to something that the machine will actually run. Some go directly to binary. Some (most GNU programs like gcc) go to a pure assembly language that is then converted (compiled) to binary by another program (gas in the case of gnu).

There are also translators. I used a FORTRAN-to-C translator (I think by Zortech) back in 1994 to convert Cray Blitz to C. I then started rewriting big pieces to clean up the code (A translator is stupid, and since F77 had no pointers, there was no way to use pointers in the translation and the resulting C code was just ugly. I have seen lots of other translators that will sort of take you from one language to another, although to be honest, when you translate Fortran to C, you get FORTRAN programming using the C syntax, which is not very elegant or fast...

In any case, I would neither claim that the C version of Cray Blitz was new and original, any more than I would claim that the GCC output (.s assembly language) was new and original... If someone reads you a book but uses sign language, is that "new"? Same idea... :)

User avatar
JuLieN
Posts: 2945
Joined: Mon May 05, 2008 10:16 am
Location: Nantes (France)
Contact:

Re: Fabien's open letter to the community

Post by JuLieN » Wed Jan 26, 2011 6:38 pm

Thx for these insights. :) And believe me, the asm code generated by GCC is far for optimal either. I learned to code on the Amiga computer, and back in those days we used pure 68k asm. No compiler was even close to produce half as fast code.

Then, on my PC days, I had debate with GCC zealots telling me that nowadays compilers were much more advanced and challenging everyone to write faster assembly code by hand. I wasn't so interested to put this to a test anymore but didn't believe it either. So I took it with a grin, last year, when Apple switched from GCC to LLVM and advertised that the binaries would be up to 100% faster. The everyday practice shown an average increase of perfs between 20-30%, but that's still much better than GCC. And I'm sure there's still lots of room for improvement.

(Sorry for this being a bit off-topic).
"The only good bug is a dead bug." (Don Dailey)
Image [Blog: http://tinyurl.com/predateur ] [Facebook: http://tinyurl.com/fbpredateur ] [MacEngines: http://tinyurl.com/macengines ]

Sven
Posts: 3578
Joined: Thu May 15, 2008 7:57 pm
Location: Berlin, Germany

Re: Fabien's open letter to the community

Post by Sven » Wed Jan 26, 2011 6:44 pm

bob wrote:
Xann wrote:
bob wrote:Just for the record, to eliminate this specific argument, when Zach, CT, I and others looked at the fruit/rybka1 question, we did _not_ involve Strelka. Strelka was the thing that exposed the issue, but we directly compared fruit to rybka, so the strelka issue could not be raised again...
What happened then?

Fabien.
We found _lots_ of similarities. Zach created a web page that went into great detail with the analysis. There are some obvious differences between Fruit and Rybka, but there are a _ton_ of similarities. Too many to be pure luck.
But these similarities are not a proof of code copying.

Sven

Xann
Posts: 125
Joined: Sat Jan 22, 2011 6:14 pm
Location: Lille, France

Re: Fabien's open letter to the community

Post by Xann » Wed Jan 26, 2011 7:11 pm

bob wrote:
Xann wrote:How are these differences possible?
It's because I, and I assume some others as well, look "through" the code all the way to what it computes (the mathematical function that the code implements).
And we compare what Strelka computes with what Fruit computes.
"What", not "how".
And we find a match.

Bob, does this makes sense to you?

Fabien.
Yes and No.

Yes, in that comparing outputs is one way to detect similarity. But it doesn't guarantee that one is a derivative or cousin of the other. But it makes you think. The harder process is the one several of us undertook, led by Zach, to actually compare pieces of Rybka binary, de-compiled by hand back to C, against pieces of the Fruit source. That was more eye-opening.
Just making sure there is no misunderstanding here.

By "compute" I mean pieces of code, not the engine I/O.
E.g. a bitboard bishop mobility vs. board scan one.

Fabien.

SuneF
Posts: 127
Joined: Thu Sep 17, 2009 9:19 am

Re: Fabien's open letter to the community

Post by SuneF » Wed Jan 26, 2011 10:36 pm

bob wrote: Still do not follow. Let's take Crafty. Which was, originally a bitboard version of Cray Blitz. And to further complicate it, it was ported from FORTRAN to C. The first step was FORTRAN to C, then from mailbox to bitboard. Is that a "rewrite" Hardly. That is a translation, just as converting from German to English is not a "rewrite".
You did however change the name from Cray Blitz to Crafty. That indicates to me that even you consider such a big rewrite as being a new engine.
Did Crafty produce the exact same output as Cray Blitz - I think not. Due to the change in structures there would have been stuff left out or modified. The core of the engine is completely altered, it is not a simple translation.
bob wrote: So bitboard or mailbox is irrelevant. Crafty went from traditional Slate/Atkin bitboards, to rotated bitboards, to magic move generation.
Yet the program was exactly the same (except for speed) for each conversion...
You can't compare going from mailbox to bitboard with going from rotated to magics. The first is a total rewrite of 10000 lines of code while the second is just changing a few macros.
bob wrote: Much of Crafty has no reference to bitboards. Search(). NextMove() and its friends. Quiesce().
As I mentioned Strelka looks different from Fruit there as well, so even in places that _could_ have been left untouched the code has changed. Strelkas's nextmove looks more like it is Crafty inspired actually.

Maybe there would have been more obvious similarities in code had we had the original to compare with instead of a reverse engineered engine with its own improvements...

User avatar
Don
Posts: 5106
Joined: Tue Apr 29, 2008 2:27 pm

Re: Fabien's open letter to the community

Post by Don » Wed Jan 26, 2011 11:16 pm

AdminX wrote:
hgm wrote:
AdminX wrote:Oh come on please! I find it hard to believe that Vas could create a new number one chess engine from the ground up without ANY reference material at all. What the hell is he a Chess Programing GOD? We are talking about 4 number one chess engines back to back.
You've probably never written a Chess engine yourself. All authors periodically start to rewrite completely from scratch.
I will just cut out your personal attack and cut to the chase. No I have not written a chess program myself, not in C anyway. :) It was more like Basic (not a chess engine) and that was a very long time ago. Yes, Programers do start from scratch from time to time, However how many do you know that create a New number 1 in such a short time frame from nothing at all? :twisted:
What was the time frame? I believe I could lose all the sources to komodo and doch and recover within a few months and probably end up with a stronger program.

I think any programmer knows that if you spend a day writing code and you accidentally end up with a snapshot of where you started in the morning, you can write it again within an hour or two. If the code is real simple it takes longer but if it's complex and required a lot of thought, you get it back much quicker.

If I had to restart a new komodo there would be a LOT that I would not even have to think about because I have already figured it out.

User avatar
Matthias Gemuh
Posts: 3234
Joined: Thu Mar 09, 2006 8:10 am
Contact:

Re: Fabien's open letter to the community

Post by Matthias Gemuh » Wed Jan 26, 2011 11:16 pm

SuneF wrote:
bob wrote: Still do not follow. Let's take Crafty. Which was, originally a bitboard version of Cray Blitz. And to further complicate it, it was ported from FORTRAN to C. The first step was FORTRAN to C, then from mailbox to bitboard. Is that a "rewrite" Hardly. That is a translation, just as converting from German to English is not a "rewrite".

Did Crafty produce the exact same output as Cray Blitz - I think not. Due to the change in structures there would have been stuff left out or modified. The core of the engine is completely altered, it is not a simple translation.

...

"The core of the engine is completely altered, it is not a simple translation." ?

I disagree about that.
I would have 95% translation and 5% simplifications/improvements.

If you can understand the individual lines of code, you can translate them.

Matthias.
My engine was quite strong till I added knowledge to it.
http://www.chess.hylogic.de

User avatar
Don
Posts: 5106
Joined: Tue Apr 29, 2008 2:27 pm

Re: Fabien's open letter to the community

Post by Don » Wed Jan 26, 2011 11:26 pm

Gian-Carlo Pascutto wrote:
hgm wrote: You've probably never written a Chess engine yourself. All authors periodically start to rewrite completely from scratch.
Bah, I don't think this is universal. Although I've done them, I'm not a fan of rewrites. Serious refactoring can be as good if the design is somewhat decent. If the engine gets big enough with features (not a factor for you, I'm sure!), the effort of rewriting becomes too big.

Of course, most people don't get a decent design the first time they write an engine, unless they were already experienced programmers. I certainly wasn't when I wrote my first engine...

But anyway, I do not believe all authors just "periodically" completely rewrite their engines.
I think you are correct. I personally AM a fan of rewrites but I think there are many chess authors that don't ever rewrite, or have only done so once in years.

User avatar
Houdini
Posts: 1471
Joined: Mon Mar 15, 2010 11:00 pm
Contact:

Re: Fabien's open letter to the community

Post by Houdini » Wed Jan 26, 2011 11:43 pm

Don wrote:I think you are correct. I personally AM a fan of rewrites but I think there are many chess authors that don't ever rewrite, or have only done so once in years.
Rewriting for the sake of rewriting doesn't serve any purpose at all.
Software with a good architecture will survive many years and many changes.

Robert

Post Reply