Cache evaluation score in qsearch

Instead of just drop evaluation score after stand pat
logic save it in TT so to be reused if the same position
occurs again.

Note that we NEVER use the cached value apart to avoid an
evaluation call, in particulary we never return to caller
after a succesful tt hit.

To accomodate this a new value type VALUE_TYPE_EVAL has been
introduced so that ok_to_use_TT() always returns false.

With this patch we cut about 15% of total evaluation calls.

Signed-off-by: Marco Costalba <mcostalba@gmail.com>

diff --git a/src/movepick.cpp b/src/movepick.cpp
index 6a7fd4ebce3e50bcc8d598b5d04702ad4fe7a455..eb686f7938837d23acb86e0812ea52e1f442d72d 100644 (file)
--- a/src/movepick.cpp
+++ b/src/movepick.cpp
@@ -66,7 +66,7 @@ namespace {
 /// move ordering is at the current node.
 
 MovePicker::MovePicker(const Position& p, bool pv, Move ttm,
-                       const SearchStack& ss, Depth d, EvalInfo* ei) : pos(p) {
+                       const SearchStack& ss, Depth d) : pos(p) {
   pvNode = pv;
   ttMove = ttm;
   mateKiller = (ss.mateKiller == ttm)? MOVE_NONE : ss.mateKiller;
@@ -81,20 +81,15 @@ MovePicker::MovePicker(const Position& p, bool pv, Move ttm,
   // generating them. So avoid generating in case we know are zero.
   Color us = pos.side_to_move();
   Color them = opposite_color(us);
-  bool noCaptures =    ei
-                   && (ei->attackedBy[us][0] & pos.pieces_of_color(them)) == 0
-                   && !ei->mi->specialized_eval_exists()
-                   && (pos.ep_square() == SQ_NONE)
-                   && !pos.has_pawn_on_7th(us);
 
   if (p.is_check())
       phaseIndex = EvasionsPhaseIndex;
   else if (depth > Depth(0))
       phaseIndex = MainSearchPhaseIndex;
   else if (depth == Depth(0))
-      phaseIndex = (noCaptures ? QsearchNoCapturesPhaseIndex : QsearchWithChecksPhaseIndex);
+      phaseIndex = QsearchWithChecksPhaseIndex;
   else
-      phaseIndex = (noCaptures ? NoMovesPhaseIndex : QsearchWithoutChecksPhaseIndex);
+      phaseIndex = QsearchWithoutChecksPhaseIndex;
 
   dc = p.discovered_check_candidates(us);
   pinned = p.pinned_pieces(us);

diff --git a/src/movepick.h b/src/movepick.h
index 135b3555d2b90ae03d272659e2bdf1dbe29e1ef7..c2619be8baa03602703155e79bb0911dadc16a5c 100644 (file)
--- a/src/movepick.h
+++ b/src/movepick.h
@@ -63,7 +63,7 @@ public:
     PH_STOP
   };
 
-  MovePicker(const Position& p, bool pvnode, Move ttm, const SearchStack& ss, Depth d, EvalInfo* ei = NULL);
+  MovePicker(const Position& p, bool pvnode, Move ttm, const SearchStack& ss, Depth d);
   Move get_next_move();
   Move get_next_move(Lock &lock);
   int number_of_moves() const;

diff --git a/src/search.cpp b/src/search.cpp
index f52351920a369831119c2fecc65d483e626dfd9a..3617853e5f23d2f3589b7af48da9decbf48e4593 100644 (file)
--- a/src/search.cpp
+++ b/src/search.cpp
@@ -1434,18 +1434,38 @@ namespace {
         return VALUE_DRAW;
 
     // Transposition table lookup, only when not in PV
+    TTEntry* tte = NULL;
     bool pvNode = (beta - alpha != 1);
     if (!pvNode)
     {
-        const TTEntry* tte = TT.retrieve(pos);
+        tte = TT.retrieve(pos);
         if (tte && ok_to_use_TT(tte, depth, beta, ply))
+        {
+            assert(tte->type() != VALUE_TYPE_EVAL);
+
             return value_from_tt(tte->value(), ply);
+        }
     }
 
     // Evaluate the position statically
     EvalInfo ei;
+    Value staticValue;
     bool isCheck = pos.is_check();
-    Value staticValue = (isCheck ? -VALUE_INFINITE : evaluate(pos, ei, threadID));
+
+    if (isCheck)
+        staticValue = -VALUE_INFINITE;
+
+    else if (tte && tte->type() == VALUE_TYPE_EVAL)
+    {
+        // Use the cached evaluation score if possible
+        assert(tte->value() == evaluate(pos, ei, threadID));
+        assert(ei.futilityMargin == Value(0));
+
+        staticValue = tte->value();
+        ei.futilityMargin = Value(0); // manually initialize futilityMargin
+    }
+    else
+        staticValue = evaluate(pos, ei, threadID);
 
     if (ply == PLY_MAX - 1)
         return evaluate(pos, ei, threadID);
@@ -1460,6 +1480,11 @@ namespace {
         TT.store(pos, value_to_tt(bestValue, ply), depth, MOVE_NONE, VALUE_TYPE_EXACT);
         return bestValue;
     }
+    else if (!isCheck && !tte && ei.futilityMargin == 0)
+    {
+        // Store the score to avoid a future costly evaluation() call
+        TT.store(pos, value_to_tt(bestValue, ply), Depth(-127*OnePly), MOVE_NONE, VALUE_TYPE_EVAL);
+    }
 
     if (bestValue > alpha)
         alpha = bestValue;
@@ -1467,7 +1492,7 @@ namespace {
     // Initialize a MovePicker object for the current position, and prepare
     // to search the moves.  Because the depth is <= 0 here, only captures,
     // queen promotions and checks (only if depth == 0) will be generated.
-    MovePicker mp = MovePicker(pos, pvNode, MOVE_NONE, EmptySearchStack, depth, isCheck ? NULL : &ei);
+    MovePicker mp = MovePicker(pos, pvNode, MOVE_NONE, EmptySearchStack, depth);
     Move move;
     int moveCount = 0;
     Bitboard dcCandidates = mp.discovered_check_candidates();

diff --git a/src/tt.cpp b/src/tt.cpp
index 83c9f50f0f6aaafb7abb9f73c4d304e52772a304..c88aef486e3e6f3a755f0f4daee7f7ab04b6e107 100644 (file)
--- a/src/tt.cpp
+++ b/src/tt.cpp
@@ -137,7 +137,7 @@ void TranspositionTable::store(const Position &pos, Value v, Depth d,
 /// transposition table. Returns a pointer to the TTEntry or NULL
 /// if position is not found.
 
-const TTEntry* TranspositionTable::retrieve(const Position &pos) const {
+TTEntry* TranspositionTable::retrieve(const Position &pos) const {
 
   TTEntry *tte = first_entry(pos);
 

diff --git a/src/tt.h b/src/tt.h
index 03ce1f553df77f9d5e46cf5232602bd7b956b13d..02913efe7f66f0bd1a162de084bdbf1b54cb4a38 100644 (file)
--- a/src/tt.h
+++ b/src/tt.h
@@ -45,7 +45,7 @@ public:
   Depth depth() const { return Depth(depth_); }
   Move move() const { return Move(data & 0x7FFFF); }
   Value value() const { return Value(value_); }
-  ValueType type() const { return ValueType((data >> 20) & 3); }
+  ValueType type() const { return ValueType((data >> 20) & 7); }
   int generation() const { return (data >> 23); }
 
 private:
@@ -67,7 +67,7 @@ public:
   void set_size(unsigned mbSize);
   void clear();
   void store(const Position &pos, Value v, Depth d, Move m, ValueType type);
-  const TTEntry* retrieve(const Position &pos) const;
+  TTEntry* retrieve(const Position &pos) const;
   void new_search();
   void insert_pv(const Position &pos, Move pv[]);
   int full();

diff --git a/src/value.h b/src/value.h
index a3ddc00048408ff927d214169965b76f922c6b2d..a2f7014b02ad37ec678607c22a20c3690dd7a7a3 100644 (file)
--- a/src/value.h
+++ b/src/value.h
@@ -36,7 +36,8 @@ enum ValueType {
   VALUE_TYPE_NONE = 0,
   VALUE_TYPE_UPPER = 1,  // Upper bound
   VALUE_TYPE_LOWER = 2,  // Lower bound
-  VALUE_TYPE_EXACT = 3   // Exact score
+  VALUE_TYPE_EXACT = 3,  // Exact score
+  VALUE_TYPE_EVAL  = 4   // Evaluation cache
 };