Strelka Reverse Engineered from Rybka: Details Examined

Discussion of chess software programming and technical issues.

Moderators: hgm, Dann Corbit, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
CThinker
Posts: 388
Joined: Wed Mar 08, 2006 9:08 pm
Contact:

Re: Strelka Reverse Engineered from Rybka: Details Examined

Post by CThinker » Thu May 01, 2008 3:26 pm

Guetti wrote:Not a very good example, in my opinion. Move generation routines are not very useful for this comparision. I'm pretty sure my gencaptures code matches 95% the one of crafty, as does almost every bitboard engine on the planet. My code for EP generation looks different, but this is shear luck.
If you examine the code again, you will realize that it puts scores as the moves are being generated. Do you know a lot of engines that do that?

Of those very few engines that put scores during move generation, how many of them give a score of 22 for ep capture?

I think this is a unique combination of code. I have to say that Rick has made a good choice on the section of code to demonstrate that Rybka and Strelka are identical.

Michael Sherwin
Posts: 3196
Joined: Fri May 26, 2006 1:00 am
Location: WY, USA
Full name: Michael Sherwin

Re: Strelka Reverse Engineered from Rybka: Details Examined

Post by Michael Sherwin » Thu May 01, 2008 3:29 pm

Hi Rick,

I applaud your effort!

There is nothing wrong with being on a crusade to prove an important truth.

However, the gist of what Juri wrote (about the creation of Strelka) is that he wanted to show the world that Vas did a rewrite of Fruit into bitboards.

So, I imagine that Juri used the code of Fruit and the binary of Rybka to match the functions, the best he could, in an attempt to prove his point.

What the chess programming community, IMO, would be more interested in is, how well did Juri prove his point!

If Juri is indeed correct then we need to decide upon the morality of how Rybka was created.

I for one, think that as soon as the code for Fruit was released it became a 'starting point' for anyone to write (not copy) a chess program. It is no different then if Fabien wrote a very detailed book on chess programming that was closely followed to create a new chess program which was then improved before release. I agree with Fabien that Strelka is not a clone of Fruit and by extention, Rybka is not then a clone of Fruit.

If Strelka is a backward engineered Rybka then that just shows that Juri was telling the truth (at least in one post) about why he created Strelka. He was also on a crusade! And maybe he just wanted the morality of Rybka discussed.
If you are on a sidewalk and the covid goes beep beep
Just step aside or you might have a bit of heat
Covid covid runs through the town all day
Can the people ever change their ways
Sherwin the covid's after you
Sherwin if it catches you you're through

Uri Blass
Posts: 8942
Joined: Wed Mar 08, 2006 11:37 pm
Location: Tel-Aviv Israel

Re: Strelka Reverse Engineered from Rybka: Details Examined

Post by Uri Blass » Thu May 01, 2008 3:37 pm

Guetti wrote:Not a very good example, in my opinion. Move generation routines are not very useful for this comparision. I'm pretty sure my gencaptures code matches 95% the one of crafty, as does almost every bitboard engine on the planet. My code for EP generation looks different, but this is shear luck.
Here is my generation of pawn captures left. I'm pretty sure, in assembly it will look the same as most of the others.

Code: Select all

cap_left = (&#40;pieces & ~0x0101010101010101ULL&#41; << 7&#41; & ppos.mbAllPieces&#91;stm^1&#93;;
while &#40;cap_left&#41;
	&#123;
		targetsq = FirstOne&#40;cap_left&#41;;
		fromsq = targetsq - pawn_capL&#91;stm&#93;;
		captured = abs&#40;ppos.mBoard&#91;targetsq&#93;);
		if &#40;Rank&#40;targetsq&#41; == promo_rank&#91;WHITE&#93;)
		&#123;
			for &#40;int j = 5; j > 1; j--) &#123;
				Allmoves&#91;mvnos&#93;.move = set_move&#40;fromsq, targetsq, PAWN, captured, j, 0&#41;;
				Allmoves&#91;mvnos&#93;.sval = j*100;
				mvnos++;
			&#125;
		&#125; else &#123;
			Allmoves&#91;mvnos&#93;.move = set_move&#40;fromsq, targetsq, PAWN, captured, 0, 0&#41;;
			Allmoves&#91;mvnos&#93;.sval = 0;
			mvnos++;
		&#125;
		cap_left &= clear_mask&#91;targetsq&#93;;
	&#125;
One thin that strikes me in you code is:

list->move = (from << 6) | to | FlagEnpassant;

This is exactly the move format of Fruit.
I for example do

list->move = from | (to << 6) | etc....
Because I found it more logical.
I do not believe that the move capture generator of almost every bitboard program is the same or almost the same.

The move generator of strelka generates captures in the following order:

1)Captures by knights
2)Captures by bishops
3)Captures by rooks
4)Captures by Queens
5)Captures by the king
6)promotions
7)promotions that are also captures
8)Captures by pawns.

