X-Git-Url: https://git.sesse.net/?a=blobdiff_plain;f=src%2Fsearch.cpp;h=792c97296421d56728362257343414fe2e012f85;hb=9083050be692b2d9a4f281e78b967755e00cfc39;hp=32a6ae611d57576a8ebff679f694c9ddde88a0ef;hpb=061f98a9e3ae439fac13b4b2dda4be47977994b1;p=stockfish diff --git a/src/search.cpp b/src/search.cpp index 32a6ae61..792c9729 100644 --- a/src/search.cpp +++ b/src/search.cpp @@ -1,6 +1,6 @@ /* Stockfish, a UCI chess playing engine derived from Glaurung 2.1 - Copyright (C) 2004-2021 The Stockfish developers (see AUTHORS file) + Copyright (C) 2004-2022 The Stockfish developers (see AUTHORS file) Stockfish is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by @@ -69,9 +69,9 @@ namespace { // Reductions lookup table, initialized at startup int Reductions[MAX_MOVES]; // [depth or moveNumber] - Depth reduction(bool i, Depth d, int mn, bool rangeReduction, Value delta, Value rootDelta) { + Depth reduction(bool i, Depth d, int mn, Value delta, Value rootDelta) { int r = Reductions[d] * Reductions[mn]; - return (r + 1358 - int(delta) * 1024 / int(rootDelta)) / 1024 + (!i && r > 904) + rangeReduction; + return (r + 1358 - int(delta) * 1024 / int(rootDelta)) / 1024 + (!i && r > 904); } constexpr int futility_move_count(bool improving, Depth depth) { @@ -88,30 +88,6 @@ 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. If we have an uci_elo then // we convert it to a suitable fractional skill level using anchoring to CCRL Elo // (goldfish 1.13 = 2000) and a fit through Ordo derived Elo for match (TC 60+0.6) @@ -327,15 +303,11 @@ void Thread::search() { multiPV = std::min(multiPV, rootMoves.size()); - doubleExtensionAverage[WHITE].set(0, 100); // initialize the running average at 0% - doubleExtensionAverage[BLACK].set(0, 100); // initialize the running average at 0% + complexityAverage.set(232, 1); - nodesLastExplosive = nodes; - nodesLastNormal = nodes; - state = EXPLOSION_NONE; - trend = SCORE_ZERO; - optimism[ us] = Value(25); - optimism[~us] = -optimism[us]; + trend = SCORE_ZERO; + optimism[ us] = Value(25); + optimism[~us] = -optimism[us]; int searchAgainCounter = 0; @@ -496,7 +468,10 @@ void Thread::search() { double reduction = (1.47 + mainThread->previousTimeReduction) / (2.32 * timeReduction); double bestMoveInstability = 1.073 + std::max(1.0, 2.25 - 9.9 / rootDepth) * totBestMoveChanges / Threads.size(); - double totalTime = Time.optimum() * fallingEval * reduction * bestMoveInstability; + int complexity = mainThread->complexityAverage.value(); + double complexPosition = std::clamp(1.0 + (complexity - 232) / 1750.0, 0.5, 1.5); + + double totalTime = Time.optimum() * fallingEval * reduction * bestMoveInstability * complexPosition; // Cap used time in case of a single legal move for a better viewer experience in tournaments // yielding correct scores and sufficiently fast moves. @@ -544,14 +519,6 @@ 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; @@ -589,9 +556,10 @@ namespace { bool givesCheck, improving, didLMR, priorCapture; bool captureOrPromotion, doFullDepthSearch, moveCountPruning, ttCapture; Piece movedPiece; - int moveCount, captureCount, quietCount, bestMoveCount, improvement; + int moveCount, captureCount, quietCount, bestMoveCount, improvement, complexity; // Step 1. Initialize node + Thread* thisThread = pos.this_thread(); ss->inCheck = pos.checkers(); priorCapture = pos.captured_piece(); Color us = pos.side_to_move(); @@ -639,9 +607,6 @@ namespace { 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 @@ -760,6 +725,7 @@ namespace { ss->staticEval = eval = VALUE_NONE; improving = false; improvement = 0; + complexity = 0; goto moves_loop; } else if (ss->ttHit) @@ -803,6 +769,9 @@ namespace { : 200; improving = improvement > 0; + complexity = abs(ss->staticEval - (us == WHITE ? eg_value(pos.psq_score()) : -eg_value(pos.psq_score()))); + + thisThread->complexityAverage.update(complexity); // Step 7. Futility pruning: child node (~25 Elo). // The depth condition is important for mate finding. @@ -818,7 +787,7 @@ namespace { && (ss-1)->statScore < 23767 && eval >= beta && eval >= ss->staticEval - && ss->staticEval >= beta - 20 * depth - improvement / 15 + 204 + && ss->staticEval >= beta - 20 * depth - improvement / 15 + 204 + complexity / 25 && !excludedMove && pos.non_pawn_material(us) && (ss->ply >= thisThread->nmpMinPly || us != thisThread->nmpColor)) @@ -938,8 +907,6 @@ namespace { moves_loop: // When in check, search starts here - int rangeReduction = 0; - // Step 11. A small Probcut idea, when we are in check (~0 Elo) probCutBeta = beta + 409; if ( ss->inCheck @@ -1026,7 +993,7 @@ moves_loop: // When in check, search starts here moveCountPruning = moveCount >= futility_move_count(improving, depth); // Reduced depth of the next LMR search - int lmrDepth = std::max(newDepth - reduction(improving, depth, moveCount, rangeReduction > 2, delta, thisThread->rootDelta), 0); + int lmrDepth = std::max(newDepth - reduction(improving, depth, moveCount, delta, thisThread->rootDelta), 0); if ( captureOrPromotion || givesCheck) @@ -1042,7 +1009,7 @@ moves_loop: // When in check, search starts here continue; // SEE based pruning (~9 Elo) - if (!pos.see_ge(move, Value(-218) * depth)) + if (!pos.see_ge(move, Value(-217) * depth)) continue; } else @@ -1053,7 +1020,7 @@ moves_loop: // When in check, search starts here // Continuation history based pruning (~2 Elo) if ( lmrDepth < 5 - && history < -3000 * depth + 3000) + && history < -3875 * (depth - 1)) continue; history += thisThread->mainHistory[us][from_to(move)]; @@ -1061,7 +1028,7 @@ moves_loop: // When in check, search starts here // Futility pruning: parent node (~9 Elo) if ( !ss->inCheck && lmrDepth < 8 - && ss->staticEval + 142 + 139 * lmrDepth + history / 64 <= alpha) + && ss->staticEval + 138 + 137 * lmrDepth + history / 64 <= alpha) continue; // Prune moves with negative SEE (~3 Elo) @@ -1071,64 +1038,67 @@ moves_loop: // When in check, search starts here } // Step 14. Extensions (~66 Elo) - - // Singular extension search (~58 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 - // result is lower than ttValue minus a margin, then we will extend the ttMove. - if ( !rootNode - && depth >= 6 + 2 * (PvNode && tte->is_pv()) - && move == ttMove - && !excludedMove // Avoid recursive singular search - /* && ttValue != VALUE_NONE Already implicit in the next condition */ - && abs(ttValue) < VALUE_KNOWN_WIN - && (tte->bound() & BOUND_LOWER) - && tte->depth() >= depth - 3) + // We take care to not overdo to avoid search getting stuck. + if (ss->ply < thisThread->rootDepth * 2) { - Value singularBeta = ttValue - 3 * depth; - Depth singularDepth = (depth - 1) / 2; + // Singular extension search (~58 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 + // result is lower than ttValue minus a margin, then we will extend the ttMove. + if ( !rootNode + && depth >= 6 + 2 * (PvNode && tte->is_pv()) + && move == ttMove + && !excludedMove // Avoid recursive singular search + /* && ttValue != VALUE_NONE Already implicit in the next condition */ + && abs(ttValue) < VALUE_KNOWN_WIN + && (tte->bound() & BOUND_LOWER) + && tte->depth() >= depth - 3) + { + Value singularBeta = ttValue - 3 * depth; + Depth singularDepth = (depth - 1) / 2; - ss->excludedMove = move; - value = search(pos, ss, singularBeta - 1, singularBeta, singularDepth, cutNode); - ss->excludedMove = MOVE_NONE; + ss->excludedMove = move; + value = search(pos, ss, singularBeta - 1, singularBeta, singularDepth, cutNode); + ss->excludedMove = MOVE_NONE; - if (value < singularBeta) - { - extension = 1; + if (value < singularBeta) + { + extension = 1; - // Avoid search explosion by limiting the number of double extensions - if ( !PvNode - && value < singularBeta - 75 - && ss->doubleExtensions <= 6) - extension = 2; - } + // Avoid search explosion by limiting the number of double extensions + if ( !PvNode + && value < singularBeta - 75 + && ss->doubleExtensions <= 6) + extension = 2; + } - // Multi-cut pruning - // Our ttMove is assumed to fail high, and now we failed high also on a reduced - // search without the ttMove. So we assume this expected Cut-node is not singular, - // that multiple moves fail high, and we can prune the whole subtree by returning - // a soft bound. - else if (singularBeta >= beta) - return singularBeta; - - // If the eval of ttMove is greater than beta, we reduce it (negative extension) - else if (ttValue >= beta) - extension = -2; - } + // Multi-cut pruning + // Our ttMove is assumed to fail high, and now we failed high also on a reduced + // search without the ttMove. So we assume this expected Cut-node is not singular, + // that multiple moves fail high, and we can prune the whole subtree by returning + // a soft bound. + else if (singularBeta >= beta) + return singularBeta; + + // If the eval of ttMove is greater than beta, we reduce it (negative extension) + else if (ttValue >= beta) + extension = -2; + } - // Check extensions (~1 Elo) - else if ( givesCheck - && depth > 6 - && abs(ss->staticEval) > 100) - extension = 1; + // Check extensions (~1 Elo) + else if ( givesCheck + && depth > 6 + && abs(ss->staticEval) > 100) + extension = 1; - // Quiet ttMove extensions (~0 Elo) - else if ( PvNode - && move == ttMove - && move == ss->killers[0] - && (*contHist[0])[movedPiece][to_sq(move)] >= 10000) - extension = 1; + // Quiet ttMove extensions (~0 Elo) + else if ( PvNode + && move == ttMove + && move == ss->killers[0] + && (*contHist[0])[movedPiece][to_sq(move)] >= 10000) + extension = 1; + } // Add extension to new depth newDepth += extension; @@ -1159,7 +1129,7 @@ moves_loop: // When in check, search starts here || !captureOrPromotion || (cutNode && (ss-1)->moveCount > 1))) { - Depth r = reduction(improving, depth, moveCount, rangeReduction > 2, delta, thisThread->rootDelta); + Depth r = reduction(improving, depth, moveCount, delta, thisThread->rootDelta); // Decrease reduction at some PvNodes (~2 Elo) if ( PvNode @@ -1206,10 +1176,6 @@ moves_loop: // When in check, search starts here value = -search(pos, ss+1, -(alpha+1), -alpha, d, true); - // Range reductions (~3 Elo) - if (ss->staticEval - value < 30 && depth > 7) - rangeReduction++; - // If the son is reduced and fails high it will be re-searched at full depth doFullDepthSearch = value > alpha && d < newDepth; doDeeperSearch = value > (alpha + 62 + 20 * (newDepth - d));