Null move pruning

[Dann Corbit]

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?

Branching factor is the time to complete the subseqent ply divided by the time to complete the current ply.

For instance, if ply 12 takes 10 seconds and ply 11 takes 3 seconds, then the branching factor is 10/3 = 3.33.

Each search will differ a little, so it should be considered as an average over a large number of positions and plies.

Here are the conditions from Scorpio as to when Scorpio will perform a null move or not:

Code: Select all

if(!sb->hstack[sb->hply - 1].checks       // Not in check
 && !sb->pstack->mate_threat              // No mate threat  
 && sb->pstack->node_type != PV_NODE      // Not a pv node
 && sb->pstack->hash_flags != AVOID_NULL  // Not an "avoid null move" state
 && sb->piece_c[sb->player]               // I have at least one full piece
 && sb->all_man_c > 5                     // There are at least 5 chessmen left
 ) {
 // Do null move search here...
 }

[cms271828]

Ok, when you put it like that regarding branching factor, its quite obvious, and efficient as you don't need to execute anything during a search, except between the searches of the iterative deepening.

For the null move (R=2), I'm doing:

Null move on root node (if possible)
Node must not be in check for null move
D >= 4, so that D-1-2 is not 0, after following Bob's advice of not going into QS directly after null.
Won't play null move if the previous move was null move.


I also need to add something for when a few pieces left.
I don't quite get what the 'No mate threat' means, and also what is a PV node? If that means a node on the principle variation, then I think since I search my hash before playing null move, that might deal with that (but I'm not sure).

[vladstamate]

Hmm,

If I try the null move at root node before I generate and make any moves and that fails high and I return beta, what move should I actually make? There is no PV, since the PV from null move is not really useful since it starts with the wrong side to move.

How can null-move be done at root nodes? Am I missing something?

Regards,
Vlad.

[Dann Corbit]

Consider IID at ply 13

[bob]

Ok, when you put it like that regarding branching factor, its quite obvious, and efficient as you don't need to execute anything during a search, except between the searches of the iterative deepening.

For the null move (R=2), I'm doing:

Null move on root node (if possible)
Node must not be in check for null move
D >= 4, so that D-1-2 is not 0, after following Bob's advice of not going into QS directly after null.
Won't play null move if the previous move was null move.


I also need to add something for when a few pieces left.
I don't quite get what the 'No mate threat' means, and also what is a PV node? If that means a node on the principle variation, then I think since I search my hash before playing null move, that might deal with that (but I'm not sure).

Hang on a sec. I didn't say "don't go into q-search following a null". I simply said there is a danger. One thing several have used is R=3 until you get within 5-6-7 plies of the frontier (depth=0) and then back off to R=2. But doing null-move _everywhere_ was actually better for me in testing, but once I added checks to the q-search I removed the R=2 step down and use R=3 everywhere, which is even better now.

[bob]

Hmm,

If I try the null move at root node before I generate and make any moves and that fails high and I return beta, what move should I actually make? There is no PV, since the PV from null move is not really useful since it starts with the wrong side to move.

How can null-move be done at root nodes? Am I missing something?

Regards,
Vlad.

You would never do it at the root. We only use null-move to quickly terminate a complete search at some node, because we are doing so well that even if we play a null our opponent fails low, which makes us fail high. But at the root you can't just fail high and say "I am winning". You actually have to play a real move so you never try a null-move search at all there. I actually have a separate Search() function called SearchRoot() since there are several things you don't want to do at the root. For example (besides null-move) I don't do a hash probe, because again I can't terminate the search due to a hash hit, I need a best move to play.

[vladstamate]

Hmm,

If I try the null move at root node before I generate and make any moves and that fails high and I return beta, what move should I actually make? There is no PV, since the PV from null move is not really useful since it starts with the wrong side to move.

How can null-move be done at root nodes? Am I missing something?

Regards,
Vlad.

You would never do it at the root. We only use null-move to quickly terminate a complete search at some node, because we are doing so well that even if we play a null our opponent fails low, which makes us fail high. But at the root you can't just fail high and say "I am winning". You actually have to play a real move so you never try a null-move search at all there. I actually have a separate Search() function called SearchRoot() since there are several things you don't want to do at the root. For example (besides null-move) I don't do a hash probe, because again I can't terminate the search due to a hash hit, I need a best move to play.

Thank you for confirming. That is what I do too (two search funtions, one for root only, etc). My comment was following colin's post:

Null move on root node (if possible)

where I think it is never possible to do a null move at root.

Regards,
Vlad.

[jwes]

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?

Branching factor is the time to complete the subseqent ply divided by the time to complete the current ply.

For instance, if ply 12 takes 10 seconds and ply 11 takes 3 seconds, then the branching factor is 10/3 = 3.33.

Each search will differ a little, so it should be considered as an average over a large number of positions and plies.

One problem with this is that it makes reductions look better than extensions.

[bob]

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?

Branching factor is the time to complete the subseqent ply divided by the time to complete the current ply.

For instance, if ply 12 takes 10 seconds and ply 11 takes 3 seconds, then the branching factor is 10/3 = 3.33.

Each search will differ a little, so it should be considered as an average over a large number of positions and plies.

One problem with this is that it makes reductions look better than extensions.

Actually, (and unfortunately) this is not the definition of "branching factor" The term "branching factor" is clearly defined in AI books dealing with tree searching, and is defined as the number of out-bound branches from any node. In Chess, it is more of an "average branching factor" since different nodes have a different number of legal moves out of them. In a pure search approach like minimax, the branching factor can actually be computed as Dann says, since if each node has 10 moves leading from it, each depth will take 10x longer than the last.

But in chess, the term that should really be used is "effective branching factor". Which takes the shape of the tree and tries to extract the actual branching factor by assuming that if an iteration takes twice as long for the next iteration, then the branching factor must be 2. The actual branching factor for chess averages 38 according to most AI books, maybe +/- 3 or so depending on the book. The effective branching factor is the number most want to use today, as it is the number that predicts how long the next iteration will take, based on the time the last iteration took.

Today, EBF of 2.0 is pretty common with the pruning and reductions being done, while the real BF is holding at an average of 38 since the rules of the game have not been changed at all.

[cms271828]

Ok, I've separated my search to include a root node, but I'm somewhat confused.
If you used null move in the root, and it returned a value, then I can see theres no move to play, which makes sense.

But, in the root, doesn't beta=infinity, so how can you have val>=beta occuring at the root? So at the root, the null move should never return.

Or perhaps I've missed the point