I do not think that this order is the most logical order and if rybka has the same order then it is clearly an evidence for reverse engineering.

Uri

Guetti

Re: Strelka Reverse Engineered from Rybka: Details Examined

Post by Guetti » Thu May 01, 2008 3:58 pm

Uri Blass wrote: The move generator of strelka generates captures in the following order:

1)Captures by knights
2)Captures by bishops
3)Captures by rooks
4)Captures by Queens
5)Captures by the king
6)promotions
7)promotions that are also captures
8)Captures by pawns.

I do not think that this order is the most logical order and if rybka has the same order then it is clearly an evidence for reverse engineering.

Uri
Sorry, but Crafty generates the moves in exactly the same order.
I do it the same in my engine. Why? The order can effect search efficiency, and since I read once Bob tested this, I simply chose the same order than him. Why invent the wheel from scratch?

Now, it is not my goal to defend a cloner, but I think you have to come up with better things for prove.
Last edited by Guetti on Thu May 01, 2008 4:09 pm, edited 2 times in total.

Guetti

Re: Strelka Reverse Engineered from Rybka: Details Examined

Post by Guetti » Thu May 01, 2008 4:05 pm

CThinker wrote:
Guetti wrote:Not a very good example, in my opinion. Move generation routines are not very useful for this comparision. I'm pretty sure my gencaptures code matches 95% the one of crafty, as does almost every bitboard engine on the planet. My code for EP generation looks different, but this is shear luck.
If you examine the code again, you will realize that it puts scores as the moves are being generated. Do you know a lot of engines that do that?

Of those very few engines that put scores during move generation, how many of them give a score of 22 for ep capture?

I think this is a unique combination of code. I have to say that Rick has made a good choice on the section of code to demonstrate that Rybka and Strelka are identical.
BY the way, if you looked at my code I posted above, yes, I do assign a score during move generation (and have done before Strelka).
Of course you are correct with the score of 22, but this I counted to the other 5%, that's why I wrote 95% identical. Now if you're looking at fine differences like that, I have absoluteley no objection, that are indeed clues, but Ricks approach was that the general structure looks the same. And this will be true for a lot of bitboard engines.

Uri Blass
Posts: 8942
Joined: Wed Mar 08, 2006 11:37 pm
Location: Tel-Aviv Israel

Re: Strelka Reverse Engineered from Rybka: Details Examined

Post by Uri Blass » Thu May 01, 2008 5:08 pm

Guetti wrote:
Uri Blass wrote: The move generator of strelka generates captures in the following order:

1)Captures by knights
2)Captures by bishops
3)Captures by rooks
4)Captures by Queens
5)Captures by the king
6)promotions
7)promotions that are also captures
8)Captures by pawns.

I do not think that this order is the most logical order and if rybka has the same order then it is clearly an evidence for reverse engineering.

Uri
Sorry, but Crafty generates the moves in exactly the same order.
I do it the same in my engine. Why? The order can effect search efficiency, and since I read once Bob tested this, I simply chose the same order than him. Why invent the wheel from scratch?

Now, it is not my goal to defend a cloner, but I think you have to come up with better things for prove.
I did not look much at Crafty's code so I did not check the order that it generates captures but I see no reason to generate promotion after generating capture by small pieces.

