X-Git-Url: https://git.sesse.net/?a=blobdiff_plain;f=src%2Fsearch.cpp;h=a0427f5cc5c91e42c1702a07fa72604805d28bec;hb=62f6d39204696ba327989419891d2f9bef2d0117;hp=ebd004d39c541d5632163ffe8817f113a6891f74;hpb=77bb9a94aed2a78d98e04399207f51ed92d531d3;p=stockfish

diff --git a/src/search.cpp b/src/search.cpp
index ebd004d3..a0427f5c 100644
--- a/src/search.cpp
+++ b/src/search.cpp
@@ -1052,37 +1052,50 @@ namespace {
     if (depth < OnePly)
         return qsearch(pos, ss, alpha, 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
     oldAlpha = alpha;
     alpha = Max(value_mated_in(ply), alpha);
     beta = Min(value_mate_in(ply+1), beta);
     if (alpha >= beta)
         return alpha;
 
-    // Transposition table lookup. At PV nodes, we don't use the TT for
-    // pruning, but only for move ordering. This is to avoid problems in
-    // the following areas:
+    // Step 4. Transposition table lookup
+    // At PV nodes, we don't use the TT for pruning, but only for move ordering.
+    // This is to avoid problems in the following areas:
     //
     // * Repetition draw detection
     // * Fifty move rule detection
     // * Searching for a mate
     // * Printing of full PV line
-    //
     tte = TT.retrieve(pos.get_key());
     ttMove = (tte ? tte->move() : MOVE_NONE);
 
-    // Go with internal iterative deepening if we don't have a TT move
+    // Step 5. Evaluate the position statically
+    // At PV nodes we do this only to update gain statistics
+    isCheck = pos.is_check();
+    if (!isCheck)
+    {
+        EvalInfo ei;
+        ss[ply].eval = evaluate(pos, ei, threadID);
+        update_gains(pos, ss[ply - 1].currentMove, ss[ply - 1].eval, ss[ply].eval);
+    }
+
+    // Step 6. Razoring (is omitted in PV nodes)
+    // Step 7. Static null move pruning (is omitted in PV nodes)
+    // Step 8. Null move search with verification search (is omitted in PV nodes)
+
+    // Step 9. Internal iterative deepening
     if (   UseIIDAtPVNodes
         && depth >= 5*OnePly
         && ttMove == MOVE_NONE)
@@ -1092,24 +1105,14 @@ namespace {
         tte = TT.retrieve(pos.get_key());
     }
 
-    isCheck = pos.is_check();
-    if (!isCheck)
-    {
-        // Update gain statistics of the previous move that lead
-        // us in this position.
-        EvalInfo ei;
-        ss[ply].eval = evaluate(pos, ei, threadID);
-        update_gains(pos, ss[ply - 1].currentMove, ss[ply - 1].eval, ss[ply].eval);
-    }
+    // Step 10. Loop through moves
+    // Loop through all legal moves until no moves remain or a beta cutoff occurs
 
-    // Initialize a MovePicker object for the current position, and prepare
-    // to search all moves
+    // Initialize a MovePicker object for the current position
     mateThreat = pos.has_mate_threat(opposite_color(pos.side_to_move()));
-    CheckInfo ci(pos);
     MovePicker mp = MovePicker(pos, ttMove, depth, H, &ss[ply]);
+    CheckInfo ci(pos);
 
-    // Loop through all legal moves until no moves remain or a beta cutoff
-    // occurs.
     while (   alpha < beta
            && (move = mp.get_next_move()) != MOVE_NONE
            && !TM.thread_should_stop(threadID))
@@ -1120,7 +1123,7 @@ namespace {
       moveIsCheck = pos.move_is_check(move, ci);
       captureOrPromotion = pos.move_is_capture_or_promotion(move);
 
-      // Decide the new search depth
+      // Step 11. Decide the new search depth
       ext = extension(pos, move, true, captureOrPromotion, moveIsCheck, singleEvasion, mateThreat, &dangerous);
 
       // Singular extension search. We extend the TT move if its value is much better than
@@ -1146,17 +1149,21 @@ namespace {
 
       newDepth = depth - OnePly + ext;
 
-      // Update current move
+      // Update current move (this must be done after singular extension search)
       movesSearched[moveCount++] = ss[ply].currentMove = move;
 
-      // Make and search the move
+      // Step 12. Futility pruning (is omitted in PV nodes)
+
+      // Step 13. Make the move
       pos.do_move(move, st, ci, moveIsCheck);
 
-      if (moveCount == 1) // The first move in list is the PV
+      // Step extra. pv search (only in PV nodes)
+      // The first move in list is the expected PV
+      if (moveCount == 1)
           value = -search_pv(pos, ss, -beta, -alpha, newDepth, ply+1, threadID);
       else
       {
-        // Try to reduce non-pv search depth by one ply if move seems not problematic,
+        // Step 14. Reduced search
         // if the move fails high will be re-searched at full depth.
         bool doFullDepthSearch = true;
 
@@ -1174,19 +1181,24 @@ namespace {
             }
         }
 
-        if (doFullDepthSearch) // Go with full depth non-pv search
+        // Step 15. Full depth search
+        if (doFullDepthSearch)
         {
             ss[ply].reduction = Depth(0);
             value = -search(pos, ss, -alpha, newDepth, ply+1, true, threadID);
+
+            // Step extra. pv search (only in PV nodes)
             if (value > alpha && value < beta)
                 value = -search_pv(pos, ss, -beta, -alpha, newDepth, ply+1, threadID);
         }
       }
+
+      // Step 16. Undo move
       pos.undo_move(move);
 
       assert(value > -VALUE_INFINITE && value < VALUE_INFINITE);
 
-      // New best move?
+      // Step 17. Check for new best move
       if (value > bestValue)
       {
           bestValue = value;
@@ -1199,7 +1211,7 @@ namespace {
           }
       }
 
-      // Split?
+      // Step 18. Check for split
       if (   TM.active_threads() > 1
           && bestValue < beta
           && depth >= MinimumSplitDepth
@@ -1212,11 +1224,13 @@ namespace {
           break;
     }
 
-    // All legal moves have been searched.  A special case: If there were
+    // Step 19. Check for mate and stalemate
+    // All legal moves have been searched and if there were
     // no legal moves, it must be mate or stalemate.
     if (moveCount == 0)
         return (isCheck ? value_mated_in(ply) : VALUE_DRAW);
 
+    // Step 20. Update tables
     // If the search is not aborted, update the transposition table,
     // history counters, and killer moves.
     if (AbortSearch || TM.thread_should_stop(threadID))
@@ -1316,16 +1330,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
@@ -1374,36 +1406,23 @@ 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);
     }
 
-    // Initialize a MovePicker object for the current position, and prepare
-    // to search all moves.
+    // Step 10. Loop through moves
+    // Loop through all legal moves until no moves remain or a beta cutoff occurs
+
+    // Initialize a MovePicker object for the current position
     MovePicker mp = MovePicker(pos, ttMove, depth, H, &ss[ply]);
     CheckInfo ci(pos);
 
-    // Loop through all legal moves until no moves remain or a beta cutoff occurs
     while (   bestValue < beta
            && (move = mp.get_next_move()) != MOVE_NONE
            && !TM.thread_should_stop(threadID))
@@ -1417,7 +1436,7 @@ namespace {
       singleEvasion = (isCheck && mp.number_of_evasions() == 1);
       captureOrPromotion = pos.move_is_capture_or_promotion(move);
 
-      // Decide the new search depth
+      // Step 11. Decide the new search depth
       ext = extension(pos, move, false, captureOrPromotion, moveIsCheck, singleEvasion, mateThreat, &dangerous);
 
       // Singular extension search. We extend the TT move if its value is much better than
@@ -1444,10 +1463,10 @@ namespace {
 
       newDepth = depth - OnePly + ext;
 
-      // Update current move
+      // Update current move (this must be done after singular extension search)
       movesSearched[moveCount++] = ss[ply].currentMove = move;
 
-      // Futility pruning
+      // Step 12. Futility pruning
       if (   !isCheck
           && !dangerous
           && !captureOrPromotion
@@ -1473,10 +1492,10 @@ namespace {
           }
       }
 
-      // Make and search the move
+      // Step 13. Make the move
       pos.do_move(move, st, ci, moveIsCheck);
 
-      // Try to reduce non-pv search depth by one ply if move seems not problematic,
+      // Step 14. Reduced search
       // if the move fails high will be re-searched at full depth.
       bool doFullDepthSearch = true;
 
@@ -1494,16 +1513,19 @@ namespace {
           }
       }
 
-      if (doFullDepthSearch) // Go with full depth non-pv search
+      // Step 15. Full depth search
+      if (doFullDepthSearch)
       {
           ss[ply].reduction = Depth(0);
           value = -search(pos, ss, -(beta-1), newDepth, ply+1, true, threadID);
       }
+
+      // Step 16. Undo move
       pos.undo_move(move);
 
       assert(value > -VALUE_INFINITE && value < VALUE_INFINITE);
 
-      // New best move?
+      // Step 17. Check for new best move
       if (value > bestValue)
       {
           bestValue = value;
@@ -1514,7 +1536,7 @@ namespace {
               ss[ply].mateKiller = move;
       }
 
-      // Split?
+      // Step 18. Check for split
       if (   TM.active_threads() > 1
           && bestValue < beta
           && depth >= MinimumSplitDepth
@@ -1527,11 +1549,14 @@ namespace {
           break;
     }
 
-    // All legal moves have been searched. A special case: If there were
+    // Step 19. Check for mate and stalemate
+    // All legal moves have been searched and if there were
     // no legal moves, it must be mate or stalemate.
+    // If one move was excluded return fail low.
     if (!moveCount)
         return excludedMove ? beta - 1 : (pos.is_check() ? value_mated_in(ply) : VALUE_DRAW);
 
+    // Step 20. Update tables
     // If the search is not aborted, update the transposition table,
     // history counters, and killer moves.
     if (AbortSearch || TM.thread_should_stop(threadID))
@@ -1765,6 +1790,7 @@ namespace {
     Position pos(*sp->pos);
     CheckInfo ci(pos);
     SearchStack* ss = sp->sstack[threadID];
+    StateInfo st;
     Value value = -VALUE_INFINITE;
     Move move;
     int moveCount;
@@ -1772,8 +1798,9 @@ namespace {
     bool useFutilityPruning =     sp->depth < 7 * OnePly //FIXME: sync with search
                               && !isCheck;
 
-    while (    lock_grab_bool(&(sp->lock))
-           &&  sp->bestValue < sp->beta
+    lock_grab(&(sp->lock));
+
+    while (    sp->bestValue < sp->beta
            && !TM.thread_should_stop(threadID)
            && (move = sp->mp->get_next_move()) != MOVE_NONE)
     {
@@ -1801,29 +1828,28 @@ namespace {
           if (   moveCount >= futility_move_count(sp->depth)
               && ok_to_prune(pos, move, ss[sp->ply].threatMove)
               && sp->bestValue > value_mated_in(PLY_MAX))
+          {
+              lock_grab(&(sp->lock));
               continue;
+          }
 
           // Value based pruning
           Value futilityValueScaled = sp->futilityValue - moveCount * 8; //FIXME: sync with search
 
           if (futilityValueScaled < sp->beta)
           {
-              if (futilityValueScaled > sp->bestValue) // Less then 1% of cases
-              {
-                  lock_grab(&(sp->lock));
-                  if (futilityValueScaled > sp->bestValue)
-                      sp->bestValue = futilityValueScaled;
-                  lock_release(&(sp->lock));
-              }
+              lock_grab(&(sp->lock));
+
+              if (futilityValueScaled > sp->bestValue)
+                  sp->bestValue = futilityValueScaled;
               continue;
           }
       }
 
-      // Make and search the move.
-      StateInfo st;
+      // Step 13. Make the move
       pos.do_move(move, st, ci, moveIsCheck);
 
-      // Try to reduce non-pv search depth by one ply if move seems not problematic,
+      // Step 14. Reduced search
       // if the move fails high will be re-searched at full depth.
       bool doFullDepthSearch = true;
 
@@ -1840,36 +1866,36 @@ namespace {
           }
       }
 
-      if (doFullDepthSearch) // Go with full depth non-pv search
+      // Step 15. Full depth search
+      if (doFullDepthSearch)
       {
           ss[sp->ply].reduction = Depth(0);
           value = -search(pos, ss, -(sp->beta - 1), newDepth, sp->ply+1, true, threadID);
       }
+
+      // Step 16. Undo move
       pos.undo_move(move);
 
       assert(value > -VALUE_INFINITE && value < VALUE_INFINITE);
 
-      // New best move?
-      if (value > sp->bestValue) // Less then 2% of cases
+      // Step 17. Check for new best move
+      lock_grab(&(sp->lock));
+
+      if (value > sp->bestValue && !TM.thread_should_stop(threadID))
       {
-          lock_grab(&(sp->lock));
-          if (value > sp->bestValue && !TM.thread_should_stop(threadID))
+          sp->bestValue = value;
+          if (sp->bestValue >= sp->beta)
           {
-              sp->bestValue = value;
-              if (sp->bestValue >= sp->beta)
-              {
-                  sp->stopRequest = true;
-                  sp_update_pv(sp->parentSstack, ss, sp->ply);
-              }
+              sp->stopRequest = true;
+              sp_update_pv(sp->parentSstack, ss, sp->ply);
           }
-          lock_release(&(sp->lock));
       }
     }
 
     /* Here we have the lock still grabbed */
 
-    sp->cpus--;
     sp->slaves[threadID] = 0;
+    sp->cpus--;
 
     lock_release(&(sp->lock));
   }
@@ -1895,8 +1921,9 @@ namespace {
     int moveCount;
     Move move;
 
-    while (    lock_grab_bool(&(sp->lock))
-           &&  sp->alpha < sp->beta
+    lock_grab(&(sp->lock));
+
+    while (    sp->alpha < sp->beta
            && !TM.thread_should_stop(threadID)
            && (move = sp->mp->get_next_move()) != MOVE_NONE)
     {
@@ -1957,33 +1984,30 @@ namespace {
       assert(value > -VALUE_INFINITE && value < VALUE_INFINITE);
 
       // New best move?
-      if (value > sp->bestValue) // Less then 2% of cases
+      lock_grab(&(sp->lock));
+
+      if (value > sp->bestValue && !TM.thread_should_stop(threadID))
       {
-          lock_grab(&(sp->lock));
-          if (value > sp->bestValue && !TM.thread_should_stop(threadID))
+          sp->bestValue = value;
+          if (value > sp->alpha)
           {
-              sp->bestValue = value;
-              if (value > sp->alpha)
-              {
-                  // Ask threads to stop before to modify sp->alpha
-                  if (value >= sp->beta)
-                      sp->stopRequest = true;
-
-                  sp->alpha = value;
-
-                  sp_update_pv(sp->parentSstack, ss, sp->ply);
-                  if (value == value_mate_in(sp->ply + 1))
-                      ss[sp->ply].mateKiller = move;
-              }
+              // Ask threads to stop before to modify sp->alpha
+              if (value >= sp->beta)
+                  sp->stopRequest = true;
+
+              sp->alpha = value;
+
+              sp_update_pv(sp->parentSstack, ss, sp->ply);
+              if (value == value_mate_in(sp->ply + 1))
+                  ss[sp->ply].mateKiller = move;
           }
-          lock_release(&(sp->lock));
       }
     }
 
     /* Here we have the lock still grabbed */
 
-    sp->cpus--;
     sp->slaves[threadID] = 0;
+    sp->cpus--;
 
     lock_release(&(sp->lock));
   }