What do you folks make of this ?

[hyatt]

Bob Hyatt replied:
The first one that jumped out at me when we started the process was the code segment containing the setjmp()/longjmp() construct. You can find references to this in the past. It is an unusual way to unwind a search that is not thread-happy, and invites very subtle bugs. The usage was identical in both programs with the surrounding code. There were others.

You can't just ignore bolded sentence. It is important. It suggest not only that idea of (setjmp()/longjmp()) is used but the way it is used is identical, meaning surrounding code is verbatim copied.

Actually you can ignore the extra stuff that doesn't support your own point of view. It happens all the time, in fact. Let's not let a little "out of context" stuff confuse a debate by introducing actual facts...

[hyatt]

The first one that jumped out at me when we started the process was the code segment containing the setjmp()/longjmp() construct. You can find references to this in the past. It is an unusual way to unwind a search that is not thread-happy, and invites very subtle bugs.

I am curious why this would not be thread safe. And why you consider it unnatural.

The idea is that when you call setjmp() you establish a 'return point" in your program. Later, when you execute longjmp() you return to the point immediately following that setjmp() call. The stack is restored to what it was at that point. But what about all the global data? You have threads that might be spinning waiting on a lock, or on something else. You have a global board state that is corrupted and has to be restored. How do you cleanly restore the _global_ data to where it was just prior to that setjmp() call? Suppose you create threads when you start a search, and then they terminate when the search "backs out". You have to do something to get rid of them manually. You have to get rid of them before you start to restore the global state so that they don't un-fix something you just restored.

It is just not the way to write threaded code. It was eventually made "thread-safe" in the POSIX terminology, which means it won't crash the program if you use it, but there are so many side-effects I don't know of anyone that would risk all the side-effects of doing this. It is far easier to unwind the search in the natural way, by using "return" so that whatever was done by the search also gets undone. Then you don't have to undo things that are not necessary, etc. Code is far simpler overall.

[hyatt]

The first one that jumped out at me when we started the process was the code segment containing the setjmp()/longjmp() construct. You can find references to this in the past. It is an unusual way to unwind a search that is not thread-happy, and invites very subtle bugs.

I am curious why this would not be thread safe. And why you consider it unnatural.

Just to be helpful, here's the User Guide to setjmp()/longjmp()
it's fairly specific about what to do in that using it wrongly, or without consulting the user guide, is likely to lead to crash and burn.

It is NOT unusual for the purpose of jumping out of search and returning to the root. Ed used it, I used a more primitive version of it until I got hassled by support programmers, one of my programmers used it and refused to stop using it. Bob really can't claim use of setjmp() means copying, or that the code around it means copying, because the code around it is quite likely forced anyway.

_NEITHER_ of you used setjmp()/longjmp(). It is a pure C library function. You might have used something similar in assembly, but then I'll bet you didn't do a recursive search in assembly, and did the same thing I did in Cray Blitz and had a loop on the "ply" variable. Then there is no call stack to unwind. So let's get off of this "I did it" business. I did the same in Cray Blitz and do not think of "setjmp()/longjmp()" at all when describing what I did back then. The two things are completely unrelated.

setjmp
Home » Library Reference » Reference » setjmp

Summary
#include <setjmp.h>

int setjmp (
jmp_buf env); /* current environment */
Description
The setjmp function saves the current state of the CPU in env. The state may be restored by a subsequent call to the longjmp function. When used together, the setjmp and longjmp functions provide you with a way to execute a non-local goto.

A call to the setjmp function saves the current instruction address as well as other CPU registers. A subsequent call to the longjmp function restores the instruction pointer and registers, and execution resumes at the point just after the setjmp call.

Local variables and function arguments are restored only if declared with the volatile attribute.

Return Value
The setjmp function returns a value of 0 when the current state of the CPU has been copied to env. A non-zero value indicates that the longjmp function was executed to return to the setjmp function call. In such a case, the return value is the value passed to the longjmp function.

