Rybka 1.0 vs. Strelka

[kranium]

"I took many things" can be interpreted as "I took many ideas".
Depends how you wish to interpret it.

exactly my point, it's one of many interpretations ...

[chrisw]

According to the evidence provided, I see two possibilities.
1. The Rybka author took Fruit code and modified it.
2. The Ryka author studied Fruit code and took the ideas in it.

Item 1 is illegal and item 2 is legal. There is obviously no way to differentiate which one was done. I assume that there are no patents on any of Fruit's algorithms. If this is the case, then it is not wrong, immoral or unethical to read the code, study the code, improve the code, rewrite the code, alter the code, etc. and then write your own version.

The code is not identical. The similar parts that have been demonstrated are all trivial anyway.

If you read the thread that I just posted ("Questions for Vas") and still believe that, then I would have to seriously question your expertise on the matter. How many engines do you know that store both an upper and lower bound in the hash table? How many do you know that use setjmp to exit the search function? How many do you know that store only the hashkeys for game history?

I'm not saying that it's impossible for any other engine to have these same ideas in them. But there are very many low level similarities (in non trivial areas), and only to Fruit.

Using the same techniques is not illegal, immoral or otherwise bad in any way. To read and understand what Fruit is doing and then do the same thing yourself is not wrong, even if you do it the same way.

Everyone who wrote a chess program borrowed ideas from other people. People who claim otherwise are liars. Either that or they do not use alpha-beta, null move pruning, hash tables, etc.

I think that the mud slinging contest is a silly farce.
Slingers: "LOOK HE COPIED!"
Of course, we *all* did. Let's be honest. Everyone who failed to learn from Fruit's code is an idiot.

Personally, I learned nothing. I really don't like Fruit's code at all. Feel free to say whatever you want about me...

I think you are a smart person, but if you do not read and understand the ideas in Fruit your engine will never be as strong as Fruit.

I totally disagree. What did Fabien study before he wrote fruit?

I would guess that he studied all available chess programs, articles, books and papers. I would guess that he read chess programming boards and things of that nature.

It is not an accident that all successful chess programs use hash tables (and almost all use Zobrist hashing).
It is not an accident that all successful chess programs use some variant of either:
A. Alpha-beta
or:
B. MTD(f)
It is not an accident that all successful chess programs use move ordering.
The fundamental parts of most evaluations will also be very similar.
All chess programs will count the wood.
All successful chess programs will evaluate pawn structure.
Successful chess programs will have *most* features in common and many of them will be very similar to some other program or article (no doubt the program or article that they learned it from).

People who claim to have invented everything in their chess program are not thinking clearly. Of course with crafty (one of the oldest public source programs) most of it is probably your invention, but some significant fraction will also have been borrowed from other programs or articles.

My point was that nobody has to read _fruit_ to write a program that is strong. In fact, fruit is "old news" and there are stronger freeware programs around.

Many of us developed hashing independently. If you find the original paper on Greenblatt's chess program he also had a transposition table, although he did not us hashing, he actually encoded the entire position exactly so there would be no errors. Other programs of the early 70's did this (including chess 4.x by the way) but it was not an efficient way to do things obviously. I added hashing to my program around 1976 or so after re-reading the greenblatt article that was published in the DEC journal. The idea of SEE came from the original paper on COKO published in the CACM journal.

Looking at other programs can certainly help, because it shows real implementations rather than abstract descriptions/algorithms.

Bob,

You ignored the point being made. Dann said that some things are so well known now that everybody does them more or less the same way.

For example, the famous Zach piece of disassembly of Rybka, he chose a chuck of search connected to move ordering. Take a look at your own Crafty, it will be the same or similar. I forget what is optimal ordering, but it will be something similar to this:

1. is there a move from hash to play?

2. try a couple of moves from the killer list

3. try the good captures, sorted SEE/MVLA

4. try the remaining non-captures (sorted by history list)

5. try the losing captures

