On Crafty...

[Houdini]

I do expect there could be assembly code matches if there have been any cut_and_paste; we could try the common compiler options/switches and there are the common compilers in use.

Rasjid

For your info, Bob's bubble sort in root.c and the wikipedia code (both as shown on page 2 of this thread) would produce nearly identical assembler.

Robert

[bob]

I do expect there could be assembly code matches if there have been any cut_and_paste; we could try the common compiler options/switches and there are the common compilers in use.

Rasjid

For your info, Bob's bubble sort in root.c and the wikipedia code (both as shown on page 2 of this thread) would produce nearly identical assembler.

Robert

Would depend on a _lot_ of assumptions. "swap()?" Might use X86 xchg instruction. I didn't. And of course that ignores the _other_ bubble-sort that is the one that actually makes any difference, in quiesce.

When one writes such a simple function as bubble sort, one would expect great similarity (perhaps not in variable names, or other small details, but bubble-sort _is_ bubble-sort. And I have never called my sort anything else for those two places.

We didn't use "bubble-sort" to detect Rybka containing fruit/crafty code. we used much larger blocks of code, that were _far_ more complex.

[bob]

Bob, repeating the same personal attack 1000 times is hardly interesting... why don't you comment on the substance?

Like I said, you've established a convincing argument for claiming the originality and/or copyrightability of your bubble sort code.
The following demonstrates that you didn't copy any code:

Different variable names. No "swap()" function. Loops are done differently (he uses simple counter, I use a pointer). In other words. not even close.

And the following quote is about copyright infringement:

Does the code in the wiki look _exactly_ like the code in Crafty? Not to me, so how can I sue them for copyright infringement when they didn't copy my code exactly? You can't copyright "ideas".

Two questions:
1) If somebody else on this forum would make the same argument as you did in this thread, using similar wording, wouldn't you be the first to crucify the poor fellow?

You seem to have great difficulty with context. If someone writes a trivial algorithm like bubble-sort, I would expect that the implementations would look _very_ similar. I mean, bubble-sort is sort of well-known, is it not? But I didn't bring up bubble-sort. Milos did. He claimed I "copied knuth verbatim." I didn't. For the fruit/rybka/crafty/ip*/robo*/et. al. discussions, nobody is trying to find a bubble-sort in each and use that as proof copying was done. Quite the contrary, we have explicitly looked for "unique implementations". EvaluateWinner() in Crafty is complicated, and unique, and nobody would write it _exactly_ the same way. Yet it appears in Rybka 1.6.1... Ditto for Fruit search oddities and Rybka 1 beta. Ditto for the egtb probe bug left in Crafty accidentally when Nalimov replaced Edwards tablebasese. Magically ended up in Rybka 1.6.1. The list goes on and on. You (and most others here) have not seen 10% of the ICGA investigation results, yet. Once the process is concluded, everything will be made public and this story will be "laid to rest" once and for all.

2) Why don't you apply your own logic to the rotated bitboard code you claim Robbo (but you probably mean Ippo) copied from Crafty? Is the code _exactly_ the same? If it isn't, can you claim copyright?

I originally looked at IP_ENG.c, which I believe is just a translation to English variable names (sort of, anyway). I looked specifically at the initialization code. Which has quirks. One of which is a poor bit numbering scheme that I corrected about 2 years ago. There are others. They are present in ip*. Which means all of the derivatives as well...

As far as being _exactly_ the same, it is unlikely. IP* and friends are reverse-engineered, obviously. I don't dimension an array as "int xyz[0100];" I use the more traditional "int xyz[64];" (0100 is an octal number.) There are lots of those kinds of things that IDA pro or whatever produces that would make a perfect match unlikely. But there are quirks present that would make original code even more unlikely...

Cheers,
Robert

[bob]

