BB's Rybka/Ippolit comparison

[beram]

Hi Folks,
After reading the complete report, as a logical thinking human being - that is being a non-programmer - there is obvious only one possible conclusion: Ippolit is not a clone of Rybka.
And after reading Ed (Rebel)'s postings - (being the programmer of worldchampion Rebel) - I am only more convinced.

There is only one question left to solve and that's who is BB ? is he Johan de Koning ? Anthony ? or ?....
Anyway BB, on behalf of all the cc-dummies, many thanks for shining your clear light on this murky darkness.

Kind regards from a cc enthousiastic,
Bram Mourik

[Rebel]

Finished reading the BB document. A couple of comments:

1) Different piece-definitions, different promotion, castling, ep definitions. One of the last things a RE programmer will do is to touch this, the work involved + the risk for bugs is extremely high without detailed and precise knowledge what is going on. It's a hint Ippo*.* isn't a clone.

2) Missing in the document: LMR similarities / differences

3) One thing still amazes me, perhaps BB can explain the technical process. How do you know what is what? I assume you took the R3 executable as your starting point, then how do you eventually learn (detect) what is what from the gibberish disassembled machine code. For instance and taken from your document, how do you know this is about castling and not about something totally else? See code below.

4) It's hard for me (although willing) to accept your document as real without understanding how you did the work and came to your conclusions. Not that I want to disparage your work but with so many weird things going on the last year it should be excluded the document is a bad joke, for instance, to change the banned Ippo*.* status.

One thing for sure: you are a chess programmer

Ed

0x482a00: xor %eax,%eax
0x482a02: cmp $0x6,%ecx # if to is G1
0x482a05: mov %eax,2392757(%rip) # 50move = 0
0x482a0b: jne 0x482a84 ###### then do Q-side ooo
0x482a0d: xorq $0xa0,2392584(%rip) # WhOcc ^= F1 | H1
0x482a18: xorq $0xa0,2392637(%rip) # WhRook ^= F1 | H1
0x482a23: xorq $0xa0,2392698(%rip) # Occupied ^= F1 | H1
0x482a2e: xorq $0x9,2392682(%rip) # Right45 ^= F1 | H1
0x482a36: addl $0x5a0000,2392712(%rip) # Static += 90op+0eg
0x482a40: mov %eax,2392310(%rip) # Board[H1] = Empty
0x482a46: mov $0x80008000,%rax
0x482a50: movl $0x8,2392282(%rip) # Board[F1] = WhRook
0x482a5a: xor %rax,2392655(%rip) # Left90 ^= F1 | H1
0x482a61: mov $0x800100000,%rax
0x482a6b: xor %rax,2392614(%rip) # Left45 ^= F1 | H1
0x482a72: mov $0xd8b3287ea544969,%rax
0x482a7c: xor %rax,2392653(%rip) # Hash ^= WRf1 | WRh1
0x482a83: retq ###### below is Q-side
0x482a84: xorq $0x9,2392468(%rip) # WhOcc ^= A1 | D1
0x482a8c: xorq $0x9,2392524(%rip) # WhRook ^ = A1 | D1
0x482a94: xorq $0x9,2392588(%rip) # Occupied ^ = A1 | D1
0x482a9c: xorq $0x201,2392561(%rip) # Left45 ^ = A1 | D1
0x482aa7: xorq $0x10000400,2392558(%rip) # Right45 ^= A1 | D1
0x482ab2: addl $0x820000,2392588(%rip) # Static += 130op+0eg
0x482abc: mov %eax,2392158(%rip) # Board[A1] = Empty
0x482ac2: mov $0x80000080,%eax
0x482ac7: movl $0x8,2392155(%rip) # Board[D1] = WhRook
0x482ad1: xor %rax,2392536(%rip) # Left90 ^= A1 | D1
0x482ad8: mov $0xaaaff37267ceded3,%rax
0x482ae2: xor %rax,2392551(%rip) # Hash ^= WRa1 | WRd1
0x482ae9: retq

[Robert Flesher]

Hi Folks,
After reading the complete report, as a logical thinking human being - that is being a non-programmer - there is obvious only one possible conclusion: Ippolit is not a clone of Rybka.
And after reading Ed (Rebel)'s postings - (being the programmer of worldchampion Rebel) - I am only more convinced.

There is only one question left to solve and that's who is BB ? is he Johan de Koning ? Anthony ? or ?....
Anyway BB, on behalf of all the cc-dummies, many thanks for shining your clear light on this murky darkness.

Kind regards from a cc enthousiastic,
Bram Mourik

I hope you know I was kidding when I stated it was , Johan de Koning. I was just having a bit of fun.