Nobody tries losing captures first, do they?
Nobody looks at hash second.
Most will use identical move ordering based on the results of tests - which ordering gives overall fastest response. Test results are going to dictate a particular ordering system - everybody can find this independently, and then everybody has similarly structured code at that level.

So it's no good coming in at this level of program structure and saying similarities add up, therefore more and more evidence of copying, because of course these similarities add up. If a programmer read and studied competing source beforehand, Crafty, Fruit, whatever, the similarities will add up even more and quite legally so.

I think it is Rick Fadden in another thread who describes Strelka having 'identical code' to Rybka, identical functions, identical function calls, same data going in, same data coming out - that sounds like what a copy program would do.

Where, in our current case are these identical code fragments? Where are the identical data flows through them?

imo any involved in this campaign should have assembled and proved this data BEFORE opening any threads on the subject. So where is it?

[Guetti]

Bob,

You ignored the point being made. Dann said that some things are so well known now that everybody does them more or less the same way.

For example, the famous Zach piece of disassembly of Rybka, he chose a chuck of search connected to move ordering. Take a look at your own Crafty, it will be the same or similar. I forget what is optimal ordering, but it will be something similar to this:

1. is there a move from hash to play?

2. try a couple of moves from the killer list

3. try the good captures, sorted SEE/MVLA

4. try the remaining non-captures (sorted by history list)

5. try the losing captures

Nobody tries losing captures first, do they?
Nobody looks at hash second.
Most will use identical move ordering based on the results of tests - which ordering gives overall fastest response. Test results are going to dictate a particular ordering system - everybody can find this independently, and then everybody has similarly structured code at that level.

So it's no good coming in at this level of program structure and saying similarities add up, therefore more and more evidence of copying, because of course these similarities add up. If a programmer read and studied competing source beforehand, Crafty, Fruit, whatever, the similarities will add up even more and quite legally so.

I think it is Rick Fadden in another thread who describes Strelka having 'identical code' to Rybka, identical functions, identical function calls, same data going in, same data coming out - that sounds like what a copy program would do.

Where, in our current case are these identical code fragments? Where are the identical data flows through them?

imo any involved in this campaign should have assembled and proved this data BEFORE opening any threads on the subject. So where is it?

I agree here that most engines use a the same sequence of move ordering. My engine does exactly the same sequence you described above in general (most of the time).

But, to somebody that would disassemble a binary or look at the source of my engine, it looks quite different (and I don't claim the code is any good!!). I took the idea of a nextmove() function from crafty (idea, not code). Then in source it would look like that:

1. Try move from hash, if available and check if legal

2. Try some legal killer moves

3. If in check generate check evasions

4. if in check, pick check evasion with the highest score (MVVLVA scores of check evasion moves are assigned during move generation). If no moves left, we are done.

5. generate captures

6. Try good captures sorted by MVVLVA (assigned during move generation)

7. generate rest of moves

8. Try rest of moves, followed by bad captures sorted by SEE

Therefore, on a more detailed level, or source code level, it looks quite different than other engines. And the closer you look in detail, the more differences you will find in the programming of different engines, because, as Bob stressed out several times, different people just code differently.

e.g. you could split up point number 3 further:

a) Try to capture the figure that gives check to the king
b) Try to move the king out of check
c) Try to move a piece in between the attacking figure and the king

Now, generating check evasion is a very low level function, so a lot of people will probably do it in this order. Others maybe don't have a special function for check evasions at all, I don't know. But how exactly it is coded will never look the same (does the engine use bitboards or not, how many function calls etc, etc).

What I want to point out is, generally speaking, most engines look similarly, but in detail, no engine should look the same as another, with exactly the same functions, etc.

[bob]

According to the evidence provided, I see two possibilities.
1. The Rybka author took Fruit code and modified it.
2. The Ryka author studied Fruit code and took the ideas in it.

Item 1 is illegal and item 2 is legal. There is obviously no way to differentiate which one was done. I assume that there are no patents on any of Fruit's algorithms. If this is the case, then it is not wrong, immoral or unethical to read the code, study the code, improve the code, rewrite the code, alter the code, etc. and then write your own version.

