"Automated Discovery of Search Extensions"

Code, algorithms, languages, construction...
User avatar
Uly
Posts: 838
Joined: Thu Jun 10, 2010 5:33 am

Re: "Automated Discovery of Search Extensions"

Post by Uly » Sat Jun 26, 2010 5:17 pm

BB+ wrote:R3 (3153): Kaufman's eval
That was in since R2.3.1, actually, it was ditched for Rybka 3 and became Rybka 3 Human instead.

benstoker
Posts: 110
Joined: Thu Jun 10, 2010 7:32 pm
Real Name: Ben Stoker

Re: "Automated Discovery of Search Extensions"

Post by benstoker » Sat Jun 26, 2010 5:36 pm

Rebel wrote:One even might wonder if extensions (except maybe for checks) make sense any longer as they might bite the latest concept of LMR.

Another issue: Now that I understand this new LMR concept it's probably fair to say it was first introduced by Rybka and it became the sole reason for its dominance of the last years. But eventually the secret became known and it's now available for every chess programmer. The interesting question remains how the Rybka's secret became known. The most heard opinion is by RE. But it can also be more simple. If we go back to another breakthrough in CC, the discovery of recursive-null-move back in 1995 (or so) it was simply a voluntary leak by the inventor (Frans Morsch) himself. He told Donninger about it who then made it an article in the ICCA journal. Nowadays recursive-null-move is standard. What if Vas in a weak or open :mrgreen: moment (unconsciously) gave away the idea? We could stop all discussion then. No cloning.

Speculation: now that the algorithm is in the open we might expect a new race. A new chance is given for the old commercial generation, Fritz, Shredder, Hiarcs. If their evaluation is better than those of Rybka, Stockfish, Ippo* then they might have a chance to take the crown again.

So 3 subjects in 1 post.

Ed
Ed, do you know of any articles that outline a kind of 'genealogy' of computer chess concepts, i.e., tracing the origins of the major contributions back to the 60s?

User avatar
thorstenczub
Posts: 593
Joined: Wed Jun 09, 2010 12:51 pm
Real Name: Thorsten Czub
Location: United States of Europe, germany, NRW, Lünen
Contact:

Re: "Automated Discovery of Search Extensions"

Post by thorstenczub » Sat Jun 26, 2010 6:13 pm

Rebel wrote: Speculation: now that the algorithm is in the open we might expect a new race. A new chance is given for the old commercial generation, Fritz, Shredder, Hiarcs. If their evaluation is better than those of Rybka, Stockfish, Ippo* then they might have a chance to take the crown again.

So 3 subjects in 1 post.

Ed
when will you try the idea in prodeo, ed ?

mcostalba
Posts: 91
Joined: Thu Jun 10, 2010 11:45 pm
Real Name: Marco Costalba

Re: "Automated Discovery of Search Extensions"

Post by mcostalba » Sat Jun 26, 2010 6:28 pm

Rebel wrote: Thanks Marco ;) Just for clarity, you are the SF author? Please forgive my ignorance nowadays, I am catching up lately. :mrgreen:
I am one of the SF developers, yes.
Rebel wrote: Our Bob of course will comment, he always does. I am not sure if he totally agrees on the historic perspective.
Of course he won't. He never does :-) that's why we love him.

User avatar
Uly
Posts: 838
Joined: Thu Jun 10, 2010 5:33 am

Re: "Automated Discovery of Search Extensions"

Post by Uly » Sat Jun 26, 2010 8:03 pm

thorstenczub wrote:when will you try the idea in prodeo, ed ?
Wow, is there a chance for a ProDeo 1.7/2.0 at all!?

User avatar
Rebel
Posts: 515
Joined: Wed Jun 09, 2010 7:45 pm
Real Name: Ed Schroder

Re: "Automated Discovery of Search Extensions"

Post by Rebel » Sat Jun 26, 2010 10:50 pm

benstoker wrote: Ed, do you know of any articles that outline a kind of 'genealogy' of computer chess concepts, i.e., tracing the origins of the major contributions back to the 60s?
I think the best man to answer this is Bob.

Ed
Last edited by Rebel on Sat Jun 26, 2010 10:54 pm, edited 1 time in total.

User avatar
Rebel
Posts: 515
Joined: Wed Jun 09, 2010 7:45 pm
Real Name: Ed Schroder

Re: "Automated Discovery of Search Extensions"

Post by Rebel » Sat Jun 26, 2010 10:52 pm

thorstenczub wrote:when will you try the idea in prodeo, ed ?
Only when Holland becomes WC :mrgreen:, else not in this live I am afraid.

