Nullmove bugs

[Sven]

Can anyone spot any problems that I'm not immediately noticing?

EDIT: Dorpsgek source code can be found here.

I found another issue that is not related to null move stuff but I guess you should correct it.

In search.c, function Search(), you do this at ply 0 before printing the search info and PV:

Code: Select all

                if (!ply) {
                    /* Convert mate scores to XBoard standard */
                    if (value >= MATE-500) {
                        value = 100000 + (MATE - value)/2;
                    }

                    if &#40;value <= -MATE+500&#41; &#123;
                        value = -100000 + (-MATE - value&#41;/2;
                    &#125;

First of all, in my opinion the second part should be

Code: Select all

value = -(100000 + (MATE - value)/2);

which is not the same as what you have.

Second point, you should only change a local copy of "value" at this point which is then only used for printing, while the original "value" should keep its mate scoring system that your search needs (MATE - ply resp. -(MATE - ply)).

[ZirconiumX]

Your nullmove does not change hash key. It must be different because the side to move has changed.

Hash probe code regenerates the key before probing. It's not much of an overhead to scan the board to generate a key from scratch.

But what if you need the updated hash key already before probing? Actually I see where that is the case: in IsTrivialDraw() you need the hash key for repetition check, and you call it prior to hash probing ... That might lead to a couple of wrong decisions regarding a repetition draw, which could of course lead to weaker play. Not sure, though, whether the effect would be so drastical to see null move delivering almost zero improvement.

draw.c, lines 37-45:

Code: Select all

    /* Repetition check */
    count = 0;
    for &#40;i = 0; i < bd->fifty; i += 2&#41; &#123;
        if &#40;bd->rep&#91;i&#93; == &#40;bd->hash >> 32&#41;)
            count++;
    &#125;
    if &#40;count >= 3&#41; &#123;
        return 1;
    &#125;

Since the fifty-move counter is zeroed, this should never trigger a draw claim after nullmove. Still, I'll move it up to before the draw check.

3: where is the code that prevent your search to do null move pruning recursively??

At the moment there is none, but I doubt this is critical right now. Recursive nullmove is not quite as bad as it seems - Toga does it just fine.

Can anyone spot any problems that I'm not immediately noticing?

EDIT: Dorpsgek source code can be found here.

I found another issue that is not related to null move stuff but I guess you should correct it.

In search.c, function Search(), you do this at ply 0 before printing the search info and PV:

Code: Select all

                if (!ply) {
                    /* Convert mate scores to XBoard standard */
                    if (value >= MATE-500) {
                        value = 100000 + (MATE - value)/2;
                    }

                    if &#40;value <= -MATE+500&#41; &#123;
                        value = -100000 + (-MATE - value&#41;/2;
                    &#125;

First of all, in my opinion the second part should be

Code: Select all

value = -(100000 + (MATE - value)/2);

which is not the same as what you have.

Second point, you should only change a local copy of "value" at this point which is then only used for printing, while the original "value" should keep its mate scoring system that your search needs (MATE - ply resp. -(MATE - ply)).

Fixed; thanks for pointing it out.

SPRT status:

Code: Select all

Score of New vs Old: 117 - 155 - 74  [0.445] 346

[Sven]

Since the fifty-move counter is zeroed, this should never trigger a draw claim after nullmove.

But you store that wrong hash key in bd->rep[...] and use it later on for repetition checks some plies after the null move, and there it might fail.

[ZirconiumX]

Since the fifty-move counter is zeroed, this should never trigger a draw claim after nullmove.

But you store that wrong hash key in bd->rep[...] and use it later on for repetition checks some plies after the null move, and there it might fail.

Okay, I get your point now. I'll put this on the to-fix list, along with all the other mysterious crashes I can never reproduce (Ilari, if the program segfaults, cutechess terminating it is not helpful because i get no core dump to work with).

SPRT failed, which was not entirely unexpected. Still, it's progress from being a 200 Elo regression.

Code: Select all

Score of New vs Old: 248 - 320 - 142  [0.449] 710
ELO difference: -35.35 +/- 22.95
SPRT: llr -2.97, lbound -2.94, ubound 2.94 - H0 was accepted
Finished match

[ZirconiumX]

I tested Marco's suggestion to not nullmove when eval >= beta.

It did better, but still failed SPRT.

Code: Select all

Score of New vs Old: 415 - 478 - 257  [0.473] 1150
ELO difference: -19.05 +/- 17.70
SPRT: llr -2.95, lbound -2.94, ubound 2.94 - H0 was accepted

Maybe I give up on nullmove? It seems to give me nothing.

[JVMerlino]

I tested Marco's suggestion to not nullmove when eval >= beta.

It did better, but still failed SPRT.

Code: Select all

Score of New vs Old: 415 - 478 - 257  [0.473] 1150
ELO difference: -19.05 +/- 17.70
SPRT: llr -2.95, lbound -2.94, ubound 2.94 - H0 was accepted

Maybe I give up on nullmove? It seems to give me nothing.

A bug-free nullmove implementation is a pretty good ELO boost for any engine. Don't give up just yet.

[elpapa]

if (depth >= 4 && nodetype != NodeTypePV && !incheck && PopCount(b->sidemask[b->side] > 2)) {
[­/code]

How did you come up with depth >=4? Depth >= 2 works best for me. Make sure you call qsearch when depth <= 0 and not depth == 0 if you make this change.

[ZirconiumX]

if (depth >= 4 && nodetype != NodeTypePV && !incheck && PopCount(b->sidemask[b->side] > 2)) {
[­/code]

How did you come up with depth >=4? Depth >= 2 works best for me. Make sure you call qsearch when depth <= 0 and not depth == 0 if you make this change.

Nullmove reduces by R + 1. My R is 3, so 3 + 1 = 4. I'll fiddle about with it after this latest test (requiring 4 or more pieces for the side to move) runs to completion.

And thanks for the encouragement, John.

[elpapa]

if (depth >= 4 && nodetype != NodeTypePV && !incheck && PopCount(b->sidemask[b->side] > 2)) {
[­/code]

How did you come up with depth >=4? Depth >= 2 works best for me. Make sure you call qsearch when depth <= 0 and not depth == 0 if you make this change.

Nullmove reduces by R + 1. My R is 3, so 3 + 1 = 4. I'll fiddle about with it after this latest test (requiring 4 or more pieces for the side to move) runs to completion.

Yes, but you can still do null move pruning, even if the remaining depth is less than 4.

[ZirconiumX]

if (depth >= 4 && nodetype != NodeTypePV && !incheck && PopCount(b->sidemask[b->side] > 2)) {
[­/code]

How did you come up with depth >=4? Depth >= 2 works best for me. Make sure you call qsearch when depth <= 0 and not depth == 0 if you make this change.

Nullmove reduces by R + 1. My R is 3, so 3 + 1 = 4. I'll fiddle about with it after this latest test (requiring 4 or more pieces for the side to move) runs to completion.

Yes, but you can still do null move pruning, even if the remaining depth is less than 4.

You *can*, but the overhead of doing it at low depths starts to outweigh its benefits. Dorpsgek is an incredibly slow program at ~700knps. An extra 2 million nodes of overhead costs Stockfish little, but it costs Dorpsgek a lot more.