Null-move pruning and the hash table

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.
micron
Posts: 155
Joined: Mon Feb 15, 2010 8:33 am
Location: New Zealand

Null-move pruning and the hash table

Post by micron » Sun Mar 28, 2010 8:21 am

I just implemented null-move pruning in Spandrel. Still glowing with newbie delight at the speedup (after tuning, a nominal 10 ply search from the start went from 7.5 to 1.0 s) I have two questions:

[1] Apparently a TT probe can return advice that a null-move is not worth attempting. How does that work?

[2] When the null-move produces a cutoff, it is tempting to hash the node/score in the TT. But doing this gives me a slowdown of 2--3 X, with many more TT misses. Is it a Bad Idea to hash these nodes, or am I doing something wrong? The score is saved as a LOWER_BOUND.

Robert P.

Mincho Georgiev
Posts: 454
Joined: Sat Apr 04, 2009 4:44 pm
Location: Bulgaria
Contact:

Re: Null-move pruning and the hash table

Post by Mincho Georgiev » Sun Mar 28, 2010 8:52 am

Hi Robert!

[1] "advice that null move is not worth attempting" is not the correct interpretation, it's more likely the stored indicator to point that null move is absolutely forbidden instead, since the previous move was null move, and you are about to make 2 nulls in a row, which is undesirable at least.

[2] There are a lot of different implementations on that subject. I don't store it, since there is no gain in my impl., others do. Regardless, 2-3x slowdown is absolutely huge, and probably something is wrong indeed.

Teemu Pudas
Posts: 88
Joined: Wed Mar 25, 2009 11:49 am

Re: Null-move pruning and the hash table

Post by Teemu Pudas » Sun Mar 28, 2010 9:59 am

[1] if (tt_depth >= depth - R - 1 && tt_score < beta && tt_type & UPPER) skip_null(); // If a plain reduced search without nullmove won't produce a cutoff...

[2] You have a bug.

micron
Posts: 155
Joined: Mon Feb 15, 2010 8:33 am
Location: New Zealand

Re: Null-move pruning and the hash table

Post by micron » Sun Mar 28, 2010 10:35 am

Mincho Georgiev wrote: [1] "advice that null move is not worth attempting" is not the correct interpretation, it's more likely the stored indicator to point that null move is absolutely forbidden instead, since the previous move was null move, and you are about to make 2 nulls in a row, which is undesirable at least.

[2] There are a lot of different implementations on that subject. I don't store it, since there is no gain in my impl., others do. Regardless, 2-3x slowdown is absolutely huge, and probably something is wrong indeed.
[1] I specifically allow 2 (but of course not 3) nulls in a row (e.g. white at ply n then black at ply n+1), because it proved faster. How is this "undesirable at least"?
[2] I find it all too easy to believe that something is "wrong indeed". Thanks, Mincho.
Robert P.

micron
Posts: 155
Joined: Mon Feb 15, 2010 8:33 am
Location: New Zealand

Re: Null-move pruning and the hash table

Post by micron » Sun Mar 28, 2010 11:00 am

Teemu Pudas wrote:[1] if (tt_depth >= depth - R - 1 && tt_score < beta && tt_type & UPPER) skip_null(); // If a plain reduced search without nullmove won't produce a cutoff...

[2] You have a bug.
[1] Ah, thank you, that seems to predict reliably that null-move won't cutoff and therefore should not be attempted. In my program, though, it turns out to save a negligible number of attempts.
Without skip_null: 45366 null-moves 36240 cutoffs (79%)
With skip_null: 45304 null moves 36240 cutoffs (79%)

[2] Good, if I can fix the bug in the TT save, null-move pruning should produce even better results...

Robert P.

User avatar
michiguel
Posts: 6388
Joined: Thu Mar 09, 2006 7:30 pm
Location: Chicago, Illinois, USA
Contact:

Re: Null-move pruning and the hash table

Post by michiguel » Sun Mar 28, 2010 11:05 am

micron wrote:I just implemented null-move pruning in Spandrel. Still glowing with newbie delight at the speedup (after tuning, a nominal 10 ply search from the start went from 7.5 to 1.0 s) I have two questions:

[1] Apparently a TT probe can return advice that a null-move is not worth attempting. How does that work?

[2] When the null-move produces a cutoff, it is tempting to hash the node/score in the TT. But doing this gives me a slowdown of 2--3 X, with many more TT misses. Is it a Bad Idea to hash these nodes, or am I doing something wrong? The score is saved as a LOWER_BOUND.

Robert P.
Spandrel is a gould name!

Miguel
PS: architect or evolutionary biologist?