[thorstenczub]

the debates in CCC, in Hiarcs forum and even in the Rybka Forum, told us:
we don't want to allow names and postings of the CLONE PRGs because they are piracy,
clones, support thiefs, etc etc ...

but this is not the truth.

they give a damn shit if these programs are clones or not. that is not in their interest to find out.

the only purpose all this censorship has is to save the interests of commercial programmers.

of rybka, if hiarcs. and in CCC the possible interest of the Shop ICD and the rating list guys need to be in good stand with the programmers and therefore like to censor it.


It was never about cloning or not. it was always about the market and stealing money,
possible money from the commercial programmers.

therefore the whole discussions are a farce.
bob tries to convince them (Mayer, Conkie, Harvey, Banks, Hull, Silver, ...)
but they are not interested what Ippo/Fire... is.

They are interested to care for their special programmer(s) - therefore they censor. delete.
create witch hunts.

IMO it makes no sense to discuss with them. waiting for an apology ? from them ?
they will not do so. why should they.
They only wanted the BEST for their interest groups. this allowed them to throw the first stone.
the best to computerchess.

the best for all of us.
this justifies anything.

[LiquidNitrogen]

There's something else that may have escaped notice.

The writer of this document must have been a published author of an International Computer Games Association Journal article. I've seen this "format" before, and as a 3-time author myself, I recognized it right away.

Compare the layout of the PDF file to these ICGA Journal articles I authored:

http://www.GothicChess.com/80.pdf

http://www.GothicChess.com/7_piece.pdf

I'm just saying, this author was very knowledgeable and an experienced technical writer as well.

[BB+]

No one ever accused Fabien or Bob Hyatt about peeking into the binaries of the earlier top programs like Shredder or Fritz to learn about their workings.

On the other hand, Donninger famously boasted that he got ideas from Shredder via a debugger.

I noticed most of the document is structured: "Rybka does it like this, but IPPOLIT does it like that..', or "Rybka does it like this, while IPPOLIT does...." But at one point author writes: "Rybka has extra bonuses [..... ], but I ignore these". Not IPPOLIT but _I_, the author of the report.

The text in context:

Here I give a random sampling of 10 different configurations. The process in both is the same, to say that a piece ``hits'' the opposing king if a square around it is attacked. There is then a multiplier based upon how many [sic, it looks like a forgot a period here] Rybka has extra bonuses when a piece has an x-ray attack (from a friendly piece) against a square near the enemy king (example: wRa1, wNa2, bPa7, bKb8, so the white rook x-ray attacks the {\tt a7} square), but I ignore these [emphasis added]. Rybka demands that the opponent have a queen on the board to give a penalty, while IPPOLIT does not. All of these values are scaled with the phase. Both only count at most one pawn that attacks the king area. The IPPOLIT values are re-scaled to millipawns.

\begin{table}[h]
\begin{center}
\begin{tabular}{|l|r|r|r|r|r|r|r|r|r|@{\hskip2pt}r@{\hskip2pt}|}\hline
Attackers&N&Q&BQ&RN&QP&QR&RBB&RNP&QBN&QRBP\\\hline
Rybka&0&0&223&400&124&281&711&801&932&1057\\\hline
IPPOLIT&20&50&270&250&200&320&610&450&780&1600\\\hline
\end{tabular}
\end{center}
\end{table}

Note that Rybka also has a deduction when the king has no flee square.

So it seems that the text indicates I ignored the extra Rybka bonuses when making the table. I'm not quite sure how IPPOLIT could ignore the bonuses when making the table?

He concentrated on finding differences between Rybka and Ippolit.

I could agree that this was my concentration, though I also think that I tried to state the facts, and let them lie where they may. If you want similarities, they can be enumerated, but I didn't think that a tit-for-tat totalling of list-counts was the most apropos, given the claims about "cloning". Just for a random "similarity", in Appendix B.3 you can see that both use "move [...] is not a king move, is not ep, or hash-move, does not give check, and bad SEE" as part of a condition for ignoring a move [particularly interesting is the "not a king move" constraint]. Looking (carefully) at the pseudocode here, you can see that the main difference is that Rybka has some extra condition about a captured piece being a pawn, and does a comparison between EVAL and SCOUT (erroneously called SCORE at some points). There are many other instances like this. For instance, both have a similar "SCOUT is big and MOVE can leave to a repetition" check (unique to them, I think), though Rybka varies the "big" here. I think I said, even when posting on the Rybka forum back in January or whenever, that I found it impossible to conceive that the IPPOLIT maker(s) did not know how Rybka worked; but given that the claim was that they were "clones", and that "code" was copied, I chose to emphasize the counter-evidence to this. I would also hope that a careful reading of the report would make it clear that IPPOLIT must have "come from" Rybka in some sense, though not at the level of "code" [as an aside, I tend to agree with Alan Sassler and others that reverse engineering is a legitimate form of discovery].

