next singular extension test

[bob]

Hi,

some engines set the search window on next depth to value-of-last-depth +/- window. Thus in pv alpha = value_of_last_depth - window and beta = value_of_last_depth + window. The expected value the search will return in pv-nodes is then alpha + (beta - alpha) / 2.
If window is small, then alpha will be near the expected value. If the window is large you´ll get no singular extension even if there is only one good move als alpha is far below the expected value.

Maybe you can use value_of_last_depth as test for singularity in pv nodes. This will not depend on window-size and -symetrie and is stable on research. If singular extension will result in a fail low at root the research with larger window may result in not doing singular extension any longer if using alpha. This will make the effect of singular extension rather random at pv nodes. Hash will not solve the problem (at least in spike).

Greetings Volker

I used an aspiration window of +/- 30 during the singular tests. That's one place where Hsu's implementation is superior, in that the aspiration window doesn't change a thing in the way he tests for singularity.

[Ralph Stoesser]

I think the net effect of this change is something like "no SE-extension on SE-extension child nodes", similar to the null move condition. But then, the appropriate code change should look a little differently...

But this should be already taken care of by the non recursive condition here:

Code: Select all

    singularExtensionNode =   depth >= SingularExtensionDepth[PvNode]
                           && tte
                           && tte->move()
                           && !excludedMove // Do not allow recursive singular extension search
                           && is_lower_bound(tte->type())
                           && tte->depth() >= depth - 3 * OnePly;

This condition means "no SE on the same ply". I meant "no SE on ply+1 if ply was an exclusion search ply". But my assumption was wrong. Because of the huge depth reduction in SE search (depth/2) and the depth >= SingularExtensionDepth[PvNode] condition that would happen too seldom (only in late endgames) to have an effect.

To also apply the exclusion key on the child nodes of an exclusion search seams to help in preserving valuable TT entries. I've also tried to put the whole exlusion subtree into the exclusion pool (only dynamically with the help of the search stack, without storing the exclusion key in position key), but the tested scheme seemed to work best.

So I take back what I wrote and would propose to test this patch on a quad.

[mcostalba]

So I take back what I wrote and would propose to test this patch on a quad.

Test was stopped earlier because result is very bad:

Orig - Mod: 451 - 385 - 1579 (-9 elo!)

Time control 20" + 0.1 on a QUAD, 4 threads.

Here is the tested patch:

Code: Select all

Subject: Use "exclusion search" key also at first level childs

The idea is to avoid overwrite of high depth TT values by
the shallow depth ones by SE that have the additional
burden to use lowered beta values, so a fail low position
searched at high depth could be overwritten with a fail-high
flag after a SE at small depth and even with an artificially
reduced beta.

Patch by Ralph Stoesser.

---
 src/search.cpp |    5 +++--
 1 files changed, 3 insertions(+), 2 deletions(-)

