Strelka Reverse Engineered from Rybka: Details Examined

[rfadden]

In this thread I start by giving examples that show how Strelka is reverse engineered from Rybka.

There was discussion in a thread titled "Strelka 2.0" in the General Topic section, and people mentioned that they want to see some proof, so this is the thread were I will be writing and beginning this process.

This will take a while.

---------------

Looking at the subroutines of Rybka 1.0 Beta, they start off (using my names), from low memory locations on up, as follows:

Code: Select all

Mem_Fill_X                .text 00401000 00000077 R . . . . . . 
Mem_Fill_Y                .text 00401080 00000077 R . . . . . . 
Init_Board                .text 00401100 0000046E R . . . B . . 
Eval_Mob                  .text 00401570 00000800 R . . . . . . 
Evaluate                  .text 00401D70 00001718 R . . . B . . 
Board_From_Fen            .text 00403490 0000012F R . . . . . . 
Gen_Captures              .text 004035C0 00000FCC R . . . B . . 
Gen_Checks                .text 00404590 000019B0 R . . . . . . 
Gen_Evasions              .text 00405F40 00000FD6 R . . . B . . 
Gen_Quiet_Moves           .text 00406F20 00000EE2 R . . . B . . 
Move_Is_Legal             .text 00407E10 0000059D R . . . . . . 
Mem_Fill_A                .text 004083B0 000000FA R . . . . . . 
Mem_Fill_B                .text 004084B0 000000BB R . . . . . . 
Board_Init_MaskingA       .text 00408570 000005D5 R . . . . . . 
Board_Init_MaskingB       .text 00408B50 000005CA R . . . . . . 
Assembly_Bit_Search       .text 00409120 00000019 R . . . . . . 
Init_Console              .text 00409140 00000074 R . . . . . . 
Init_for_Commands         .text 004091C0 000000DD R . . . . . . 
Init_SomethingA           .text 004092A0 00000037 R . . . . . . 
Parse_Position            .text 004092E0 0000008D R . . . B . . 
Send_Best_Move            .text 00409370 000001AB R . . . . . . 
Start_Go                  .text 00409520 00000388 R . . . . . . 
Search_Check              .text 004098B0 00000082 R . . . . . . 
Command_Interpretter      .text 00409940 000003B4 R . . . . . . 
Move_Do_Castle            .text 00409D00 00000249 R . . . . . . 
Move_Undo_Castle          .text 00409F50 000001BD R . . . . . . 
Move_Do                   .text 0040A110 00000665 R . . . B . . 
Move_Undo                 .text 0040A780 000002C3 R . . . . . . 
Move_Do_Null              .text 0040AA50 0000009C R . . . . . . 
Move_From_String          .text 0040AAF0 000000A7 R . . . . . . 
Hash_Table_Proc           .text 0040ABC0 0000033B R . . . . . . 
Next_Move                 .text 0040AF00 0000025E R . . . . . . 
History_Store             .text 0040B180 00000034 R . . . . . . 
Trans_Min_Store           .text 0040B1C0 000000AD R . . . . . . 
Pawn_Get_Info             .text 0040B270 00000A23 R . . . . . . 
Start_Search              .text 0040BCA0 000004D9 R . . . B . . 
Full_Search               .text 0040C180 000005B3 R . . . . . . 
Full_Check_Search         .text 0040C740 0000022D R . . . B . . 
Full_PV_Search            .text 0040C970 000004C2 R . . . . . . 
Qu_Search                 .text 0040CE40 00000364 R . . . B . . 
Qu_Check_Search           .text 0040D1B0 00000202 R . . . B . . 
Full_Root                 .text 0040D3C0 00000585 R . . . . . . 
Full_Root_Base            .text 0040D950 000000CC R . . . . . . 
SEE_Move                  .text 0040DA20 00000808 R . . . . . . 
AllocTransTable           .text 0040E230 00000052 R . . . . . . 
Trans_Clear               .text 0040E290 000000A0 R . . . B . . 
Trans_Store               .text 0040E330 000000EF R . . . . . . 
Trans_Move_Store          .text 0040E420 000000E9 R . . . . . . 
Trans_Logic               .text 0040E510 000000D1 R . . . . . . 
Trans_Max_Store           .text 0040E5F0 000000D1 R . . . . . . 
Get_off_663000            .text 0040E6C1 00000006 R . . . . . . 
Enter_Critical_Section    .text 0040E798 0000002F R . . . . . . 
Unknown_Critical_SectionB .text 0040E83C 000000F4 R . . . . . . 
Malloc                    .text 0040EA17 000000C3 R . . . . . . 
Strstr                    .text 0040EAE0 00000086 R . . . . . . 
Unknown_Strstr_related    .text 0040EB80 000000BE R . . . . . . 
Call_UnknownA             .text 0040EC3E 00000011 R . . . . . . 
atoi                      .text 0040EC4F 00000005 R . . . . . . 
Unknown_Critical_SectionA .text 0040EC54 0000017C R . . . . . . 
strtok                    .text 0040EDDB 000000BF R . . . B . . 
Printf                    .text 0040EE9A 0000009C R . . . . . . 
Exit_0_                   .text 0040F1DB 00000011 R . . . . . . 
LongJump                  .text 0040F268 000000AD R . . . B . . 
start                     .text 0040F534 0000000A R . . . . . . 
Small_unknown_calls_Sleep .text 0040F77E 00000040 R . . . . . . 
Init_Pawn_Table           .text 00413B60 0000007A R . . . . . . 
Special_Init              .text 004176A0 0000002B R . . . . . . 
RtlUnwind                 .text 00417872 00000006 R . . . . . . 
Shift_Right_Double        .text 00417880 0000001F R . . . . . . 
Shift_Left_Double         .text 004178A0 0000001F R . . . . . . 
nullsub_1                 .text 004178BF 00000001 R . . . . . . 
Setjmp                    .text 00417940 0000007B R . . . . . . 