Mincho Georgiev
Posts: 454
Joined: Sat Apr 04, 2009 4:44 pm
Location: Bulgaria
Contact:

Re: Null-move pruning and the hash table

Post by Mincho Georgiev » Sun Mar 28, 2010 11:11 am

micron wrote:
Mincho Georgiev wrote: [1] "advice that null move is not worth attempting" is not the correct interpretation, it's more likely the stored indicator to point that null move is absolutely forbidden instead, since the previous move was null move, and you are about to make 2 nulls in a row, which is undesirable at least.

[2] There are a lot of different implementations on that subject. I don't store it, since there is no gain in my impl., others do. Regardless, 2-3x slowdown is absolutely huge, and probably something is wrong indeed.
[1] I specifically allow 2 (but of course not 3) nulls in a row (e.g. white at ply n then black at ply n+1), because it proved faster. How is this "undesirable at least"?
[2] I find it all too easy to believe that something is "wrong indeed". Thanks, Mincho.
Robert P.

Recursive null move pruning is widely spread scheme. This means, that
more than one null moves are allowed in one branch (line) of the search.
However, this is absolutely different from making 2/3 null moves in a row.
The last brings a huge risk of tactical blunders and it may cause the search to assume that position is good and cuts off, when actually could be very bad instead.

User avatar
hgm
Posts: 23631
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Null-move pruning and the hash table

Post by hgm » Sun Mar 28, 2010 11:43 am

Mincho Georgiev wrote:Recursive null move pruning is widely spread scheme. This means, that
more than one null moves are allowed in one branch (line) of the search.
However, this is absolutely different from making 2/3 null moves in a row.
The last brings a huge risk of tactical blunders and it may cause the search to assume that position is good and cuts off, when actually could be very bad instead.
Why is that? I don't pay any attention to the number of null moves in a row in micro-Max, and found never any adverse effects of it. I would say at the very worst it could be a (small) waste of time. Two null moves in a row cannot both fail high. For the first to fail high, it is necessary that the second fails low, and then it would be like you had not searched it at all, as a low-failing null move does not affect the search or score. You only prune when it fails high. And if the second null move fails high, making the first fail low, where it otherwise would have failed high, it merely means that you are in zugzwang, and that the search after the two null moves acted as a verification search that detected that (despite of its high reduction), so that you don't trust the null-move, and do a normal search in stead.

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

Re: Null-move pruning and the hash table

Post by bob » Sun Mar 28, 2010 3:20 pm

micron wrote:I just implemented null-move pruning in Spandrel. Still glowing with newbie delight at the speedup (after tuning, a nominal 10 ply search from the start went from 7.5 to 1.0 s) I have two questions:

[1] Apparently a TT probe can return advice that a null-move is not worth attempting. How does that work?

[2] When the null-move produces a cutoff, it is tempting to hash the node/score in the TT. But doing this gives me a slowdown of 2--3 X, with many more TT misses. Is it a Bad Idea to hash these nodes, or am I doing something wrong? The score is saved as a LOWER_BOUND.

Robert P.
The idea is that the hash table can show that a null-move won't fail high. Works like this:

Your current depth remaining is N. Let's choose 8 here. Your current alpha=0.20, and beta=0.21 (you choose the values, doesn't matter here).

You do a hash probe to see if you can terminate the search. You get a hit, but the draft (remaining depth for the hash entry) is only 7, so you can't use that result to end the search. But if you compare the table result and discover that it suggests that a normal search here will not fail high (entry is of type UPPER, or EXACT where table bound / value is < beta) you can make a pretty good guess that a null-move search will also not fail high, since doing nothing is worse than playing a real move, and the best real move you could find did not fail high when you searched it to store this hash entry. All that you need to test is that (a) the table draft is at least greater than depth - R - 1 (where R is normal null-move depth reduction amount) and that the table value suggests that the score is < beta.

All you do is avoid doing nulls when they will not help, it is a very slight performance improvement.

Mincho Georgiev
Posts: 454
Joined: Sat Apr 04, 2009 4:44 pm
Location: Bulgaria
Contact:

Re: Null-move pruning and the hash table

Post by Mincho Georgiev » Sun Mar 28, 2010 3:59 pm

I guess,I've misunderstood the subject. We are talking about two different things here, sorry if I mislead you, Robert P..
What I've pointed out was the null move indicator that I use, not the method that Bob Hyatt just describes.
H.G., what you are saying sounds reasonable, but I still don't understand how that could act as verification. I've only tried so far the verified null move pruning, where after cut-off, the search continues with reduced depth.
In a meantime, I've decided to run a test with Pawny - with/without null moves in a row. I will post the results later.

Post Reply