diff --git a/src/search.cpp b/src/search.cpp
index 59025fb..2d21424 100644
--- a/src/search.cpp
+++ b/src/search.cpp
@@ -1010,9 +1010,10 @@ namespace {
     // Step 4. Transposition table lookup
 
     // We don't want the score of a partial search to overwrite a previous full search
-    // TT value, so we use a different position key in case of an excluded move exists.
+    // TT value, so we use a different position key we are at the root or at the first
+    // level child nodes of an exclusion search.
     excludedMove = ss->excludedMove;
-    posKey = excludedMove ? pos.get_exclusion_key() : pos.get_key();
+    posKey = excludedMove || (ss-1)->excludedMove ? pos.get_exclusion_key() : pos.get_key();
 
     tte = TT.retrieve(posKey);
     ttMove = (tte ? tte->move() : MOVE_NONE);
 

[Ralph Stoesser]

So I take back what I wrote and would propose to test this patch on a quad.

Test was stopped earlier because result is very bad:

Orig - Mod: 451 - 385 - 1579 (-9 elo!)

Time control 20" + 0.1 on a QUAD, 4 threads.

Here is the tested patch:

Code: Select all

Subject: Use "exclusion search" key also at first level childs

The idea is to avoid overwrite of high depth TT values by
the shallow depth ones by SE that have the additional
burden to use lowered beta values, so a fail low position
searched at high depth could be overwritten with a fail-high
flag after a SE at small depth and even with an artificially
reduced beta.

Patch by Ralph Stoesser.

---
 src/search.cpp |    5 +++--
 1 files changed, 3 insertions(+), 2 deletions(-)

diff --git a/src/search.cpp b/src/search.cpp
index 59025fb..2d21424 100644
--- a/src/search.cpp
+++ b/src/search.cpp
@@ -1010,9 +1010,10 @@ namespace {
     // Step 4. Transposition table lookup
 
     // We don't want the score of a partial search to overwrite a previous full search
-    // TT value, so we use a different position key in case of an excluded move exists.
+    // TT value, so we use a different position key we are at the root or at the first
+    // level child nodes of an exclusion search.
     excludedMove = ss->excludedMove;
-    posKey = excludedMove ? pos.get_exclusion_key() : pos.get_key();
+    posKey = excludedMove || (ss-1)->excludedMove ? pos.get_exclusion_key() : pos.get_key();
 
     tte = TT.retrieve(posKey);
     ttMove = (tte ? tte->move() : MOVE_NONE);
 

Did you initialize ss->excludedMove = MOVE_NONE in root_search() ?

[mcostalba]

Did you initialize ss->excludedMove = MOVE_NONE in root_search() ?

In id_loop(), so before root_search() there is the call:

Code: Select all

init_ss_array(ss, PLY_MAX_PLUS_2);

Where the function is defined as:

Code: Select all

  // init_ss_array() does a fast reset of the first entries of a SearchStack
  // array and of all the excludedMove and skipNullMove entries.

  void init_ss_array(SearchStack* ss, int size) {

    for &#40;int i = 0; i < size; i++, ss++)
    &#123;
        ss->excludedMove = MOVE_NONE;
        ss->skipNullMove = false;
        ss->reduction = DEPTH_ZERO;

        if &#40;i < 3&#41;
            ss->killers&#91;0&#93; = ss->killers&#91;1&#93; = ss->mateKiller = MOVE_NONE;
    &#125;
  &#125;

BTW ss[0] corresponds to the root_search() as you can easily verify.

Then, when ss->excludedMove is set, it is always reset when the search return at the call point, for instance in singluar extension code:

Code: Select all

ss->excludedMove = move;
ss->skipNullMove = true;
Value v = search<NonPV>&#40;pos, ss, b - 1, b, depth / 2, ply&#41;;
ss->skipNullMove = false;
ss->excludedMove = MOVE_NONE;

[Ralph Stoesser]

Did you initialize ss->excludedMove = MOVE_NONE in root_search() ?

In id_loop(), so before root_search() there is the call:

Code: Select all

init_ss_array(ss, PLY_MAX_PLUS_2);

Where the function is defined as:

Code: Select all

  // init_ss_array() does a fast reset of the first entries of a SearchStack
  // array and of all the excludedMove and skipNullMove entries.

  void init_ss_array(SearchStack* ss, int size) {

    for &#40;int i = 0; i < size; i++, ss++)
    &#123;
        ss->excludedMove = MOVE_NONE;
        ss->skipNullMove = false;
        ss->reduction = DEPTH_ZERO;

        if &#40;i < 3&#41;
            ss->killers&#91;0&#93; = ss->killers&#91;1&#93; = ss->mateKiller = MOVE_NONE;
    &#125;
  &#125;

BTW ss[0] corresponds to the root_search() as you can easily verify.

Then, when ss->excludedMove is set, it is always reset when the search return at the call point, for instance in singluar extension code:

Code: Select all

ss->excludedMove = move;
ss->skipNullMove = true;
Value v = search<NonPV>&#40;pos, ss, b - 1, b, depth / 2, ply&#41;;
ss->skipNullMove = false;
ss->excludedMove = MOVE_NONE;

Yes, that's right.
Interesting how much your result differs from mine.
BTW I tested against the latest internal version I had, not against SF 1.8, because of the search stack bugs.
Anyhow, thanks for testing.