Look at the above list of functions. These are all labeled by use of Strelka. Strelka has this same code. These module names are from Strelka, except for possibly 8 or 9.

So almost all of these function labels came from Strelka. I matched up the code with Strelka and so many details line up so perfectly. Examples of a slight difference are "Mem_Fill_X", and "Mem_Fill_Y" where Rybka initializes a few things differently than Strelka 2.0.

Starting from the top of the list I looked down and I decided to start by picking a function that would be a pure or near-pure rip-off of Rybka.

Just now I took another look at Gen_Captures

My first example is from Gen_Captures because there is an easy to understand chunk of code near the bottom of this function that has a lot of constants in it. One of the things that I mentioned to people is that "all of the constants line up", that is you look in the binary and you see constants and you look in Strelka and you see exactly the same constants, in the same location.

So in Strelka source look at the bottom of Gen_Captures and you see this:

Code: Select all

    if ((to = Board->ep_square) != 0) {
      mask_to = ((&#40;Board->mp&#91;BlackPawn&#93;) >> 9&#41; & 0x007F7F7F7F7F7F7F&#41; & (&#40;unsigned __int64&#41;1 << to&#41;;
      if &#40;mask_to != 0&#41; &#123;
        from = to + 9;
        list->move = &#40;from << 6&#41; | to | FlagEnpassant;
        &#40;list++)->score = 22;
      &#125;
      mask_to = ((&#40;Board->mp&#91;BlackPawn&#93;) >> 7&#41; & 0x00FEFEFEFEFEFEFE&#41; & (&#40;unsigned __int64&#41;1 << to&#41;;
      if &#40;mask_to != 0&#41; &#123;
        from = to + 7;
        list->move = &#40;from << 6&#41; | to | FlagEnpassant;
        &#40;list++)->score = 22;
      &#125;
    &#125;
  &#125;
  list->move = 0;
&#125;

And the original code in Rybka looks like this:

Code: Select all

.text:004044E9 loc_4044E9:                             ; CODE XREF: Gen_Captures+EDF
.text:004044E9                 cmp     Board_ep_square, 0
.text:004044F0                 jz      loc_40457F
.text:004044F6                 mov     ecx, Board_ep_square
.text:004044FC                 mov     eax, 1
.text:00404501                 xor     edx, edx
.text:00404503                 call    Shift_Left_Double
.text:00404508                 mov     ecx, eax
.text:0040450A                 and     ecx, [esp+40h+var_28]
.text:0040450E                 mov     [esp+40h+var_18], eax
.text:00404512                 mov     eax, edx
.text:00404514                 and     eax, edi
.text:00404516                 and     ecx, 7F7F7F7Fh
.text:0040451C                 and     eax, 7F7F7Fh
.text:00404521                 or      ecx, eax
.text:00404523                 jz      short loc_404546
.text:00404525                 mov     eax, Board_ep_square
.text:0040452A                 lea     ecx, [eax+9]
.text:0040452D                 shl     ecx, 6
.text:00404530                 or      ecx, eax
.text:00404532                 or      ecx, 4000h
.text:00404538                 mov     [esi], ecx
.text:0040453A                 add     esi, 4
.text:0040453D                 mov     dword ptr [ebx], 16h
.text:00404543                 add     ebx, 4
.text:00404546
.text:00404546 loc_404546:                             ; CODE XREF: Gen_Captures+F63
.text:00404546                 mov     eax, [esp+40h+var_18]
.text:0040454A                 and     eax, [esp+40h+var_10]
.text:0040454E                 and     edx, [esp+40h+var_C]
.text:00404552                 and     eax, 0FEFEFEFEh
.text:00404557                 and     edx, 0FEFEFEh
.text:0040455D                 or      eax, edx
.text:0040455F                 jz      short loc_40457F
.text:00404561                 mov     eax, Board_ep_square
.text:00404566                 lea     edx, [eax+7]
.text:00404569                 shl     edx, 6
.text:0040456C                 or      edx, eax
.text:0040456E                 or      edx, 4000h
.text:00404574                 mov     [esi], edx
.text:00404576
.text:00404576 loc_404576:                             ; CODE XREF: Gen_Captures+7EA
.text:00404576                 mov     dword ptr [ebx], 16h
.text:0040457C                 add     esi, 4
.text:0040457F
.text:0040457F loc_40457F:                             ; CODE XREF: Gen_Captures+747
.text:0040457F                                         ; Gen_Captures+7D4j ...
.text:0040457F                 pop     edi
.text:00404580                 mov     dword ptr [esi], 0
.text:00404586                 pop     esi
.text:00404587                 pop     ebx
.text:00404588                 mov     esp, ebp
.text:0040458A                 pop     ebp
.text:0040458B                 retn
.text:0040458B Gen_Captures    endp

These chunks of code are identical. (The assembler looks better on the screen because it is colorized and numeric constants stand out in green).

In a next posting I'll start at the top of Gen_Captures, but in this first example I want show show the assembler that's relatively easy to read and most importantly, every shift operation exactly matches, every number added exactly matches, the masks exactly match, the local variables of the subroutine match, and the references to the Board structures and global variables exactly match.

This C code was derived from this Assembly code.

In the Assembler Listing:

First the global "Board->ep_square" is tested versus 0
And then inside the conditional, a "1" is loaded into one 32 bit register and a "0" is loaded into the other and then the function "Shift_Left_Double" is called to shift this 64 bit number (which happens to be 1) to the left by an amount equal to "Board->ep_square".

The term "Board->mp[BlackPawn]) >> 9" comes in from "var_28" and if you look at the Strelka C you see this term being used in the lines of code above, and in Rybka you see this same reference. In the previous code this term was calculated and saved, then used here.

This value is then used in a bitwise AND with "0x007F7F7F7F7F7F7F". This is shown being loaded into two 32 bit words in the assembly language.
The result of this masking is tested and if it is not zero then 9 is added to the "to" field, this is then shifted left 6, and OR with "to" is performed, and then this is ORed with "FlagEnpassant" which is 4000h. Then 4 is added to a register which is the "list++" operation and this is then used with an offset to store "22" into the "score" field of this structure. Note that Rybka includes the constant 16h (hex) which is is 22 (decimal).

Keep looking at the assembly language. Note that this process of exact matching continues. Every operation matches. Just to hit some highlights, you see the exact Bit Mask "0x00FEFEFEFEFEFEFE" in the assembly, and you see the adding 7, the shift left 6, everything exactly matches.

So an assembly language expert with some time to study this and all of the code above this in "Gen_Captures" sees the assembly exactly matches the Strelka C and as the example above shows all of these picky and exact constants, all appear in exactly the proper place.

One of these programs preceeded the other. One is a reverse engineered version of the other. Rybka was first.

This is getting long and I will continue giving examples in the next posting, tomorrow.

Big Picture Summary: All of the code above matches, all of the code below matches, everything matches (with some exception, but the amount of material that matches exactly is stunning).

this is just the first post. Continuing...

[Guetti]

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.

[Aleks Peshkov]

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?

[rfadden]

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

[CThinker]

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]

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.

[Uri Blass]

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]

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.

[Guetti]

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]

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