Null move pruning

[bob]

Looking at the code again in blue http://web.archive.org/web/200404270146 ... llmove.htm
I'm concerned about the depth, since say D=1, this wouldn't call alphabeta (or qs in my case) with depth 0, but with depth -2.

So perhaps we need to surround that block with 'IF D >= 3...' so that alphabeta (or qs) gets called by passing in 0 or greater depth.

Yes, the code in blue requires some "if (depth >= ...)" guard. If you want to allow your null move search to start directly with qsearch, i.e. with zero plies of full-width search, then the condition should be "if (depth - 1 - R >= 0)" which is equivalent to "if (depth >= R + 1)". Otherwise (which is what I would prefer since I think a null move search that does only qsearch can be dangerous),

You can also add a layer of checking moves at the first q-search ply (which is what I do) to avoid most of the problems you'd get from collapsing the tree and dropping right into a capture-only search which might not be able to properly refute the null-move and lead to a ton of errors.

the condition should be "if (depth - 1 - R >= XX)" or "if (depth >= R + 1 + XX)" where XX denotes the minimum number of plies above the horizon that you allow to start a null move search.

Code: Select all

if (depth >= R + 1 + XX) {
    MakeNullMove();
    val = -AlphaBeta(depth - 1 - R, -beta, -beta + 1);
    UnmakeNullMove();
    if (val >= beta)
        return beta;
}

Sven

[bob]

I don't think there is any danger jumping directly into QS with a null move, more than with any other move. If there is a threat that cannot be found by the opponent in a QS reply to null move, then it would not be found in QS after a real move either, and as a cosequence also not after a a two ply delaying tactic (as is almost always available) plus a real move. So searching the real moves after a d=1 null move fails high is an almost certain waste of time, as the search is almost guaranteed to come up with a delaying tactic that fails high, even when there would be a threat that is non-detectable in QS.

There is a huge danger, because not only do you not find the correct refutation because the q-search might only do captures, but you also just lopped 2-3 plies off the search and moved that error much closer to the root where you might not be able to escape the effect. This is what led several of us to independently discover what Heinz called "adaptive null-move search" so that R was reduced near the tips to avoid these errors. Or you can add at least checks to the first layer of q-search nodes so that you won't overlook simple mates that break the null-move search.

[Ross Boyd]

There are two well known solutions to safegard against bad zugzwang searches. There is verified null move search (by Omid David) where you go ahead and do a quick search to refute the move, and double null move technique (by Vincent Diepveen) which says that you can never do two null moves in a row. I like Vincent's solution as it is simple and clear.

Hi Dann,

With regard to Vincent's double-null move, I was under the impression that he DOES allow two null moves in a row. The idea being that 2 null moves in a row will pick up zugzwang problems ... but it may just need a couple extra ply of search to detect them.

However, allowing MORE than 2 null moves in a row should be prevented as the null move searches would then simply degenerate into practically no depth at all.

Ross

[cms271828]

Thanks for tips, I'm not really concerned about zugzwangs at present, I think I'll just cut the null move when board starts to get very empty.

I've been debugging all day, cause my hash keys were not matching, but I seem to have fixed it, almost reaching 13ply in 5 mins from a start position, and my debugger isn't moaning any more.

Couple of questions now that I've got to here..
does it matter if I use null move at the root?

And I want to performance test engine, I have node/sec counts, but thats just speed, I was thinking of calculating average branching factor as appose to just depth, which is time dependent.

Any thoughts?

[Dann Corbit]

Thanks for tips, I'm not really concerned about zugzwangs at present, I think I'll just cut the null move when board starts to get very empty.

I've been debugging all day, cause my hash keys were not matching, but I seem to have fixed it, almost reaching 13ply in 5 mins from a start position, and my debugger isn't moaning any more.

Couple of questions now that I've got to here..
does it matter if I use null move at the root?

It's perfectly fine

And I want to performance test engine, I have node/sec counts, but thats just speed, I was thinking of calculating average branching factor as appose to just depth, which is time dependent.

Any thoughts?