This is all very fine but where you draw the line for copyright?
If I take Knuth's code and translate it to C (and change variable names in the process) do I then hold a copyright? Yes, no? What if change change data types so I compare pointers instead of numbers. Is that enough to claim my own copyright? What if I swap both key and value instead of just value? Is it now sufficient? How can anyone tell when it is?
If original code contained a bug (for example doesn't make swaps in last iteration), and my also contains it, but I made all the changes (translation, changing data types, changing swapping, changing sort direction, changing sort index bounds) does this invalidates my copyright?
You think a court judge would have consistent opinion on that?

Personally, I think the bubble sort is too short for copyright of the object code. It's been implemented thousands of times, and most simple variations have all been tried. In other words, I'd put in the public domain unless there was something very unusual about it. In the source code, though, if you used non-simple variable names it might be copyrightable.

Every byte of Crafty is in the public domain, but not every sequence of bytes. For instance, I'll bet there is an 'A' in Crafty but I can use that snippet all I like: AAA. No violation. At some point the expression of an idea, whether in source, object or general plan, becomes so unlikely to think of independently that it becomes copyrightable. Borderline cases take a judge to decide, and he will listen to experts. At some point it's a crapshoot, though.

Also, the "type" of bug is important.

In the Crafty/Rybka case, two specific bugs have been mentioned.

1. In the Edwards tablebase format, for the kp vs kp database (we did not have any 5 piece files with 2 pawns or more) he did not consider en passant captures when he generated them. If you probed in a position where an ep capture is either possible or will be possible in the future, you would get a wrong answer. I added code in Crafty to check for (a) pawns are on adjacent files, else no EP capture is possible; (b) pawns have not "passed each other"; (c) one of the two pawns is on its original square so it can advance two squares at once to create the EP possibility. If all of those were true, the EGTB probes into kpkp were disabled. Eugene came along much later and did this correctly. In fact, his EGTBs pre-dated Rybka by several years. And his handled EP captures properly so the tests above were not needed. At the point we finished testing his code and settled on the compression blocksize, I replaced the Edwards tables with his and the Edwards tables were no longer available from my ftp site. Later, along came Rybka, supposedly written from scratch, and initially using the Nalimov EGTBs since they were all that were available, and Rybka 1.6.1 clearly has egtb.cpp included. But it also has the code above to handle EP in Edwards format. How did it get there? Why would he write that on his own when that tablebase format was long since discarded and _everybody_ used either Nalimov or Thompson, or else wrote their own (Rybka 1.6.1 used Nalimov). Probability of that happening? zero.

2. I have always had a function in Crafty, modelled after the Slate/Atkin "clean-up" idea that forces mate when pawns are gone and one side has mating material. Simple idea is to drive the king to the edge of the board and then let the search find the forced mate. And over time, I made it more "inclusive" so that it would work in some unexpected cases. Which had exceptions. Originally, I always called this function and let it make the decision "can I handle this position or not?" If not, it returned 99999, Evaluate() realized that this meant that EvaluateMate() was refusing to handle this position for some reason, and it did a normal eval. Later, to avoid the procedure call overhead, I moved the test up to where I called EvaluateMate() so that I didn't call it if it didn't apply. But the check for the 99999 return was left in Evaluate(). Since EvaluateMate() never returned 99999, that branch was predicted 100% of the time and it didn't hurt, but it was certainly dead code. Which also appears at the _same_ point in Rybka's Evaluate(). What is the probability of Rybka having an EvaluateMate() that is _identical_ to Crafty's, and then having that "ms = EvaluateMate(); if (ms == 99999) break;" code at the point where it was called? When there is _zero_ code in EvaluateMate() that can return 99999 (or any other large odd number, returning 99998 would actually break the program completely since in Crafty +infinity = 32767... The probability of that being "original code" is zero.

So it is not the presence of "any bug" in two implementations that is the red flag. It is the presence of the same bug in both, where the first occurrence can be explained by the author (me) and it is clear that nobody else would have written exactly the same code, with the same return values, and then tested for a return value that was impossible for the code to produce...

There are others in our report...

[Zach Wegner]

It can be safely said that Crafty's code is beyond reproach.
All contributed code is clearly documented.

I don't think that's really true. As an easy example, the Random32() function STILL doesn't have attribution, even though it's been brought up a zillion times before...

Then what is this:

Code: Select all

/*
 *******************************************************************************
 *                                                                             *
 *  A 32 bit random number generator. An implementation in C of the algorithm  *
 *  given by Knuth, the art of computer programming, vol. 2, pp. 26-27. We use *
 *  e=32, so we have to evaluate y(n) = y(n - 24) + y(n - 55) mod 2^32, which  *
 *  is implicitly done by unsigned arithmetic.                                 *
 *                                                                             *
 *******************************************************************************
 */
unsigned int Random32(void) {

That is taken from utility.c, starting at line #2991.

This is in Crafty version 20.0, same source file:

Code: Select all

/*
 A 32 bit random number generator. An implementation in C of the algorithm
 given by Knuth, the art of computer programming, vol. 2, pp. 26-27. We use
 e=32, so we have to evaluate y(n) = y(n - 24) + y(n - 55) mod 2^32, which
 is implicitly done by unsigned arithmetic.
 */

unsigned int Random32(void)
{

Or this in version 17.0, same file:

Code: Select all

/*

A 32 bit random number generator. An implementation in C of the algorithm given by
Knuth, the art of computer programming, vol. 2, pp. 26-27. We use e=32, so 
we have to evaluate y(n) = y(n - 24) + y(n - 55) mod 2^32, which is implicitly
done by unsigned arithmetic.

*/

unsigned int Random32(void) {

So care to explain _exactly_ what you are talking about???

Seems like a perfect citation to ma, page number, title of book, author, etc. Sheesh, are you now trying to emulate Milos?

As far as the "this has been brought up a zillion times before" wouldn't you call that just "a bit of an exaggeration"? It has been brought up exactly zero times...

Just for the record, from Crafty 11.13 that played in the WMCCC in 1996, which anyone can find in that specific source file:

Code: Select all

*

A 32 bit random number generator. An implementation in C of the algorithm given by
Knuth, the art of computer programming, vol. 2, pp. 26-27. We use e=32, so 
we have to evaluate y(n) = y(n - 24) + y(n - 55) mod 2^32, which is implicitly
done by unsigned arithmetic.

*/

unsigned int Random32(void)
{

All I can say is "ahem... better check your facts before writing nonsense, don't you think?"

Well there's this: http://www.stmintz.com/ccc/index.php?id=324659
where you said:

You are wrong. This originally came fro Knuth volume 2, pages 26-27. I
never claimed I wrote the code. In fact, the comments in utility.c quote
Knuth as the source. Although the code itself came from the book Numerical
Recipes as they distributed a CDRom with the source code for everything in
it.

I don't know who Gijsbert Wiesenekker is. If he wrote the RNG for Knuth,
then he is the author. If not then he isn't the author. However, when
I use the term "my RNG" it obviously means "the RNG _I_ am currently using"
as opposed to anything else you might dream up.

...though a bit of a search in the online NR books didn't find anything.

And then there's the same code in ZZZZZZ, from 1993-1994: http://cap.connx.com/chess-engines/zzzzzz/util.c

I don't really know whether Gijsbert wrote it or not (possibly it was copied from Crafty to ZZZZZZ), but at least from your statements in the above link it seems clear that you didn't write it yourself.

[bob]

It can be safely said that Crafty's code is beyond reproach.
All contributed code is clearly documented.

I don't think that's really true. As an easy example, the Random32() function STILL doesn't have attribution, even though it's been brought up a zillion times before...

Then what is this:

Code: Select all

/*
 *******************************************************************************
 *                                                                             *
 *  A 32 bit random number generator. An implementation in C of the algorithm  *
 *  given by Knuth, the art of computer programming, vol. 2, pp. 26-27. We use *
 *  e=32, so we have to evaluate y(n) = y(n - 24) + y(n - 55) mod 2^32, which  *
 *  is implicitly done by unsigned arithmetic.                                 *
 *                                                                             *
 *******************************************************************************
 */
unsigned int Random32(void) {

That is taken from utility.c, starting at line #2991.

This is in Crafty version 20.0, same source file:

Code: Select all

/*
 A 32 bit random number generator. An implementation in C of the algorithm
 given by Knuth, the art of computer programming, vol. 2, pp. 26-27. We use
 e=32, so we have to evaluate y(n) = y(n - 24) + y(n - 55) mod 2^32, which
 is implicitly done by unsigned arithmetic.
 */

unsigned int Random32(void)
{

Or this in version 17.0, same file:

Code: Select all

/*

A 32 bit random number generator. An implementation in C of the algorithm given by
Knuth, the art of computer programming, vol. 2, pp. 26-27. We use e=32, so 
we have to evaluate y(n) = y(n - 24) + y(n - 55) mod 2^32, which is implicitly
done by unsigned arithmetic.

*/

unsigned int Random32(void) {

So care to explain _exactly_ what you are talking about???

Seems like a perfect citation to ma, page number, title of book, author, etc. Sheesh, are you now trying to emulate Milos?

As far as the "this has been brought up a zillion times before" wouldn't you call that just "a bit of an exaggeration"? It has been brought up exactly zero times...

Just for the record, from Crafty 11.13 that played in the WMCCC in 1996, which anyone can find in that specific source file:

Code: Select all

*

A 32 bit random number generator. An implementation in C of the algorithm given by
Knuth, the art of computer programming, vol. 2, pp. 26-27. We use e=32, so 
we have to evaluate y(n) = y(n - 24) + y(n - 55) mod 2^32, which is implicitly
done by unsigned arithmetic.

*/

unsigned int Random32(void)
{

All I can say is "ahem... better check your facts before writing nonsense, don't you think?"

Well there's this: http://www.stmintz.com/ccc/index.php?id=324659
where you said:

You are wrong. This originally came fro Knuth volume 2, pages 26-27. I
never claimed I wrote the code. In fact, the comments in utility.c quote
Knuth as the source. Although the code itself came from the book Numerical
Recipes as they distributed a CDRom with the source code for everything in
it.

I don't know who Gijsbert Wiesenekker is. If he wrote the RNG for Knuth,
then he is the author. If not then he isn't the author. However, when
I use the term "my RNG" it obviously means "the RNG _I_ am currently using"
as opposed to anything else you might dream up.

...though a bit of a search in the online NR books didn't find anything.

And then there's the same code in ZZZZZZ, from 1993-1994: http://cap.connx.com/chess-engines/zzzzzz/util.c

I don't really know whether Gijsbert wrote it or not (possibly it was copied from Crafty to ZZZZZZ), but at least from your statements in the above link it seems clear that you didn't write it yourself.

Did I say I "wrote it myself"? On the few occasions where I have used code written by others, I have _always_ cited the source as accurately as possible. Even when I borrow ideas, such as the old 2-level hash table, I correctly cited Ken Thompson and Belle as the source of the idea...

That random number generator code has been in Cray Blitz and Crafty forever. I did, at one time, use something different, but it was problematic when mixing architectures (32 bit vs 36 bit vs 60 bit vs 64 bit so I went back to the simpler version.

But my point was, the code is cited explicitly, if you look at the comments, giving the title of the book, and the page number(s) where the code can be found. I did have to type it myself, but I didn't write it.

So exactly what is the issue here? I didn't write the code. I didn't claim I wrote the code. I gave an explicit citation for its origin... Is this any different than using one of the several C built-in random number generators? I don't think so...

[Sven]

I do expect there could be assembly code matches if there have been any cut_and_paste; we could try the common compiler options/switches and there are the common compilers in use.

Rasjid

For your info, Bob's bubble sort in root.c and the wikipedia code (both as shown on page 2 of this thread) would produce nearly identical assembler.

Would you accept that the "Wikipedia code", similar to the "Knuth code" (as I pointed out in my previous post above), provides nothing but an algorithm?

Bubble sort in Wikipedia (simple version, not "optimized"):

Code: Select all

procedure bubbleSort( A : list of sortable items )
  do
    swapped = false
    for each i in 1 to length(A) - 1 inclusive do:
      if A[i-1] > A[i] then
        swap( A[i-1], A[i] )
        swapped = true
      end if
    end for
  while swapped
end procedure

And that would produce zero assembler code, unless you actually implement it in a programming language (above is pseudocode only).

It is hard to believe that a decent programmer does not see the difference ...

Sven

[Sven]

Well there's this: http://www.stmintz.com/ccc/index.php?id=324659
where you said:

You are wrong. This originally came fro Knuth volume 2, pages 26-27. I
never claimed I wrote the code. In fact, the comments in utility.c quote
Knuth as the source. Although the code itself came from the book Numerical
Recipes as they distributed a CDRom with the source code for everything in
it.

I don't know who Gijsbert Wiesenekker is. If he wrote the RNG for Knuth,
then he is the author. If not then he isn't the author. However, when
I use the term "my RNG" it obviously means "the RNG _I_ am currently using"
as opposed to anything else you might dream up.

...though a bit of a search in the online NR books didn't find anything.

And then there's the same code in ZZZZZZ, from 1993-1994: http://cap.connx.com/chess-engines/zzzzzz/util.c

I don't really know whether Gijsbert wrote it or not (possibly it was copied from Crafty to ZZZZZZ), but at least from your statements in the above link it seems clear that you didn't write it yourself.

Bold face above added by me.

My google says:
Numerical Recipes in C (page 283)
Numerical Recipes in C (PDF version)
First Edition was published in 1988, a first version might have been available earlier on university level, though.

Crafty "Random32()" seems closest to the function "ran3()" described in that book but the latter is written for floating numbers between 0.0 and 1.0 and therefore would have required a few changes to be used for integers.

"Knuth book" Volume 2, Third Edition
Start at bottom of page no. 27 = page 40 of online document, where you can read:

"A much better type of additive generator was devised in 1958 by G. J. Mitchell and D. P. Moore [unpublished], who suggested the somewhat unusual sequence defined by

X(n) = (X(n-24) + X(n-55)) mod m, n >= 55,

where m is even, and where X(0), ..., X(54) are arbitrary integers not all even. [...]"

The "Knuth book" (everyone knows the correct title) is now available in Third Edition from 1997, Second Edition appeared in 1981, so obviously Bob referred to the latter.

So the timeline seems to be:
1958: RNG suggested by Mitchell/Moore
1981 (maybe earlier): RNG described in "Knuth book"
1988 (maybe earlier): C implementation of RNG in "Numerical Recipes" book
1980s (late?)/1990s: RNG implementation in Crafty
1993/1994: RNG implementation in ZZZZZZ, identical to Crafty

And again, there are much more important issues than this one ...

Sven

[bob]

Well there's this: http://www.stmintz.com/ccc/index.php?id=324659
where you said:

You are wrong. This originally came fro Knuth volume 2, pages 26-27. I
never claimed I wrote the code. In fact, the comments in utility.c quote
Knuth as the source. Although the code itself came from the book Numerical
Recipes as they distributed a CDRom with the source code for everything in
it.

I don't know who Gijsbert Wiesenekker is. If he wrote the RNG for Knuth,
then he is the author. If not then he isn't the author. However, when
I use the term "my RNG" it obviously means "the RNG _I_ am currently using"
as opposed to anything else you might dream up.

...though a bit of a search in the online NR books didn't find anything.

And then there's the same code in ZZZZZZ, from 1993-1994: http://cap.connx.com/chess-engines/zzzzzz/util.c

I don't really know whether Gijsbert wrote it or not (possibly it was copied from Crafty to ZZZZZZ), but at least from your statements in the above link it seems clear that you didn't write it yourself.

Bold face above added by me.

My google says:
Numerical Recipes in C (page 283)
Numerical Recipes in C (PDF version)
First Edition was published in 1988, a first version might have been available earlier on university level, though.

Crafty "Random32()" seems closest to the function "ran3()" described in that book but the latter is written for floating numbers between 0.0 and 1.0 and therefore would have required a few changes to be used for integers.

"Knuth book" Volume 2, Third Edition
Start at bottom of page no. 27 = page 40 of online document, where you can read:

"A much better type of additive generator was devised in 1958 by G. J. Mitchell and D. P. Moore [unpublished], who suggested the somewhat unusual sequence defined by

X(n) = (X(n-24) + X(n-55)) mod m, n >= 55,

where m is even, and where X(0), ..., X(54) are arbitrary integers not all even. [...]"

The "Knuth book" (everyone knows the correct title) is now available in Third Edition from 1997, Second Edition appeared in 1981, so obviously Bob referred to the latter.

So the timeline seems to be:
1958: RNG suggested by Mitchell/Moore
1981 (maybe earlier): RNG described in "Knuth book"
1988 (maybe earlier): C implementation of RNG in "Numerical Recipes" book
1980s (late?)/1990s: RNG implementation in Crafty
1993/1994: RNG implementation in ZZZZZZ, identical to Crafty

And again, there are much more important issues than this one ...

Sven

One other note. Only reason I even included a PRNG in Crafty was for the book. Early on, I used a standard PRNG, but there really was not such a thing that worked across all platforms, all operating systems, and all compilers, to produce the same set of PRNs. yet I needed exactly that because I used the PRNs for the Zobrist hash signature that is used in the book. I wanted to be able to distribute a book that worked everywhere. Initially, the book had to be build from scratch if the PRNG didn't provide the same sequence. Endian was still an issue until at some point I solved that as well. Today I really don't need the PRNG in crafty any longer, because the Zobrist numbers are initialized at compile-time using specific constants...