Compare the layout of the PDF file to these ICGA Journal articles I authored:

Here is the start of my source file:

Code: Select all

\documentclass{article}
\usepackage{marvosym}
\begin{document}
\hyphenation{IPPOLIT}
\hyphenation{Rybka}
[...]

Using LaTeX is not that complicated. Indeed, it almost mandatory in the sciences by now. [I actually knew a philosopher who used it, as they were tired of .doc I guess].

I will address the more technical questions/comments of Whittington and Schröder in a separate post.

[BB+]

2) Missing in the document: LMR similarities / differences

There are some of each. It is a bit confusing because Rybka does not split CUT/ALL nodes into separate functions. In Rybka at CUT nodes, when the phase is ORDINARY moves (that don't give check), the reduction is 6 half-ply until the 12th move, when it increases to 7 half-ply. In IPPOLIT, there is an additional check that a move is not extended, and then the reduction is 4+BSR(4+cnt)) (my correspondence with other programmers actually indicates that the details of ALL node LMR is much more important for strength consideration, and it is almost irrelevant at CUT nodes). For ALL nodes, both start after three moves have been considered, and IPPOLIT is BSR(1+cnt) and Rybka is 2 until the 12th move, when there is an increase to 3.

In tabular form, we have

Code: Select all

        0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 ...
CUT-IPP 6 6 6 6 7 7 7 7 7 7 7 7 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 9 9 ...
CUT-RYB 6 6 6 6 6 6 6 6 6 6 6 6 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 ...
ALL-IPP 0 0 0 2 2 2 2 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 ...
ALL-RYB 0 0 0 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 ...

Of course, the first move is rather unlikely to be an ORDINARY move here (it will be TRANS). Both also have some LMR when in-check, with differences of a comparable size. IPPOLIT treats "exclude" nodes the same as ALL nodes, while Rybka does no LMR at them.

3) One thing still amazes me, perhaps BB can explain the technical process. How do you know what is what?

Take the executable. Run it. Run "gdb --pid X" where X is the process number. Then "disassemble 0x400000 0x500000" (more than enough, usually). Then grep for "call" on the dump of this, to get an idea of where functions start. Do "go infinite", stop a random point, and note where the instruction pointer is. More forwards/backwards from the current subroutine.

After this, it is can be guesswork, or trial/error, or comparison with IPPOLIT and friends. For instance, if a function calls no other functions, there are a limited number of possibilities for it. If it is also doing something with a hash, perhaps it is the pawn-eval function. If a function starts by anding with 0x3f and shifting by 6, it is probably doing something with a move (make/undo or move-is-ok, for instance). If it is passed a stack that gets moves (again noted by their structure with 0x3f and shifts by 6) put into it, it is probably move generation. For search functions, you can note that there is access to the hash table at the start, and they call lots of other functions. I think the castling code given is one of the more easy things to understand. In my daily job, I often have to track/fix bugs of other people (and sometimes myself), so this helps me be more facile about asm code and gdb. Maybe I should also stress that it is a lot of work, with guessing (sometimes wrong, to be corrected by later info) and trial/error prevalent.

