Revert evaluation cache
authorMarco Costalba <mcostalba@gmail.com>
Thu, 27 Dec 2012 11:13:31 +0000 (12:13 +0100)
committerMarco Costalba <mcostalba@gmail.com>
Thu, 27 Dec 2012 12:57:17 +0000 (13:57 +0100)
And return on using TT as backing store for position
evaluations.

Tests (even on single thread) show eval cache was a regression.
In multi thread result should be even worst because eval cache
is a per-thread struct, while TT is shared.

After 4957 games at 15"+0.05 (single thread)
eval cache vs master 969 - 1093 - 2895  -9 ELO

So previous reported result of +18 ELO was probably due to an
issue in the testing framework (a bug in cutechess-cli) that
has been fixed in the meanwhile.

bench: 5386711

src/evaluate.cpp
src/evaluate.h
src/search.cpp
src/thread.h
src/tt.cpp
src/tt.h

index 1f396f7..9756add 100644 (file)
@@ -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, int16_t margins[]);
+  Score evaluate_king(const Position& pos, EvalInfo& ei, Value margins[]);
 
   template<Color Us>
   Score evaluate_threats(const Position& pos, EvalInfo& ei);
@@ -364,27 +364,13 @@ Value do_evaluate(const Position& pos, Value& margin) {
   assert(!pos.checkers());
 
   EvalInfo ei;
+  Value margins[COLOR_NB];
   Score score, mobilityWhite, mobilityBlack;
-
-  Key key = pos.key();
   Thread* th = pos.this_thread();
-  Eval::Entry* e = th->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.
-  e->margins[WHITE] = e->margins[BLACK] = VALUE_ZERO;
+  margins[WHITE] = margins[BLACK] = VALUE_ZERO;
 
   // Initialize score by reading the incrementally updated scores included
   // in the position object (material + piece square tables) and adding
@@ -400,8 +386,7 @@ Value do_evaluate(const Position& pos, Value& margin) {
   if (ei.mi->specialized_eval_exists())
   {
       margin = VALUE_ZERO;
-      e->value = ei.mi->evaluate(pos);
-      return e->value;
+      return ei.mi->evaluate(pos);
   }
 
   // Probe the pawn hash table
@@ -420,8 +405,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, e->margins)
-          - evaluate_king<BLACK, Trace>(pos, ei, e->margins);
+  score +=  evaluate_king<WHITE, Trace>(pos, ei, margins)
+          - evaluate_king<BLACK, Trace>(pos, ei, margins);
 
   // Evaluate tactical threats, we need full attack information including king
   score +=  evaluate_threats<WHITE>(pos, ei)
@@ -467,7 +452,7 @@ Value do_evaluate(const Position& pos, Value& margin) {
            sf = ScaleFactor(50);
   }
 
-  margin = Value(e->margins[pos.side_to_move()]);
+  margin = 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
@@ -484,8 +469,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(Value(e->margins[WHITE]))
-                  << ", Black: " << to_cp(Value(e->margins[BLACK]))
+      TraceStream << "\nUncertainty margin: White: " << to_cp(margins[WHITE])
+                  << ", Black: " << to_cp(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) << "% * "
@@ -493,7 +478,7 @@ Value do_evaluate(const Position& pos, Value& margin) {
                   << "Total evaluation: " << to_cp(v);
   }
 
-  return e->value = pos.side_to_move() == WHITE ? v : -v;
+  return pos.side_to_move() == WHITE ? v : -v;
 }
 
 
@@ -768,7 +753,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, int16_t margins[]) {
+  Score evaluate_king(const Position& pos, EvalInfo& ei, Value margins[]) {
 
     const Color Them = (Us == WHITE ? BLACK : WHITE);
 
@@ -868,7 +853,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] += int16_t(mg_value(KingDangerTable[Us == Search::RootColor][attackUnits]));
+        margins[Us] += mg_value(KingDangerTable[Us == Search::RootColor][attackUnits]);
     }
 
     if (Trace)
index accb7d6..a76d10d 100644 (file)
@@ -20,7 +20,6 @@
 #if !defined(EVALUATE_H_INCLUDED)
 #define EVALUATE_H_INCLUDED
 
-#include "misc.h"
 #include "types.h"
 
 class Position;
