fixing the null move search "bug"

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Uri Blass
Posts: 8594
Joined: Wed Mar 08, 2006 11:37 pm
Location: Tel-Aviv Israel

fixing the null move search "bug"

Post by Uri Blass » Sat Feb 01, 2014 7:32 am

There are programs that can never see zugzwangs simply because they use null move pruning.

People tried different ways to solve the problem(including double null move pruning and verification search) but I did not read about trying the simplest fix that say simply to not use dubious null move pruning when the remaining depth is high.

Not using null move pruning when the remaining depth is bigger than 20 is going to solve the zugzwang problem in the endgame and I doubt if it is going to give a reduction in playing strength.

Even not using null move pruning when the remaining depth is bigger than 14 seems not to change the elo of stockfish significantly(not at 15+0.05 and probably not at 60+0.05 when I still do not have enough games in the stockfish framework).

Uri Blass
Posts: 8594
Joined: Wed Mar 08, 2006 11:37 pm
Location: Tel-Aviv Israel

Re: fixing the null move search "bug"

Post by Uri Blass » Sat Feb 01, 2014 8:46 am

Still not enough games and it may be because of bad luck but the results so far suggest that stockfish lose 3.19 elo at 60+0.05
with possible error of 4.7 elo.

Even if it lose elo
It still does not mean that the idea is not good if you use bigger depth or maybe condition about depth relative to number of nodes.

Sergei S. Markoff
Posts: 224
Joined: Mon Sep 12, 2011 9:27 pm
Location: Moscow, Russia
Contact:

Re: fixing the null move search "bug"

Post by Sergei S. Markoff » Sat Feb 01, 2014 11:25 am

I think you should try some tech to predict zugzwang probability and than use a predicted value to decide at which depth you should do verification/deny null move.

Zugzwang probability obviously depends on how much possible moves you have and how your pieces used in protecting other, attacked pieces. So it should strongly correlate with mobility, number of pieces that are attacked and also number of opponent passers stopped by attack their forward squares.
The Force Be With You!

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

Re: fixing the null move search "bug"

Post by bob » Sat Feb 01, 2014 3:23 pm

Uri Blass wrote:There are programs that can never see zugzwangs simply because they use null move pruning.

People tried different ways to solve the problem(including double null move pruning and verification search) but I did not read about trying the simplest fix that say simply to not use dubious null move pruning when the remaining depth is high.

Not using null move pruning when the remaining depth is bigger than 20 is going to solve the zugzwang problem in the endgame and I doubt if it is going to give a reduction in playing strength.

Even not using null move pruning when the remaining depth is bigger than 14 seems not to change the elo of stockfish significantly(not at 15+0.05 and probably not at 60+0.05 when I still do not have enough games in the stockfish framework).
This has been done. Crafty did it years ago. Problem is, reducing near the root is a BIG savings. If you don't do it within N plies of the root, the trees are bigger and the overall effect is a significant loss of Elo.

This was discussed either on CCC or r.g.c.c years ago...

Uri Blass
Posts: 8594
Joined: Wed Mar 08, 2006 11:37 pm
Location: Tel-Aviv Israel

Re: fixing the null move search "bug"

Post by Uri Blass » Sat Feb 01, 2014 4:18 pm

It seems that at least in 1 minute per game the elo loss of stockfish is small and I am not sure if it is not a statistical error.
when I avoid null move pruning at depth that is at least 15 plies
I see the following result in the stockfish framework

ELO: -1.90 +-2.8 (95%) LOS: 8.8%
Total: 18986 W: 2915 L: 3019 D: 13052

I will try a different trick that is avoiding null move pruning when
the depth is at least 12 plies and also the number of legal moves is not bigger than the depth(in a big majority of the cases the remaining depth is smaller than 12 so I do not need to do the expensive counting of the number of legal moves).

The idea is that zugzwang happen more often when the number of legal moves is small so in most cases in the middle game when there are 30 legal moves or something like that I am going to use null move pruning
because the remaining depth is going to be less than 30 plies.

