X-Git-Url: https://git.sesse.net/?p=stockfish;a=blobdiff_plain;f=src%2Fsearch.cpp;h=6d1a66e5f8688b24e6c5d9f96d7e8fd5c4b2c2c9;hp=8993a4b05fbf3069c8f55e092cfa4d27ee6b8dc5;hb=8152a74ab4f703717fdb493cf9059f89be9a4fba;hpb=93349d0dbd22f063b39e6815c02835a4748fffbc diff --git a/src/search.cpp b/src/search.cpp index 8993a4b0..6d1a66e5 100644 --- a/src/search.cpp +++ b/src/search.cpp @@ -62,9 +62,9 @@ namespace { enum NodeType { NonPV, PV }; // Razor and futility margins - constexpr int RazorMargin = 600; + constexpr int RazorMargin = 661; Value futility_margin(Depth d, bool improving) { - return Value((175 - 50 * improving) * d / ONE_PLY); + return Value((168 - 51 * improving) * d / ONE_PLY); } // Reductions lookup table, initialized at startup @@ -72,7 +72,7 @@ namespace { Depth reduction(bool i, Depth d, int mn) { int r = Reductions[d / ONE_PLY] * Reductions[mn]; - return ((r + 512) / 1024 + (!i && r > 1024)) * ONE_PLY; + return ((r + 520) / 1024 + (!i && r > 999)) * ONE_PLY; } constexpr int futility_move_count(bool improving, int depth) { @@ -82,7 +82,7 @@ namespace { // History and stats update bonus, based on depth int stat_bonus(Depth depth) { int d = depth / ONE_PLY; - return d > 17 ? 0 : 29 * d * d + 138 * d - 134; + return d > 17 ? -8 : 22 * d * d + 151 * d - 140; } // Add a small random component to draw evaluations to avoid 3fold-blindness @@ -191,7 +191,7 @@ namespace { void Search::init() { for (int i = 1; i < MAX_MOVES; ++i) - Reductions[i] = int(22.9 * std::log(i)); + Reductions[i] = int(23.4 * std::log(i)); } @@ -271,13 +271,13 @@ void MainThread::search() { // Check if there are threads with a better score than main thread if ( Options["MultiPV"] == 1 && !Limits.depth - && !Skill(Options["Skill Level"]).enabled() + && !(Skill(Options["Skill Level"]).enabled() || Options["UCI_LimitStrength"]) && rootMoves[0].pv[0] != MOVE_NONE) { std::map votes; Value minScore = this->rootMoves[0].score; - // Find out minimum score and reset votes for moves which can be voted + // Find out minimum score for (Thread* th: Threads) minScore = std::min(minScore, th->rootMoves[0].score); @@ -287,7 +287,14 @@ void MainThread::search() { votes[th->rootMoves[0].pv[0]] += (th->rootMoves[0].score - minScore + 14) * int(th->completedDepth); - if (votes[th->rootMoves[0].pv[0]] > votes[bestThread->rootMoves[0].pv[0]]) + if (bestThread->rootMoves[0].score >= VALUE_MATE_IN_MAX_PLY) + { + // Make sure we pick the shortest mate + if (th->rootMoves[0].score > bestThread->rootMoves[0].score) + bestThread = th; + } + else if ( th->rootMoves[0].score >= VALUE_MATE_IN_MAX_PLY + || votes[th->rootMoves[0].pv[0]] > votes[bestThread->rootMoves[0].pv[0]]) bestThread = th; } } @@ -335,11 +342,18 @@ void Thread::search() { beta = VALUE_INFINITE; multiPV = Options["MultiPV"]; + // Pick integer skill levels, but non-deterministically round up or down // such that the average integer skill corresponds to the input floating point one. + // UCI_Elo is converted 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) results spanning a wide range of k values. PRNG rng(now()); - int intLevel = int(Options["Skill Level"]) + - ((Options["Skill Level"] - int(Options["Skill Level"])) * 1024 > rng.rand() % 1024 ? 1 : 0); + double floatLevel = Options["UCI_LimitStrength"] ? + clamp(std::pow((Options["UCI_Elo"] - 1346.6) / 143.4, 1 / 0.806), 0.0, 20.0) : + double(Options["Skill Level"]); + int intLevel = int(floatLevel) + + ((floatLevel - int(floatLevel)) * 1024 > rng.rand() % 1024 ? 1 : 0); Skill skill(intLevel); // When playing with strength handicap enable MultiPV search that we will @@ -395,15 +409,15 @@ void Thread::search() { selDepth = 0; // Reset aspiration window starting size - if (rootDepth >= 5 * ONE_PLY) + if (rootDepth >= 4 * ONE_PLY) { Value previousScore = rootMoves[pvIdx].previousScore; - delta = Value(20); + delta = Value(23); alpha = std::max(previousScore - delta,-VALUE_INFINITE); beta = std::min(previousScore + delta, VALUE_INFINITE); // Adjust contempt based on root move's previousScore (dynamic contempt) - int dct = ct + 88 * previousScore / (abs(previousScore) + 200); + int dct = ct + 86 * previousScore / (abs(previousScore) + 176); contempt = (us == WHITE ? make_score(dct, dct / 2) : -make_score(dct, dct / 2)); @@ -498,12 +512,12 @@ void Thread::search() { && !Threads.stop && !mainThread->stopOnPonderhit) { - double fallingEval = (314 + 9 * (mainThread->previousScore - bestValue)) / 581.0; + double fallingEval = (354 + 10 * (mainThread->previousScore - bestValue)) / 692.0; fallingEval = clamp(fallingEval, 0.5, 1.5); // If the bestMove is stable over several iterations, reduce time accordingly - timeReduction = lastBestMoveDepth + 10 * ONE_PLY < completedDepth ? 1.95 : 1.0; - double reduction = std::pow(mainThread->previousTimeReduction, 0.528) / timeReduction; + timeReduction = lastBestMoveDepth + 9 * ONE_PLY < completedDepth ? 1.97 : 0.98; + double reduction = (1.36 + mainThread->previousTimeReduction) / (2.29 * timeReduction); // Use part of the gained time from a previous stable move for the current move for (Thread* th : Threads) @@ -578,7 +592,7 @@ namespace { Move ttMove, move, excludedMove, bestMove; Depth extension, newDepth; Value bestValue, value, ttValue, eval, maxValue; - bool ttHit, ttPv, inCheck, givesCheck, improving; + bool ttHit, ttPv, inCheck, givesCheck, improving, doLMR; bool captureOrPromotion, doFullDepthSearch, moveCountPruning, ttCapture; Piece movedPiece; int moveCount, captureCount, quietCount, singularLMR; @@ -739,7 +753,7 @@ namespace { } else if (ttHit) { - // Never assume anything on values stored in TT + // Never assume anything about values stored in TT ss->staticEval = eval = tte->eval(); if (eval == VALUE_NONE) ss->staticEval = eval = evaluate(pos); @@ -782,9 +796,9 @@ namespace { // Step 9. Null move search with verification search (~40 Elo) if ( !PvNode && (ss-1)->currentMove != MOVE_NULL - && (ss-1)->statScore < 23200 + && (ss-1)->statScore < 22661 && eval >= beta - && ss->staticEval >= beta - 36 * depth / ONE_PLY + 225 + && ss->staticEval >= beta - 33 * depth / ONE_PLY + 299 && !excludedMove && pos.non_pawn_material(us) && (ss->ply >= thisThread->nmpMinPly || us != thisThread->nmpColor)) @@ -792,7 +806,7 @@ namespace { assert(eval - beta >= 0); // Null move dynamic reduction based on depth and value - Depth R = ((823 + 67 * depth / ONE_PLY) / 256 + std::min(int(eval - beta) / 200, 3)) * ONE_PLY; + Depth R = ((835 + 70 * depth / ONE_PLY) / 256 + std::min(int(eval - beta) / 185, 3)) * ONE_PLY; ss->currentMove = MOVE_NULL; ss->continuationHistory = &thisThread->continuationHistory[NO_PIECE][0]; @@ -809,7 +823,7 @@ namespace { if (nullValue >= VALUE_MATE_IN_MAX_PLY) nullValue = beta; - if (thisThread->nmpMinPly || (abs(beta) < VALUE_KNOWN_WIN && depth < 12 * ONE_PLY)) + if (thisThread->nmpMinPly || (abs(beta) < VALUE_KNOWN_WIN && depth < 13 * ONE_PLY)) return nullValue; assert(!thisThread->nmpMinPly); // Recursive verification is not allowed @@ -835,7 +849,7 @@ namespace { && depth >= 5 * ONE_PLY && abs(beta) < VALUE_MATE_IN_MAX_PLY) { - Value raisedBeta = std::min(beta + 216 - 48 * improving, VALUE_INFINITE); + Value raisedBeta = std::min(beta + 191 - 46 * improving, VALUE_INFINITE); MovePicker mp(pos, ttMove, raisedBeta - ss->staticEval, &thisThread->captureHistory); int probCutCount = 0; @@ -867,7 +881,7 @@ namespace { } // Step 11. Internal iterative deepening (~2 Elo) - if (depth >= 8 * ONE_PLY && !ttMove) + if (depth >= 7 * ONE_PLY && !ttMove) { search(pos, ss, alpha, beta, depth - 7 * ONE_PLY, cutNode); @@ -941,7 +955,7 @@ moves_loop: // When in check, search starts from here // 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 ( depth >= 8 * ONE_PLY + if ( depth >= 6 * ONE_PLY && move == ttMove && !rootNode && !excludedMove // Avoid recursive singular search @@ -962,7 +976,7 @@ moves_loop: // When in check, search starts from here extension = ONE_PLY; singularLMR++; - if (value < singularBeta - std::min(3 * depth / ONE_PLY, 39)) + if (value < singularBeta - std::min(4 * depth / ONE_PLY, 36)) singularLMR++; } @@ -978,7 +992,7 @@ moves_loop: // When in check, search starts from here // Check extension (~2 Elo) else if ( givesCheck - && (pos.blockers_for_king(~us) & from_sq(move) || pos.see_ge(move))) + && (pos.is_discovery_check_on_king(~us, move) || pos.see_ge(move))) extension = ONE_PLY; // Castling extension @@ -1013,7 +1027,7 @@ moves_loop: // When in check, search starts from here && !givesCheck && (!pos.advanced_pawn_push(move) || pos.non_pawn_material(~us) > BishopValueMg)) { - // Move count based pruning (~30 Elo) + // Move count based pruning if (moveCountPruning) continue; @@ -1022,23 +1036,23 @@ moves_loop: // When in check, search starts from here lmrDepth /= ONE_PLY; // Countermoves based pruning (~20 Elo) - if ( lmrDepth < 3 + ((ss-1)->statScore > 0 || (ss-1)->moveCount == 1) + if ( lmrDepth < 4 + ((ss-1)->statScore > 0 || (ss-1)->moveCount == 1) && (*contHist[0])[movedPiece][to_sq(move)] < CounterMovePruneThreshold && (*contHist[1])[movedPiece][to_sq(move)] < CounterMovePruneThreshold) continue; // Futility pruning: parent node (~2 Elo) - if ( lmrDepth < 7 + if ( lmrDepth < 6 && !inCheck - && ss->staticEval + 256 + 200 * lmrDepth <= alpha) + && ss->staticEval + 250 + 211 * lmrDepth <= alpha) continue; // Prune moves with negative SEE (~10 Elo) - if (!pos.see_ge(move, Value(-29 * lmrDepth * lmrDepth))) + if (!pos.see_ge(move, Value(-(31 - std::min(lmrDepth, 18)) * lmrDepth * lmrDepth))) continue; } - else if ((!givesCheck || !extension) - && !pos.see_ge(move, -PawnValueEg * (depth / ONE_PLY))) // (~20 Elo) + else if ( (!givesCheck || !extension) + && !pos.see_ge(move, Value(-199) * (depth / ONE_PLY))) // (~20 Elo) continue; } @@ -1105,32 +1119,52 @@ moves_loop: // When in check, search starts from here + (*contHist[0])[movedPiece][to_sq(move)] + (*contHist[1])[movedPiece][to_sq(move)] + (*contHist[3])[movedPiece][to_sq(move)] - - 4000; + - 4729; + + // Reset statScore to zero if negative and most stats shows >= 0 + if ( ss->statScore < 0 + && (*contHist[0])[movedPiece][to_sq(move)] >= 0 + && (*contHist[1])[movedPiece][to_sq(move)] >= 0 + && thisThread->mainHistory[us][from_to(move)] >= 0) + ss->statScore = 0; // Decrease/increase reduction by comparing opponent's stat score (~10 Elo) - if (ss->statScore >= 0 && (ss-1)->statScore < 0) + if (ss->statScore >= -99 && (ss-1)->statScore < -116) r -= ONE_PLY; - else if ((ss-1)->statScore >= 0 && ss->statScore < 0) + else if ((ss-1)->statScore >= -117 && ss->statScore < -144) r += ONE_PLY; // Decrease/increase reduction for moves with a good/bad history (~30 Elo) - r -= ss->statScore / 20000 * ONE_PLY; + r -= ss->statScore / 16384 * ONE_PLY; } Depth d = clamp(newDepth - r, ONE_PLY, newDepth); value = -search(pos, ss+1, -(alpha+1), -alpha, d, true); - doFullDepthSearch = (value > alpha && d != newDepth); + doFullDepthSearch = (value > alpha && d != newDepth), doLMR = true; } else - doFullDepthSearch = !PvNode || moveCount > 1; + doFullDepthSearch = !PvNode || moveCount > 1, doLMR = false; // Step 17. Full depth search when LMR is skipped or fails high if (doFullDepthSearch) + { value = -search(pos, ss+1, -(alpha+1), -alpha, newDepth, !cutNode); + if (doLMR && !captureOrPromotion) + { + int bonus = value > alpha ? stat_bonus(newDepth) + : -stat_bonus(newDepth); + + if (move == ss->killers[0]) + bonus += bonus / 4; + + update_continuation_histories(ss, movedPiece, to_sq(move), bonus); + } + } + // For PV nodes only, do a full PV search on the first move or after a fail // high (in the latter case search only if value < beta), otherwise let the // parent node fail low with value <= alpha and try another move. @@ -1341,7 +1375,7 @@ moves_loop: // When in check, search starts from here { if (ttHit) { - // Never assume anything on values stored in TT + // Never assume anything about values stored in TT if ((ss->staticEval = bestValue = tte->eval()) == VALUE_NONE) ss->staticEval = bestValue = evaluate(pos); @@ -1368,7 +1402,7 @@ moves_loop: // When in check, search starts from here if (PvNode && bestValue > alpha) alpha = bestValue; - futilityBase = bestValue + 128; + futilityBase = bestValue + 153; } const PieceToHistory* contHist[] = { (ss-1)->continuationHistory, (ss-2)->continuationHistory,