See Also
longjmp

Example
#include <setjmp.h>
#include <stdio.h> /* for printf */

jmp_buf env; /* jump environment (must be global) */
bit error_flag;

void trigger (void) {
.
.
.
/* processing code here */
.
.
.
if (error_flag != 0) {
longjmp (env, 1); /* return 1 to setjmp */
}
.
.
.
}


void recover (void) {
/* recovery code here */
}


void tst_longjmp (void) {
.
.
.
if (setjmp (env) != 0) { /* setjmp returns a 0 */
printf ("LONGJMP called\n");
recover ();
}

else {
printf ("SETJMP called\n");

error_flag = 1; /* force an error */

trigger ();
}
}

longjmp
Home » Library Reference » Reference » longjmp

Summary
#include <setjmp.h>

void longjmp (
jmp_buf env, /* environment to restore */
int retval); /* return value */
Description
The longjmp function restores the state which was previously stored in env by the setjmp function. The retval argument specifies the value to return from the setjmp function.

The longjmp and setjmp functions may be used to execute a non-local goto. They are usually utilized to pass control to an error recovery routine.

Local variables and function arguments are restored only if declared with the volatile attribute.

Return Value
None.

See Also
setjmp

Example
#include <setjmp.h>
#include <stdio.h> /* for printf */

jmp_buf env; /* jump environment (must be global) */
bit error_flag;

void trigger (void) {
.
.
.
/* processing code here */
.
.
.
if (error_flag != 0) {
longjmp (env, 1); /* return 1 to setjmp */
}
.
.
.
}


void recover (void) {
/* recovery code here */
}


void tst_longjmp (void) {
.
.
.
if (setjmp (env) != 0) { /* setjmp returns a 0 */
printf ("LONGJMP called\n");
recover ();
}

else {
printf ("SETJMP called\n");

error_flag = 1; /* force an error */

trigger ();
}
}

[zwegner]

Allow me some remarks. I deliberately take the Vas=innocent position for the sake of the discussion.

Here is a list that I came up with (again I rely partially on ZW) of "suspicious" things in Rybka:
* Re-use of exact same File/Rank/Line arrays in PST values (as opposed to an "idea" where statics would be built up in this way, but with different numbers)

One can only add the word suspicious if one have checked more programs (say 10-15) and found no such similarities. Perhaps things like these are common in many chess programs. Have Bob, Zach, you, checked 10-15 programs for its absence?

I have looked at many, many open source programs. I can assure you that no original engine has PSTs can be calculated with the same constant arrays. Fruit/Toga/other derivatives will have the same values, obviously. Sloppy is another case that has the same PSTs--but the author clearly said that his evaluation was copied from Fruit. If there are closed source programs that have PSTs from the same constants, I would likely have the same opinion about them as Rybka.

* Time management and UCI parsing, particularly the "0.0" appearance

The 0.0 case is indeed suspicious. UCI parsing: perhaps its code is public domain. Fabien took it and so did Vas. Has this option been researched by Zach, Bob and you?

This has some remote possibility of being true, but I think it can be ignored. The code as implemented in Fruit is licensed under the GPL, and AFAIK Fabien never released any part of Fruit as public domain. Fabien could have given the rights to Vas though. I think if either of these possibilities were true, someone would have said something about it (particularly Vas).