The code is not identical. The similar parts that have been demonstrated are all trivial anyway.

If you read the thread that I just posted ("Questions for Vas") and still believe that, then I would have to seriously question your expertise on the matter. How many engines do you know that store both an upper and lower bound in the hash table? How many do you know that use setjmp to exit the search function? How many do you know that store only the hashkeys for game history?

I'm not saying that it's impossible for any other engine to have these same ideas in them. But there are very many low level similarities (in non trivial areas), and only to Fruit.

Using the same techniques is not illegal, immoral or otherwise bad in any way. To read and understand what Fruit is doing and then do the same thing yourself is not wrong, even if you do it the same way.

Everyone who wrote a chess program borrowed ideas from other people. People who claim otherwise are liars. Either that or they do not use alpha-beta, null move pruning, hash tables, etc.

I think that the mud slinging contest is a silly farce.
Slingers: "LOOK HE COPIED!"
Of course, we *all* did. Let's be honest. Everyone who failed to learn from Fruit's code is an idiot.

Personally, I learned nothing. I really don't like Fruit's code at all. Feel free to say whatever you want about me...

I think you are a smart person, but if you do not read and understand the ideas in Fruit your engine will never be as strong as Fruit.

I totally disagree. What did Fabien study before he wrote fruit?

I would guess that he studied all available chess programs, articles, books and papers. I would guess that he read chess programming boards and things of that nature.

It is not an accident that all successful chess programs use hash tables (and almost all use Zobrist hashing).
It is not an accident that all successful chess programs use some variant of either:
A. Alpha-beta
or:
B. MTD(f)
It is not an accident that all successful chess programs use move ordering.
The fundamental parts of most evaluations will also be very similar.
All chess programs will count the wood.
All successful chess programs will evaluate pawn structure.
Successful chess programs will have *most* features in common and many of them will be very similar to some other program or article (no doubt the program or article that they learned it from).

People who claim to have invented everything in their chess program are not thinking clearly. Of course with crafty (one of the oldest public source programs) most of it is probably your invention, but some significant fraction will also have been borrowed from other programs or articles.

My point was that nobody has to read _fruit_ to write a program that is strong. In fact, fruit is "old news" and there are stronger freeware programs around.

Many of us developed hashing independently. If you find the original paper on Greenblatt's chess program he also had a transposition table, although he did not us hashing, he actually encoded the entire position exactly so there would be no errors. Other programs of the early 70's did this (including chess 4.x by the way) but it was not an efficient way to do things obviously. I added hashing to my program around 1976 or so after re-reading the greenblatt article that was published in the DEC journal. The idea of SEE came from the original paper on COKO published in the CACM journal.

Looking at other programs can certainly help, because it shows real implementations rather than abstract descriptions/algorithms.

Toga based on fruit is still the strongest free source code so saying that fruit is old news is not correct.

Fruit derivative free source is still the strongest.

Uri

I'm using fruit in my cluster testing. Glaurung is at least 100 elo stronger. I will try to add Toga at some point when I have time to see where it stacks up. But if I were starting, and wanted to read/study some program source before starting, Fruit is not where I would start today.

I think the "mailbox" approach is outdated, and there are stronger programs to look at that are written more clearly.

[bob]

According to the evidence provided, I see two possibilities.
1. The Rybka author took Fruit code and modified it.
2. The Ryka author studied Fruit code and took the ideas in it.

Item 1 is illegal and item 2 is legal. There is obviously no way to differentiate which one was done. I assume that there are no patents on any of Fruit's algorithms. If this is the case, then it is not wrong, immoral or unethical to read the code, study the code, improve the code, rewrite the code, alter the code, etc. and then write your own version.

The code is not identical. The similar parts that have been demonstrated are all trivial anyway.

If you read the thread that I just posted ("Questions for Vas") and still believe that, then I would have to seriously question your expertise on the matter. How many engines do you know that store both an upper and lower bound in the hash table? How many do you know that use setjmp to exit the search function? How many do you know that store only the hashkeys for game history?

