Rybka is made out of People! (serious problem exposed)

[rfadden]

There is a problem in Rybka and in this posting I will give supporting information and the required background information so I can then state the problem and then suggest a happy solution to this problem.

I am raising the problem with Node Count (problem described below) and one of the most important factors is that the critical "Event Count" within Rybka occurs only at one location within five separate recursive search subroutines, and so the number of routines and the fact that only one of these routines is "instrumented" is central to this problem. Since this is central to the problem I will list all of the key subroutines within Rybka 1.0 beta and I'll give the hierarchy of calls so the reader can see which module includes the "instrumentation" and which modules include no instrumentation.

Here is a listing of subroutines from Start (program entry point) through all key search and evaluation functions, and note that only the routine named "Full_Search" includes an "Event Count" and this event count is within a specific conditionally executed location within this module, which means that the problem is even worse than you might think from an initial quick look.

* == Recursive (calls itself)

Start ->
Init_for_Commands ->
Command_Interpretter

Command_Interpretter ->
Start_Go ->
Start_Search

Start_Search ->
Full_Root_Base ->
Full_Root


Full_Root ->
*Full_Search
*Full_Check_Search
*Full_PV_Search
Move_Do
Evaluate
SEE_Move
Move_Undo
GetTickCount
fprintf

*Full_Search -> <<<Instrumented only within a conditional>>>
*Full_Search
*Full_Check_Search
*Full_PV_Search
*Qu_Search
GetTickCount
Move_Do_Null
Move_Do
Next_Move
Evaluate
Trans_Move_Store
Trans_Max_Store
Move_Undo
SetJump_Return
Search_Check

*Full_Check_Search ->
*Full_Check_Search
*Full_Search
*Qu_Search
Gen_Evasions
Move_Do
Evaluate
Trans_Min_Store
Trans_Move_Store
Trans_Max_Store
Move_Undo

*Full_PV_Search ->
*Full_PV_Search
*Full_Search
*Full_Check_Search
*Qu_Search
Gen_Evasions
Move_Do
Next_Move
Evaluate
SEE_Move
Trans_Move_Store
Trans_Max_Store
Trans_Min_Store
History_Store
Trans_Store
Move_Undo

*Qu_Search ->
*Qu_Search
*Qu_Check_Search
Gen_Captures
Gen_Checks
Move_Do
Evaluate
Eval_Mobility
SEE_Move
Move_Undo

*Qu_Check_Search ->
*Qu_Check_Search
*Qu_Search
Gen_Evasions
Move_Do
Evaluate
Move_Undo

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

In a chess playing program, the term "Node Count" generally means the number of chess positions considered during the search of the tree of moves.

Rybka does not count Nodes, it does not include a tally of the nodes that it encounters during search.

Rybka instead counts how many times it calls "Trans_Max_Store" within the recursive "Full_Search" subroutine. Most importantly note that there are FIVE Recursive search subroutines which we can name 1) Full_Search, 2) Full_Check_Search, 3) Full_PV_Search, 4) Qu_Search, and 5) Qu_Check_Search, and note that only one of these subroutines includes the code that increments the internal count of "entities" being counted. There is only one location in the program where the Entity Count is incremented (and that is a very rarely executed location within the program).

There is no other node counting or estimating in the program. No other tally of the number of times something is occurring. When Rybka prints out a "Node Count" or a "Nodes Per Second" value the number printed is simply a perturbed version of this rare Entity Count.

So note again, the entity being counted is the number of times that a Maximum is stored in the Transposition Table, and note that this count is only performed within just one of the five recursive search routines: "Full_Search." So note that Trans_Max_Store is also invoked within the recursive search subroutine called Full_Check_Search, but within this module there is no Entity Count update code.

The above described Entity Count is a very low count that does not represent the number of nodes searched by Rybka.

To emphasize this point, here is the calculation used to produce an estimate of Nodes encountered.

Keep in mind that two dwords are used to contain the entity count which are labeled "nodeTickHigh" and "nodeTickLow". One detail which must be explained is that the nodeTickLow is used in a count down mode, not count up. This detail is important because some low order bits of nodeTickLow are used in a tricky way (described below) and in order to understand the calculation the reader must understand that this set of bits starts with the value 1024 and each time that EntityCount is "bumped" this value is actually decremented. When this decremented value hits zero then at that time the high order bits in "nodeTickHigh" are incremented, and the low order bits in "nodeTickLow" are then reset back to 1024 in order to continue counting down.

Initialization Time:
nodeTickHigh = 1;
nodeTickLow = 1024;

Entity Count Time:
nodeTickLow = nodeTickLow - 1;
if (nodeTickLow == 0) {
nodeTickHigh = nodeTickHigh + 1;
nodeTickLow = 1024;
}


Final Obfuscated Event Count Calculation:

entityCount = (nodeTickHigh << 10) - nodeTickLow;

badNodeCount = (entityCount << 3) | (nodeTickLow & 0xF);


That's it! That is the "very low information content" obfuscated and "munged" node count value of Rybka.


