Search code documentation take II

[stockfish] / src / search.cpp

diff --git a/src/search.cpp b/src/search.cpp
index 3a70c8f797fde7e299f9fa39d020dd9352d91d73..16f73d47bdee8ba3f5feedff584ba11aa5461900 100644 (file)
--- a/src/search.cpp
+++ b/src/search.cpp
@@ -1267,29 +1267,30 @@ namespace {
     if (depth < OnePly)
         return qsearch(pos, ss, beta-1, beta, Depth(0), ply, threadID);
 
-    // Initialize, and make an early exit in case of an aborted search,
-    // an instant draw, maximum ply reached, etc.
+    // Step 1. Initialize node and poll
+    // Polling can abort search.
     init_node(ss, ply, threadID);
 
-    // After init_node() that calls poll()
+    // Step 2. Check for aborted search and immediate draw
     if (AbortSearch || TM.thread_should_stop(threadID))
         return Value(0);
 
     if (pos.is_draw() || ply >= PLY_MAX - 1)
         return VALUE_DRAW;
 
-    // Mate distance pruning
+    // Step 3. Mate distance pruning
     if (value_mated_in(ply) >= beta)
         return beta;
 
     if (value_mate_in(ply + 1) < beta)
         return beta - 1;
 
+    // Step 4. Transposition table lookup
+
     // We don't want the score of a partial search to overwrite a previous full search
     // TT value, so we use a different position key in case of an excluded move exsists.
     Key posKey = excludedMove ? pos.get_exclusion_key() : pos.get_key();
 
-    // Transposition table lookup
     tte = TT.retrieve(posKey);
     ttMove = (tte ? tte->move() : MOVE_NONE);
 
@@ -1299,9 +1300,9 @@ namespace {
         return value_from_tt(tte->value(), ply);
     }
 
+    // Step 5. Evaluate the position statically
     isCheck = pos.is_check();
 
-    // Evaluate the position statically
     if (!isCheck)
     {
         if (tte && (tte->type() & VALUE_TYPE_EVAL))
@@ -1315,16 +1316,34 @@ namespace {
         update_gains(pos, ss[ply - 1].currentMove, ss[ply - 1].eval, ss[ply].eval);
     }
 
-    // Static null move pruning. We're betting that the opponent doesn't have
-    // a move that will reduce the score by more than FutilityMargins[int(depth)]
-    // if we do a null move.
+    // Step 6. Razoring
+    if (   !value_is_mate(beta)
+        && !isCheck
+        && depth < RazorDepth
+        && staticValue < beta - (0x200 + 16 * depth)
+        && ss[ply - 1].currentMove != MOVE_NULL
+        && ttMove == MOVE_NONE
+        && !pos.has_pawn_on_7th(pos.side_to_move()))
+    {
+        Value rbeta = beta - (0x200 + 16 * depth);
+        Value v = qsearch(pos, ss, rbeta-1, rbeta, Depth(0), ply, threadID);
+        if (v < rbeta)
+          return v; //FIXME: Logically should be: return (v + 0x200 + 16 * depth);
+    }
+
+    // Step 7. Static null move pruning
+    // We're betting that the opponent doesn't have a move that will reduce
+    // the score by more than fuility_margin(depth) if we do a null move.
     if (  !isCheck
         && allowNullmove
         && depth < RazorDepth
         && staticValue - futility_margin(depth, 0) >= beta)
         return staticValue - futility_margin(depth, 0);
 
-    // Null move search
+    // Step 8. Null move search with verification search
+    // When we jump directly to qsearch() we do a null move only if static value is
+    // at least beta. Otherwise we do a null move if static value is not more than
+    // NullMoveMargin under beta.
     if (    allowNullmove
         &&  depth > OnePly
         && !isCheck
@@ -1373,26 +1392,12 @@ namespace {
                 return beta - 1;
         }
     }
-    // Null move search not allowed, try razoring
-    else if (   !value_is_mate(beta)
-             && !isCheck
-             && depth < RazorDepth
-             && staticValue < beta - (NullMoveMargin + 16 * depth)
-             && ss[ply - 1].currentMove != MOVE_NULL
-             && ttMove == MOVE_NONE
-             && !pos.has_pawn_on_7th(pos.side_to_move()))
-    {
-        Value rbeta = beta - (NullMoveMargin + 16 * depth);
-        Value v = qsearch(pos, ss, rbeta-1, rbeta, Depth(0), ply, threadID);
-        if (v < rbeta)
-          return v;
-    }
 
-    // Go with internal iterative deepening if we don't have a TT move
+    // Step 9. Internal iterative deepening
     if (UseIIDAtNonPVNodes && ttMove == MOVE_NONE && depth >= 8*OnePly &&
         !isCheck && ss[ply].eval >= beta - IIDMargin)
     {
-        search(pos, ss, beta, Min(depth/2, depth-2*OnePly), ply, false, threadID);
+        search(pos, ss, beta, depth/2, ply, false, threadID);
         ttMove = ss[ply].pv[ply];
         tte = TT.retrieve(posKey);
     }
@@ -1835,7 +1840,7 @@ namespace {
           if (ss[sp->ply].reduction)
           {
               value = -search(pos, ss, -(sp->beta-1), newDepth-ss[sp->ply].reduction, sp->ply+1, true, threadID);
-              doFullDepthSearch = (value >= sp->beta);
+              doFullDepthSearch = (value >= sp->beta && !TM.thread_should_stop(threadID));
           }
       }
 
@@ -1932,7 +1937,7 @@ namespace {
           {
               Value localAlpha = sp->alpha;
               value = -search(pos, ss, -localAlpha, newDepth-ss[sp->ply].reduction, sp->ply+1, true, threadID);
-              doFullDepthSearch = (value > localAlpha);
+              doFullDepthSearch = (value > localAlpha && !TM.thread_should_stop(threadID));
           }
       }
 
@@ -1942,16 +1947,14 @@ namespace {
           ss[sp->ply].reduction = Depth(0);
           value = -search(pos, ss, -localAlpha, newDepth, sp->ply+1, true, threadID);
 
-          if (value > localAlpha && value < sp->beta)
+          if (value > localAlpha && value < sp->beta && !TM.thread_should_stop(threadID))
           {
               // If another thread has failed high then sp->alpha has been increased
               // to be higher or equal then beta, if so, avoid to start a PV search.
               localAlpha = sp->alpha;
               if (localAlpha < sp->beta)
                   value = -search_pv(pos, ss, -sp->beta, -localAlpha, newDepth, sp->ply+1, threadID);
-              else
-                  assert(TM.thread_should_stop(threadID));
-        }
+          }
       }
       pos.undo_move(move);