Flag critical search tree in hash table

Introducing new concept, saving principal lines into the transposition table
to generate a "critical search tree" which we can reuse later for intelligent
pruning/extension decisions.

For instance in this patch we just reduce reduction for these lines. But a lot
of other ideas are possible.

To go further : tune some parameters, how to add or remove lines from the
critical search tree, how to use these lines in search choices, etc.

STC :
LLR: 2.94 (-2.94,2.94) [0.50,4.50]
Total: 59761 W: 13321 L: 12863 D: 33577 +2.23 ELO
http://tests.stockfishchess.org/tests/view/5c34da5d0ebc596a450c53d3

LTC :
LLR: 2.96 (-2.94,2.94) [0.00,3.50]
Total: 26826 W: 4439 L: 4191 D: 18196 +2.9 ELO
http://tests.stockfishchess.org/tests/view/5c35ceb00ebc596a450c65b2

Special thanks to Miguel Lahoz for his help in transposition table in/out.

Bench: 3399866

diff --git a/src/search.cpp b/src/search.cpp
index c8e6c8b653662256e6fcc9521c62a13350815b60..b7e04fad2b22484ec2237e9d1f3ecdd81aece60a 100644 (file)
--- a/src/search.cpp
+++ b/src/search.cpp
@@ -577,7 +577,7 @@ namespace {
     Move ttMove, move, excludedMove, bestMove;
     Depth extension, newDepth;
     Value bestValue, value, ttValue, eval, maxValue, pureStaticEval;
-    bool ttHit, inCheck, givesCheck, improving;
+    bool ttHit, pvHit, inCheck, givesCheck, improving;
     bool captureOrPromotion, doFullDepthSearch, moveCountPruning, skipQuiets, ttCapture, pvExact;
     Piece movedPiece;
     int moveCount, captureCount, quietCount;
@@ -643,6 +643,7 @@ namespace {
     ttValue = ttHit ? value_from_tt(tte->value(), ss->ply) : VALUE_NONE;
     ttMove =  rootNode ? thisThread->rootMoves[thisThread->pvIdx].pv[0]
             : ttHit    ? tte->move() : MOVE_NONE;
+    pvHit = ttHit ? tte->pv_hit() : false;
 
     // At non-PV nodes we check for an early TT cutoff
     if (  !PvNode
@@ -676,6 +677,11 @@ namespace {
         return ttValue;
     }
 
+    if (   depth > 6 * ONE_PLY
+        && !excludedMove
+        && PvNode)
+        pvHit = true;
+
     // Step 5. Tablebases probe
     if (!rootNode && TB::Cardinality)
     {
@@ -709,7 +715,7 @@ namespace {
                 if (    b == BOUND_EXACT
                     || (b == BOUND_LOWER ? value >= beta : value <= alpha))
                 {
-                    tte->save(posKey, value_to_tt(value, ss->ply), b,
+                    tte->save(posKey, value_to_tt(value, ss->ply), pvHit, b,
                               std::min(DEPTH_MAX - ONE_PLY, depth + 6 * ONE_PLY),
                               MOVE_NONE, VALUE_NONE);
 
@@ -760,7 +766,7 @@ namespace {
         else
             ss->staticEval = eval = pureStaticEval = -(ss-1)->staticEval + 2 * Eval::Tempo;
 
-        tte->save(posKey, VALUE_NONE, BOUND_NONE, DEPTH_NONE, MOVE_NONE, pureStaticEval);
+        tte->save(posKey, VALUE_NONE, pvHit, BOUND_NONE, DEPTH_NONE, MOVE_NONE, pureStaticEval);
     }
 
     // Step 7. Razoring (~2 Elo)
@@ -875,6 +881,7 @@ namespace {
         tte = TT.probe(posKey, ttHit);
         ttValue = ttHit ? value_from_tt(tte->value(), ss->ply) : VALUE_NONE;
         ttMove = ttHit ? tte->move() : MOVE_NONE;
+        pvHit = ttHit ? tte->pv_hit() : false;
     }
 
 moves_loop: // When in check, search starts from here
@@ -1035,6 +1042,10 @@ moves_loop: // When in check, search starts from here
       {
           Depth r = reduction<PvNode>(improving, depth, moveCount);
 
+          // Decrease reduction if position is or has been on the PV
+          if (pvHit && !PvNode)
+              r -= ONE_PLY;
+
           // Decrease reduction if opponent's move count is high (~10 Elo)
           if ((ss-1)->moveCount > 15)
               r -= ONE_PLY;
@@ -1217,7 +1228,7 @@ moves_loop: // When in check, search starts from here
         bestValue = std::min(bestValue, maxValue);
 
     if (!excludedMove)
-        tte->save(posKey, value_to_tt(bestValue, ss->ply),
+        tte->save(posKey, value_to_tt(bestValue, ss->ply), pvHit,
                   bestValue >= beta ? BOUND_LOWER :
                   PvNode && bestMove ? BOUND_EXACT : BOUND_UPPER,
                   depth, bestMove, pureStaticEval);
@@ -1247,7 +1258,7 @@ moves_loop: // When in check, search starts from here
     Move ttMove, move, bestMove;
     Depth ttDepth;
     Value bestValue, value, ttValue, futilityValue, futilityBase, oldAlpha;
-    bool ttHit, inCheck, givesCheck, evasionPrunable;
+    bool ttHit, pvHit, inCheck, givesCheck, evasionPrunable;
     int moveCount;
 
     if (PvNode)
@@ -1281,6 +1292,7 @@ moves_loop: // When in check, search starts from here
     tte = TT.probe(posKey, ttHit);
     ttValue = ttHit ? value_from_tt(tte->value(), ss->ply) : VALUE_NONE;
     ttMove = ttHit ? tte->move() : MOVE_NONE;
+    pvHit = ttHit ? tte->pv_hit() : false;
 
     if (  !PvNode
         && ttHit
@@ -1318,7 +1330,7 @@ moves_loop: // When in check, search starts from here
         if (bestValue >= beta)
         {
             if (!ttHit)
-                tte->save(posKey, value_to_tt(bestValue, ss->ply), BOUND_LOWER,
+                tte->save(posKey, value_to_tt(bestValue, ss->ply), pvHit, BOUND_LOWER,
                           DEPTH_NONE, MOVE_NONE, ss->staticEval);
 
             return bestValue;
@@ -1429,7 +1441,7 @@ moves_loop: // When in check, search starts from here
     if (inCheck && bestValue == -VALUE_INFINITE)
         return mated_in(ss->ply); // Plies to mate from the root
 
-    tte->save(posKey, value_to_tt(bestValue, ss->ply),
+    tte->save(posKey, value_to_tt(bestValue, ss->ply), pvHit,
               bestValue >= beta ? BOUND_LOWER :
               PvNode && bestValue > oldAlpha  ? BOUND_EXACT : BOUND_UPPER,
               ttDepth, bestMove, ss->staticEval);

diff --git a/src/tt.cpp b/src/tt.cpp
index 653d081f8f0eb01859408043467a4e0486241f2f..d05de9163164faa62f307c3ae16565094c62f152 100644 (file)
--- a/src/tt.cpp
+++ b/src/tt.cpp
@@ -31,7 +31,7 @@
 TranspositionTable TT; // Our global transposition table
 
 /// TTEntry::save saves a TTEntry
-void TTEntry::save(Key k, Value v, Bound b, Depth d, Move m, Value ev) {
+void TTEntry::save(Key k, Value v, bool PvNode, Bound b, Depth d, Move m, Value ev) {
 
   assert(d / ONE_PLY * ONE_PLY == d);
 
@@ -47,7 +47,7 @@ void TTEntry::save(Key k, Value v, Bound b, Depth d, Move m, Value ev) {
       key16     = (uint16_t)(k >> 48);
       value16   = (int16_t)v;
       eval16    = (int16_t)ev;
-      genBound8 = (uint8_t)(TT.generation8 | b);
+      genBound8 = (uint8_t)(TT.generation8 | PvNode << 2 | b);
       depth8    = (int8_t)(d / ONE_PLY);
   }
 }
@@ -122,7 +122,7 @@ TTEntry* TranspositionTable::probe(const Key key, bool& found) const {
   for (int i = 0; i < ClusterSize; ++i)
       if (!tte[i].key16 || tte[i].key16 == key16)
       {
-          tte[i].genBound8 = uint8_t(generation8 | tte[i].bound()); // Refresh
+          tte[i].genBound8 = uint8_t(generation8 | tte[i].pv_hit() << 2 | tte[i].bound()); // Refresh
 
           return found = (bool)tte[i].key16, &tte[i];
       }
@@ -131,11 +131,11 @@ TTEntry* TranspositionTable::probe(const Key key, bool& found) const {
   TTEntry* replace = tte;
   for (int i = 1; i < ClusterSize; ++i)
       // Due to our packed storage format for generation and its cyclic
-      // nature we add 259 (256 is the modulus plus 3 to keep the lowest
+      // nature we add 263 (263 is the modulus plus 7 to keep the lowest
       // two bound bits from affecting the result) to calculate the entry
       // age correctly even after generation8 overflows into the next cycle.
-      if (  replace->depth8 - ((259 + generation8 - replace->genBound8) & 0xFC) * 2
-          >   tte[i].depth8 - ((259 + generation8 -   tte[i].genBound8) & 0xFC) * 2)
+      if (  replace->depth8 - ((263 + generation8 - replace->genBound8) & 0xF8)
+          >   tte[i].depth8 - ((263 + generation8 -   tte[i].genBound8) & 0xF8))
           replace = &tte[i];
 
   return found = false, replace;

diff --git a/src/tt.h b/src/tt.h
index 2cf82f58d317d2a5fb6ace239e1aa00dcee33ff3..8b98dbd52a2006daca7933e008dad9cbb4adf3d3 100644 (file)
--- a/src/tt.h
+++ b/src/tt.h
@@ -30,7 +30,8 @@
 /// move       16 bit
 /// value      16 bit
 /// eval value 16 bit
-/// generation  6 bit
+/// generation  5 bit
+/// PvNode      1 bit
 /// bound type  2 bit
 /// depth       8 bit
 
@@ -40,8 +41,9 @@ struct TTEntry {
   Value value() const { return (Value)value16; }
   Value eval()  const { return (Value)eval16; }
   Depth depth() const { return (Depth)(depth8 * int(ONE_PLY)); }
+  bool pv_hit() const { return (bool)(genBound8 & 0x4); }
   Bound bound() const { return (Bound)(genBound8 & 0x3); }
-  void save(Key k, Value v, Bound b, Depth d, Move m, Value ev);
+  void save(Key k, Value v, bool PvNode, Bound b, Depth d, Move m, Value ev);
 
 private:
   friend class TranspositionTable;
@@ -76,7 +78,7 @@ class TranspositionTable {
 
 public:
  ~TranspositionTable() { free(mem); }
-  void new_search() { generation8 += 4; } // Lower 2 bits are used by Bound
+  void new_search() { generation8 += 8; } // Lower 3 bits are used by PV flag and Bound
   TTEntry* probe(const Key key, bool& found) const;
   int hashfull() const;
   void resize(size_t mbSize);

diff --git a/tests/instrumented.sh b/tests/instrumented.sh
index 137d0e4af2c8ea0a93c3c6975d2118b804363f10..eb70466fc24f52ef86b1ba0b792804d14cd2c554 100755 (executable)
--- a/tests/instrumented.sh
+++ b/tests/instrumented.sh
@@ -45,6 +45,7 @@ race:TTEntry::bound
 race:TTEntry::save
 race:TTEntry::value
 race:TTEntry::eval
+race:TTEntry::pv_hit
 
 race:TranspositionTable::probe
 race:TranspositionTable::hashfull