Rewrite search best value update
authorMarco Costalba <mcostalba@gmail.com>
Wed, 3 Oct 2012 12:11:20 +0000 (14:11 +0200)
committerMarco Costalba <mcostalba@gmail.com>
Fri, 5 Oct 2012 11:53:05 +0000 (13:53 +0200)
A simplification and also a small speed-up of
about 1% mainly due to reducing calls to
thisThread->cutoff_occurred().

Worst case split point recovering time after a
cut-off occurred is limited to 3 msec on my slow
PC, and usually is below 1 msec, so it seems safe
to remove the cutoff_occurred() check.

No functional change.

src/search.cpp

index 77300708f1331104a07f744c9a703cc0aa1770f6..95f99d0177e960dc3b4fd7e6f6c2b5ce634a2acc 100644 (file)
@@ -55,6 +55,9 @@ namespace {
   // Set to true to force running with one thread. Used for debugging
   const bool FakeSplit = false;
 
+  // This is the minimum interval in msec between two check_time() calls
+  const int TimerResolution = 5;
+
   // Different node types, used as template parameter
   enum NodeType { Root, PV, NonPV, SplitPointRoot, SplitPointPV, SplitPointNonPV };
 
@@ -88,10 +91,6 @@ namespace {
     return (Depth) Reductions[PvNode][std::min(int(d) / ONE_PLY, 63)][std::min(mn, 63)];
   }
 
-  // This is the minimum interval in msec between two check_time() calls
-  const int TimerResolution = 5;
-
-
   size_t MultiPV, UCIMultiPV, PVIdx;
   TimeManager TimeMgr;
   int BestMoveChanges;
@@ -99,7 +98,6 @@ namespace {
   bool SkillLevelEnabled, Chess960;
   History H;
 
-
   template <NodeType NT>
   Value search(Position& pos, Stack* ss, Value alpha, Value beta, Depth depth);
 
@@ -505,7 +503,7 @@ namespace {
     Key posKey;
     Move ttMove, move, excludedMove, bestMove, threatMove;
     Depth ext, newDepth;
-    Value bestValue, value, oldAlpha, ttValue;
+    Value bestValue, value, ttValue;
     Value refinedValue, nullValue, futilityValue;
     bool pvMove, inCheck, singularExtensionNode, givesCheck;
     bool captureOrPromotion, dangerous, doFullDepthSearch;
@@ -514,7 +512,6 @@ namespace {
     // Step 1. Initialize node
     Thread* thisThread = pos.this_thread();
     moveCount = playedMoveCount = 0;
-    oldAlpha = alpha;
     inCheck = pos.in_check();
 
     if (SpNode)
@@ -771,10 +768,7 @@ split_point_start: // At split points actual search starts from here
 
     // Step 11. Loop through moves
     // Loop through all pseudo-legal moves until no moves remain or a beta cutoff occurs
-    while (    bestValue < beta
-           && (move = mp.next_move<SpNode>()) != MOVE_NONE
-           && !thisThread->cutoff_occurred()
-           && !Signals.stop)
+    while (bestValue < beta && (move = mp.next_move<SpNode>()) != MOVE_NONE)
     {
       assert(is_ok(move));
 
@@ -958,7 +952,10 @@ split_point_start: // At split points actual search starts from here
       // was aborted because the user interrupted the search or because we
       // ran out of time. In this case, the return value of the search cannot
       // be trusted, and we don't update the best move and/or PV.
-      if (RootNode && !Signals.stop)
+      if (Signals.stop || thisThread->cutoff_occurred())
+          return bestValue;
+
+      if (RootNode)
       {
           RootMove& rm = *std::find(RootMoves.begin(), RootMoves.end(), move);
 
@@ -984,16 +981,16 @@ split_point_start: // At split points actual search starts from here
       if (value > bestValue)
       {
           bestValue = value;
-          bestMove = move;
 
-          if (   PvNode
-              && value > alpha
-              && value < beta) // We want always alpha < beta
+          if (value > alpha)
           {
-              alpha = bestValue; // Update alpha here!
+              bestMove = move;
+
+              if (PvNode && value < beta)
+                  alpha = bestValue; // Update alpha here! Always alpha < beta
           }
 
-          if (SpNode && !thisThread->cutoff_occurred())
+          if (SpNode)
           {
               sp->bestValue = bestValue;
               sp->bestMove = bestMove;
@@ -1004,17 +1001,18 @@ split_point_start: // At split points actual search starts from here
           }
       }
 
-      // Step 19. Check for split
+      // Step 19. Check for splitting the search
       if (   !SpNode
           &&  depth >= Threads.min_split_depth()
           &&  bestValue < beta
-          &&  Threads.available_slave_exists(thisThread)
-          && !Signals.stop
-          && !thisThread->cutoff_occurred())
+          &&  Threads.available_slave_exists(thisThread))
           bestValue = Threads.split<FakeSplit>(pos, ss, alpha, beta, bestValue, &bestMove,
                                                depth, threatMove, moveCount, mp, NT);
     }
 
+    if (SpNode)
+        return bestValue;
+
     // Step 20. Check for mate and stalemate
     // All legal moves have been searched and if there are no legal moves, it
     // must be mate or stalemate. Note that we can have a false positive in
@@ -1022,7 +1020,7 @@ split_point_start: // At split points actual search starts from here
     // harmless because return value is discarded anyhow in the parent nodes.
     // If we are in a singular extension search then return a fail low score.
     // A split node has at least one move, the one tried before to be splitted.
-    if (!SpNode && !moveCount)
+    if (!moveCount)
         return excludedMove ? alpha : inCheck ? mated_in(ss->ply) : VALUE_DRAW;
 
     // If we have pruned all the moves without searching return a fail-low score
@@ -1033,20 +1031,12 @@ split_point_start: // At split points actual search starts from here
         bestValue = alpha;
     }
 
-    // Step 21. Update tables
-    // Update transposition table entry, killers and history
-    if (!SpNode && !Signals.stop && !thisThread->cutoff_occurred())
+    if (bestValue >= beta) // Failed high
     {
-        Move ttm = bestValue <= oldAlpha ? MOVE_NONE : bestMove;
-        Bound bt = bestValue <= oldAlpha ? BOUND_UPPER
-                 : bestValue >= beta ? BOUND_LOWER : BOUND_EXACT;
-
-        TT.store(posKey, value_to_tt(bestValue, ss->ply), bt, depth, ttm, ss->eval, ss->evalMargin);
+        TT.store(posKey, value_to_tt(bestValue, ss->ply), BOUND_LOWER, depth,
+                 bestMove, ss->eval, ss->evalMargin);
 
-        // Update killers and history for non capture cut-off moves
-        if (    bestValue >= beta
-            && !pos.is_capture_or_promotion(bestMove)
-            && !inCheck)
+        if (!pos.is_capture_or_promotion(bestMove) && !inCheck)
         {
             if (bestMove != ss->killers[0])
             {
@@ -1066,6 +1056,10 @@ 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->eval, ss->evalMargin);
 
     assert(bestValue > -VALUE_INFINITE && bestValue < VALUE_INFINITE);