Merge branch 'eval_cache'

Use an eval cache instead of TT to store node
position evaluations.

It is already an improvment and, because it frees
two TT entry slots, paves the way to extend TT to
store both upper and lower bounds.

After 4855 games, single thread, 15"+0.05
Mod vs Orig 1165 -920 - 2770 ELO +18

bench: 5149248

diff --git a/src/evaluate.cpp b/src/evaluate.cpp
index 40c98a982d897af633ef4f8315f771f8d7229bbc..f27c04ec834ae4ef3b870b6a56739382b556ad2f 100644 (file)
--- a/src/evaluate.cpp
+++ b/src/evaluate.cpp
@@ -244,7 +244,7 @@ namespace {
   Score evaluate_pieces_of_color(const Position& pos, EvalInfo& ei, Score& mobility);
 
   template<Color Us, bool Trace>
-  Score evaluate_king(const Position& pos, EvalInfo& ei, Value margins[]);
+  Score evaluate_king(const Position& pos, EvalInfo& ei, int16_t margins[]);
 
   template<Color Us>
   Score evaluate_threats(const Position& pos, EvalInfo& ei);
@@ -364,12 +364,26 @@ Value do_evaluate(const Position& pos, Value& margin) {
   assert(!pos.in_check());
 
   EvalInfo ei;
-  Value margins[COLOR_NB];
   Score score, mobilityWhite, mobilityBlack;
 
+  Key key = pos.key();
+  Eval::Entry* e = pos.this_thread()->evalTable[key];
+
+  // If e->key matches the position's hash key, it means that we have analysed
+  // this node before, and we can simply return the information we found the last
+  // time instead of recomputing it.
+  if (e->key == key)
+  {
+      margin = Value(e->margins[pos.side_to_move()]);
+      return e->value;
+  }
+
+  // Otherwise we overwrite current content with this node info.
+  e->key = key;
+
   // margins[] store the uncertainty estimation of position's evaluation
   // that typically is used by the search for pruning decisions.
-  margins[WHITE] = margins[BLACK] = VALUE_ZERO;
+  e->margins[WHITE] = e->margins[BLACK] = VALUE_ZERO;
 
   // Initialize score by reading the incrementally updated scores included
   // in the position object (material + piece square tables) and adding
@@ -385,7 +399,8 @@ Value do_evaluate(const Position& pos, Value& margin) {
   if (ei.mi->specialized_eval_exists())
   {
       margin = VALUE_ZERO;
-      return ei.mi->evaluate(pos);
+      e->value = ei.mi->evaluate(pos);
+      return e->value;
   }
 
   // Probe the pawn hash table
@@ -404,8 +419,8 @@ Value do_evaluate(const Position& pos, Value& margin) {
 
   // Evaluate kings after all other pieces because we need complete attack
   // information when computing the king safety evaluation.
-  score +=  evaluate_king<WHITE, Trace>(pos, ei, margins)
-          - evaluate_king<BLACK, Trace>(pos, ei, margins);
+  score +=  evaluate_king<WHITE, Trace>(pos, ei, e->margins)
+          - evaluate_king<BLACK, Trace>(pos, ei, e->margins);
 
   // Evaluate tactical threats, we need full attack information including king
   score +=  evaluate_threats<WHITE>(pos, ei)
@@ -451,7 +466,7 @@ Value do_evaluate(const Position& pos, Value& margin) {
            sf = ScaleFactor(50);
   }
 
-  margin = margins[pos.side_to_move()];
+  margin = Value(e->margins[pos.side_to_move()]);
   Value v = interpolate(score, ei.mi->game_phase(), sf);
 
   // In case of tracing add all single evaluation contributions for both white and black
@@ -468,8 +483,8 @@ Value do_evaluate(const Position& pos, Value& margin) {
       Score b = make_score(ei.mi->space_weight() * evaluate_space<BLACK>(pos, ei), 0);
       trace_add(SPACE, apply_weight(w, Weights[Space]), apply_weight(b, Weights[Space]));
       trace_add(TOTAL, score);
-      TraceStream << "\nUncertainty margin: White: " << to_cp(margins[WHITE])
-                  << ", Black: " << to_cp(margins[BLACK])
+      TraceStream << "\nUncertainty margin: White: " << to_cp(Value(e->margins[WHITE]))
+                  << ", Black: " << to_cp(Value(e->margins[BLACK]))
                   << "\nScaling: " << std::noshowpos
                   << std::setw(6) << 100.0 * ei.mi->game_phase() / 128.0 << "% MG, "
                   << std::setw(6) << 100.0 * (1.0 - ei.mi->game_phase() / 128.0) << "% * "
@@ -477,7 +492,7 @@ Value do_evaluate(const Position& pos, Value& margin) {
                   << "Total evaluation: " << to_cp(v);
   }
 
-  return pos.side_to_move() == WHITE ? v : -v;
+  return e->value = pos.side_to_move() == WHITE ? v : -v;
 }
 
 
@@ -752,7 +767,7 @@ Value do_evaluate(const Position& pos, Value& margin) {
   // evaluate_king<>() assigns bonuses and penalties to a king of a given color
 
   template<Color Us, bool Trace>
-  Score evaluate_king(const Position& pos, EvalInfo& ei, Value margins[]) {
+  Score evaluate_king(const Position& pos, EvalInfo& ei, int16_t margins[]) {
 
     const Color Them = (Us == WHITE ? BLACK : WHITE);
 
@@ -852,7 +867,7 @@ Value do_evaluate(const Position& pos, Value& margin) {
         // be very big, and so capturing a single attacking piece can therefore
         // result in a score change far bigger than the value of the captured piece.
         score -= KingDangerTable[Us == Search::RootColor][attackUnits];
-        margins[Us] += mg_value(KingDangerTable[Us == Search::RootColor][attackUnits]);
+        margins[Us] += int16_t(mg_value(KingDangerTable[Us == Search::RootColor][attackUnits]));
     }
 
     if (Trace)

diff --git a/src/evaluate.h b/src/evaluate.h
index a76d10d143f5d44d66900f91ac7dcd5dd68b2ba8..accb7d632a5694ba6c6be32d978f76dea41f40e4 100644 (file)
--- a/src/evaluate.h
+++ b/src/evaluate.h
@@ -20,6 +20,7 @@
 #if !defined(EVALUATE_H_INCLUDED)
 #define EVALUATE_H_INCLUDED
 
+#include "misc.h"
 #include "types.h"
 
 class Position;
@@ -30,6 +31,16 @@ extern void init();
 extern Value evaluate(const Position& pos, Value& margin);
 extern std::string trace(const Position& pos);
 
+const int TableSize = 262144;
+
+struct Entry {
+  Key key;
+  Value value;
+  int16_t margins[2];
+};
+
+struct Table : HashTable<Entry, TableSize> {};
+
 }
 
 #endif // !defined(EVALUATE_H_INCLUDED)

diff --git a/src/search.cpp b/src/search.cpp
index da20f15e3352964a596137a7f581e2e885b9e6ed..f6c2233b1519b8887f19919c789059e603e019d7 100644 (file)
--- a/src/search.cpp
+++ b/src/search.cpp
@@ -574,31 +574,17 @@ namespace {
     // Step 5. Evaluate the position statically and update parent's gain statistics
     if (inCheck)
         ss->staticEval = ss->evalMargin = eval = VALUE_NONE;
-
-    else if (tte)
+    else
     {
-        // Following asserts are valid only in single thread condition because
-        // TT access is always racy and its contents cannot be trusted.
-        assert(tte->static_value() != VALUE_NONE || Threads.size() > 1);
-        assert(ttValue != VALUE_NONE || tte->type() == BOUND_NONE || Threads.size() > 1);
-
-        ss->staticEval = eval = tte->static_value();
-        ss->evalMargin = tte->static_value_margin();
-
-        if (eval == VALUE_NONE || ss->evalMargin == VALUE_NONE) // Due to a race
-            eval = ss->staticEval = evaluate(pos, ss->evalMargin);
+        eval = ss->staticEval = evaluate(pos, ss->evalMargin);
 
         // Can ttValue be used as a better position evaluation?
-        if (ttValue != VALUE_NONE)
+        if (tte && ttValue != VALUE_NONE)
+        {
             if (   ((tte->type() & BOUND_LOWER) && ttValue > eval)
                 || ((tte->type() & BOUND_UPPER) && ttValue < eval))
                 eval = ttValue;
-    }
-    else
-    {
-        eval = ss->staticEval = evaluate(pos, ss->evalMargin);
-        TT.store(posKey, VALUE_NONE, BOUND_NONE, DEPTH_NONE, MOVE_NONE,
-                 ss->staticEval, ss->evalMargin);
+        }
     }
 
     // Update gain for the parent non-capture move given the static position
@@ -1051,8 +1037,7 @@ split_point_start: // At split points actual search starts from here
 
     if (bestValue >= beta) // Failed high
     {
-        TT.store(posKey, value_to_tt(bestValue, ss->ply), BOUND_LOWER, depth,
-                 bestMove, ss->staticEval, ss->evalMargin);
+        TT.store(posKey, value_to_tt(bestValue, ss->ply), BOUND_LOWER, depth, bestMove);
 
         if (!pos.is_capture_or_promotion(bestMove) && !inCheck)
         {
@@ -1077,7 +1062,7 @@ split_point_start: // At split points actual search starts from here
     else // Failed low or PV search
         TT.store(posKey, value_to_tt(bestValue, ss->ply),
                  PvNode && bestMove != MOVE_NONE ? BOUND_EXACT : BOUND_UPPER,
-                 depth, bestMove, ss->staticEval, ss->evalMargin);
+                 depth, bestMove);
 
     assert(bestValue > -VALUE_INFINITE && bestValue < VALUE_INFINITE);
 
@@ -1154,19 +1139,10 @@ split_point_start: // At split points actual search starts from here
     {
         if (fromNull)
         {
+            // Approximated score. Real one is slightly higher due to tempo
             ss->staticEval = bestValue = -(ss-1)->staticEval;
             ss->evalMargin = VALUE_ZERO;
         }
-        else if (tte)
-        {
-            assert(tte->static_value() != VALUE_NONE || Threads.size() > 1);
-
-            ss->staticEval = bestValue = tte->static_value();
-            ss->evalMargin = tte->static_value_margin();
-
-            if (ss->staticEval == VALUE_NONE || ss->evalMargin == VALUE_NONE) // Due to a race
-                ss->staticEval = bestValue = evaluate(pos, ss->evalMargin);
-        }
         else
             ss->staticEval = bestValue = evaluate(pos, ss->evalMargin);
 
@@ -1174,8 +1150,7 @@ split_point_start: // At split points actual search starts from here
         if (bestValue >= beta)
         {
             if (!tte)
-                TT.store(pos.key(), value_to_tt(bestValue, ss->ply), BOUND_LOWER,
-                         DEPTH_NONE, MOVE_NONE, ss->staticEval, ss->evalMargin);
+                TT.store(pos.key(), value_to_tt(bestValue, ss->ply), BOUND_LOWER, DEPTH_NONE, MOVE_NONE);
 
             return bestValue;
         }
@@ -1204,8 +1179,8 @@ split_point_start: // At split points actual search starts from here
       // Futility pruning
       if (   !PvNode
           && !InCheck
-          && !givesCheck
           && !fromNull
+          && !givesCheck
           &&  move != ttMove
           &&  enoughMaterial
           &&  type_of(move) != PROMOTION
@@ -1284,9 +1259,7 @@ split_point_start: // At split points actual search starts from here
               }
               else // Fail high
               {
-                  TT.store(posKey, value_to_tt(value, ss->ply), BOUND_LOWER,
-                           ttDepth, move, ss->staticEval, ss->evalMargin);
-
+                  TT.store(posKey, value_to_tt(value, ss->ply), BOUND_LOWER, ttDepth, move);
                   return value;
               }
           }
@@ -1300,7 +1273,7 @@ split_point_start: // At split points actual search starts from here
 
     TT.store(posKey, value_to_tt(bestValue, ss->ply),
              PvNode && bestValue > oldAlpha ? BOUND_EXACT : BOUND_UPPER,
-             ttDepth, bestMove, ss->staticEval, ss->evalMargin);
+             ttDepth, bestMove);
 
     assert(bestValue > -VALUE_INFINITE && bestValue < VALUE_INFINITE);
 
@@ -1591,20 +1564,12 @@ void RootMove::insert_pv_in_tt(Position& pos) {
   StateInfo state[MAX_PLY_PLUS_2], *st = state;
   TTEntry* tte;
   int ply = 0;
-  Value v, m;
 
   do {
       tte = TT.probe(pos.key());
 
       if (!tte || tte->move() != pv[ply]) // Don't overwrite correct entries
-      {
-          if (pos.in_check())
-              v = m = VALUE_NONE;
-          else
-              v = evaluate(pos, m);
-
-          TT.store(pos.key(), VALUE_NONE, BOUND_NONE, DEPTH_NONE, pv[ply], v, m);
-      }
+          TT.store(pos.key(), VALUE_NONE, BOUND_NONE, DEPTH_NONE, pv[ply]);
 
       assert(pos.move_is_legal(pv[ply]));
       pos.do_move(pv[ply++], *st++);

diff --git a/src/thread.h b/src/thread.h
index 4b0a5026d9bc2396617e0c1bcce09ef901555837..6c3c18affdb0a134b08f4f23cbb87a5a87a40dd6 100644 (file)
--- a/src/thread.h
+++ b/src/thread.h
@@ -22,6 +22,7 @@
 
 #include <vector>
 
+#include "evaluate.h"
 #include "material.h"
 #include "movepick.h"
 #include "pawns.h"
@@ -108,6 +109,7 @@ public:
   void wait_for_stop_or_ponderhit();
 
   SplitPoint splitPoints[MAX_SPLITPOINTS_PER_THREAD];
+  Eval::Table evalTable;
   MaterialTable materialTable;
   PawnTable pawnTable;
   size_t idx;

diff --git a/src/tt.cpp b/src/tt.cpp
index 9dbfcb5ac92e5fada772fd8c20a74a4a41921c63..40dca0d3b2524b221d14f0d2a7fccf2049d3a64a 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.
 
-void TranspositionTable::store(const Key posKey, Value v, Bound t, Depth d, Move m, Value statV, Value kingD) {
+void TranspositionTable::store(const Key posKey, Value v, Bound t, Depth d, Move m) {
 
   int c1, c2, c3;
   TTEntry *tte, *replace;
@@ -98,7 +98,7 @@ void TranspositionTable::store(const Key posKey, Value v, Bound t, Depth d, Move
           if (m == MOVE_NONE)
               m = tte->move();
 
-          tte->save(posKey32, v, t, d, m, generation, statV, kingD);
+          tte->save(posKey32, v, t, d, m, generation);
           return;
       }
 
@@ -110,7 +110,7 @@ void TranspositionTable::store(const Key posKey, Value v, Bound t, Depth d, Move
       if (c1 + c2 + c3 > 0)
           replace = tte;
   }
-  replace->save(posKey32, v, t, d, m, generation, statV, kingD);
+  replace->save(posKey32, v, t, d, m, generation);
 }
 
 

diff --git a/src/tt.h b/src/tt.h
index 3edd5e8a1fdfda660eedc08ea89c57261eeb364b..719f178d59e8956dbe3467eb44a397de15bd61be 100644 (file)
--- a/src/tt.h
+++ b/src/tt.h
@@ -44,7 +44,7 @@
 class TTEntry {
 
 public:
-  void save(uint32_t k, Value v, Bound b, Depth d, Move m, int g, Value statV, Value statM) {
+  void save(uint32_t k, Value v, Bound b, Depth d, Move m, int g) {
 
     key32        = (uint32_t)k;
     move16       = (uint16_t)m;
@@ -52,8 +52,6 @@ public:
     generation8  = (uint8_t)g;
     value16      = (int16_t)v;
     depth16      = (int16_t)d;
-    staticValue  = (int16_t)statV;
-    staticMargin = (int16_t)statM;
   }
   void set_generation(int g) { generation8 = (uint8_t)g; }
 
@@ -63,14 +61,12 @@ public:
   Value value() const               { return (Value)value16; }
   Bound type() const                { return (Bound)bound; }
   int generation() const            { return (int)generation8; }
-  Value static_value() const        { return (Value)staticValue; }
-  Value static_value_margin() const { return (Value)staticMargin; }
 
 private:
   uint32_t key32;
   uint16_t move16;
   uint8_t bound, generation8;
-  int16_t value16, depth16, staticValue, staticMargin;
+  int16_t value16, depth16;
 };
 
 
@@ -100,7 +96,7 @@ public:
   ~TranspositionTable();
   void set_size(size_t mbSize);
   void clear();
-  void store(const Key posKey, Value v, Bound type, Depth d, Move m, Value statV, Value kingD);
+  void store(const Key posKey, Value v, Bound type, Depth d, Move m);
   TTEntry* probe(const Key posKey) const;
   void new_search();
   TTEntry* first_entry(const Key posKey) const;