Document Elo impact of various parts of search

In order to understand better the impact of various techniques used in search,
Elo estimates have been run at STC for 60000 games (statistical error ~1.8 Elo),
disabling each feature in turn. This should help future improvements and
simplifications to pick suitable targets.

The list of tests is:
step  7 : http://tests.stockfishchess.org/tests/view/5abcbb4b0ebc5902926cf1ca
step  8 : http://tests.stockfishchess.org/tests/view/5abcbb680ebc5902926cf1cc
step  9 : http://tests.stockfishchess.org/tests/view/5abcbb850ebc5902926cf1ce
step 10 : http://tests.stockfishchess.org/tests/view/5abcbbeb0ebc5902926cf1d2
step 11 : http://tests.stockfishchess.org/tests/view/5abcbbbf0ebc5902926cf1d0
step 13 : http://tests.stockfishchess.org/tests/view/5abd03680ebc5902926cf20b
step 13a: http://tests.stockfishchess.org/tests/view/5abd29660ebc5902926cf22a
step 13b: http://tests.stockfishchess.org/tests/view/5abd29820ebc5902926cf22c
step 14 : http://tests.stockfishchess.org/tests/view/5abd03860ebc5902926cf20f
step 14a: http://tests.stockfishchess.org/tests/view/5abd2b6c0ebc5902926cf230
step 14b: http://tests.stockfishchess.org/tests/view/5abd2b8d0ebc5902926cf232
step 14c: http://tests.stockfishchess.org/tests/view/5abd2bad0ebc5902926cf234
step 14d: http://tests.stockfishchess.org/tests/view/5abd2bcf0ebc5902926cf236
step 14e: http://tests.stockfishchess.org/tests/view/5abd2bf10ebc5902926cf238

This patch documents this in the code.

Note that it will be a waste to recompute these estimates often, even a couple
of [0,5] patches are unlikely to change them by more than the error bars. The
interest of the Elo annotations in the code is not in the details, but in high-
lighting trends such as razoring (2 Elo) and singular extensions (60 Elo). These
estimates should be recomputed at most once a year.

Closes https://github.com/official-stockfish/Stockfish/pull/1522

No functional change.

diff --git a/src/evaluate.cpp b/src/evaluate.cpp
index f4811aea82433945cf77d9ffcfc9191aa23f05ad..3e0533b20c7d8c730c08976bb5c016f39746b742 100644 (file)
--- a/src/evaluate.cpp
+++ b/src/evaluate.cpp
@@ -373,7 +373,7 @@ namespace {
 
         if (Pt == ROOK)
         {
-            // Bonus for aligning rook with with enemy pawns on the same rank/file
+            // Bonus for aligning rook with enemy pawns on the same rank/file
             if (relative_rank(Us, s) >= RANK_5)
                 score += RookOnPawn * popcount(pos.pieces(Them, PAWN) & PseudoAttacks[ROOK][s]);
 
@@ -692,7 +692,7 @@ namespace {
             }
             else if (pos.pieces(Us) & blockSq)
                 bonus += make_score(w + r * 2, w + r * 2);
-        } // rr != 0
+        } // w != 0
 
         // Scale down bonus for candidate passers which need more than one
         // pawn push to become passed or have a pawn in front of them.

