Nullmove bugs

Discussion of chess software programming and technical issues.

Moderators: hgm, Harvey Williamson, bob

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
ZirconiumX
Posts: 1327
Joined: Sun Jul 17, 2011 9:14 am

Nullmove bugs

Post by ZirconiumX » Sun Aug 28, 2016 4:02 pm

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.
Some believe in the almighty dollar.

I believe in the almighty printf statement.

Volker Annuss
Posts: 173
Joined: Mon Sep 03, 2007 7:15 am

Re: Nullmove bugs

Post by Volker Annuss » Sun Aug 28, 2016 4:24 pm

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

Sven
Posts: 3822
Joined: Thu May 15, 2008 7:57 pm
Location: Berlin, Germany
Full name: Sven Schüle
Contact:

Re: Nullmove bugs

Post by Sven » Sun Aug 28, 2016 5:22 pm

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
Posts: 1327
Joined: Sun Jul 17, 2011 9:14 am

Re: Nullmove bugs

Post by ZirconiumX » Sun Aug 28, 2016 5:33 pm

Volker Annuss wrote: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.
Sven Schüle wrote: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 :oops: 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.
Some believe in the almighty dollar.

I believe in the almighty printf statement.

bob
Posts: 20471
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Nullmove bugs

Post by bob » Sun Aug 28, 2016 6:32 pm

ZirconiumX wrote:
Volker Annuss wrote: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.
Sven Schüle wrote: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 :oops: 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
Posts: 1327
Joined: Sun Jul 17, 2011 9:14 am

Re: Nullmove bugs

Post by ZirconiumX » Sun Aug 28, 2016 6:46 pm

bob wrote: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
Some believe in the almighty dollar.

I believe in the almighty printf statement.

elcabesa
Posts: 806
Joined: Sun May 23, 2010 11:32 am
Contact:

Re: Nullmove bugs

Post by elcabesa » Sun Aug 28, 2016 7:03 pm

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 &#40;depth >= 4 && nodetype != NodeTypePV && !incheck && PopCount&#40;b->sidemask&#91;b->side&#93; > 2&#41; && allowPV==true&#41; &#123;
        b->side ^= 1;
        int fifty = b->fifty;
        allowPV = false;

        value = -Search&#40;b, -beta, -beta+1, depth - 4, ply + 1, &child_pv, NodeTypeCut, allowPV&#41;;

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

        if &#40;value >= beta&#41; &#123;
            return value;
        &#125;
    &#125; 
    allowPV = true;
    ...continue search...

Sven
Posts: 3822
Joined: Thu May 15, 2008 7:57 pm
Location: Berlin, Germany
Full name: Sven Schüle
Contact:

Re: Nullmove bugs

Post by Sven » Sun Aug 28, 2016 7:15 pm

ZirconiumX wrote:
Volker Annuss wrote: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
Posts: 3822
Joined: Thu May 15, 2008 7:57 pm
Location: Berlin, Germany
Full name: Sven Schüle
Contact:

Re: Nullmove bugs

Post by Sven » Sun Aug 28, 2016 7:22 pm

elcabesa wrote: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.
elcabesa wrote: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.
elcabesa wrote: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 &#40;depth >= 4 && nodetype != NodeTypePV && !incheck && PopCount&#40;b->sidemask&#91;b->side&#93; > 2&#41; && allowPV==true&#41; &#123;
        b->side ^= 1;
        int fifty = b->fifty;
        allowPV = false;

        value = -Search&#40;b, -beta, -beta+1, depth - 4, ply + 1, &child_pv, NodeTypeCut, allowPV&#41;;

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

        if &#40;value >= beta&#41; &#123;
            return value;
        &#125;
    &#125; 
    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
Posts: 806
Joined: Sun May 23, 2010 11:32 am
Contact:

Re: Nullmove bugs

Post by elcabesa » Sun Aug 28, 2016 7:35 pm

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

Post Reply