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!
Simple questions about Nullmove
Moderators: hgm, Rebel, chrisw
-
- Posts: 855
- Joined: Sun May 23, 2010 1:32 pm
Re: Simple questions about Nullmove
my code is very similar to the one of the mediocrechess blog
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
Code: Select all
pos.doNullMove();
nullVal = -alphaBeta(ply+1, depth - red, -beta, -beta+1, childPV);
pos.undoNullMove();
if (nullVal >= beta)
return nullVal;
-
- Posts: 127
- Joined: Sat Dec 29, 2012 12:07 am
Re: Simple questions about Nullmove
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?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
-
- Posts: 855
- Joined: Sun May 23, 2010 1:32 pm
Re: Simple questions about Nullmove
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
it can exceed beta if you use a failsoft framework
-
- Posts: 937
- Joined: Fri Mar 10, 2006 4:29 pm
- Location: Germany
Re: Simple questions about Nullmove
This is a null-window search and the returned value can't be inside the search window.Ralf Müller wrote: ↑Sat Sep 08, 2018 12:06 pm 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!
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.
Jörg Oster
-
- Posts: 5566
- Joined: Tue Feb 28, 2012 11:56 pm
Re: Simple questions about Nullmove
Where is the problem with that if you test on "nullVal >= beta"?Ralf Müller wrote: ↑Sat Sep 08, 2018 12:25 pmThank 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?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
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).
-
- Posts: 4052
- Joined: Thu May 15, 2008 9:57 pm
- Location: Berlin, Germany
- Full name: Sven Schüle
Re: Simple questions about Nullmove
I'll try to clean up some misunderstandings. Normal alpha-beta search is:Ralf Müller wrote: ↑Sat Sep 08, 2018 12:25 pmThank 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?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
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.
Sven Schüle (engine author: Jumbo, KnockOut, Surprise)
-
- Posts: 27808
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: Simple questions about Nullmove
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.
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.
-
- Posts: 4052
- Joined: Thu May 15, 2008 9:57 pm
- Location: Berlin, Germany
- Full name: Sven Schüle
Re: Simple questions about Nullmove
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.
Sven Schüle (engine author: Jumbo, KnockOut, Surprise)
-
- Posts: 127
- Joined: Sat Dec 29, 2012 12:07 am
Re: Simple questions about Nullmove
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?
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?