I think the question is why does everyone return after value>=beta from a null-window search? And if these search inconsistencies are so harmless, why not make full use of the returned null-window value and do the re-search with the tighter bounds -search<PV>(pos, ss+1, -beta, -value)?zamar wrote:Why could it not happen? It's called search instability. (Or maybe I missed your point again?)Ralph Stoesser wrote: No, my point is the following. Does value >= beta really mean a fail high?
To say it with code ...
Code: Select all
if (PvNode && value > alpha) { if (value >= beta) { value = newDepth < ONE_PLY ? -qsearch<NonPV>(pos, ss+1, -beta, -(beta-1), DEPTH_ZERO, ply+1) : - search<NonPV>(pos, ss+1, -beta, -(beta-1), newDepth, ply+1); if (value < beta) please_explain_why_this_may_happen(); // TODO } ... }
SF 1.9.1 question about search()
Moderators: hgm, Rebel, chrisw
-
- Posts: 741
- Joined: Tue May 22, 2007 11:13 am
Re: SF 1.9.1 question about search()
-
- Posts: 2684
- Joined: Sat Jun 14, 2008 9:17 pm
Re: SF 1.9.1 question about search()
SF uses a quite aggressive aspiration window so I am not sure about how much could be saved in this way.Rein Halbersma wrote: I think the question is why does everyone return after value>=beta from a null-window search? And if these search inconsistencies are so harmless, why not make full use of the returned null-window value and do the re-search with the tighter bounds -search<PV>(pos, ss+1, -beta, -value)?
-
- Posts: 741
- Joined: Tue May 22, 2007 11:13 am
Re: SF 1.9.1 question about search()
It seems that there are 2 extremes:mcostalba wrote:SF uses a quite aggressive aspiration window so I am not sure about how much could be saved in this way.Rein Halbersma wrote: I think the question is why does everyone return after value>=beta from a null-window search? And if these search inconsistencies are so harmless, why not make full use of the returned null-window value and do the re-search with the tighter bounds -search<PV>(pos, ss+1, -beta, -value)?
a) avoid search instabilities by not using aspiration windows at the root, only re-searching if value>alpha
b) tolerate search instabilities by doing aggresive aspiration windows, re-searching if alpha < value < beta with window [-beta, -value]
SF is now close to the latter extreme, but without the final step of doing the tightest possible re-search window. Why the asymmetric treatment of possible search instabilities?
-
- Posts: 2250
- Joined: Wed Mar 08, 2006 8:47 pm
- Location: Hattingen, Germany
Re: SF 1.9.1 question about search()
Yes, makes sense. I did not recognize PvNode is a template parameter from Ralph's code snippet - Naming Convention? I would call it TemplbPvNode or somethingmcostalba wrote:Not to be pedantic, but I would like to spend few words on this because templates are heavily used in SF and because it seems is one of the few engines with available sources that use this powerful C++ feature.zamar wrote: (1) PvNode is a template parameter, so we want this code to be generated only for PV nodes. Speed optimization trick.
And the two functions will then be compiled indipendently.
So the bottom line is that templates are a facility to generate a family of different functions starting from a single and shared...ehm..template
This greatly reduce source code redundancy with zero speed penalty overhead.
-
- Posts: 613
- Joined: Sun Jan 18, 2009 7:03 am
Re: SF 1.9.1 question about search()
Terminating the search at fail low doesn't sound a good idea. I mean if you research with [value, beta] window, and search just found that this line is really dubious and fails low, then because value > alpha, we terminate the search. Not really what we want, right?Rein Halbersma wrote: SF is now close to the latter extreme, but without the final step of doing the tightest possible re-search window. Why the asymmetric treatment of possible search instabilities?
Joona Kiiski
-
- Posts: 741
- Joined: Tue May 22, 2007 11:13 am
Re: SF 1.9.1 question about search()
I don't understand your comment: what I wrote was to re-search with a tighter window, but I did not offer a suggestion of what to do in case of a fail-low search instability. Perhaps that's the reason for the asymmetry: if you don't research if value>= beta, you'll never know if perhaps a re-search would have given a lower value (at leat not at this ply level). OTOH, if you re-search with an overly optimistic window of [value, beta], you might detect the search instability. Is that it?zamar wrote:Terminating the search at fail low doesn't sound a good idea. I mean if you research with [value, beta] window, and search just found that this line is really dubious and fails low, then because value > alpha, we terminate the search. Not really what we want, right?Rein Halbersma wrote: SF is now close to the latter extreme, but without the final step of doing the tightest possible re-search window. Why the asymmetric treatment of possible search instabilities?
In any case, just to avoid confusion:
Current code:
Code: Select all
if (PvNode && value > alpha && value < beta)
value = newDepth < ONE_PLY ? -qsearch<PV>(pos, ss+1, -beta, -alpha, DEPTH_ZERO, ply+1)
: - search<PV>(pos, ss+1, -beta, -alpha, newDepth, ply+1);
Code: Select all
if (PvNode && alpha < beta-1 && value > alpha)
value = newDepth < ONE_PLY ? -qsearch<PV>(pos, ss+1, -beta, -alpha, DEPTH_ZERO, ply+1)
: - search<PV>(pos, ss+1, -beta, -alpha, newDepth, ply+1);
Code: Select all
if (PvNode && value > alpha && value < beta)
value = newDepth < ONE_PLY ? -qsearch<PV>(pos, ss+1, -beta, -(value-1), DEPTH_ZERO, ply+1)
: - search<PV>(pos, ss+1, -beta, -(value-1), newDepth, ply+1);
-
- Posts: 613
- Joined: Sun Jan 18, 2009 7:03 am
Re: SF 1.9.1 question about search()
And what we are supposed to do ín case of fail-low?? Because search instability is quite high in Stockfish, I believe we would face fail-low around 30-40% of all cases.Rein Halbersma wrote: Most aggressive code that will re-search under the assumption of value as a lower bound. Using a window [value-1, beta] to be able to detect whether a new return of the value is an exact score or a bound.
Code: Select all
if (PvNode && value > alpha && value < beta) value = newDepth < ONE_PLY ? -qsearch<PV>(pos, ss+1, -beta, -(value-1), DEPTH_ZERO, ply+1) : - search<PV>(pos, ss+1, -beta, -(value-1), newDepth, ply+1);
Joona Kiiski
-
- Posts: 613
- Joined: Sun Jan 18, 2009 7:03 am
Re: SF 1.9.1 question about search()
Here is the symmetry: We do not research when value <= alpha (although it's possible that research might give value > alpha). Neither we research when value >= beta (which is just value <= alpha from opponent's point of view), although it's possible that research might return value < beta.Rein Halbersma wrote:[
if you don't research if value>= beta, you'll never know if perhaps a re-search would have given a lower value (at leat not at this ply level).
In the past we tried different strategies, but nothing worked better than what we are currently doing...
root_search() is exception of course!
Joona Kiiski
-
- Posts: 2684
- Joined: Sat Jun 14, 2008 9:17 pm
Re: SF 1.9.1 question about search()
Apart that I really hate hungarian notationGerd Isenberg wrote: Naming Convention? I would call it TemplbPvNode or something
http://en.wikipedia.org/wiki/Hungarian_notation
because introduces an unuseful redundancy (every half decent IDE has a variable lookup facility), is prone to errors and is also ugly, here the used naming convention is that template parameters start with capital letters (as for the constants) while variables start with lower case.
-
- Posts: 741
- Joined: Tue May 22, 2007 11:13 am
Re: SF 1.9.1 question about search()
[quote="zamar"][quote="Rein Halbersma"][
if you don't research if value>= beta, you'll never know if perhaps a re-search would have given a lower value (at leat not at this ply level).
[/quote]
Here is the symmetry: We do not research when value <= alpha (although it's possible that research might give value > alpha). Neither we research when value >= beta (which is just value <= alpha from opponent's point of view), although it's possible that research might return value < beta.
[/quote]
With aspiration windows as you do in SF, you are right: a null-window result value<=alpha could be a false fail low. But if you search at the root with a [-INF,+INF] window, then during the PV nodes, you are guaranteed that a fail-low on a search with a truncated upper window really is failing low.
if you don't research if value>= beta, you'll never know if perhaps a re-search would have given a lower value (at leat not at this ply level).
[/quote]
Here is the symmetry: We do not research when value <= alpha (although it's possible that research might give value > alpha). Neither we research when value >= beta (which is just value <= alpha from opponent's point of view), although it's possible that research might return value < beta.
[/quote]
With aspiration windows as you do in SF, you are right: a null-window result value<=alpha could be a false fail low. But if you search at the root with a [-INF,+INF] window, then during the PV nodes, you are guaranteed that a fail-low on a search with a truncated upper window really is failing low.