@@ -31,16 +30,6 @@ 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)
index 4663678..3ba0dbc 100644 (file)
@@ -575,17 +575,31 @@ namespace {
     // Step 5. Evaluate the position statically and update parent's gain statistics
     if (inCheck)
         ss->staticEval = ss->evalMargin = eval = VALUE_NONE;
-    else
+
+    else if (tte)
     {
-        eval = ss->staticEval = evaluate(pos, ss->evalMargin);
+        // 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);
 
         // Can ttValue be used as a better position evaluation?
-        if (tte && ttValue != VALUE_NONE)
-        {
+        if (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
@@ -1041,7 +1055,8 @@ 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);
+        TT.store(posKey, value_to_tt(bestValue, ss->ply), BOUND_LOWER, depth,
+                 bestMove, ss->staticEval, ss->evalMargin);
 
         if (!pos.is_capture_or_promotion(bestMove) && !inCheck)
         {
@@ -1066,7 +1081,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);
+                 depth, bestMove, ss->staticEval, ss->evalMargin);
 
     assert(bestValue > -VALUE_INFINITE && bestValue < VALUE_INFINITE);
 
@@ -1147,6 +1162,16 @@ split_point_start: // At split points actual search starts from here
             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);
 
@@ -1154,7 +1179,8 @@ 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);
+                TT.store(pos.key(), value_to_tt(bestValue, ss->ply), BOUND_LOWER,
+                         DEPTH_NONE, MOVE_NONE, ss->staticEval, ss->evalMargin);
 
             return bestValue;
         }
@@ -1263,7 +1289,9 @@ 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);
+                  TT.store(posKey, value_to_tt(value, ss->ply), BOUND_LOWER,
+                           ttDepth, move, ss->staticEval, ss->evalMargin);
+
                   return value;
               }
           }
@@ -1277,7 +1305,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);
+             ttDepth, bestMove, ss->staticEval, ss->evalMargin);
 
     assert(bestValue > -VALUE_INFINITE && bestValue < VALUE_INFINITE);
 
@@ -1574,7 +1602,7 @@ void RootMove::insert_pv_in_tt(Position& pos) {
       tte = TT.probe(pos.key());
 
       if (!tte || tte->move() != pv[ply]) // Don't overwrite correct entries
-          TT.store(pos.key(), VALUE_NONE, BOUND_NONE, DEPTH_NONE, pv[ply]);
+          TT.store(pos.key(), VALUE_NONE, BOUND_NONE, DEPTH_NONE, pv[ply], VALUE_NONE, VALUE_NONE);
 
       assert(MoveList<LEGAL>(pos).contains(pv[ply]));
 
index c6dc831..2d8a675 100644 (file)
@@ -22,7 +22,6 @@
 
 #include <vector>
 
-#include "evaluate.h"
 #include "material.h"
 #include "movepick.h"
 #include "pawns.h"
@@ -109,7 +108,6 @@ public:
   void wait_for_stop_or_ponderhit();
 
   SplitPoint splitPoints[MAX_SPLITPOINTS_PER_THREAD];
-  Eval::Table evalTable;
   Material::Table materialTable;
   Endgames endgames;
   Pawns::Table pawnsTable;
index 40dca0d..9dbfcb5 100644 (file)
@@ -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) {
+void TranspositionTable::store(const Key posKey, Value v, Bound t, Depth d, Move m, Value statV, Value kingD) {
 
   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);
+          tte->save(posKey32, v, t, d, m, generation, statV, kingD);
           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);
+  replace->save(posKey32, v, t, d, m, generation, statV, kingD);
 }
 
 
index 719f178..3edd5e8 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) {
+  void save(uint32_t k, Value v, Bound b, Depth d, Move m, int g, Value statV, Value statM) {
 
     key32        = (uint32_t)k;
     move16       = (uint16_t)m;
@@ -52,6 +52,8 @@ 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; }
 
@@ -61,12 +63,14 @@ 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;
+  int16_t value16, depth16, staticValue, staticMargin;
 };
 
 
@@ -96,7 +100,7 @@ public:
   ~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 type, Depth d, Move m, Value statV, Value kingD);
   TTEntry* probe(const Key posKey) const;
   void new_search();
   TTEntry* first_entry(const Key posKey) const;