Document Elo impact of various parts of search
authorJoost VandeVondele <Joost.VandeVondele@gmail.com>
Sun, 1 Apr 2018 01:13:29 +0000 (03:13 +0200)
committerStéphane Nicolet <cassio@free.fr>
Sun, 1 Apr 2018 01:21:45 +0000 (03:21 +0200)
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.

src/evaluate.cpp
src/search.cpp
src/timeman.h

index f4811ae..3e0533b 100644 (file)
@@ -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.
index f078336..43193f1 100644 (file)
@@ -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;
index 4e58ceb..fad898e 100644 (file)
@@ -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