You want the best move to be generated first because it can save you time later when you do not need to change order of moves in the move list when you pick first move to search.

A Capture that is a promotion is the best candidate to be generated first because it is probably better than other captures.

Uri

Guetti

Re: Strelka Reverse Engineered from Rybka: Details Examined

Post by Guetti » Thu May 01, 2008 5:21 pm

I don't know how others do it, but I assign them a score depending on the promoted piece, which makes them end up at the correct place during movesorting. This way I can generate the promotions together with the other pawn moves.

Dann Corbit
Posts: 12000
Joined: Wed Mar 08, 2006 7:57 pm
Location: Redmond, WA USA
Contact:

Re: Strelka Reverse Engineered from Rybka: Details Examined

Post by Dann Corbit » Thu May 01, 2008 7:03 pm

rfadden wrote:
Aleks Peshkov wrote:
rfadden wrote:In this thread I start by giving examples that show how Strelka is reverse engineered from Rybka.
It is a known fact, that was confirmed by Strelka's author from the very beginning about a year ago. Why should we waste time reading your long posts about reverse engineering of open source code?
The answer is: a few others were saying essentially "Show us the Details" and so as I wrote above I have started doing what these guys are asking.

In your case you don't have to read this.

Doesn't it seem that you have the choice to read or not to read...

Also, people have different interests.

I agree that you don't need to look at this at all. This is not a problem.

Thanks.

I'm continuing... I take the point about gen_captures not being the perfect example, but keep in mind that if we make it to example 89 then by that time you will see so many different routines all with this same pattern. All constants, all function arguments, the order that functions are called, the numeric constants passed to routines, they all come from the Rybka binary... I will continue showing this...

I'll be back
I want to see it. I am particularly interested in:
Things that are in Rybka and in Strelka but not in Fruit and which are unusual.

Uri Blass
Posts: 8942
Joined: Wed Mar 08, 2006 11:37 pm
Location: Tel-Aviv Israel

Re: Strelka Reverse Engineered from Rybka: Details Examined

Post by Uri Blass » Thu May 01, 2008 8:52 pm

Guetti wrote:I don't know how others do it, but I assign them a score depending on the promoted piece, which makes them end up at the correct place during movesorting. This way I can generate the promotions together with the other pawn moves.
I think that captures by pawns should be generated before captures by other pieces because later captures by pawns have better chances to be ordered first.

The order of generating is also important because correct order of generating moves can save sorting later so the logical order is first promotions and after it captures by pawn and only after it captures by knights and other pieces.

Note that I did not test if changing the move ordering in this way cause strelka to become better and it is possible that things are counter intuitive.

Uri

User avatar
michiguel
Posts: 6401
Joined: Thu Mar 09, 2006 7:30 pm
Location: Chicago, Illinois, USA
Contact:

Re: Strelka Reverse Engineered from Rybka: Details Examined

Post by michiguel » Thu May 01, 2008 9:56 pm

Uri Blass wrote:
Guetti wrote:
Uri Blass wrote: The move generator of strelka generates captures in the following order:

1)Captures by knights
2)Captures by bishops
3)Captures by rooks
4)Captures by Queens
5)Captures by the king
6)promotions
7)promotions that are also captures
8)Captures by pawns.

I do not think that this order is the most logical order and if rybka has the same order then it is clearly an evidence for reverse engineering.

Uri
Sorry, but Crafty generates the moves in exactly the same order.
I do it the same in my engine. Why? The order can effect search efficiency, and since I read once Bob tested this, I simply chose the same order than him. Why invent the wheel from scratch?

Now, it is not my goal to defend a cloner, but I think you have to come up with better things for prove.
I did not look much at Crafty's code so I did not check the order that it generates captures but I see no reason to generate promotion after generating capture by small pieces.

You want the best move to be generated first because it can save you time later when you do not need to change order of moves in the move list when you pick first move to search.

A Capture that is a promotion is the best candidate to be generated first because it is probably better than other captures.

Uri
What you say is true if you have the moves in a list and you loop increasing the index to find the best. If you loop decreasing the index (from the end to the start), you will be better off generating promotions last.

Miguel

Post Reply