diff --git a/src/search.cpp b/src/search.cpp
index f0783363e79766fc682dabbf42fc4d0d0cda9469..43193f1059540e0a92e4895e78b313044ced29f8 100644 (file)
--- a/src/search.cpp
+++ b/src/search.cpp
@@ -698,7 +698,7 @@ namespace {
     if (skipEarlyPruning || !pos.non_pawn_material(pos.side_to_move()))
         goto moves_loop;
 
-    // Step 7. Razoring (skipped when in check)
+    // Step 7. Razoring (skipped when in check, ~2 Elo)
     if (  !PvNode
         && depth < 3 * ONE_PLY
         && eval <= alpha - RazorMargin[depth / ONE_PLY])
@@ -709,14 +709,14 @@ namespace {
             return v;
     }
 
-    // Step 8. Futility pruning: child node (skipped when in check)
+    // Step 8. Futility pruning: child node (skipped when in check, ~30 Elo)
     if (   !rootNode
         &&  depth < 7 * ONE_PLY
         &&  eval - futility_margin(depth, improving) >= beta
         &&  eval < VALUE_KNOWN_WIN) // Do not return unproven wins
         return eval;
 
-    // Step 9. Null move search with verification search
+    // Step 9. Null move search with verification search (~40 Elo)
     if (   !PvNode
         &&  eval >= beta
         &&  ss->staticEval >= beta - 36 * depth / ONE_PLY + 225
@@ -759,7 +759,7 @@ namespace {
         }
     }
 
-    // Step 10. ProbCut (skipped when in check)
+    // Step 10. ProbCut (skipped when in check, ~10 Elo)
     // If we have a good enough capture and a reduced search returns a value
     // much above beta, we can (almost) safely prune the previous move.
     if (   !PvNode
@@ -799,7 +799,7 @@ namespace {
             }
     }
 
-    // Step 11. Internal iterative deepening (skipped when in check)
+    // Step 11. Internal iterative deepening (skipped when in check, ~2 Elo)
     if (    depth >= 6 * ONE_PLY
         && !ttMove
         && (PvNode || ss->staticEval + 128 >= beta))
@@ -864,9 +864,9 @@ moves_loop: // When in check, search starts from here
       moveCountPruning =   depth < 16 * ONE_PLY
                         && moveCount >= FutilityMoveCounts[improving][depth / ONE_PLY];
 
-      // Step 13. Extensions
+      // Step 13. Extensions (~70 Elo)
 
-      // Singular extension search. If all moves but one fail low on a search
+      // Singular extension search (~60 Elo). If all moves but one fail low on a search
       // of (alpha-s, beta-s), and just one fails high on (alpha, beta), then
       // that move is singular and should be extended. To verify this we do a
       // reduced search on on all the other moves but the ttMove and if the
@@ -883,7 +883,7 @@ moves_loop: // When in check, search starts from here
           if (value < rBeta)
               extension = ONE_PLY;
       }
-      else if (    givesCheck // Check extension
+      else if (    givesCheck // Check extension (~2 Elo)
                && !moveCountPruning
                &&  pos.see_ge(move))
           extension = ONE_PLY;
@@ -891,7 +891,7 @@ moves_loop: // When in check, search starts from here
       // Calculate new depth for this move
       newDepth = depth - ONE_PLY + extension;
 
-      // Step 14. Pruning at shallow depth
+      // Step 14. Pruning at shallow depth (~170 Elo)
       if (  !rootNode
           && pos.non_pawn_material(pos.side_to_move())
           && bestValue > VALUE_MATED_IN_MAX_PLY)
@@ -900,7 +900,7 @@ moves_loop: // When in check, search starts from here
               && !givesCheck
               && (!pos.advanced_pawn_push(move) || pos.non_pawn_material() >= Value(5000)))
           {
-              // Move count based pruning
+              // Move count based pruning (~30 Elo)
               if (moveCountPruning)
               {
                   skipQuiets = true;
@@ -910,24 +910,24 @@ moves_loop: // When in check, search starts from here
               // Reduced depth of the next LMR search
               int lmrDepth = std::max(newDepth - reduction<PvNode>(improving, depth, moveCount), DEPTH_ZERO) / ONE_PLY;
 
-              // Countermoves based pruning
+              // Countermoves based pruning (~20 Elo)
               if (   lmrDepth < 3
                   && (*contHist[0])[movedPiece][to_sq(move)] < CounterMovePruneThreshold
                   && (*contHist[1])[movedPiece][to_sq(move)] < CounterMovePruneThreshold)
                   continue;
 
-              // Futility pruning: parent node
+              // Futility pruning: parent node (~2 Elo)
               if (   lmrDepth < 7
                   && !inCheck
                   && ss->staticEval + 256 + 200 * lmrDepth <= alpha)
                   continue;
 
-              // Prune moves with negative SEE
+              // Prune moves with negative SEE (~10 Elo)
               if (   lmrDepth < 8
                   && !pos.see_ge(move, Value(-35 * lmrDepth * lmrDepth)))
                   continue;
           }
-          else if (    depth < 7 * ONE_PLY
+          else if (    depth < 7 * ONE_PLY // (~20 Elo)
                    && !extension
                    && !pos.see_ge(move, -Value(CapturePruneMargin[depth / ONE_PLY])))
                   continue;

diff --git a/src/timeman.h b/src/timeman.h
index 4e58cebb5120991b16f50ae86e6063c78bed78bb..fad898e2d09ecefcf2b9163ecea3653dc62baddb 100644 (file)
--- a/src/timeman.h
+++ b/src/timeman.h
@@ -33,7 +33,7 @@ public:
   void init(Search::LimitsType& limits, Color us, int ply);
   TimePoint optimum() const { return optimumTime; }
   TimePoint maximum() const { return maximumTime; }
-  TimePoint elapsed() const { return Search::Limits.npmsec ? 
+  TimePoint elapsed() const { return Search::Limits.npmsec ?
                                      TimePoint(Threads.nodes_searched()) : now() - startTime; }
 
   int64_t availableNodes; // When in 'nodes as time' mode