Add eval cache infrastructure

With this patch series we want to introduce a per-thread
evaluation cache to store node evaluation and do not
rely anymore on the TT table for this.

This patch just introduces the infrastructure.

No functional change.

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_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);
 
   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;
   assert(!pos.in_check());
 
   EvalInfo ei;

-  Value margins[COLOR_NB];

   Score score, mobilityWhite, mobilityBlack;
 
   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[] 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
 
   // 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;
   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
   }
 
   // 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.
 
   // 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)
 
   // 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);
   }
 
            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
   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);
       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) << "% * "
                   << "\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);
   }
 
                   << "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>
   // 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);
 
 
     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];
         // 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)
     }
 
     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
 
 #if !defined(EVALUATE_H_INCLUDED)
 #define EVALUATE_H_INCLUDED
 

+#include "misc.h"

 #include "types.h"
 
 class Position;
 #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);
 
 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)
 }
 
 #endif // !defined(EVALUATE_H_INCLUDED)

diff --git a/src/thread.h b/src/thread.h
index 6817e20e53e78fb0d9be02d2031ab3439d10d13d..488feeb50053541b45c86bb02db7d151d22934a3 100644 (file)
--- a/src/thread.h
+++ b/src/thread.h
@@ -22,6 +22,7 @@
 
 #include <vector>
 
 
 #include <vector>
 

+#include "evaluate.h"

 #include "material.h"
 #include "movepick.h"
 #include "pawns.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];
   void wait_for_stop_or_ponderhit();
 
   SplitPoint splitPoints[MAX_SPLITPOINTS_PER_THREAD];

+  Eval::Table evalTable;

   MaterialTable materialTable;
   PawnTable pawnTable;
   size_t idx;
   MaterialTable materialTable;
   PawnTable pawnTable;
   size_t idx;