Store distinct upper and lower bound scores

This is more complex than what I'd like but I
was unable to split in small chunks.

Here we add 2 slots to TTEntry (valueUpper and depthUpper)
so that sizeof(TTEntry) returns to the original 16 bytes
and we can pack exactly 4 entries in a 64 bytes cache line.

Now we save an upper bound score alongside a lower (exact)
score. The idea is to increase TT cut-offs rates becuase
there is now an higher probability for a node to use TT info.

This patch is highly experimental and probably needs further
steps as is hinted by an unrealistic bench number:

bench: 2022385

diff --git a/src/search.cpp b/src/search.cpp
index f6c2233b1519b8887f19919c789059e603e019d7..07405d42beed4a52f586d0ccae66c4b327797226 100644 (file)
--- a/src/search.cpp
+++ b/src/search.cpp
@@ -482,7 +482,7 @@ namespace {
     Key posKey;
     Move ttMove, move, excludedMove, bestMove, threatMove;
     Depth ext, newDepth;
     Key posKey;
     Move ttMove, move, excludedMove, bestMove, threatMove;
     Depth ext, newDepth;

-    Value bestValue, value, ttValue;
+    Value bestValue, value, ttValue, ttValueUpper;

     Value eval, nullValue, futilityValue;
     bool inCheck, givesCheck, pvMove, singularExtensionNode;
     bool captureOrPromotion, dangerous, doFullDepthSearch;
     Value eval, nullValue, futilityValue;
     bool inCheck, givesCheck, pvMove, singularExtensionNode;
     bool captureOrPromotion, dangerous, doFullDepthSearch;


@@ -544,31 +544,43 @@ namespace {
     tte = TT.probe(posKey);
     ttMove = RootNode ? RootMoves[PVIdx].pv[0] : tte ? tte->move() : MOVE_NONE;
     ttValue = tte ? value_from_tt(tte->value(), ss->ply) : VALUE_NONE;
     tte = TT.probe(posKey);
     ttMove = RootNode ? RootMoves[PVIdx].pv[0] : tte ? tte->move() : MOVE_NONE;
     ttValue = tte ? value_from_tt(tte->value(), ss->ply) : VALUE_NONE;

+    ttValueUpper = tte ? value_from_tt(tte->value_upper(), ss->ply) : VALUE_NONE;

 
     // At PV nodes we check for exact scores, while at non-PV nodes we check for
     // a fail high/low. Biggest advantage at probing at PV nodes is to have a
     // smooth experience in analysis mode. We don't probe at Root nodes otherwise
     // we should also update RootMoveList to avoid bogus output.
 
     // At PV nodes we check for exact scores, while at non-PV nodes we check for
     // a fail high/low. Biggest advantage at probing at PV nodes is to have a
     // smooth experience in analysis mode. We don't probe at Root nodes otherwise
     // we should also update RootMoveList to avoid bogus output.

-    if (   !RootNode
-        && tte
-        && tte->depth() >= depth
-        && ttValue != VALUE_NONE // Only in case of TT access race
-        && (           PvNode ?  tte->type() == BOUND_EXACT
-            : ttValue >= beta ? (tte->type() & BOUND_LOWER)
-                              : (tte->type() & BOUND_UPPER)))
+    if (!RootNode && tte)

     {
     {

-        TT.refresh(tte);
-        ss->currentMove = ttMove; // Can be MOVE_NONE
+        // Fail High
+        if (  (tte->type() & BOUND_LOWER)
+            && ttValue >= beta
+            && tte->depth() >= depth
+            && ttValue != VALUE_NONE) // Only in case of TT access race
+        {
+            // Update killers, we assume ttMove caused a cut-off
+            if (    ttMove
+                && !pos.is_capture_or_promotion(ttMove)
+                &&  ttMove != ss->killers[0])
+            {
+                ss->killers[1] = ss->killers[0];
+                ss->killers[0] = ttMove;
+            }
+            TT.refresh(tte);
+            ss->currentMove = ttMove; // Can be MOVE_NONE
+            return ttValue;
+        }

 
 

-        if (    ttValue >= beta
-            &&  ttMove
-            && !pos.is_capture_or_promotion(ttMove)
-            &&  ttMove != ss->killers[0])
+        // Fail Low
+        if (  (tte->type() & BOUND_UPPER)
+            && ttValueUpper < beta
+            && tte->depth_upper() >= depth
+            && ttValueUpper != VALUE_NONE) // Only in case of TT access race

         {
         {

-            ss->killers[1] = ss->killers[0];
-            ss->killers[0] = ttMove;
+            TT.refresh(tte);
+            ss->currentMove = ttMove; // Can be MOVE_NONE
+            return ttValueUpper;

         }
         }

-        return ttValue;

     }
 
     // Step 5. Evaluate the position statically and update parent's gain statistics
     }
 
     // Step 5. Evaluate the position statically and update parent's gain statistics


@@ -1089,7 +1101,7 @@ split_point_start: // At split points actual search starts from here
     const TTEntry* tte;
     Key posKey;
     Move ttMove, move, bestMove;
     const TTEntry* tte;
     Key posKey;
     Move ttMove, move, bestMove;

-    Value bestValue, value, ttValue, futilityValue, futilityBase, oldAlpha;
+    Value bestValue, value, ttValue, ttValueUpper, futilityValue, futilityBase, oldAlpha;

     bool givesCheck, enoughMaterial, evasionPrunable, fromNull;
     Depth ttDepth;
 
     bool givesCheck, enoughMaterial, evasionPrunable, fromNull;
     Depth ttDepth;
 


@@ -1111,21 +1123,34 @@ split_point_start: // At split points actual search starts from here
     tte = TT.probe(posKey);
     ttMove = tte ? tte->move() : MOVE_NONE;
     ttValue = tte ? value_from_tt(tte->value(),ss->ply) : VALUE_NONE;
     tte = TT.probe(posKey);
     ttMove = tte ? tte->move() : MOVE_NONE;
     ttValue = tte ? value_from_tt(tte->value(),ss->ply) : VALUE_NONE;

+    ttValueUpper = tte ? value_from_tt(tte->value_upper(),ss->ply) : VALUE_NONE;

 
     // Decide whether or not to include checks, this fixes also the type of
     // TT entry depth that we are going to use. Note that in qsearch we use
     // only two types of depth in TT: DEPTH_QS_CHECKS or DEPTH_QS_NO_CHECKS.
     ttDepth = InCheck || depth >= DEPTH_QS_CHECKS ? DEPTH_QS_CHECKS
                                                   : DEPTH_QS_NO_CHECKS;
 
     // Decide whether or not to include checks, this fixes also the type of
     // TT entry depth that we are going to use. Note that in qsearch we use
     // only two types of depth in TT: DEPTH_QS_CHECKS or DEPTH_QS_NO_CHECKS.
     ttDepth = InCheck || depth >= DEPTH_QS_CHECKS ? DEPTH_QS_CHECKS
                                                   : DEPTH_QS_NO_CHECKS;

-    if (   tte
-        && tte->depth() >= ttDepth
-        && ttValue != VALUE_NONE // Only in case of TT access race
-        && (           PvNode ?  tte->type() == BOUND_EXACT
-            : ttValue >= beta ? (tte->type() & BOUND_LOWER)
-                              : (tte->type() & BOUND_UPPER)))
+    if (tte)

     {
     {

-        ss->currentMove = ttMove; // Can be MOVE_NONE
-        return ttValue;
+        // Fail High
+        if (  (tte->type() & BOUND_LOWER)
+            && ttValue >= beta
+            && tte->depth() >= ttDepth
+            && ttValue != VALUE_NONE) // Only in case of TT access race
+        {
+            ss->currentMove = ttMove; // Can be MOVE_NONE
+            return ttValue;
+        }
+
+        // Fail Low
+        if (  (tte->type() & BOUND_UPPER)
+            && ttValueUpper < beta
+            && tte->depth_upper() >= ttDepth
+            && ttValueUpper != VALUE_NONE) // Only in case of TT access race
+        {
+            ss->currentMove = ttMove; // Can be MOVE_NONE
+            return ttValueUpper;
+        }

     }
 
     // Evaluate the position statically
     }
 
     // Evaluate the position statically

diff --git a/src/tt.cpp b/src/tt.cpp
index 40dca0d3b2524b221d14f0d2a7fccf2049d3a64a..8a66812a79c1eda84909dc20d09ead945a1c89de 100644 (file)
--- a/src/tt.cpp
+++ b/src/tt.cpp
@@ -82,7 +82,7 @@ void TranspositionTable::clear() {
 /// more valuable than a TTEntry t2 if t1 is from the current search and t2 is from
 /// a previous search, or if the depth of t1 is bigger than the depth of t2.
 
 /// more valuable than a TTEntry t2 if t1 is from the current search and t2 is from
 /// a previous search, or if the depth of t1 is bigger than the depth of t2.
 

-void TranspositionTable::store(const Key posKey, Value v, Bound t, Depth d, Move m) {
+void TranspositionTable::store(const Key posKey, Value v, Bound b, Depth d, Move m) {

 
   int c1, c2, c3;
   TTEntry *tte, *replace;
 
   int c1, c2, c3;
   TTEntry *tte, *replace;


@@ -92,13 +92,16 @@ void TranspositionTable::store(const Key posKey, Value v, Bound t, Depth d, Move
 
   for (int i = 0; i < ClusterSize; i++, tte++)
   {
 
   for (int i = 0; i < ClusterSize; i++, tte++)
   {

-      if (!tte->key() || tte->key() == posKey32) // Empty or overwrite old
+      if (!tte->key())
+          tte->save(posKey32, v, b, d, m, generation);
+
+      if (tte->key() == posKey32)

       {
           // Preserve any existing ttMove
           if (m == MOVE_NONE)
               m = tte->move();
 
       {
           // Preserve any existing ttMove
           if (m == MOVE_NONE)
               m = tte->move();
 

-          tte->save(posKey32, v, t, d, m, generation);
+          tte->update(v, b, d, m, generation);

           return;
       }
 
           return;
       }
 


@@ -110,7 +113,7 @@ void TranspositionTable::store(const Key posKey, Value v, Bound t, Depth d, Move
       if (c1 + c2 + c3 > 0)
           replace = tte;
   }
       if (c1 + c2 + c3 > 0)
           replace = tte;
   }

-  replace->save(posKey32, v, t, d, m, generation);
+  replace->save(posKey32, v, b, d, m, generation);

 }
 
 
 }
 
 

diff --git a/src/tt.h b/src/tt.h
index 719f178d59e8956dbe3467eb44a397de15bd61be..6c7caf75fce19bbab5c55886a26e6d75f27f47c1 100644 (file)
--- a/src/tt.h
+++ b/src/tt.h
@@ -46,19 +46,43 @@ class TTEntry {
 public:
   void save(uint32_t k, Value v, Bound b, Depth d, Move m, int g) {
 
 public:
   void save(uint32_t k, Value v, Bound b, Depth d, Move m, int g) {
 

-    key32        = (uint32_t)k;
-    move16       = (uint16_t)m;
-    bound        = (uint8_t)b;
-    generation8  = (uint8_t)g;
-    value16      = (int16_t)v;
-    depth16      = (int16_t)d;
+    key32       = (uint32_t)k;
+    move16      = (uint16_t)m;
+    bound       = (uint8_t)b;
+    generation8 = (uint8_t)g;
+    valueUpper = (int16_t)(b & BOUND_UPPER ? v : VALUE_NONE);
+    depthUpper = (int16_t)(b & BOUND_UPPER ? d : DEPTH_NONE);
+    valueLower = (int16_t)(b & BOUND_LOWER ? v : VALUE_NONE);
+    depthLower = (int16_t)(b & BOUND_LOWER ? d : DEPTH_NONE);

   }
   }

+
+  void update(Value v, Bound b, Depth d, Move m, int g) {
+
+    move16      = (uint16_t)m;
+    bound      |= (uint8_t)b;
+    generation8 = (uint8_t)g;
+
+    if (b & BOUND_UPPER)
+    {
+        valueUpper = (int16_t)v;
+        depthUpper = (int16_t)d;
+    }
+
+    if (b & BOUND_LOWER)
+    {
+        valueLower = (int16_t)v;
+        depthLower = (int16_t)d;
+    }
+  }
+

   void set_generation(int g) { generation8 = (uint8_t)g; }
 
   uint32_t key() const              { return key32; }
   void set_generation(int g) { generation8 = (uint8_t)g; }
 
   uint32_t key() const              { return key32; }

-  Depth depth() const               { return (Depth)depth16; }
+  Depth depth() const               { return (Depth)depthLower; }
+  Depth depth_upper() const         { return (Depth)depthUpper; }

   Move move() const                 { return (Move)move16; }
   Move move() const                 { return (Move)move16; }

-  Value value() const               { return (Value)value16; }
+  Value value() const               { return (Value)valueLower; }
+  Value value_upper() const         { return (Value)valueUpper; }

   Bound type() const                { return (Bound)bound; }
   int generation() const            { return (int)generation8; }
 
   Bound type() const                { return (Bound)bound; }
   int generation() const            { return (int)generation8; }
 


@@ -66,7 +90,7 @@ private:
   uint32_t key32;
   uint16_t move16;
   uint8_t bound, generation8;
   uint32_t key32;
   uint16_t move16;
   uint8_t bound, generation8;

-  int16_t value16, depth16;
+  int16_t valueLower, depthLower, valueUpper, depthUpper;

 };
 
 
 };
 
 


@@ -96,7 +120,7 @@ public:
   ~TranspositionTable();
   void set_size(size_t mbSize);
   void clear();
   ~TranspositionTable();
   void set_size(size_t mbSize);
   void clear();

-  void store(const Key posKey, Value v, Bound type, Depth d, Move m);
+  void store(const Key posKey, Value v, Bound b, Depth d, Move m);

   TTEntry* probe(const Key posKey) const;
   void new_search();
   TTEntry* first_entry(const Key posKey) const;
   TTEntry* probe(const Key posKey) const;
   void new_search();
   TTEntry* first_entry(const Key posKey) const;

diff --git a/src/types.h b/src/types.h
index 9b36fd89fde9f9505dc54a2093bab49711cbf651..2219b40becd8d929e8e73186374e2895b2411e40 100644 (file)
--- a/src/types.h
+++ b/src/types.h
@@ -163,7 +163,7 @@ enum Bound {
   BOUND_NONE  = 0,
   BOUND_UPPER = 1,
   BOUND_LOWER = 2,
   BOUND_NONE  = 0,
   BOUND_UPPER = 1,
   BOUND_LOWER = 2,

-  BOUND_EXACT = BOUND_UPPER | BOUND_LOWER
+  BOUND_EXACT = BOUND_UPPER | BOUND_LOWER | 4

 };
 
 enum Value {
 };
 
 enum Value {