I'm not saying that it's impossible for any other engine to have these same ideas in them. But there are very many low level similarities (in non trivial areas), and only to Fruit.

Using the same techniques is not illegal, immoral or otherwise bad in any way. To read and understand what Fruit is doing and then do the same thing yourself is not wrong, even if you do it the same way.

Everyone who wrote a chess program borrowed ideas from other people. People who claim otherwise are liars. Either that or they do not use alpha-beta, null move pruning, hash tables, etc.

I think that the mud slinging contest is a silly farce.
Slingers: "LOOK HE COPIED!"
Of course, we *all* did. Let's be honest. Everyone who failed to learn from Fruit's code is an idiot.

Personally, I learned nothing. I really don't like Fruit's code at all. Feel free to say whatever you want about me...

I think you are a smart person, but if you do not read and understand the ideas in Fruit your engine will never be as strong as Fruit.

I totally disagree. What did Fabien study before he wrote fruit?

I would guess that he studied all available chess programs, articles, books and papers. I would guess that he read chess programming boards and things of that nature.

It is not an accident that all successful chess programs use hash tables (and almost all use Zobrist hashing).
It is not an accident that all successful chess programs use some variant of either:
A. Alpha-beta
or:
B. MTD(f)
It is not an accident that all successful chess programs use move ordering.
The fundamental parts of most evaluations will also be very similar.
All chess programs will count the wood.
All successful chess programs will evaluate pawn structure.
Successful chess programs will have *most* features in common and many of them will be very similar to some other program or article (no doubt the program or article that they learned it from).

People who claim to have invented everything in their chess program are not thinking clearly. Of course with crafty (one of the oldest public source programs) most of it is probably your invention, but some significant fraction will also have been borrowed from other programs or articles.

My point was that nobody has to read _fruit_ to write a program that is strong. In fact, fruit is "old news" and there are stronger freeware programs around.

Many of us developed hashing independently. If you find the original paper on Greenblatt's chess program he also had a transposition table, although he did not us hashing, he actually encoded the entire position exactly so there would be no errors. Other programs of the early 70's did this (including chess 4.x by the way) but it was not an efficient way to do things obviously. I added hashing to my program around 1976 or so after re-reading the greenblatt article that was published in the DEC journal. The idea of SEE came from the original paper on COKO published in the CACM journal.

Looking at other programs can certainly help, because it shows real implementations rather than abstract descriptions/algorithms.

Bob,

You ignored the point being made. Dann said that some things are so well known now that everybody does them more or less the same way.

For example, the famous Zach piece of disassembly of Rybka, he chose a chuck of search connected to move ordering. Take a look at your own Crafty, it will be the same or similar. I forget what is optimal ordering, but it will be something similar to this:

Aha, a hypothesis to test. I have three ways to order moves. NextRootMove() orders moves for ply-1 only. NextMove() orders moves at plies where the side on move is not in check. NextEvasion() orders moves at plies where the side on move is in check. If you take all three of those, I will bet you will not find any 5 or 10 line block of code that matches code in _any_ other chess program unless that code was directly borrowed from Crafty. It is one thing to suggest high-level ideas, hash-move first, then good captures, then killers. But the killer is in the details, because there are hundreds of ways to do that, with uncountable ways to express those "ways" in actual programming language examples.

Those simple ideas about move ordering take 500 lines of code in Crafty. Not counting things like SEE that are used in them. Do you _really_ believe that you will find duplicate blocks of code in another program that uses the same basic ordering?

How many different ways can you write a page of text explaining how SEE works? That's the problem here. Programming languages are just as rich in variety of expression as is a normal language used to write a book. How often do you read two different mystery or advanture novels and say "damn, this chapter is the same as the one in the book I read last month by a different author?" Only time I have ever had that happen is when reading text books by a few prolific textbook authors that borrow text from book A and use it in book B. But they wrote the original so it was theirs to copy. Otherwise it just doesn't happen. At least not as a matter of coincidence.

But I'm willing to test the hypotheses about move ordering. Just name a freeware program and I will post the comparison between them and Crafty, if their source is available. It will be enlightening. What is being purported to be quite common is really a zillion-sigma event in statistical terms.