syzygy
Posts: 4455
Joined: Tue Feb 28, 2012 10:56 pm

Re: fixing the null move search "bug"

Post by syzygy » Sat Feb 01, 2014 4:41 pm

Uri Blass wrote:It seems that at least in 1 minute per game the elo loss of stockfish is small and I am not sure if it is not a statistical error.
when I avoid null move pruning at depth that is at least 15 plies
So with 1 minute per game you manage to almost hide all the damage.

Uri Blass
Posts: 8594
Joined: Wed Mar 08, 2006 11:37 pm
Location: Tel-Aviv Israel

Re: fixing the null move search "bug"

Post by Uri Blass » Sat Feb 01, 2014 4:50 pm

syzygy wrote:
Uri Blass wrote:It seems that at least in 1 minute per game the elo loss of stockfish is small and I am not sure if it is not a statistical error.
when I avoid null move pruning at depth that is at least 15 plies
So with 1 minute per game you manage to almost hide all the damage.
Maybe and Maybe there is no demage(0 is inside the error bounds in both cases).

Results so far:
15 seconds per game+0.05 seconds per move
ELO: 0.33 +-2.9 (95%) LOS: 58.8%
Total: 20000 W: 3699 L: 3680 D: 12621

60 seconds per game+0.05 seconds per move
ELO: -1.94 +-2.7 (95%) LOS: 8.3%
Total: 19124 W: 2935 L: 3042 D: 13147

syzygy
Posts: 4455
Joined: Tue Feb 28, 2012 10:56 pm

Re: fixing the null move search "bug"

Post by syzygy » Sat Feb 01, 2014 4:51 pm

Uri Blass wrote:
syzygy wrote:
Uri Blass wrote:It seems that at least in 1 minute per game the elo loss of stockfish is small and I am not sure if it is not a statistical error.
when I avoid null move pruning at depth that is at least 15 plies
So with 1 minute per game you manage to almost hide all the damage.
Maybe and Maybe there is no demage(0 is inside the error bounds in both cases).
Any maybe pigs can fly.

Uri Blass
Posts: 8594
Joined: Wed Mar 08, 2006 11:37 pm
Location: Tel-Aviv Israel

Re: fixing the null move search "bug"

Post by Uri Blass » Wed Feb 05, 2014 9:31 am

syzygy wrote:
Uri Blass wrote:
syzygy wrote:
Uri Blass wrote:It seems that at least in 1 minute per game the elo loss of stockfish is small and I am not sure if it is not a statistical error.
when I avoid null move pruning at depth that is at least 15 plies
So with 1 minute per game you manage to almost hide all the damage.
Maybe and Maybe there is no demage(0 is inside the error bounds in both cases).
Any maybe pigs can fly.
I do not see something illogical with the idea that there is no demage in not doing null move pruning when the depth is high.

There are some problems that stockfish cannot solve regardless of time because of null move pruning so it seems obvious that avoiding null move pruning is productive at time control that is long enough.

The maximal depth that stockfish can get is 100 and null move verification does not help because of huge reduction that stockfish is using today
so if we use time control that is long enough for stockfish to get depth 100 in every move then it is clear that stockfish without null move pruning at depth that is bigger than 50 is going to be better than default stockfish.

depth that is bigger than 14 at 1 minute per game may not be enough and I guess that it is the case based on the results but it is not something that is obvious

Uri Blass
Posts: 8594
Joined: Wed Mar 08, 2006 11:37 pm
Location: Tel-Aviv Israel

Re: fixing the null move search "bug"

Post by Uri Blass » Wed Feb 05, 2014 9:36 am

I can add that I wonder if people did some research about the demage of not detecting zugzwang based on fixed depth games between different version of the same program that both use null move pruning but one of them use also verification search so it prune move based on null move pruning only if it finds also a legal move that creates a cutoff at the same depth.

Post Reply