Nullmove bugs

Discussion of chess software programming and technical issues.

Moderators: hgm, Dann Corbit, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
elpapa
Posts: 205
Joined: Sun Jan 18, 2009 10:27 pm
Location: Sweden
Full name: Patrik Karlsson

Re: Nullmove bugs

Post by elpapa » Mon Aug 29, 2016 9:06 pm

ZirconiumX wrote:
elpapa wrote:
ZirconiumX wrote:
elpapa wrote:
ZirconiumX wrote: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.
Ok, then there's a reasoning behind it. I thought that maybe you hadn't considered it.

zenpawn
Posts: 336
Joined: Sat Aug 06, 2016 6:31 pm
Location: United States

Re: Nullmove bugs

Post by zenpawn » Mon Aug 29, 2016 9:32 pm

elcabesa wrote: 2: aren't you trying calling null move pruning when it's not necessary? for example when static_eval << beta
Question about this. Does this mean the benefit of only checking the null move in eval > beta cases outweighs the cost of calculating the static evaluation at every node (vs just qsearch nodes)?

ZirconiumX
Posts: 1327
Joined: Sun Jul 17, 2011 9:14 am

Re: Nullmove bugs

Post by ZirconiumX » Mon Aug 29, 2016 9:39 pm

The proof will lie in the Elo, I suppose.

Though really I should do something about the performance of it. If TSCP had a smarter search, it would outsearch Dorpsgek easily.

While a conversion to Make/Unmake would probably be a good idea, there is an awful lot of information and board state that needs to be updated, so I suspect the recalculation may offset the memory bandwidth.
Some believe in the almighty dollar.

I believe in the almighty printf statement.

thomasahle
Posts: 74
Joined: Thu Feb 27, 2014 7:19 pm

Re: Nullmove bugs

Post by thomasahle » Mon Aug 29, 2016 10:46 pm

ZirconiumX wrote: 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.
As a data point, Sunfish is only around 30knps and it still benefits from doing null moves all the way down to depth=1. For slow engines as much as fast, pruning is key.

ZirconiumX
Posts: 1327
Joined: Sun Jul 17, 2011 9:14 am

Re: Nullmove bugs

Post by ZirconiumX » Tue Aug 30, 2016 10:23 am

Well the "4 or more pieces to nullmove" patch is a slight loss, but now within error bounds.

Code: Select all

Score of New vs Old&#58; 1311 - 1343 - 719  &#91;0.495&#93; 3373
ELO difference&#58; -3.30 +/- 10.39
SPRT&#58; llr -2.95, lbound -2.94, ubound 2.94 - H0 was accepted
I suppose you're right, Thomas.

Now I'll see if lowering the depth requirement helps.
Some believe in the almighty dollar.

I believe in the almighty printf statement.

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

Re: Nullmove bugs

Post by bob » Tue Aug 30, 2016 4:37 pm

ZirconiumX wrote:
elpapa wrote:
ZirconiumX wrote:
elpapa wrote:
ZirconiumX wrote: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.
This is wrong. NULL-MOVE should NOT "add extra overhead". It reduces the size of the tree, which is why we use it. Otherwise it would be worthless.

ZirconiumX
Posts: 1327
Joined: Sun Jul 17, 2011 9:14 am

Re: Nullmove bugs

Post by ZirconiumX » Tue Aug 30, 2016 7:13 pm

I was referring to null move fail lows.

Also, if somebody found a way of ordering moves perfectly, I suspect people would use that instead of theoretically unsound pruning that causes imperfections.

But that's besides the point.

Current SPRT progress on depth >= 3:

Code: Select all

Score of New vs Old&#58; 837 - 761 - 632 &#91;0.517&#93; 2230
ELO difference&#58; 11.85 +/- 12.20
SPRT&#58; llr 1.76, lbound -2.94, ubound 2.94
We have a positive elo result! But it's nothing earth shattering. More testing to be done later.
Some believe in the almighty dollar.

I believe in the almighty printf statement.

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

Re: Nullmove bugs

Post by bob » Tue Aug 30, 2016 8:34 pm

ZirconiumX wrote:I was referring to null move fail lows.

Also, if somebody found a way of ordering moves perfectly, I suspect people would use that instead of theoretically unsound pruning that causes imperfections.

But that's besides the point.

Current SPRT progress on depth >= 3:

Code: Select all

Score of New vs Old&#58; 837 - 761 - 632 &#91;0.517&#93; 2230
ELO difference&#58; 11.85 +/- 12.20
SPRT&#58; llr 1.76, lbound -2.94, ubound 2.94
We have a positive elo result! But it's nothing earth shattering. More testing to be done later.
Ordering is not the issue here, it is effort, as in search space. null-move searches a MUCH smaller tree than a single normal move would search, because of the reduced depth. The null-move observation, as defined by Beal, actually works and is not nearly as speculative in nature as forward-pruning approaches.

Last time I tested, removing null-move cost me 40 Elo. Removing LMR cost me 40 Elo. Removing both cost me 120 Elo. That has probably increased over the last few years...

zenpawn
Posts: 336
Joined: Sat Aug 06, 2016 6:31 pm
Location: United States

Re: Nullmove bugs

Post by zenpawn » Wed Aug 31, 2016 8:28 pm

Is the nodetype != NodeTypePV condition a requirement of null move pruning? I ask because when I added that restriction, my search became painfully slow.

User avatar
Evert
Posts: 2929
Joined: Fri Jan 21, 2011 11:42 pm
Location: NL
Contact:

Re: Nullmove bugs

Post by Evert » Wed Aug 31, 2016 8:56 pm

zenpawn wrote:Is the nodetype != NodeTypePV condition a requirement of null move pruning? I ask because when I added that restriction, my search became painfully slow.
Shouldn't matter that much. There aren't that many PV nodes, but if the null-move fails high (which might get backed up to the root and trigger a research with a larger aspiration window) it might be costly, especially if the fail-high is undeserved. I guess it will depend a lot on how you handle your aspiration window and other minor details.

EDIT: I just tried with Jazz; allowing null-move in the PV adds about 2% to the node count for a fixed depth search (NPS is constant, so the time to depth increases by a similar 2%). Seems it should just be a speed optimisation to not do it in PV nodes.

Post Reply