1. is there a move from hash to play?

2. try a couple of moves from the killer list

3. try the good captures, sorted SEE/MVLA

4. try the remaining non-captures (sorted by history list)

5. try the losing captures

Nobody tries losing captures first, do they?
Nobody looks at hash second.
Most will use identical move ordering based on the results of tests - which ordering gives overall fastest response. Test results are going to dictate a particular ordering system - everybody can find this independently, and then everybody has similarly structured code at that level.

I agree in the approach or _result_ of normal ordering discussions. Yes the moves are ordered in much the same way (I have exceptions that I can explain). But we are talking about the source code to do those things. My move "selection" code is about 500 lines of code, spread over three different modules, used in three different ways (damn, there are actually four, as the q-search uses still another ordering scheme). For functions with a constant input, and a constant output, there are till a near infinite number of ways to write the code inside the function to deliver that functionality.

So it's no good coming in at this level of program structure and saying similarities add up, therefore more and more evidence of copying, because of course these similarities add up. If a programmer read and studied competing source beforehand, Crafty, Fruit, whatever, the similarities will add up even more and quite legally so.

What Zach and CT have presented are not "similarities". They are identical blocks of code. There is a _HUGE_ difference between the two things. Similar functionality would be quite common in chess. Identical lines of code will be incredibly rare.

I think it is Rick Fadden in another thread who describes Strelka having 'identical code' to Rybka, identical functions, identical function calls, same data going in, same data coming out - that sounds like what a copy program would do.

I suspect many have a "GenerateMoves" function. Some names are quite obvious. Probably almost everyone has Search(). And Quiesce(). I have added QuiesceChecks() and QuiesceEvastions(). Others may well have those. Because most of us try to name functions with some sort of relevant name to make the code easier to read. What is more revealing is what is _in_ those functions however. I can only think of a few names to use for such a function as above. GenerateMoves. MoveGenerator. GenerateCaptures/GenerateNoncaptures. GenerateCaptures/GenerateQuietMoves, Given a hundred programs, duplication of names would be expected. But that is all that is expected to be similar. Some names are "high-level or abstract". Search(). score. Evaluate(), ply, depth, draft, MakeMove()/DoMove()/ExecuteMove(). The internals are very low-level with a _very_ low probability of duplication.

Where, in our current case are these identical code fragments? Where are the identical data flows through them?

imo any involved in this campaign should have assembled and proved this data BEFORE opening any threads on the subject. So where is it?

Zach and CT have been providing this. That is what originally caught my eye. And then everyone started this "duplicate code is a frequent thing" discussion. I have read the papers on this written by people at Stanford (among others). I have been grading large and small assignments for 38 years. In the first compiler class I taught, I gave students a detailed algorithm LR(1) for parsing. And even with that detailed starting point, no two were ever the same in terms of a block of code containing 10 lines that were identical. Chess algorithms are not defined that precisely, so the chance of duplication is incredibly small, not "expected" as is being proposed here over and over.

[bob]

Bob,

You ignored the point being made. Dann said that some things are so well known now that everybody does them more or less the same way.

For example, the famous Zach piece of disassembly of Rybka, he chose a chuck of search connected to move ordering. Take a look at your own Crafty, it will be the same or similar. I forget what is optimal ordering, but it will be something similar to this:

1. is there a move from hash to play?

2. try a couple of moves from the killer list

3. try the good captures, sorted SEE/MVLA

4. try the remaining non-captures (sorted by history list)

5. try the losing captures

Nobody tries losing captures first, do they?
Nobody looks at hash second.
Most will use identical move ordering based on the results of tests - which ordering gives overall fastest response. Test results are going to dictate a particular ordering system - everybody can find this independently, and then everybody has similarly structured code at that level.

So it's no good coming in at this level of program structure and saying similarities add up, therefore more and more evidence of copying, because of course these similarities add up. If a programmer read and studied competing source beforehand, Crafty, Fruit, whatever, the similarities will add up even more and quite legally so.

