Retire can_return_tt() and rewirte TT-hit code

[stockfish] / src / search.cpp

diff --git a/src/search.cpp b/src/search.cpp
index 4d1a6af784d1e41217df9b29c3676c20a55dc6cd..a3d8781889a690e15e0b91c4044c0243245f90d1 100644 (file)
--- a/src/search.cpp
+++ b/src/search.cpp
@@ -104,36 +104,11 @@ namespace {
   bool connected_moves(const Position& pos, Move m1, Move m2);
   Value value_to_tt(Value v, int ply);
   Value value_from_tt(Value v, int ply);
   bool connected_moves(const Position& pos, Move m1, Move m2);
   Value value_to_tt(Value v, int ply);
   Value value_from_tt(Value v, int ply);

-  bool can_return_tt(const TTEntry* tte, Depth depth, Value ttValue, Value beta);

   bool connected_threat(const Position& pos, Move m, Move threat);
   Value refine_eval(const TTEntry* tte, Value ttValue, Value defaultEval);
   Move do_skill_level();
   string uci_pv(const Position& pos, int depth, Value alpha, Value beta);
 
   bool connected_threat(const Position& pos, Move m, Move threat);
   Value refine_eval(const TTEntry* tte, Value ttValue, Value defaultEval);
   Move do_skill_level();
   string uci_pv(const Position& pos, int depth, Value alpha, Value beta);
 

-  // is_dangerous() checks whether a move belongs to some classes of known
-  // 'dangerous' moves so that we avoid to prune it.
-  FORCE_INLINE bool is_dangerous(const Position& pos, Move m, bool captureOrPromotion) {
-
-    // Castle move?
-    if (type_of(m) == CASTLE)
-        return true;
-
-    // Passed pawn move?
-    if (   type_of(pos.piece_moved(m)) == PAWN
-        && pos.pawn_is_passed(pos.side_to_move(), to_sq(m)))
-        return true;
-
-    // Entering a pawn endgame?
-    if (    captureOrPromotion
-        &&  type_of(pos.piece_on(to_sq(m))) != PAWN
-        &&  type_of(m) == NORMAL
-        && (  pos.non_pawn_material(WHITE) + pos.non_pawn_material(BLACK)
-            - PieceValue[Mg][pos.piece_on(to_sq(m))] == VALUE_ZERO))
-        return true;
-
-    return false;
-  }
-

 } // namespace
 
 
 } // namespace
 
 


