From 73018a03375b4b72ee482eb5a4a2152d7e4f0aac Mon Sep 17 00:00:00 2001 From: =?utf8?q?Ste=CC=81phane=20Nicolet?= Date: Thu, 23 Sep 2021 23:19:06 +0200 Subject: [PATCH] Detect search explosions This patch detects some search explosions (due to double extensions in search.cpp) which can happen in some pathological positions, and takes measures to ensure progress in search even for these pathological situations. While a small number of double extensions can be useful during search (for example to resolve a tactical sequence), a sustained regime of double extensions leads to search explosion and a non-finishing search. See the discussion in https://github.com/official-stockfish/Stockfish/pull/3544 and the issue https://github.com/official-stockfish/Stockfish/issues/3532 . The implemented algorithm is the following: a) at each node during search, store the current depth in the stack. Double extensions are by definition levels of the stack where the depth at ply N is strictly higher than depth at ply N-1. b) during search, calculate for each thread a running average of the number of double extensions in the last 4096 visited nodes. c) if one thread has more than 2% of double extensions for a sustained period of time (6 millions consecutive nodes, or about 4 seconds on my iMac), we decide that this thread is in an explosion state and we calm down this thread by preventing it to do any double extension for the next 6 millions nodes. To calculate the running averages, we also introduced a auxiliary class generalizing the computations of ttHitAverage variable we already had in code. The implementation uses an exponential moving average of period 4096 and resolution 1/1024, and all computations are done with integers for efficiency. ----------- Example where the patch solves a search explosion: ``` ./stockfish ucinewgame position fen 8/Pk6/8/1p6/8/P1K5/8/6B1 w - - 37 130 go infinite ``` This algorithm does not affect search in normal, non-pathological positions. We verified, for instance, that the usual bench is unchanged up to depth 20 at least, and that the node numbers are unchanged for a search of the starting position at depth 32. ------------- See https://github.com/official-stockfish/Stockfish/pull/3714 Bench: 5575265 --- src/misc.h | 27 ++++++++++++++++++ src/search.cpp | 76 +++++++++++++++++++++++++++++++++++++++----------- src/search.h | 1 + src/thread.h | 8 ++++-- src/types.h | 5 ++++ 5 files changed, 99 insertions(+), 18 deletions(-) diff --git a/src/misc.h b/src/misc.h index dae37cd9..7a3369e8 100644 --- a/src/misc.h +++ b/src/misc.h @@ -85,6 +85,33 @@ static inline const union { uint32_t i; char c[4]; } Le = { 0x01020304 }; static inline const bool IsLittleEndian = (Le.c[0] == 4); +// RunningAverage : a class to calculate a running average of a series of values. +// For efficiency, all computations are done with integers. +class RunningAverage { + public: + + // Constructor + RunningAverage() {} + + // Reset the running average to rational value p / q + void set(int64_t p, int64_t q) + { average = p * PERIOD * RESOLUTION / q; } + + // Update average with value v + void update(int64_t v) + { average = RESOLUTION * v + (PERIOD - 1) * average / PERIOD; } + + // Test if average is strictly greater than rational a / b + bool is_greater(int64_t a, int64_t b) + { return b * average > a * PERIOD * RESOLUTION ; } + + private : + static constexpr int64_t PERIOD = 4096; + static constexpr int64_t RESOLUTION = 1024; + int64_t average; +}; + + template class ValueListInserter { public: diff --git a/src/search.cpp b/src/search.cpp index b400b8f8..10a9027b 100644 --- a/src/search.cpp +++ b/src/search.cpp @@ -61,9 +61,6 @@ namespace { // Different node types, used as a template parameter enum NodeType { NonPV, PV, Root }; - constexpr uint64_t TtHitAverageWindow = 4096; - constexpr uint64_t TtHitAverageResolution = 1024; - // Futility margin Value futility_margin(Depth d, bool improving) { return Value(214 * (d - improving)); @@ -91,6 +88,30 @@ namespace { return VALUE_DRAW + Value(2 * (thisThread->nodes & 1) - 1); } + // Check if the current thread is in a search explosion + ExplosionState search_explosion(Thread* thisThread) { + + uint64_t nodesNow = thisThread->nodes; + bool explosive = thisThread->doubleExtensionAverage[WHITE].is_greater(2, 100) + || thisThread->doubleExtensionAverage[BLACK].is_greater(2, 100); + + if (explosive) + thisThread->nodesLastExplosive = nodesNow; + else + thisThread->nodesLastNormal = nodesNow; + + if ( explosive + && thisThread->state == EXPLOSION_NONE + && nodesNow - thisThread->nodesLastNormal > 6000000) + thisThread->state = MUST_CALM_DOWN; + + if ( thisThread->state == MUST_CALM_DOWN + && nodesNow - thisThread->nodesLastExplosive > 6000000) + thisThread->state = EXPLOSION_NONE; + + return thisThread->state; + } + // Skill structure is used to implement strength limit struct Skill { explicit Skill(int l) : level(l) {} @@ -310,8 +331,14 @@ void Thread::search() { multiPV = std::max(multiPV, (size_t)4); multiPV = std::min(multiPV, rootMoves.size()); - ttHitAverage = TtHitAverageWindow * TtHitAverageResolution / 2; + ttHitAverage.set(50, 100); // initialize the running average at 50% + doubleExtensionAverage[WHITE].set(0, 100); // initialize the running average at 0% + doubleExtensionAverage[BLACK].set(0, 100); // initialize the running average at 0% + + nodesLastExplosive = nodes; + nodesLastNormal = nodes; + state = EXPLOSION_NONE; trend = SCORE_ZERO; int searchAgainCounter = 0; @@ -518,6 +545,14 @@ namespace { template Value search(Position& pos, Stack* ss, Value alpha, Value beta, Depth depth, bool cutNode) { + Thread* thisThread = pos.this_thread(); + + // Step 0. Limit search explosion + if ( ss->ply > 10 + && search_explosion(thisThread) == MUST_CALM_DOWN + && depth > (ss-1)->depth) + depth = (ss-1)->depth; + constexpr bool PvNode = nodeType != NonPV; constexpr bool rootNode = nodeType == Root; const Depth maxNextDepth = rootNode ? depth : depth + 1; @@ -554,12 +589,11 @@ namespace { Value bestValue, value, ttValue, eval, maxValue, probCutBeta; bool givesCheck, improving, didLMR, priorCapture; bool captureOrPromotion, doFullDepthSearch, moveCountPruning, - ttCapture, singularQuietLMR; + ttCapture, singularQuietLMR, noLMRExtension; Piece movedPiece; int moveCount, captureCount, quietCount; // Step 1. Initialize node - Thread* thisThread = pos.this_thread(); ss->inCheck = pos.checkers(); priorCapture = pos.captured_piece(); Color us = pos.side_to_move(); @@ -602,8 +636,12 @@ namespace { (ss+1)->excludedMove = bestMove = MOVE_NONE; (ss+2)->killers[0] = (ss+2)->killers[1] = MOVE_NONE; ss->doubleExtensions = (ss-1)->doubleExtensions; + ss->depth = depth; Square prevSq = to_sq((ss-1)->currentMove); + // Update the running average statistics for double extensions + thisThread->doubleExtensionAverage[us].update(ss->depth > (ss-1)->depth); + // Initialize statScore to zero for the grandchildren of the current position. // So statScore is shared between all grandchildren and only the first grandchild // starts with statScore = 0. Later grandchildren start with the last calculated @@ -632,9 +670,8 @@ namespace { && is_ok((ss-1)->currentMove)) thisThread->lowPlyHistory[ss->ply - 1][from_to((ss-1)->currentMove)] << stat_bonus(depth - 5); - // thisThread->ttHitAverage can be used to approximate the running average of ttHit - thisThread->ttHitAverage = (TtHitAverageWindow - 1) * thisThread->ttHitAverage / TtHitAverageWindow - + TtHitAverageResolution * ss->ttHit; + // running average of ttHit + thisThread->ttHitAverage.update(ss->ttHit); // At non-PV nodes we check for an early TT cutoff if ( !PvNode @@ -948,8 +985,7 @@ moves_loop: // When in check, search starts here ss->ply); value = bestValue; - singularQuietLMR = moveCountPruning = false; - bool doubleExtension = false; + singularQuietLMR = moveCountPruning = noLMRExtension = false; // Indicate PvNodes that will probably fail low if the node was searched // at a depth equal or greater than the current depth, and the result of this search was a fail low. @@ -1069,13 +1105,13 @@ moves_loop: // When in check, search starts here extension = 1; singularQuietLMR = !ttCapture; - // Avoid search explosion by limiting the number of double extensions to at most 3 + // Avoid search explosion by limiting the number of double extensions if ( !PvNode && value < singularBeta - 93 && ss->doubleExtensions < 3) { extension = 2; - doubleExtension = true; + noLMRExtension = true; } } @@ -1146,7 +1182,7 @@ moves_loop: // When in check, search starts here r--; // Decrease reduction if the ttHit running average is large (~0 Elo) - if (thisThread->ttHitAverage > 537 * TtHitAverageResolution * TtHitAverageWindow / 1024) + if (thisThread->ttHitAverage.is_greater(537, 1024)) r--; // Decrease reduction if position is or has been on the PV @@ -1187,8 +1223,16 @@ moves_loop: // When in check, search starts here // In general we want to cap the LMR depth search at newDepth. But if // reductions are really negative and movecount is low, we allow this move - // to be searched deeper than the first move in specific cases. - Depth d = std::clamp(newDepth - r, 1, newDepth + (r < -1 && (moveCount <= 5 || (depth > 6 && PvNode)) && !doubleExtension)); + // to be searched deeper than the first move in specific cases (note that + // this may lead to hidden double extensions if newDepth got it own extension + // before). + int deeper = r >= -1 ? 0 + : noLMRExtension ? 0 + : moveCount <= 5 ? 1 + : (depth > 6 && PvNode) ? 1 + : 0; + + Depth d = std::clamp(newDepth - r, 1, newDepth + deeper); value = -search(pos, ss+1, -(alpha+1), -alpha, d, true); diff --git a/src/search.h b/src/search.h index 801baacc..ba9d0677 100644 --- a/src/search.h +++ b/src/search.h @@ -47,6 +47,7 @@ struct Stack { Move excludedMove; Move killers[2]; Value staticEval; + Depth depth; int statScore; int moveCount; bool inCheck; diff --git a/src/thread.h b/src/thread.h index 5bfa2359..2475d2ec 100644 --- a/src/thread.h +++ b/src/thread.h @@ -60,10 +60,14 @@ public: Pawns::Table pawnsTable; Material::Table materialTable; size_t pvIdx, pvLast; - uint64_t ttHitAverage; + RunningAverage ttHitAverage; + RunningAverage doubleExtensionAverage[COLOR_NB]; + uint64_t nodesLastExplosive; + uint64_t nodesLastNormal; + std::atomic nodes, tbHits, bestMoveChanges; int selDepth, nmpMinPly; Color nmpColor; - std::atomic nodes, tbHits, bestMoveChanges; + ExplosionState state; Position rootPos; StateInfo rootState; diff --git a/src/types.h b/src/types.h index 0bd4a1c4..fd643117 100644 --- a/src/types.h +++ b/src/types.h @@ -173,6 +173,11 @@ enum Bound { BOUND_EXACT = BOUND_UPPER | BOUND_LOWER }; +enum ExplosionState { + EXPLOSION_NONE, + MUST_CALM_DOWN +}; + enum Value : int { VALUE_ZERO = 0, VALUE_DRAW = 0, -- 2.39.2