Nullmove bugs

[ZirconiumX]

So I've been attempting to implement nullmove in Dorpsgek, but it seems to be going really badly.

Here is my nullmove code:

Code: Select all

    if (depth >= 4 && nodetype != NodeTypePV && !incheck && PopCount(b->sidemask[b->side] > 2)) {
        b->side ^= 1;
        int fifty = b->fifty;

        value = -Search(b, -beta, -beta+1, depth - 4, ply + 1, &child_pv, NodeTypeCut);

        b->side ^= 1;
        b->fifty = fifty;

        if (value >= beta) {
            return value;
        }
    }

Adding this code to my engine gets results in it being completely destroyed in self-play:

Code: Select all

Score of New vs Old: 22 - 106 - 15  [0.206] 143
ELO difference: -234.07 +/- 65.97
SPRT: llr -2.95, lbound -2.94, ubound 2.94 - H0 was accepted
Finished match

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

EDIT: Dorpsgek source code can be found here.

[Volker Annuss]

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

[Sven]

Other possible issues (maybe they are minor, just double check them):

- PopCount(...) > 2 seems to include pawns but you should better test the non-pawn material only, otherwise you might get zugzwang problems in pawn endings.

- I would also reset the fifty-moves counter to 0 after making a null move, since in my opinion the null move is irreversible. (There are certainly different opinions about that.)

[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.

Other possible issues (maybe they are minor, just double check them):

- PopCount(...) > 2 seems to include pawns but you should better test the non-pawn material only, otherwise you might get zugzwang problems in pawn endings.

Okay, thank you!

- I would also reset the fifty-moves counter to 0 after making a null move, since in my opinion the null move is irreversible. (There are certainly different opinions about that.)

I may have forgotten to include that when transcribing the code Yes, I do zero the fifty-move counter. That's why the fifty-move counter is backed up.

I'm going to run a test in which I copy the board before making the nullmove. Just in case I'm messing something up.

[bob]

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.

Other possible issues (maybe they are minor, just double check them):

- PopCount(...) > 2 seems to include pawns but you should better test the non-pawn material only, otherwise you might get zugzwang problems in pawn endings.

Okay, thank you!

- I would also reset the fifty-moves counter to 0 after making a null move, since in my opinion the null move is irreversible. (There are certainly different opinions about that.)

I may have forgotten to include that when transcribing the code Yes, I do zero the fifty-move counter. That's why the fifty-move counter is backed up.

I'm going to run a test in which I copy the board before making the nullmove. Just in case I'm messing something up.

Actually it is a LOT of overhead since you do this once for every node you search...

Is there anything indexed by ply that you failed to copy? (generally one copies castling status and such in MakeMove().)

[ZirconiumX]

Actually it is a LOT of overhead since you do this once for every node you search...

Perhaps, but compared to my evaluation, the copy-make overhead is not so bad.

Is there anything indexed by ply that you failed to copy? (generally one copies castling status and such in MakeMove().)

I did forget to invalidate the en-passant square, but that's been fixed in the current iteration.

At the moment, we're doing far better than we were, but it's still at best a wash. I'll let SPRT run its course though.

Code: Select all

Score of New vs Old: 109 - 113 - 63  [0.493] 285

[elcabesa]

I see 3 things that seems strange to me:

1: what happen when you call search with depth = 0 ? it start a quiescent search? otherwise when depth == 4 you call

value = -Search(b, -beta, -beta+1, 0, ply + 1, &child_pv, NodeTypeCut);

2: aren't you trying calling null move pruning when it's not necessary? for example when static_eval << beta
3: where is the code that prevent your search to do null move pruning recursively??

probably your code need to be reworked this way:

Code: Select all

if (depth >= 4 && nodetype != NodeTypePV && !incheck && PopCount(b->sidemask[b->side] > 2) && allowPV==true) {
        b->side ^= 1;
        int fifty = b->fifty;
        allowPV = false;

        value = -Search(b, -beta, -beta+1, depth - 4, ply + 1, &child_pv, NodeTypeCut, allowPV);

        b->side ^= 1;
        b->fifty = fifty;

        if (value >= beta) {
            return value;
        }
    } 
    allowPV = true;
    ...continue search...

[Sven]

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.

[Sven]

I see 3 things that seems strange to me:

1: what happen when you call search with depth = 0 ? it start a quiescent search? otherwise when depth == 4 you call

value = -Search(b, -beta, -beta+1, 0, ply + 1, &child_pv, NodeTypeCut);

That works correctly, he starts QS if depth == 0.

2: aren't you trying calling null move pruning when it's not necessary? for example when static_eval << beta

That this is missing does not explain that null move gives zero improvement for him.

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

probably your code need to be reworked this way:

Code: Select all

if (depth >= 4 && nodetype != NodeTypePV && !incheck && PopCount(b->sidemask[b->side] > 2) && allowPV==true) {
        b->side ^= 1;
        int fifty = b->fifty;
        allowPV = false;

        value = -Search(b, -beta, -beta+1, depth - 4, ply + 1, &child_pv, NodeTypeCut, allowPV);

        b->side ^= 1;
        b->fifty = fifty;

        if (value >= beta) {
            return value;
        }
    } 
    allowPV = true;
    ...continue search...

You certainly mean "allowNullMove" instead of "allowPV". I don't think it is absolutely necessary to avoid making two null moves in a row. Years ago I had the same opinion like you (and many others) but today I think it is possible, I have already tried it. The point is that you do not search the position after two consecutive null moves with the same conditions as you did before, you do it with a depth reduction of 2*R (or twice the reduction you apply per null move). And if you take care not to handle the position after two consecutive null moves as a repetition then I see no problem in it.

[elcabesa]

yes I mean AllowNullMove sorry.

with the actual code when he search with depth = 9, he do the null move and search with depth = 5, do the search another time with depth = 1 -> so it replace the search at depth 9 with a search at depth 1 since it doesn't filter out position with staticeval << beta
I may be wrong