From 114ddb789bed2d74d6a786f5da6c9ce63d44de27 Mon Sep 17 00:00:00 2001 From: Joost VandeVondele Date: Fri, 10 Jan 2020 03:02:09 +0100 Subject: [PATCH 1/1] Update Elo estimates for terms in search This updates estimates from 1.5 year ago, and adds missing terms. All estimates from tests run on fishtest at 10+0.1 (STC), 20000 games, error bars +- 3 Elo, see the original message in the pull request for the full list of tests. Noteworthy changes are step 7 (futility pruning) going from ~30 to ~50 Elo and step 13 (pruning at shallow depth) going from ~170 to ~200 Elo. Full list of tests: https://github.com/official-stockfish/Stockfish/pull/2401 @Rocky640 made the suggestion to look at time control dependence of these terms. I picked two large terms (early futility pruning and singular extension), so with small relative error. It turns out it is actually quite interesting (see figure 1). Contrary to my expectation, the Elo gain for early futility pruning is pretty time control sensitive, while singular extension gain is not. Figure 1: TC dependence of two search terms ![elo_search_tc]( http://cassio.free.fr/divers/elo_search_tc.png ) Going back to the old measurement of futility pruning (30 Elo vs today 50 Elo), the code is actually identical but the margins have changed. It seems like a nice example of how connected terms in search really are, i.e. the value of early futility pruning increased significantly due to changes elsewhere in search. No functional change. --- src/search.cpp | 32 ++++++++++++++++---------------- 1 file changed, 16 insertions(+), 16 deletions(-) diff --git a/src/search.cpp b/src/search.cpp index dfc0e5bf..6146bdf6 100644 --- a/src/search.cpp +++ b/src/search.cpp @@ -808,7 +808,7 @@ namespace { tte->save(posKey, VALUE_NONE, ttPv, BOUND_NONE, DEPTH_NONE, MOVE_NONE, eval); } - // Step 7. Razoring (~2 Elo) + // Step 7. Razoring (~1 Elo) if ( !rootNode // The required rootNode PV handling is not available in qsearch && depth < 2 && eval <= alpha - RazorMargin) @@ -817,7 +817,7 @@ namespace { improving = (ss-2)->staticEval == VALUE_NONE ? (ss->staticEval >= (ss-4)->staticEval || (ss-4)->staticEval == VALUE_NONE) : ss->staticEval >= (ss-2)->staticEval; - // Step 8. Futility pruning: child node (~30 Elo) + // Step 8. Futility pruning: child node (~50 Elo) if ( !PvNode && depth < 6 && eval - futility_margin(depth, improving) >= beta @@ -917,7 +917,7 @@ namespace { } } - // Step 11. Internal iterative deepening (~2 Elo) + // Step 11. Internal iterative deepening (~1 Elo) if (depth >= 7 && !ttMove) { search(pos, ss, alpha, beta, depth - 7, cutNode); @@ -982,7 +982,7 @@ moves_loop: // When in check, search starts from here // Calculate new depth for this move newDepth = depth - 1; - // Step 13. Pruning at shallow depth (~170 Elo) + // Step 13. Pruning at shallow depth (~200 Elo) if ( !rootNode && pos.non_pawn_material(us) && bestValue > VALUE_MATED_IN_MAX_PLY) @@ -1002,7 +1002,7 @@ moves_loop: // When in check, search starts from here && (*contHist[1])[movedPiece][to_sq(move)] < CounterMovePruneThreshold) continue; - // Futility pruning: parent node (~2 Elo) + // Futility pruning: parent node (~5 Elo) if ( lmrDepth < 6 && !inCheck && ss->staticEval + 255 + 182 * lmrDepth <= alpha @@ -1012,17 +1012,17 @@ moves_loop: // When in check, search starts from here + (*contHist[3])[movedPiece][to_sq(move)] < 30000) continue; - // Prune moves with negative SEE (~10 Elo) + // Prune moves with negative SEE (~20 Elo) if (!pos.see_ge(move, Value(-(32 - std::min(lmrDepth, 18)) * lmrDepth * lmrDepth))) continue; } - else if (!pos.see_ge(move, Value(-194) * depth)) // (~20 Elo) + else if (!pos.see_ge(move, Value(-194) * depth)) // (~25 Elo) continue; } - // Step 14. Extensions (~70 Elo) + // Step 14. Extensions (~75 Elo) - // Singular extension search (~60 Elo). If all moves but one fail low on a + // Singular extension search (~70 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 all the other moves but the ttMove and if the @@ -1101,7 +1101,7 @@ moves_loop: // When in check, search starts from here // Step 15. Make the move pos.do_move(move, st, givesCheck); - // Step 16. Reduced depth search (LMR). If the move fails high it will be + // Step 16. Reduced depth search (LMR, ~200 Elo). If the move fails high it will be // re-searched at full depth. if ( depth >= 3 && moveCount > 1 + 2 * rootNode @@ -1122,31 +1122,31 @@ moves_loop: // When in check, search starts from here if (th.marked()) r++; - // Decrease reduction if position is or has been on the PV + // Decrease reduction if position is or has been on the PV (~10 Elo) if (ttPv) r -= 2; - // Decrease reduction if opponent's move count is high (~10 Elo) + // Decrease reduction if opponent's move count is high (~5 Elo) if ((ss-1)->moveCount > 14) r--; - // Decrease reduction if ttMove has been singularly extended + // Decrease reduction if ttMove has been singularly extended (~3 Elo) if (singularLMR) r -= 2; if (!captureOrPromotion) { - // Increase reduction if ttMove is a capture (~0 Elo) + // Increase reduction if ttMove is a capture (~5 Elo) if (ttCapture) r++; - // Increase reduction for cut nodes (~5 Elo) + // Increase reduction for cut nodes (~10 Elo) if (cutNode) r += 2; // Decrease reduction for moves that escape a capture. Filter out // castling moves, because they are coded as "king captures rook" and - // hence break make_move(). (~5 Elo) + // hence break make_move(). (~2 Elo) else if ( type_of(move) == NORMAL && !pos.see_ge(reverse_move(move))) r -= 2; -- 2.39.2