@@ -199,8 +174,9 @@ void Search::think() {
   Position& pos = RootPosition;
   Chess960 = pos.is_chess960();
   Eval::RootColor = pos.side_to_move();
   Position& pos = RootPosition;
   Chess960 = pos.is_chess960();
   Eval::RootColor = pos.side_to_move();

-  Eval::ValueDraw[ Eval::RootColor] = VALUE_DRAW - Eval::ContemptFactor;
-  Eval::ValueDraw[~Eval::RootColor] = VALUE_DRAW + Eval::ContemptFactor;
+  int scaledCF = Eval::ContemptFactor * MaterialTable::game_phase(pos) / PHASE_MIDGAME;
+  Eval::ValueDraw[ Eval::RootColor] = VALUE_DRAW - Value(scaledCF);
+  Eval::ValueDraw[~Eval::RootColor] = VALUE_DRAW + Value(scaledCF);

   TimeMgr.init(Limits, pos.startpos_ply_counter(), pos.side_to_move());
   TT.new_search();
   H.clear();
   TimeMgr.init(Limits, pos.startpos_ply_counter(), pos.side_to_move());
   TT.new_search();
   H.clear();


@@ -502,7 +478,7 @@ namespace {
     Depth ext, newDepth;
     Value bestValue, value, ttValue;
     Value refinedValue, nullValue, futilityValue;
     Depth ext, newDepth;
     Value bestValue, value, ttValue;
     Value refinedValue, nullValue, futilityValue;

-    bool pvMove, inCheck, singularExtensionNode, givesCheck;
+    bool inCheck, givesCheck, pvMove, singularExtensionNode;

     bool captureOrPromotion, dangerous, doFullDepthSearch;
     int moveCount, playedMoveCount;
 
     bool captureOrPromotion, dangerous, doFullDepthSearch;
     int moveCount, playedMoveCount;
 


@@ -567,8 +543,11 @@ namespace {
     // a fail high/low. Biggest advantage at probing at PV nodes is to have a
     // smooth experience in analysis mode. We don't probe at Root nodes otherwise
     // we should also update RootMoveList to avoid bogus output.
     // a fail high/low. Biggest advantage at probing at PV nodes is to have a
     // smooth experience in analysis mode. We don't probe at Root nodes otherwise
     // we should also update RootMoveList to avoid bogus output.

-    if (!RootNode && tte && (PvNode ? tte->depth() >= depth && tte->type() == BOUND_EXACT
-                                    : can_return_tt(tte, depth, ttValue, beta)))
+    if (   !RootNode
+        && tte && tte->depth() >= depth
+        && (           PvNode ?  tte->type() == BOUND_EXACT
+            : ttValue >= beta ? (tte->type() & BOUND_LOWER)
+                              : (tte->type() & BOUND_UPPER)))

     {
         TT.refresh(tte);
         ss->currentMove = ttMove; // Can be MOVE_NONE
     {
         TT.refresh(tte);
         ss->currentMove = ttMove; // Can be MOVE_NONE


@@ -800,10 +779,17 @@ split_point_start: // At split points actual search starts from here
                         << " currmovenumber " << moveCount + PVIdx << sync_endl;
       }
 
                         << " currmovenumber " << moveCount + PVIdx << sync_endl;
       }
 

+      ext = DEPTH_ZERO;

       captureOrPromotion = pos.is_capture_or_promotion(move);
       givesCheck = pos.move_gives_check(move, ci);
       captureOrPromotion = pos.is_capture_or_promotion(move);
       givesCheck = pos.move_gives_check(move, ci);

-      dangerous = givesCheck || is_dangerous(pos, move, captureOrPromotion);
-      ext = DEPTH_ZERO;
+      dangerous =   givesCheck
+                 || pos.is_passed_pawn_push(move)
+                 || type_of(move) == CASTLE
+                 || (   captureOrPromotion // Entering a pawn endgame?
+                     && type_of(pos.piece_on(to_sq(move))) != PAWN
+                     && type_of(move) == NORMAL
+                     && (  pos.non_pawn_material(WHITE) + pos.non_pawn_material(BLACK)
+                         - PieceValue[Mg][pos.piece_on(to_sq(move))] == VALUE_ZERO));

 
       // Step 12. Extend checks and, in PV nodes, also dangerous moves
       if (PvNode && dangerous)
 
       // Step 12. Extend checks and, in PV nodes, also dangerous moves
       if (PvNode && dangerous)


@@ -843,7 +829,8 @@ split_point_start: // At split points actual search starts from here
           && !inCheck
           && !dangerous
           &&  move != ttMove
           && !inCheck
           && !dangerous
           &&  move != ttMove

-          && (bestValue > VALUE_MATED_IN_MAX_PLY || bestValue == -VALUE_INFINITE))
+          && (bestValue > VALUE_MATED_IN_MAX_PLY || (   bestValue == -VALUE_INFINITE
+                                                     && alpha > VALUE_MATED_IN_MAX_PLY)))

       {
           // Move count based pruning
           if (   depth < 16 * ONE_PLY
       {
           // Move count based pruning
           if (   depth < 16 * ONE_PLY


@@ -989,7 +976,7 @@ split_point_start: // At split points actual search starts from here
               if (PvNode && value < beta)
               {
                   alpha = value; // Update alpha here! Always alpha < beta
               if (PvNode && value < beta)
               {
                   alpha = value; // Update alpha here! Always alpha < beta

-                  if (SpNode) sp->alpha = alpha;
+                  if (SpNode) sp->alpha = value;

               }
               else // Fail high
               {
               }
               else // Fail high
               {


@@ -1079,18 +1066,18 @@ split_point_start: // At split points actual search starts from here
 
     assert(NT == PV || NT == NonPV);
     assert(alpha >= -VALUE_INFINITE && alpha < beta && beta <= VALUE_INFINITE);
 
     assert(NT == PV || NT == NonPV);
     assert(alpha >= -VALUE_INFINITE && alpha < beta && beta <= VALUE_INFINITE);

-    assert((alpha == beta - 1) || PvNode);
+    assert(PvNode || (alpha == beta - 1));

     assert(depth <= DEPTH_ZERO);
 
     StateInfo st;
     assert(depth <= DEPTH_ZERO);
 
     StateInfo st;

-    Move ttMove, move, bestMove;
-    Value ttValue, bestValue, value, evalMargin, futilityValue, futilityBase;
-    bool inCheck, enoughMaterial, givesCheck, evasionPrunable;

     const TTEntry* tte;
     const TTEntry* tte;

+    Key posKey;
+    Move ttMove, move, bestMove;
+    Value bestValue, value, ttValue, futilityValue, futilityBase;
+    bool inCheck, givesCheck, enoughMaterial, evasionPrunable;

     Depth ttDepth;
     Depth ttDepth;

-    Bound bt;
-    Value oldAlpha = alpha;

 
 

+    inCheck = pos.in_check();

     ss->currentMove = bestMove = MOVE_NONE;
     ss->ply = (ss-1)->ply + 1;
 
     ss->currentMove = bestMove = MOVE_NONE;
     ss->ply = (ss-1)->ply + 1;
 


@@ -1098,19 +1085,22 @@ split_point_start: // At split points actual search starts from here
     if (pos.is_draw<true>() || ss->ply > MAX_PLY)
         return Eval::ValueDraw[pos.side_to_move()];
 
     if (pos.is_draw<true>() || ss->ply > MAX_PLY)
         return Eval::ValueDraw[pos.side_to_move()];
 

+    // Transposition table lookup. At PV nodes, we don't use the TT for
+    // pruning, but only for move ordering.
+    posKey = pos.key();
+    tte = TT.probe(posKey);
+    ttMove = tte ? tte->move() : MOVE_NONE;
+    ttValue = tte ? value_from_tt(tte->value(),ss->ply) : VALUE_NONE;
+

     // Decide whether or not to include checks, this fixes also the type of
     // TT entry depth that we are going to use. Note that in qsearch we use
     // only two types of depth in TT: DEPTH_QS_CHECKS or DEPTH_QS_NO_CHECKS.
     // Decide whether or not to include checks, this fixes also the type of
     // TT entry depth that we are going to use. Note that in qsearch we use
     // only two types of depth in TT: DEPTH_QS_CHECKS or DEPTH_QS_NO_CHECKS.

-    inCheck = pos.in_check();
-    ttDepth = (inCheck || depth >= DEPTH_QS_CHECKS ? DEPTH_QS_CHECKS : DEPTH_QS_NO_CHECKS);
+    ttDepth = inCheck || depth >= DEPTH_QS_CHECKS ? DEPTH_QS_CHECKS : DEPTH_QS_NO_CHECKS;

 
 

-    // Transposition table lookup. At PV nodes, we don't use the TT for
-    // pruning, but only for move ordering.
-    tte = TT.probe(pos.key());
-    ttMove = (tte ? tte->move() : MOVE_NONE);
-    ttValue = tte ? value_from_tt(tte->value(),ss->ply) : VALUE_ZERO;
-
-    if (!PvNode && tte && can_return_tt(tte, ttDepth, ttValue, beta))
+    if (   tte && tte->depth() >= ttDepth
+        && (           PvNode ?  tte->type() == BOUND_EXACT
+            : ttValue >= beta ? (tte->type() & BOUND_LOWER)
+                              : (tte->type() & BOUND_UPPER)))

     {
         ss->currentMove = ttMove; // Can be MOVE_NONE
         return ttValue;
     {
         ss->currentMove = ttMove; // Can be MOVE_NONE
         return ttValue;


@@ -1119,8 +1109,8 @@ split_point_start: // At split points actual search starts from here
     // Evaluate the position statically
     if (inCheck)
     {
     // Evaluate the position statically
     if (inCheck)
     {

+        ss->eval = ss->evalMargin = VALUE_NONE;

         bestValue = futilityBase = -VALUE_INFINITE;
         bestValue = futilityBase = -VALUE_INFINITE;

-        ss->eval = evalMargin = VALUE_NONE;

         enoughMaterial = false;
     }
     else
         enoughMaterial = false;
     }
     else


@@ -1129,17 +1119,17 @@ split_point_start: // At split points actual search starts from here
         {
             assert(tte->static_value() != VALUE_NONE);
 
         {
             assert(tte->static_value() != VALUE_NONE);
 

-            evalMargin = tte->static_value_margin();

             ss->eval = bestValue = tte->static_value();
             ss->eval = bestValue = tte->static_value();

+            ss->evalMargin = tte->static_value_margin();

         }
         else
         }
         else

-            ss->eval = bestValue = evaluate(pos, evalMargin);
+            ss->eval = bestValue = evaluate(pos, ss->evalMargin);

 
         // Stand pat. Return immediately if static value is at least beta
         if (bestValue >= beta)
         {
             if (!tte)
 
         // Stand pat. Return immediately if static value is at least beta
         if (bestValue >= beta)
         {
             if (!tte)

-                TT.store(pos.key(), value_to_tt(bestValue, ss->ply), BOUND_LOWER, DEPTH_NONE, MOVE_NONE, ss->eval, evalMargin);
+                TT.store(pos.key(), value_to_tt(bestValue, ss->ply), BOUND_LOWER, DEPTH_NONE, MOVE_NONE, ss->eval, ss->evalMargin);

 
             return bestValue;
         }
 
             return bestValue;
         }


@@ -1147,7 +1137,7 @@ split_point_start: // At split points actual search starts from here
         if (PvNode && bestValue > alpha)
             alpha = bestValue;
 
         if (PvNode && bestValue > alpha)
             alpha = bestValue;
 

-        futilityBase = ss->eval + evalMargin + Value(128);
+        futilityBase = ss->eval + ss->evalMargin + Value(128);

         enoughMaterial = pos.non_pawn_material(pos.side_to_move()) > RookValueMg;
     }
 
         enoughMaterial = pos.non_pawn_material(pos.side_to_move()) > RookValueMg;
     }
 


@@ -1159,8 +1149,7 @@ split_point_start: // At split points actual search starts from here
     CheckInfo ci(pos);
 
     // Loop through the moves until no moves remain or a beta cutoff occurs
     CheckInfo ci(pos);
 
     // Loop through the moves until no moves remain or a beta cutoff occurs

-    while (   bestValue < beta
-           && (move = mp.next_move<false>()) != MOVE_NONE)
+    while ((move = mp.next_move<false>()) != MOVE_NONE)

     {
       assert(is_ok(move));
 
     {
       assert(is_ok(move));
 


@@ -1227,21 +1216,31 @@ split_point_start: // At split points actual search starts from here
 
       // Make and search the move
       pos.do_move(move, st, ci, givesCheck);
 
       // Make and search the move
       pos.do_move(move, st, ci, givesCheck);

-      value = -qsearch<NT>(pos, ss+1, -beta, -alpha, depth-ONE_PLY);
+      value = -qsearch<NT>(pos, ss+1, -beta, -alpha, depth - ONE_PLY);

       pos.undo_move(move);
 
       assert(value > -VALUE_INFINITE && value < VALUE_INFINITE);
 
       pos.undo_move(move);
 
       assert(value > -VALUE_INFINITE && value < VALUE_INFINITE);
 

-      // New best move?
+      // Check for new best move

       if (value > bestValue)
       {
           bestValue = value;
       if (value > bestValue)
       {
           bestValue = value;

-          bestMove = move;

 
 

-          if (   PvNode
-              && value > alpha
-              && value < beta) // We want always alpha < beta
-              alpha = value;
+          if (value > alpha)
+          {
+              if (PvNode && value < beta) // Update alpha here! Always alpha < beta
+              {
+                  alpha = value;
+                  bestMove = move;
+              }
+              else // Fail high
+              {
+                  TT.store(posKey, value_to_tt(value, ss->ply), BOUND_LOWER,
+                           ttDepth, move, ss->eval, ss->evalMargin);
+
+                  return value;
+              }
+          }

        }
     }
 
        }
     }
 


@@ -1250,12 +1249,9 @@ split_point_start: // At split points actual search starts from here
     if (inCheck && bestValue == -VALUE_INFINITE)
         return mated_in(ss->ply); // Plies to mate from the root
 
     if (inCheck && bestValue == -VALUE_INFINITE)
         return mated_in(ss->ply); // Plies to mate from the root
 

-    // Update transposition table
-    move = bestValue <= oldAlpha ? MOVE_NONE : bestMove;
-    bt   = bestValue <= oldAlpha ? BOUND_UPPER
-         : bestValue >= beta ? BOUND_LOWER : BOUND_EXACT;
-
-    TT.store(pos.key(), value_to_tt(bestValue, ss->ply), bt, ttDepth, move, ss->eval, evalMargin);
+    TT.store(posKey, value_to_tt(bestValue, ss->ply),
+             PvNode && bestMove != MOVE_NONE ? BOUND_EXACT : BOUND_UPPER,
+             ttDepth, bestMove, ss->eval, ss->evalMargin);

 
     assert(bestValue > -VALUE_INFINITE && bestValue < VALUE_INFINITE);
 
 
     assert(bestValue > -VALUE_INFINITE && bestValue < VALUE_INFINITE);
 


@@ -1428,20 +1424,6 @@ split_point_start: // At split points actual search starts from here
   }
 
 
   }
 
 

-  // can_return_tt() returns true if a transposition table score can be used to
-  // cut-off at a given point in search.
-
-  bool can_return_tt(const TTEntry* tte, Depth depth, Value v, Value beta) {
-
-    return   (   tte->depth() >= depth
-              || v >= std::max(VALUE_MATE_IN_MAX_PLY, beta)
-              || v < std::min(VALUE_MATED_IN_MAX_PLY, beta))
-
-          && (   ((tte->type() & BOUND_LOWER) && v >= beta)
-              || ((tte->type() & BOUND_UPPER) && v < beta));
-  }
-
-

   // refine_eval() returns the transposition table score if possible, otherwise
   // falls back on static position evaluation.
 
   // refine_eval() returns the transposition table score if possible, otherwise
   // falls back on static position evaluation.