So going over this calculation carefully again, and describing it in words, a very low and strange tally of Trans_Max_Store occurrances (tallied only within one of the recursive search subroutines) is then munged as follows: First the above entityCount is correct. Shift the high count up ten bits and subtract the low count, and this is correct.

Then the following line to turn this into nodeCount is a very strange attempt at obfuscation. Essentially take entityCount and multiply by 8 and then "sort of" randomly change the four low order bits of this nodeCount by "OR"ing in the low four bits of the "counting down" nodeTickLow value.

What this does is it gives the obfuscated nodeCount some "made up" low order bits to hide the fact that the number produced just starts out as entityCount * 8. Note if the calculation were simply left as entityCount * 8 then the user of Rybka would be able to notice that the obfuscated node count always varies by multiples of 8.

--------

So in Rybka the "nodeCount" numbers that we have been seeing are simply a very strange and low valued Entity count that does not reflect the number of nodes encountered during search.

Also note that the "NPS - Nodes Per Second" result that is output is a calculation based upon the above obfuscated nodeCount number. In other words NPS from Rybka is the direct Obfuscated Node Count, or Obfuscated Scaled Event Count per Second.

--------

Also note that whenever Depth is displayed by Rybka, a very simple further obfuscation is performed, the number displayed to the user is (depth - 2).

So in other words the display also includes the following:

obfuscatedDepth = depth - 2;

The user is only shown this obfuscatedDepth.

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

I have known the above information for two years. I didn't want to expose this information because I didn't want to cause any sort of trouble. When Rybka 1.0 beta was created, the author apparently wanted to hide the fact that it is a fast searcher with a fast evaluation routine and with nothing included which might slow evaluation. Due to really good search techniques, roughly it seems that Rybka was searching two ply deeper than many other engines. This deeper search combined with a decent and fast eval led to phenomenal success.

I noted back two years ago that the first person who mentioned this "inside knowledge" (fast searcher) was Anthony Cozzie (He mentioned this in the forums, and I saw this after I also had discovered this Obfuscation in the binary code.) I learned all of the above by looking at the machine code of the program and my guess is that Anthony also took a look and he discovered the same thing.

Back then all I had to do is look for the strings which are used for the "info display" and then note where these strings are referenced by the code. Right there at that spot in the code is where the Obfuscated Event Count is calculated. Assembly language programmers have no problem in figuring out the calculation.

At the time (something like January 2006) when Rybka was on version 1.01 beta I thought that releasing the above information might make the author upset with me. I was roughly hoping that this problem would be fixed along the way.

My feeling is that since the big Splash of the Rybka 1.0 beta achievement the author of the program has not been able to change his program to include an actual node count because this likely would call too much attention to his original attempt at Obfuscation.

Hey, by the way, the attempt at Obfuscation did work. People all along have been thinking that Rybka used some sort of Ultra Smart and Slow technique, and no as it turns out Rybka was always an efficient, lean, fast, and deep searcher (with sound search techniques and sound evaluation).

So the above Obfuscation has lasted long enough. In my opinion it is time for the above information to come out, and it is time for Rybka to change and to start telling the truth.


I was an early Rybka customer, I bought the version 1.0x, etc., and these past years of using the program I have known all along that Rybka does not give a Node Count, it does not give NPS, and it does not properly report Depth. Now that the secret is out, Rybka needs to be changed. Future versions should include a proper calculation and a proper display of Node Count, NPS, and Depth.

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

This is the Internet, man! I have been around since the beginning and so I know that there will be people who "defend" Rybka or Vas, and so before we get started with any strange and typical interactions, note that I can prove all of the above. I can give the assembly language code and give the binary of this code and give the addresses where the code appears and in your own copy of Rybka you can see these same bytes, this same code. Vas knows that what I am writing above is true and so I wouldn't expect him to put any effort into denying the above.

To clear up any doubt, I will offer a few opinions here to help balance this situation and to help put this into perspective: I think that Rybka is a fantastic work of art. Rybka is my favorite program of all time and Vas I think is a tremendous guy. Vas is brilliant, he is a great chess player and I also thoroughly enjoyed listening to him on Chess.FM during the human World Championship for example. His comments seem understated and modest and during the extended interview with him on this digital radio station he always downplayed the significance of the algorithms and techniques within these versions of Rybka. When asked about the secrets of Rybka he roughly said that Rybka just had some modest improvements to the known techniques. From what I read, Vas never made large claims about the internal techniques that were used. On the other hand he did continue to hide the fact that Rybka is a fast searcher, and the above strange obfuscation code that is in every version of Rybka will end up being an eyesore until the time that this calculation is corrected.

In the mean time note that there is a version of Rybka available which reports a correct node count and NPS during search, and this program is called Strelka (a pure reverse engineering of Rybka 1.0 beta). I walked through almost every important line of Strelka 2.0 source code and verified that every single constant and every single calculation is exactly matched by the binary code of Rybka 1.0 beta. In a following note I will list the four minor modifications that are in Strelka 2.0 that are not in Rybka 1.0 beta, and also there is one modest Rybka 1.0 technique that was apparently removed from Strelka prior to it's source being released.


