Simple questions about Nullmove

[Ralf Müller]

Hello,

I'm currently fiddling around with my nullmove pruning.
The usual pseudo code gives a search window of [-beta, -beta+1]. And if eval > beta, cut-off. (f.e. here: http://mediocrechess.blogspot.com/2007/ ... moves.html).

If I understand correctly, the eval return is always between beta and beta-1. So with this search window there isn't any chance to exceed beta, isn't it? Where is the mistake?

Many thanks!

[elcabesa]

my code is very similar to the one of the mediocrechess blog

Code: Select all

pos.doNullMove();
nullVal = -alphaBeta(ply+1, depth - red, -beta, -beta+1, childPV);
pos.undoNullMove();

if (nullVal >= beta)
  return nullVal;

as you can see, since you are searching with a window [-beta, -beta+1], having - before aphabeta call, and a check on nullVal >= beta it work

[Ralf Müller]

my code is very similar to the one of the mediocrechess blog

Code: Select all

pos.doNullMove();
nullVal = -alphaBeta(ply+1, depth - red, -beta, -beta+1, childPV);
pos.undoNullMove();

if (nullVal >= beta)
return nullVal;

as you can see, since you are searching with a window [-beta, -beta+1], having - before aphabeta call, and a check on nullVal >= beta it work

Thank you for your quick answer! But the - before alphabeta call gives a return value between [beta, beta-1], doesn't it? If so, nullVal never exceeds beta. Where's my mistake?

[elcabesa]

it return a value in the range [ beta -1; beta ] and it can not exceed beta if you use failhard.

it can exceed beta if you use a failsoft framework

[Joerg Oster]

Hello,

I'm currently fiddling around with my nullmove pruning.
The usual pseudo code gives a search window of [-beta, -beta+1]. And if eval > beta, cut-off. (f.e. here: http://mediocrechess.blogspot.com/2007/ ... moves.html).

If I understand correctly, the eval return is always between beta and beta-1. So with this search window there isn't any chance to exceed beta, isn't it? Where is the mistake?

Many thanks!

This is a null-window search and the returned value can't be inside the search window.
It only tells you whether the returned value is below beta (nullVal < beta) or equal to or above beta (nullVal >= beta), in which case you take the cutoff.

[syzygy]

my code is very similar to the one of the mediocrechess blog

Code: Select all

pos.doNullMove();
nullVal = -alphaBeta(ply+1, depth - red, -beta, -beta+1, childPV);
pos.undoNullMove();

if (nullVal >= beta)
return nullVal;

as you can see, since you are searching with a window [-beta, -beta+1], having - before aphabeta call, and a check on nullVal >= beta it work

Thank you for your quick answer! But the - before alphabeta call gives a return value between [beta, beta-1], doesn't it? If so, nullVal never exceeds beta. Where's my mistake?

Where is the problem with that if you test on "nullVal >= beta"?

The idea of nullmove pruning is that you probably have a move that is at least as good as doing nothing (a nullmove).
That means that if doing nothing is already sufficient to refute the opponent's last move (i.e. is better than beta), you can already return beta (assuming that at least one of your moves is better than beta).

So what you want to test is whether the nullmove search returns a value >= beta.
To do that most efficiently, you search with a window (beta-1, beta).

[Sven]

my code is very similar to the one of the mediocrechess blog

Code: Select all

pos.doNullMove();
nullVal = -alphaBeta(ply+1, depth - red, -beta, -beta+1, childPV);
pos.undoNullMove();

if (nullVal >= beta)
return nullVal;

as you can see, since you are searching with a window [-beta, -beta+1], having - before aphabeta call, and a check on nullVal >= beta it work

Thank you for your quick answer! But the - before alphabeta call gives a return value between [beta, beta-1], doesn't it? If so, nullVal never exceeds beta. Where's my mistake?

I'll try to clean up some misunderstandings. Normal alpha-beta search is:

score = -alphaBeta(..., -beta, -alpha, ...);

where alpha and beta are the current bounds at the current node. The recursive call descends to the child node where "alphaChild" = -beta and "betaChild" = -alpha. If the child node returns with a cutoff then it does so because of "bestChildScore >= betaChild", so it either returns -alpha (when using the fail-hard framework) or something >= -alpha (when using the fail-soft framework). In both cases the negated return value (from "-alphaBeta(...)") after returning from the child node always leads to:

score <= alpha

In this case you obviously can't get a cutoff at the current node. If, however, the child node does not return with a cutoff then you know "bestChildScore < betaChild", so the child node returns a value < -alpha, and therefore you get:

score > alpha

at your current node, which may or may not imply that score >= beta. Only here the current node might take a cutoff.

To summarize, with fail-hard framework the returned score is within [alpha .. beta] while with fail-soft framework there is no limitation. In both cases you are mostly interested in comparing the score to beta.

Now with nullmove pruning you can simply replace "alpha" by "beta - 1" (so -(beta - 1) or -beta+1 becomes "betaChild"). With fail-hard framework the returned score is within [beta - 1 .. beta]. Then the second case from above, "score > alpha", becomes "score > beta - 1" which is the same as "score >= beta". Here you see how it works: if making the null move (i.e., passing) does not allow the opponent to raise his score above "alphaChild" (which is the same as not allowing the opponent to take a cutoff since "betaChild == alphaChild + 1" in a null-window or zero-window) then you can take the null-move cutoff at the current node.

[hgm]

I think the misstake is indeed that the cutoff condition should be score >= beta, not score > beta. The latter would indeed never work in combination with fail hard, where the return score is limited to the window (inclusive).

Even with fail soft score > beta would work very poorly, as the search would almost never take the trouble to return a result > beta when it fails high.

[Sven]

Even with fail soft score > beta would work very poorly, as the search would almost never take the trouble to return a result > beta when it fails high.

At least it would "work" for parents of some ALL nodes where, with fail soft, bestScore is initialized to -INF and always stays below alpha, being caused by all children of the ALL node getting a cutoff with their score > beta (and so on). But in general I agree since "score > beta" is an incorrect cutoff condition and will also increase the tree size significantly.

[Ralf Müller]

Thank you for alle your clarifying answers, which helped me a lot!

Now I implemented the Nullmove, but somehow I expected a greater speed improvement. At depth 5 there is no speed improvement at all, at depth 6 the speed improvement is ca. 35%. Does the nullmove need a certain depth to kick in?