Here is the relevant parts of a Rybka CUT/ALL node function (and also the "exclusion" search); I elide various instructions that are irrelevant to the current discussion (and I don't always have this many comments when disassembling).

Function 0x487ac0 (White CUT/ALL node):

Code: Select all

0x00487ad5: sub    $0x918,%rsp      # first figure out what goes into [0x68]
0x00487b78: mov    0x940(%rsp),%eax # move 5th passed argument to function into eax
0x00487b72: xor    %ecx,%ecx        # set ecx as 0
0x00487b7f: mov    %eax,%r10d       # near head of function, determine CUT/ALL/exclude
0x00487b82: shr    $0xd,%r10d
0x00487b86: and    $0x1,%r10d       # is 1 at an ALL node, and 0 at a CUT node
0x00487b8d: mov    %r10d,0x68(%rsp) # put the 13th bit of 5th passed arg into [0x68]
0x00487b9a: test   $0x10,%al        # if 4th bit of 5th passed argument was set
0x00487ba0: je     0x487bad         # Think it is never set, but I would have to check
0x00487ba5: mov    %ecx,0x68(%rsp)  # put 0 into [0x68]
[...]
0x0048890a: cmpl   $0x0,0x68(%rsp)  # next compute size of LMR reduction
0x0048890f: mov    $0x2,%eax
0x00488914: mov    $0x6,%ecx        # will be 6 at CUT node, and 2 at ALL
0x00488919: cmovne %ecx,%eax        # note [0x88] also used in hash, but irrelevant
0x0048893a: mov    %eax,0x88(%rsp)  # [0x88] has size of LMR reduction
[...] # onto the main LMR computation
0x00488cba: cmpl   $0x0,0x938(%rsp) # see if the exclude move (arg 4) is nonzero
0x00488cc2: jne    0x488eac         # if so, then skip LMR
0x00488cc8: mov    0x68(%rsp),%r9d  # 0 if CUT note
0x00488ccd: mov    0x40(%rsp),%edx  # [0x40] is a count of moves tried
0x00488cd1: mov    $0x6,%ecx        # move 6 into ecx
0x00488cd6: lea    0x0(,%r9,4),%eax # put 4+[st0x68] into eax
0x00488cde: sub    %eax,%ecx        # and subtract it from ecx
[...] # some stuff about ignoring the move
0x00488d15: mov    0x920(%rsp),%edi # SCOUT into edi
0x00488d36: mov    0x920(%rsp),%r11d # SCOUT (passed var) into r11
0x00488d3e: cmp    $0x9,%ebx        # compare phase with 9 - ORDINARY MOVES
0x00488d41: je     0x488d51
0x00488d43: cmp    $0x8,%ebx        # compare phase with 8 - ORDINARY MOVES
0x00488d46: je     0x488d51
0x00488d48: cmp    $0x7,%ebx        # compare phase with 7 - all these are the same I think
0x00488d4b: jne    0x488ea7
0x00488d51: test   %r9d,%r9d        # r9 is 0 at a CUT node, 1 at ALL (see 488cc8)
0x00488d54: mov    $0x3,%eax
0x00488d59: mov    $0x0,%r9d
0x00488d5f: cmovne %r9d,%eax        # eax has 3 at ALL, 0 at CUT
0x00488d63: cmp    %eax,%edx        # compare eax to count of moves
0x00488d65: jl     0x488eaf         # skip LMR if move count is low
0x00488d6b: cmp    $0xc,%edx        # compare move count to 12
0x00488d6e: mov    0x88(%rsp),%eax   # size of move reduction into eax
0x00488d75: mov    %eax,%r10d
0x00488d78: jl     0x488d7e
0x00488d7a: lea    0x1(%rax),%r10d  # add one to reduction if move count is 12 or more
0x00488d7e: mov    0x928(%rsp),%edx # depth as a passed variable
0x00488d85: mov    %edi,%eax      # edi has extensions in it (I won't bother with these)
0x00488d87: sub    %r10d,%eax     # subtract LMR from depth
0x00488d8a: add    %eax,%edx      # "new depth", but WITHOUT normal 2 half-ply subtracted
0x00488d8c: cmp    $0x3,%edx      # if depth is 3 or less call qsearch
0x00488d8f: jg     0x488db4
0x00488d91: mov    $0x1,%ecx
0x00488da1: sub    %r11d,%ecx     # put 1-SCOUT into ecx
0x00488da4: xor    %edx,%edx      # set depth to 0
0x00488da6: callq  0x474360       # qsearch
[...]
0x00488db4: cmp    $0x7,%edx      # if depth is 7 or less call low-depth search
0x00488db7: jg     0x488df9 
0x00488dda: mov    $0x1,%ecx
0x00488ddf: add    $0xfffffffffffffffe,%edx # sub 2 from depth (normal reduction)
0x00488de5: sub    %r11d,%ecx      # ecx has 1-SCOUT
0x00488deb: callq  0x4773f0        # low depth
[...]
0x00488e60: mov    $0x1,%ecx
0x00488e65: add    $0xfffffffffffffffe,%edx # subtract 2 half-ply from depth
0x00488e71: mov    %r8d,0x20(%rsp)   # this sets the flags for the recursive CUT/ALL
0x00488e79: sub    %r11d,%ecx       # 1-SCOUT
0x00488e7c: xor    %r9d,%r9d        # no exclude move
0x00488e7f: callq  0x46dea0         # CUT/ALL node
[...]

I might stress that even this a rather big simplifcation, as Rybka has a bunch of parameters (that are not in IPPOLIT) that get compared. My strong conclusion is that Rybka doesn't actually do anything based upon this, though maybe I am wrong (in particular, they might appear in "contempt" or something).

EDIT: I was logged out due to inactivity(?) when composing this. Luckily, I was able to back-up in the browser and recover it.

[BB+]

Firstly, congratulations on a fine report - the whole computer chess community should be grateful to you for it.
Reading the report quickly at first (I like to do this to get a 'feeling'), gave me two feelings
a) that from a top-down perspective both programs were quite similar
b) from a bottom up perspective both were quite different

