From e408fd7b10503a9114962cb5972abd9957bc67c2 Mon Sep 17 00:00:00 2001 From: Joost VandeVondele Date: Sun, 1 Apr 2018 03:13:29 +0200 Subject: [PATCH] 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. --- src/evaluate.cpp | 4 ++-- src/search.cpp | 28 ++++++++++++++-------------- src/timeman.h | 2 +- 3 files changed, 17 insertions(+), 17 deletions(-) diff --git a/src/evaluate.cpp b/src/evaluate.cpp index f4811aea..3e0533b2 100644 --- 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 f0783363..43193f10 100644 --- 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(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 4e58cebb..fad898e2 100644 --- 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 -- 2.39.2