User avatar
Rebel
Posts: 515
Joined: Wed Jun 09, 2010 7:45 pm
Real Name: Ed Schroder

Re: "Automated Discovery of Search Extensions"

Post by Rebel » Sat Jun 26, 2010 10:59 pm

mcostalba wrote:
Rebel wrote: Our Bob of course will comment, he always does. I am not sure if he totally agrees on the historic perspective.
Of course he won't. He never does :-) that's why we love him.
Now wait a minute Marco, it was I who loved him first :mrgreen:

Ed

BB+
Posts: 1484
Joined: Thu Jun 10, 2010 4:26 am

Re: "Automated Discovery of Search Extensions"

Post by BB+ » Mon Jun 28, 2010 4:54 am

Ovyron wrote:
BB+ wrote:R3 (3153): Kaufman's eval
That was in since R2.3.1, actually, it was ditched for Rybka 3 and became Rybka 3 Human instead.
We must be talking about different things. R3 certainly has what I call "Kaufman's eval" (the main features are: mobility; attacks, either good-SEE or of loose pieces, and also x-rays; and "king guards"; though other aspects such as colour-based handling of bad bishops could be mentioned here also). Comparatively, my perception is that earlier Rybkas mostly had a Fruit-like eval with mobility as the dominant item in piece eval. [I don't know when restrictions like safe-square and forward mobility were first used]. I think the principal difference with R3 and Rybka 3 Human is that Kaufman included some "human-like" tweaks that didn't test well.

BB+
Posts: 1484
Joined: Thu Jun 10, 2010 4:26 am

Re: "Automated Discovery of Search Extensions"

Post by BB+ » Tue Jun 29, 2010 5:49 am

Now I remember some of the silliness in Rybka 2.3.2a. It's been maybe 2 years since I looked at it. There's a whole bunch of eval functions, some of which are "dummies" -- that is, they look an eval function, but they are missing some part of it (like rook eval). I dumped the disassembly, and grep'ed for prefetchnta (done to prefetch the pawnhash); 14 appearances, but when I put a breakpoint at each and run Rybka, only one of them is hit. I seem also to recall that the code to be used is set via some flag in the search start, and if there are more than 40 pawns on the board, then it will use some of the crazy code. :)

In any case, microwine loads the eval function into 0x46adc0, and the function runs to 0x46bfb3. Byte-size is not a perfect measure, but this is only about 4600 bytes, compared to over 12700 in Rybka 3. These large additions are what I meant by "Kaufman eval", not simply his first appearance on the Rybka team.

Testing showed it was 40 WhitePawns, and not all of the alternative code is merely extraneous.

Code: Select all

0x0055228e:   mov  0x28b19b(%rip),%rcx       # 0x7dd430
0x0055229c:   mov  %rcx,%rax           # that is, WhitePawns
0x005522a9:   shr  %rax
0x005522af:   mov  $0x5555555555555555,%r11
0x005522b9:   and  %r11,%rax
0x005522c9:   sub  %rax,%rcx
0x005522d9:   mov  %rcx,%rax
0x0055229f:   mov  $0x3333333333333333,%rbx
0x005522dc:   and  %rbx,%rcx
0x005522df:   shr  $0x2,%rax
0x005522e3:   and  %rbx,%rax           [this code is easily
0x005522e6:   add  %rcx,%rax            recognised as POPCNT
0x005522e9:   mov  %rax,%rcx            to the cognoscenti]
0x005522ec:   shr  $0x4,%rcx
0x005522f0:   add  %rax,%rcx
0x005522bf:   mov  $0xf0f0f0f0f0f0f0f,%r10
0x005522f3:   and  %r10,%rcx
0x005522cc:   mov  $0x101010101010101,%r9
0x005522f6:   imul  %r9,%rcx
0x005522fa:   shr  $0x38,%rcx
0x005522fe:   cmp  $0x28,%ecx          [ #WhitePawns vs 40 ]
0x00552308:   cmovl %r12d,%edx         [ so edx will be 1 ]
0x00552351:   test %dl,%dl
0x00552358:   je  0x552373             [ branch not taken]
0x00551e92:   mov  0x2a2067(%rip),%r8d       # 0x7f3f00
0x0055235a:   test %r8d,%r8d           [ 0 unless few pieces? ]
0x0055235d:   jne    0x552369
0x0055235f:   callq  0x46e300          [ "main" search func ]
0x00552364:   jmpq   0x552611
0x00552369:   callq  0x462a00          [ "other" search func ]
0x0055236e:   jmpq   0x552611
[...]
I think the relevant setting of 0x7f3f00 is at 0x45f3c8, when the position is set. Something is compared to 98, but I don't know what.

Post Reply