SF 1.9.1 question about search()

[Rein Halbersma]

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>&#40;pos, ss+1, -beta, -&#40;beta-1&#41;, DEPTH_ZERO, ply+1&#41;
  	                                &#58; - search<NonPV>&#40;pos, ss+1, -beta, -&#40;beta-1&#41;, newDepth, ply+1&#41;;
          if &#40;value < beta&#41;
  	        please_explain_why_this_may_happen&#40;); // TODO
      &#125;
      ...
 &#125;

Why could it not happen? It's called search instability. (Or maybe I missed your point again?)

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)?

[mcostalba]

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)?

SF uses a quite aggressive aspiration window so I am not sure about how much could be saved in this way.

[Rein Halbersma]

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)?

SF uses a quite aggressive aspiration window so I am not sure about how much could be saved in this way.

It seems that there are 2 extremes:
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?

[Gerd Isenberg]

(1) PvNode is a template parameter, so we want this code to be generated only for PV nodes. Speed optimization trick.

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.

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.

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 something

[zamar]

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?

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]

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?

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?

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?

In any case, just to avoid confusion:

Current code:

Code: Select all

if &#40;PvNode && value > alpha && value < beta&#41; 
        value = newDepth < ONE_PLY ? -qsearch<PV>&#40;pos, ss+1, -beta, -alpha, DEPTH_ZERO, ply+1&#41; 
                                   &#58; - search<PV>&#40;pos, ss+1, -beta, -alpha, newDepth, ply+1&#41;; 

Suggested safer code that will re-search even if value >= beta

Code: Select all

if &#40;PvNode && alpha < beta-1 && value > alpha&#41; 
        value = newDepth < ONE_PLY ? -qsearch<PV>&#40;pos, ss+1, -beta, -alpha, DEPTH_ZERO, ply+1&#41; 
                                   &#58; - search<PV>&#40;pos, ss+1, -beta, -alpha, newDepth, ply+1&#41;; 

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 &#40;PvNode && value > alpha && value < beta&#41; 
        value = newDepth < ONE_PLY ? -qsearch<PV>&#40;pos, ss+1, -beta, -&#40;value-1&#41;, DEPTH_ZERO, ply+1&#41; 
                                   &#58; - search<PV>&#40;pos, ss+1, -beta, -&#40;value-1&#41;, newDepth, ply+1&#41;; 

[zamar]

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 &#40;PvNode && value > alpha && value < beta&#41; 
        value = newDepth < ONE_PLY ? -qsearch<PV>&#40;pos, ss+1, -beta, -&#40;value-1&#41;, DEPTH_ZERO, ply+1&#41; 
                                   &#58; - search<PV>&#40;pos, ss+1, -beta, -&#40;value-1&#41;, newDepth, ply+1&#41;; 

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.

[zamar]

[
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).

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.

In the past we tried different strategies, but nothing worked better than what we are currently doing...

root_search() is exception of course!

[mcostalba]

Naming Convention? I would call it TemplbPvNode or something

Apart that I really hate hungarian notation

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.

[Rein Halbersma]

[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.