Right now you can use Stelka to show you the actual Node Counts and the actual NPS of Rybka 1.0. Like I said, every source line of Strelka is seen in the binary code of Rybka 1.0 beta. There is absolutely no doubt that Strelka is near perfect implementation of early Rybka. Every constant in the Rybka binary appears in Strelka source and every single calculation in the Rybka binary appears in Strelka, with every calculation in exactly the right place (except for two minor "blips" which I will write about next).

I have been working on computer chess programs since 1978 so I am not a beginner in this field.

Keep in mind that all along the key appeal of Rybka for me has been to somehow find out what kind of internal magic led to the fabulous success of this program. I am very pleased, very happy now that I have seen the internals and I have seen how the program works.

As I said, Rybka to me is a work of art, and unfortunately this wonderful creation has a "blob" of "bad stuff" stuck on it that needs to be removed. Take the Obfuscation code out of Rybka and it will then become even more pure of an example of art.

Think of the Mona Lisa with a glob of "poo" thrown onto it's surface. What would happen if we got used to this glob of poo being part of this piece of art? People who appreciate this art should request that the glob of poo be removed from Rybka. We need and want pure Rybka without the ugly and smelly glob of Obfuscation logic in the Node Count, NPS, and Depth displays.

In fact I want to see new releases of the old versions with the "poo" removed and I would like to see everyone change over to the corrected versions of this program.

I like Rybka version 1.2f for example, and I want a corrected version of Rybka 1.2f.

Sincerely,
Rick

[wgarvin]

Maybe this post would be better in the Rybka forums? I don't think Vas comes here much, if at all.

Also... it seems to me that since Rybka is a closed-source commercial program, if you don't like the way it works (e.g. obfuscating its node count) then your only real recourse is to not buy it. It is worthwhile to support open-source engines instead, since you will then have more freedom in how you use them, than you do with Rybka.

[CRoberson]

I'll be brief by comparison.

There are many reasons to obfuscate node count or anything else.
Some good and some bad.

I'll address the random manipulation of low order bits in the node count.
What a great way to tell if somebody has cloned your program.


I guess one man's problem is another man's feature.

[sje]

Is it a related issue that Rybka clones do not (in my experience) offer any kibitz comments in server play?

Shouldn't program kibitz output be required in program vs program during server play? Symbolic always does kibitz in these cases, and it does whisper as well when playing vs humans.

[rfadden]

In a nutshell, Rybka does not have a node count! Really!

The thing being counted is not nodes and it is not even close. When Rybka takes that number and multiplies by 8 then what is produces is a very LOW number compared to what the program is actually doing.

Rybka is a very fast searcher and this Obfuscated number is trying to tell exactly the opposite story.

[Bill Rogers]

Well Rick, you can take any of the top 10 programs and make them play exacty the same game and you know what the node counts on most of them will not be the same. Not everyone counts nodes in the same way no matter what you may think is the right and only way to do it. I am pointing this out as a fact because of your ranting against Rybka.
In other words "who cares".
Bill

[Chan Rasjid]

Well Rick, you can take any of the top 10 programs and make them play exacty the same game and you know what the node counts on most of them will not be the same. Not everyone counts nodes in the same way no matter what you may think is the right and only way to do it. I am pointing this out as a fact because of your ranting against Rybka.

The "standard" common-sense way of counting nodes is to count the calls to makemove(). Then a high nps reflects a program is a "fast searcher" which also generally mean a simpler evaluation.

I think it is interesting now to know Rybka relies more on search techniques than on evaluation.

Rasjid

[Harald Johnsen]

In a nutshell, Rybka does not have a node count! Really!

The thing being counted is not nodes and it is not even close. When Rybka takes that number and multiplies by 8 then what is produces is a very LOW number compared to what the program is actually doing.

Rybka is a very fast searcher and this Obfuscated number is trying to tell exactly the opposite story.

You showed that he is counting 'cut' nodes, you can not tell that this has nothing to do with node count. Perhaps that this count is more interesting for the coder than for the user.

HJ.

[Matthias Gemuh]

You showed that he is counting 'cut' nodes, you can not tell that this has nothing to do with node count. Perhaps that this count is more interesting for the coder than for the user.

HJ.

You mean that the obfuscation of a cut node count and the hiding of true search depth may be beneficial for programmer ?

Matthias.

[rfadden]

Based upon one comment here I did go over to the Rybka Chess Community Forum and there I explained that it had been suggested that I post the information at that location. After an intro I posted the same text...

Over there I'm getting some pretty interesting further thoughts from the community.

Some people seem to say "Shhh be quiet, this is a bookstore and I am reading..." and I respond... "What the hey?" to that!

Hey, this is not a bookstore or a library and I am expressing something that is important to me so no I don't think I am going to "shush." I think I am going to stick with expressing myself naturally...

Ha!