Branching factor is a far, far better measure than NPS.
Of course, reduction in branching factor is only a benefit if the things you are trimming from the search are the right things. It's easy to write a search with a branch factor of 1.0 (just always pick the top node from your list) and yet your 1000 ply search is totally useless.

[cms271828]

Hi, thing is that null move is a bit weird..

Just using alphabeta pruning represents a real portion of the space of possibilities arising from a search, so it seems natural to work out the branching factor here.

But with null move, you're looking at positions that aren't part of the search.

So if your null move returns, would you just say that node has branching factor of 1, and if it doesn't, you would have '1 (for null move played) + normal moves played (till a cut off, or all of them played)' as the branching factor for that node???

I was considering doing the above for all non-qs nodes, and getting an average.
Then could do same thing with qs nodes, but without all the null move stuff.

So I finish with 2 branching factors, one for non-qs, and one for qs.

Is that good?

[Dann Corbit]

Hi, thing is that null move is a bit weird..

Just using alphabeta pruning represents a real portion of the space of possibilities arising from a search, so it seems natural to work out the branching factor here.

But with null move, you're looking at positions that aren't part of the search.

So if your null move returns, would you just say that node has branching factor of 1, and if it doesn't, you would have '1 (for null move played) + normal moves played (till a cut off, or all of them played)' as the branching factor for that node???

I was considering doing the above for all non-qs nodes, and getting an average.
Then could do same thing with qs nodes, but without all the null move stuff.

So I finish with 2 branching factors, one for non-qs, and one for qs.

Is that good?

Branching factor is a measure for the entire search of ply N.
If null move gives you a branching factor of 1 for some ply, then almost surely it is a bug.

The best chess programs have a branching factor of about 2. Very few amateur programs approach that branching factor.

Alpha-Beta with good move ordering will give you a branch factor of about 6 (from 35 for pure mini-max).

Null move pruning will reduce it further, perhaps to 4 or so. Then, additional pruning methods such as LMR can reduce it further.

[cms271828]

Thanks, buts its too unclear for me to understand.

If you apply null move in a node, which returns since val>=beta, then that node has only had one moved played (the null move), so wouldn't its branching factor be 1?

I don't know how I can measure branching factor if I don't know its defined.

Also, when is a good time to stop the null move pruning to avoid obvious zugwangs, as I know its possible for middlegame positions to contain zugzwangs, but they are rare enough for me not to worry about.

But I think zugzwangs during endgame, could produce bad moves if I always keep the null pruning turned on.

Thanks for any input.

[Dann Corbit]

Thanks, buts its too unclear for me to understand.

If you apply null move in a node, which returns since val>=beta, then that node has only had one moved played (the null move), so wouldn't its branching factor be 1?

I don't know how I can measure branching factor if I don't know its defined.

The result of a null move hit is a search reduction of N plies (let's say two for now).

So, imagine we are doing an 8 ply search. Suppose further that there are ten legal moves. Suppose (finally) that there are two root nodes that qualify for null move reductions and none others. What would the impact be?

Probably, the pv node is unaffected. Almost all of the effort is spent searching this node anyway (the other nodes will be zero window searches).

So the search effort would be:
1. pv node search -- same time as before {perhaps half the time of the total search}
2. 7 root nodes that are not null move choices -- no change in time {same as before} = (7/9) * (1/2) = 39% of the time
3. 2 null move root nodes search much faster -- they previously took (2/9) * (1/2) = 11% of the time but now only 3% because we search 8 plies instead of 10.

Hence our total search is 8% faster than before.

So it seems that null move would be a fairly small benefit here. However, null moves happen all over the place {they are a very common occurence}. So, in real life, most of the time we will experience huge reductions from nodes in many places.

How is it that we might get a branching factor of 1? That means that we only examined one move per ply (within some constant factor). If that actually happened, then one of two things is true:
1. Every single move is forced.
2. We are pruning moves we should not prune.

Situation number 1 is very rare. If you see a branching factor of 1 in any search then probably something is wrong. Either that, or you have solved the game of chess.

[cms271828]

Yeh that makes sense pretty much, but what is branching factor?

Does it apply to a node or to a search?

If a null move is played in a node, which returns, then that node only had 1 branch.
So how do we measure it? Do we average it over all the nodes, or is it something totally different?