I think it is Rick Fadden in another thread who describes Strelka having 'identical code' to Rybka, identical functions, identical function calls, same data going in, same data coming out - that sounds like what a copy program would do.

Where, in our current case are these identical code fragments? Where are the identical data flows through them?

imo any involved in this campaign should have assembled and proved this data BEFORE opening any threads on the subject. So where is it?

I agree here that most engines use a the same sequence of move ordering. My engine does exactly the same sequence you described above in general (most of the time).

But, to somebody that would disassemble a binary or look at the source of my engine, it looks quite different (and I don't claim the code is any good!!). I took the idea of a nextmove() function from crafty (idea, not code). Then in source it would look like that:

1. Try move from hash, if available and check if legal

2. Try some legal killer moves

3. If in check generate check evasions

4. if in check, pick check evasion with the highest score (MVVLVA scores of check evasion moves are assigned during move generation). If no moves left, we are done.

5. generate captures

6. Try good captures sorted by MVVLVA (assigned during move generation)

7. generate rest of moves

8. Try rest of moves, followed by bad captures sorted by SEE

Therefore, on a more detailed level, or source code level, it looks quite different than other engines. And the closer you look in detail, the more differences you will find in the programming of different engines, because, as Bob stressed out several times, different people just code differently.

e.g. you could split up point number 3 further:

a) Try to capture the figure that gives check to the king
b) Try to move the king out of check
c) Try to move a piece in between the attacking figure and the king

Now, generating check evasion is a very low level function, so a lot of people will probably do it in this order. Others maybe don't have a special function for check evasions at all, I don't know. But how exactly it is coded will never look the same (does the engine use bitboards or not, how many function calls etc, etc).

What I want to point out is, generally speaking, most engines look similarly, but in detail, no engine should look the same as another, with exactly the same functions, etc.

That's the crux of this issue. If you have a giant "zoom lense". When you zoom all the way out, all chess engines look _exactly_ the same. They just play the game of chess. As you zoom in, more details become visible. They have a move generator, one or more search functions. And a few differences between engines begin to show up. The farther in you zoom, the more complex the picture looks, and the more difference you see. By the time you zoom all the way in to the source program level, most programs will be in the 25,000 line and up category, and the differences will be staggering. Some want to barely zoom in and say "all programs look the same." Zach/Christophe are zooming all the way in and saying "these have lots of duplicate code when it is not expected." And others keep saying "but all programs have the same structure when barely zoomed in on, so that is expected."

[bob]

"I took many things" can be interpreted as "I took many ideas".
Depends how you wish to interpret it.

exactly my point, it's one of many interpretations ...

Doesn't this remind you of one of my favorite obscene fortunes from the unix fortune-cookie program (fortune -o):

"Opinions are like assholes. Everybody has one, and nobody wants to look at anybody else's"



everybody looks at simple statements such as the one above, and then uses the most favorable interpretation for their point of view.

[chrisw]

Where, in our current case are these identical code fragments? Where are the identical data flows through them?

imo any involved in this campaign should have assembled and proved this data BEFORE opening any threads on the subject. So where is it?

Zach and CT have been providing this

Have you seen these corresponding code fragments between Fruit and Rybka?

Instead of talking about them, show them.

[Gerd Isenberg]

Where, in our current case are these identical code fragments? Where are the identical data flows through them?

imo any involved in this campaign should have assembled and proved this data BEFORE opening any threads on the subject. So where is it?

Zach and CT have been providing this

Have you seen these corresponding code fragments between Fruit and Rybka?

Instead of talking about them, show them.

As Norman already pointed out:
Comparison of reengineered Rybka 1.0 beta C-source with Strelka by Rick Fadden.

Compare the routines or the Rybka routine it with
static void parse_go(char string[]) {
from Fruit/Toga protocol.cpp you may download at some site.

So that was the UCI-go parser with initialization and control of search. Despite possible license violations, some colleagues and the ICGA might consider this a minor issue - something like using an external GUI.

So far for the additional stuff - it might as well be result of taking ideas in the right order.