* Copying of the position at the top of the search (Fruit actually copies it back at every iteration), which is pointless as-is in Rybka (it is copied back after the search, again for no reason). Both search 4 ply when a move is forced. [You can also include setjmp under this "Search Start" heading if you like, and I haven't checked whether Rybka actually copies the position, as opposed to Strelka].

Mine does the same, copy the board before the search starts. It doesn't matter if that is pointless, there are many things in mine that are not in use, they are either remains of previous ideas and forgotten to remove or I leave them there on purpose for future ideas.

Mine searched forced moves 3 plies in the early days until I increased it to 5 in order to have a better move to ponder. I don't see the relevance, 4 is an excellent value also and I suspect most programs do it this way.

The whole root search is a bit more similar than just copying the board position. I need to bust out the old disassembler again and look at it, maybe I can say more here. I should really not waste my time though

The 4 plies is a pretty big "coincidence" IMO. Maybe there are other programs that have this same value, but I don't know of them. This one piece, like so many others, isn't a smoking gun that alone proves guilt, but it certainly isn't evidence of Rybka being original.

* Great similarity in evaluation. Here the "ideas" concept comes into play. Specific things could be the 1:2:4 weighting of minor:rook:queen (why not 3:5:9?) and the identical minutiae with the DrawBishopFlag -- to offset the former, Fruit has a linear interpolation across phases, while Rybka's is more complicated.

Using Vas own words: I took many things. I don't see the relevance.

When I was going through the Fruit-eval I wrote down 2 ideas, code for trapped (white) bishop (h6/a6) and the code for freeing ones rook in Kg1<>Rh1 situations. It's perfectly legal to add these ideas to mine, release it without any breach of the GPL. Again, what's the relevance?

I will note that Rybka took these too In Rybka's case, for these patterns, the evidence is a bit more damning--there is a function just like eval_pattern in Fruit, where the same three patterns (the two you mention plus minor blocking D/E pawns IIRC) are evaluated in the exact same order. Again, somewhere between ideas and implementation, it's a big grey area. There's a lot of stuff there with evaluation, and focusing on one small part will probably not give you the full picture.

* The use of 10, 30, 60, 100 weighting in passed pawns. If this were a one-off, I could believe the recurrence of this numerology was accidental.

Mine has similar values. It's not suspicious at all.

It's actually not the values BB says--its {0, 24, 77, 154, 256}. IIRC I did a comparison and Rybka doesn't take 10-30-60-100, but rather the rounded values /256 (which was done by hand, since they all round up--i.e. not integer division). This is because the rounding is exact--if you take the Fruit values and multiply by the Rybka weights, it's exact, which wouldn't happen for just similar values.

[zwegner]

Well, in a sense you didn't need to say it because it came across through reading.

You are assuming that the average person read past the first page.

I largely agree with what you say about the ZW analysis.

Here is a list that I came up with (again I rely partially on ZW) of "suspicious" things in Rybka:
* Re-use of exact same File/Rank/Line arrays in PST values (as opposed to an "idea" where statics would be built up in this way, but with different numbers)
* Time management and UCI parsing, particularly the "0.0" appearance
* Copying of the position at the top of the search (Fruit actually copies it back at every iteration), which is pointless as-is in Rybka (it is copied back after the search, again for no reason). Both search 4 ply when a move is forced. [You can also include setjmp under this "Search Start" heading if you like, and I haven't checked whether Rybka actually copies the position, as opposed to Strelka].
* Hash entries: more differences than similarities perhaps, but both start with the same "initial segment" (lock, move, depth, date). The same is true for pawn hash (the size of the entries is not even the same in that case). [Strelka is annoying here, as it does not preserve the Rybka data structures in all cases].
* Great similarity in evaluation. Here the "ideas" concept comes into play. Specific things could be the 1:2:4 weighting of minor:rook:queen (why not 3:5:9?) and the identical minutiae with the DrawBishopFlag -- to offset the former, Fruit has a linear interpolation across phases, while Rybka's is more complicated.
* The use of 10, 30, 60, 100 weighting in passed pawns. If this were a one-off, I could believe the recurrence of this numerology was accidental.

OK, I've needed to look over this again to go over your list, I will probably have some more to add. It will be very much on a as-I-find-the-time basis though. There are a bunch of weird things to add as well--the use of multiple move makers/move generators/move sorters, some of which are more similar to Fruit than others. It's hard to say exactly what happened here though.

[Chris Whittington]

Allow me some remarks. I deliberately take the Vas=innocent position for the sake of the discussion.

Here is a list that I came up with (again I rely partially on ZW) of "suspicious" things in Rybka:
* Re-use of exact same File/Rank/Line arrays in PST values (as opposed to an "idea" where statics would be built up in this way, but with different numbers)

One can only add the word suspicious if one have checked more programs (say 10-15) and found no such similarities. Perhaps things like these are common in many chess programs. Have Bob, Zach, you, checked 10-15 programs for its absence?

* Time management and UCI parsing, particularly the "0.0" appearance

The 0.0 case is indeed suspicious. UCI parsing: perhaps its code is public domain. Fabien took it and so did Vas. Has this option been researched by Zach, Bob and you?

* Copying of the position at the top of the search (Fruit actually copies it back at every iteration), which is pointless as-is in Rybka (it is copied back after the search, again for no reason). Both search 4 ply when a move is forced. [You can also include setjmp under this "Search Start" heading if you like, and I haven't checked whether Rybka actually copies the position, as opposed to Strelka].

Mine does the same, copy the board before the search starts. It doesn't matter if that is pointless, there are many things in mine that are not in use, they are either remains of previous ideas and forgotten to remove or I leave them there on purpose for future ideas.

Mine searched forced moves 3 plies in the early days until I increased it to 5 in order to have a better move to ponder. I don't see the relevance, 4 is an excellent value also and I suspect most programs do it this way.

* Great similarity in evaluation. Here the "ideas" concept comes into play. Specific things could be the 1:2:4 weighting of minor:rook:queen (why not 3:5:9?) and the identical minutiae with the DrawBishopFlag -- to offset the former, Fruit has a linear interpolation across phases, while Rybka's is more complicated.

Using Vas own words: I took many things. I don't see the relevance.

When I was going through the Fruit-eval I wrote down 2 ideas, code for trapped (white) bishop (h6/a6) and the code for freeing ones rook in Kg1<>Rh1 situations. It's perfectly legal to add these ideas to mine, release it without any breach of the GPL. Again, what's the relevance?

* The use of 10, 30, 60, 100 weighting in passed pawns. If this were a one-off, I could believe the recurrence of this numerology was accidental.

Mine has similar values. It's not suspicious at all.

Ed

To add to this .... Bob has always made a meal out of the setjmp instruction in Rybka and Fruit, claiming nobody else does it.

Well, I used the technique in 1980-something in Z80 assembler to jump out of the search, all you need to do then is reset the stack pointer and you're fine, back at the tree root. I changed to a more 'acceptable' method of unwinding back up the tree after staff programmers made a huge fuss about how uncompliant the technique was. But, Oxford Softworks later licensed a small chess program source for porting to various small platforms and I was surprised to see the programmer using setjmp (ie jump out of the search and reset vital pointers), told him to get 'proper(!)' and he refused, claiming it was just fine. This was a highly educated and qualified university guy who wrote masses of complex stuff in a bunch of fields and was highly reliable for producing bug free code, fast.

Absolutely impossible, because setjmp() and longjmp() are _C_ things. I did things remarkably different in Cray Blitz. We used an iterated search so that when time ran out, we just exited the search function instantly. Doesn't work for recursive implementations, which I'd be willing to bet you didn't do in assembly language due to the inherent messiness. This is about how do you get out of a deep recursive stack of calls as quickly as possible. The setjmp()/longjmp() approach is a horrible solution. Global variables are in an unknown state and you have to clean them up and get them back to "sane". What about locks()? state of a file if you are writing a log? Board state assuming, logically, that no one does copy/make due to performance issues. Just because one person says "it is OK" certainly doesn't mean it is. I've seen lots of university CS faculty that write horrible code, and some that can't write code at all.

Why you think it impossible? The functional equivalent for Z80 of set/longjmp() is reset stack pointer to same as the root, and rebuild the data tables (which are now going to be all messed up) from the board representation previously saved at the root. Z80 had an instruction to load and save the SP (I assume 6502 as well, since Ed confirms). Sounds like what you did with Cray Blitz. I forget the details from 1981/2 but you're almost certainly right there was no recursive stack usage, stuff was indexed by ply and saved/loaded from a ply indexed array.

Nevertheless, this argument is not about how horrible jumping out of search is, or how politically incorrect it is to jump anywhere, but whether or not use of ....jmp() implies copying. We say we have used the jumpout ourselves, know others who have done it, and it is therefore not as rare as you claim. Hence can't be used to imply plagiarism.

btw, I assume you consider Fabien to be a really ace programmer? He did produce Fruit after all. He used it, according to you and Zach

[Chris Whittington]

Well, in a sense you didn't need to say it because it came across through reading.

You are assuming that the average person read past the first page.

I largely agree with what you say about the ZW analysis.

Here is a list that I came up with (again I rely partially on ZW) of "suspicious" things in Rybka:
* Re-use of exact same File/Rank/Line arrays in PST values (as opposed to an "idea" where statics would be built up in this way, but with different numbers)
* Time management and UCI parsing, particularly the "0.0" appearance
* Copying of the position at the top of the search (Fruit actually copies it back at every iteration), which is pointless as-is in Rybka (it is copied back after the search, again for no reason). Both search 4 ply when a move is forced. [You can also include setjmp under this "Search Start" heading if you like, and I haven't checked whether Rybka actually copies the position, as opposed to Strelka].
* Hash entries: more differences than similarities perhaps, but both start with the same "initial segment" (lock, move, depth, date). The same is true for pawn hash (the size of the entries is not even the same in that case). [Strelka is annoying here, as it does not preserve the Rybka data structures in all cases].
* Great similarity in evaluation. Here the "ideas" concept comes into play. Specific things could be the 1:2:4 weighting of minor:rook:queen (why not 3:5:9?) and the identical minutiae with the DrawBishopFlag -- to offset the former, Fruit has a linear interpolation across phases, while Rybka's is more complicated.
* The use of 10, 30, 60, 100 weighting in passed pawns. If this were a one-off, I could believe the recurrence of this numerology was accidental.

OK, I've needed to look over this again to go over your list, I will probably have some more to add. It will be very much on a as-I-find-the-time basis though. There are a bunch of weird things to add as well--the use of multiple move makers/move generators/move sorters, some of which are more similar to Fruit than others. It's hard to say exactly what happened here though.

Just out of interest, and I'm fairly open on this, although I'ld prefer to keep my rosy view of human nature and that Vas program is quite clean, what are some of the important DIFFERENCES between Fruit and Rybka? Has Vas added stuff, or does your research indicate a straight copy with no significant changes?

Second, what is your view on both the ethics and legality of a parallel development process where the INTENTION is to end up with a piece of work that is entirely self-written, both code and data, but perhaps uses a target program (say Fruit) as a testbed to verify and bugcheck the component functions - having done that, then improve, add, optimise etc. Is that ok in your book, all code and all data different?

[CPU]

When someone says "There is zero fruit code in Rybka 1" I take the common definition of "zero". 0.000, not "a little" or "not very much".

Where did he say that?

[orgfert]

Why you think it impossible? The functional equivalent for Z80 of set/longjmp() is reset stack pointer to same as the root, and rebuild the data tables (which are now going to be all messed up) from the board representation previously saved at the root. Z80 had an instruction to load and save the SP (I assume 6502 as well, since Ed confirms). Sounds like what you did with Cray Blitz. I forget the details from 1981/2 but you're almost certainly right there was no recursive stack usage, stuff was indexed by ply and saved/loaded from a ply indexed array.

Nevertheless, this argument is not about how horrible jumping out of search is, or how politically incorrect it is to jump anywhere, but whether or not use of ....jmp() implies copying. We say we have used the jumpout ourselves, know others who have done it, and it is therefore not as rare as you claim. Hence can't be used to imply plagiarism.

btw, I assume you consider Fabien to be a really ace programmer? He did produce Fruit after all. He used it, according to you and Zach

While you say you are open, it always seems you are open only to opposing Hyatt and introducing distractions from the issue like was Fabien and ace programmer.

[zwegner]

Well, in a sense you didn't need to say it because it came across through reading.

You are assuming that the average person read past the first page.

I largely agree with what you say about the ZW analysis.

Here is a list that I came up with (again I rely partially on ZW) of "suspicious" things in Rybka:
* Re-use of exact same File/Rank/Line arrays in PST values (as opposed to an "idea" where statics would be built up in this way, but with different numbers)
* Time management and UCI parsing, particularly the "0.0" appearance
* Copying of the position at the top of the search (Fruit actually copies it back at every iteration), which is pointless as-is in Rybka (it is copied back after the search, again for no reason). Both search 4 ply when a move is forced. [You can also include setjmp under this "Search Start" heading if you like, and I haven't checked whether Rybka actually copies the position, as opposed to Strelka].
* Hash entries: more differences than similarities perhaps, but both start with the same "initial segment" (lock, move, depth, date). The same is true for pawn hash (the size of the entries is not even the same in that case). [Strelka is annoying here, as it does not preserve the Rybka data structures in all cases].
* Great similarity in evaluation. Here the "ideas" concept comes into play. Specific things could be the 1:2:4 weighting of minor:rook:queen (why not 3:5:9?) and the identical minutiae with the DrawBishopFlag -- to offset the former, Fruit has a linear interpolation across phases, while Rybka's is more complicated.
* The use of 10, 30, 60, 100 weighting in passed pawns. If this were a one-off, I could believe the recurrence of this numerology was accidental.

OK, I've needed to look over this again to go over your list, I will probably have some more to add. It will be very much on a as-I-find-the-time basis though. There are a bunch of weird things to add as well--the use of multiple move makers/move generators/move sorters, some of which are more similar to Fruit than others. It's hard to say exactly what happened here though.

Just out of interest, and I'm fairly open on this, although I'ld prefer to keep my rosy view of human nature and that Vas program is quite clean, what are some of the important DIFFERENCES between Fruit and Rybka? Has Vas added stuff, or does your research indicate a straight copy with no significant changes?

Second, what is your view on both the ethics and legality of a parallel development process where the INTENTION is to end up with a piece of work that is entirely self-written, both code and data, but perhaps uses a target program (say Fruit) as a testbed to verify and bugcheck the component functions - having done that, then improve, add, optimise etc. Is that ok in your book, all code and all data different?

Sure, there are of course differences. The biggest one is that Rybka is in bitboards. This has effects all over the place. Rybka is also much faster than Fruit.

For evaluation, the tuning is all new (except for the already-mentioned constants in PSTs and passers), and the Fruit material eval has been replaced by the big imbalance table. Those are the biggest differences. Rybka has a different phase calculation and it uses lazy eval. Besides that there are also lots of pretty minor differences, some of which can be explained by the translation to bitboards (i.e. an evaluation term in bitboards or mailbox might be expressed most naturally in slightly different ways).

For search, the biggest difference is the addition of some aggressive futility pruning in Rybka. Rybka has checks in qsearch (can't remember what Fruit does there). The move sorting is different too, and the history updating is different (Rybka doesn't loop over the moves at the end). Rybka doesn't differentiate between mates in different numbers of moves. It's been a while since I looked at the Rybka search closely, but those are really the only differences I can remember. Fruit's search is just pretty generic though, so it's hard to say that this is really damning evidence--there's probably many more programs that have such similarities in search, at least after Fruit was published.

For the moral issue, it's complicated. What you say sounds legally fine, but the morals depend on what the author does IMO. If the author is up front and says that they followed the process you described, and doesn't try and commercialize the engine, I'd say it's morally OK, but I personally wouldn't want it to be playing in tournaments. If the author denies this process and commercializes the engine, then to me it's morally wrong.