I think I said to Zach that one can easily spin any of these discussions either way, unless they are plain obvious (like major sections of copied code). Zach also said that the code/ideas borderline was already hairy, and is now is probably impossible to recognise.

and these feelings/conclusions remained on second, slower reading. In a sense top-down similarities are going to be about ideas, while bottom-up similarities would point to code copying. It's also going to be true that all chess programs are going to show top-down similarities by the very nature of the process and ideas known and so on, but this one gave me a feeling there was more, and I rationalised that to the idea that maybe there was a common developer involved somehow, or that both programs came from the same school. Just a feeling and maybe quite random.

I have the opposite opinion about an "inside" programmer, largely because not even Larry Kaufman seemed to have the full Rybka code. It really does seem to be a one-man show at the end of the day (this gets called the "hit by a bus" problem in some programming circles, when a project depends too much on the knowledge of one person, though I digress, as this seems tangential in the case of Rybka). I'm not quite sure that the "Comrades" are really anti-commercial in computer chess, though at the least they appear heavily annoyed about Fruit, so it could be a GPL and/or open source gripe. As for Rajlich himself doing it, well, I think this is dismissed upon noting that IPPOLIT has bishop underpromotion...

[BTO7]

All i can say BB is your the MAN !!! Nobody could have done it better or clearer in my mind for the programmer and the novice alike. This is a masterpiece. I thank you for bringing this to the people and giving me and im sure many alike some closure on this issue. Obviously not clones. Is it re engineered I think it was well stated up above about the top down theory and bottom up. Top down with so many engines out there to grab "ideas" from im sure its evolved to this level in many top engines thus still ORIGINAL work by Ipploit authors. Great job and thanks Open Chess for helping all chess lovers out here who just wanna freely discuss ! BB if you are working on anything in the way of a program im a backer !!! Ippolit programmer ROCKS in this case great job looks Vas needs to face reality these guys are for real.

Regards
BT

[Sentinel]

2) Missing in the document: LMR similarities / differences

There are some of each. It is a bit confusing because Rybka does not split CUT/ALL nodes into separate functions. In Rybka at CUT nodes, when the phase is ORDINARY moves (that don't give check), the reduction is 6 half-ply until the 12th move, when it increases to 7 half-ply. In IPPOLIT, there is an additional check that a move is not extended, and then the reduction is 4+BSR(4+cnt)) (my correspondence with other programmers actually indicates that the details of ALL node LMR is much more important for strength consideration, and it is almost irrelevant at CUT nodes). For ALL nodes, both start after three moves have been considered, and IPPOLIT is BSR(1+cnt) and Rybka is 2 until the 12th move, when there is an increase to 3.

In tabular form, we have

Code: Select all

        0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 ...
CUT-IPP 6 6 6 6 7 7 7 7 7 7 7 7 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 9 9 ...
CUT-RYB 6 6 6 6 6 6 6 6 6 6 6 6 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 ...
ALL-IPP 0 0 0 2 2 2 2 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 ...
ALL-RYB 0 0 0 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 ...

Of course, the first move is rather unlikely to be an ORDINARY move here (it will be TRANS). Both also have some LMR when in-check, with differences of a comparable size. IPPOLIT treats "exclude" nodes the same as ALL nodes, while Rybka does no LMR at them.

Another interesting part. IIRC in the beginning this (LMR) was offered as a smoking gun by Mr. Clonkie who (wrongly ofc) claimed that Ippo and Rybka LMR is identical.
Interesting thing that Ippo scaling becomes so aggressive as 2.5 plies for moves over 30.
Marco could not believe how Ippo can get away with such an aggressive (logarithmic) LMR. Then in SF1.7 LMR became:
(int)(0.5 + log(double(depth/2)) * log(double(cnt)) / 3.0), both depth and reduction in double ply.
Lets see how this looks like for example at depth 20:

Code: Select all

cnt     0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 ...
ALL-IPP 0 0 0 2 2 2 2 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 5 5 ...
ALL-RYB 0 0 0 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 ...
ALL-SF  0 0 1 1 1 1 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 ...

And at depth 30

Code: Select all

cnt     0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 ...
ALL-IPP 0 0 0 2 2 2 2 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 5 5 ...
ALL-RYB 0 0 0 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 ...
ALL-SF  0 0 1 1 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 ...

Talking about golden cut...