X-Git-Url: https://git.sesse.net/?p=stockfish;a=blobdiff_plain;f=src%2Fsearch.cpp;h=c4ed73372df2040ffee3bc7093e61e9301011ecd;hp=e7e33edef8f7acd4b1b41e9861e7a78e36158c03;hb=282644f1413db0ccb58e2e1793d5007c58ff8ce2;hpb=b37054c310876850f6ff65b19f6cdb5f941c57dc diff --git a/src/search.cpp b/src/search.cpp index e7e33ede..c4ed7337 100644 --- a/src/search.cpp +++ b/src/search.cpp @@ -112,14 +112,22 @@ namespace { return thisThread->state; } - // Skill structure is used to implement strength limit + // 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) + // results spanning a wide range of k values. struct Skill { - explicit Skill(int l) : level(l) {} - bool enabled() const { return level < 20; } - bool time_to_pick(Depth depth) const { return depth == 1 + level; } + Skill(int skill_level, int uci_elo) { + if (uci_elo) + level = std::clamp(std::pow((uci_elo - 1346.6) / 143.4, 1 / 0.806), 0.0, 20.0); + else + level = double(skill_level); + } + bool enabled() const { return level < 20.0; } + bool time_to_pick(Depth depth) const { return depth == 1 + int(level); } Move pick_best(size_t multiPV); - int level; + double level; Move best = MOVE_NONE; }; @@ -243,10 +251,11 @@ void MainThread::search() { Time.availableNodes += Limits.inc[us] - Threads.nodes_searched(); Thread* bestThread = this; + Skill skill = Skill(Options["Skill Level"], Options["UCI_LimitStrength"] ? int(Options["UCI_Elo"]) : 0); if ( int(Options["MultiPV"]) == 1 && !Limits.depth - && !(Skill(Options["Skill Level"]).enabled() || int(Options["UCI_LimitStrength"])) + && !skill.enabled() && rootMoves[0].pv[0] != MOVE_NONE) bestThread = Threads.get_best_thread(); @@ -277,7 +286,7 @@ void Thread::search() { // The latter is needed for statScore and killer initialization. Stack stack[MAX_PLY+10], *ss = stack+7; Move pv[MAX_PLY+1]; - Value bestValue, alpha, beta, delta; + Value alpha, beta, delta; Move lastBestMove = MOVE_NONE; Depth lastBestMoveDepth = 0; MainThread* mainThread = (this == Threads.main() ? Threads.main() : nullptr); @@ -311,19 +320,7 @@ void Thread::search() { std::fill(&lowPlyHistory[MAX_LPH - 2][0], &lowPlyHistory.back().back() + 1, 0); size_t multiPV = size_t(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()); - double floatLevel = Options["UCI_LimitStrength"] ? - std::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); + Skill skill(Options["Skill Level"], Options["UCI_LimitStrength"] ? int(Options["UCI_Elo"]) : 0); // When playing with strength handicap enable MultiPV search that we will // use behind the scenes to retrieve a set of possible moves. @@ -337,8 +334,10 @@ void Thread::search() { nodesLastExplosive = nodes; nodesLastNormal = nodes; - state = EXPLOSION_NONE; - trend = SCORE_ZERO; + state = EXPLOSION_NONE; + trend = SCORE_ZERO; + optimism[ us] = Value(25); + optimism[~us] = -optimism[us]; int searchAgainCounter = 0; @@ -379,16 +378,19 @@ void Thread::search() { // Reset aspiration window starting size if (rootDepth >= 4) { - Value prev = rootMoves[pvIdx].previousScore; - delta = Value(17); + Value prev = rootMoves[pvIdx].averageScore; + delta = Value(17) + int(prev) * prev / 16384; alpha = std::max(prev - delta,-VALUE_INFINITE); beta = std::min(prev + delta, VALUE_INFINITE); - // Adjust trend based on root move's previousScore (dynamic contempt) - int tr = 113 * prev / (abs(prev) + 147); - + // Adjust trend and optimism based on root move's previousScore + int tr = sigmoid(prev, 0, 0, 147, 113, 1); trend = (us == WHITE ? make_score(tr, tr / 2) : -make_score(tr, tr / 2)); + + int opt = sigmoid(prev, 0, 25, 147, 14464, 256); + optimism[ us] = Value(opt); + optimism[~us] = -optimism[us]; } // Start with a small aspiration window and, in the case of a fail @@ -628,6 +630,8 @@ namespace { if (alpha >= beta) return alpha; } + else + thisThread->rootDelta = beta - alpha; assert(0 <= ss->ply && ss->ply < MAX_PLY); @@ -673,7 +677,7 @@ namespace { // At non-PV nodes we check for an early TT cutoff if ( !PvNode && ss->ttHit - && tte->depth() >= depth + && tte->depth() > depth - (thisThread->id() % 2 == 1) && ttValue != VALUE_NONE // Possible in case of TT access race && (ttValue >= beta ? (tte->bound() & BOUND_LOWER) : (tte->bound() & BOUND_UPPER))) @@ -790,14 +794,14 @@ namespace { ss->staticEval = eval = evaluate(pos); // Save static evaluation into transposition table - if(!excludedMove) - tte->save(posKey, VALUE_NONE, ss->ttPv, BOUND_NONE, DEPTH_NONE, MOVE_NONE, eval); + if (!excludedMove) + tte->save(posKey, VALUE_NONE, ss->ttPv, BOUND_NONE, DEPTH_NONE, MOVE_NONE, eval); } // Use static evaluation difference to improve quiet move ordering if (is_ok((ss-1)->currentMove) && !(ss-1)->inCheck && !priorCapture) { - int bonus = std::clamp(-depth * 4 * int((ss-1)->staticEval + ss->staticEval), -1000, 1000); + int bonus = std::clamp(-16 * int((ss-1)->staticEval + ss->staticEval), -2000, 2000); thisThread->mainHistory[~us][from_to((ss-1)->currentMove)] << bonus; } @@ -813,10 +817,10 @@ namespace { // Step 7. Futility pruning: child node (~50 Elo). // The depth condition is important for mate finding. - if ( !PvNode + if ( !ss->ttPv && depth < 9 && eval - futility_margin(depth, improving) >= beta - && eval < VALUE_KNOWN_WIN) // Do not return unproven wins + && eval < 15000) // 50% larger than VALUE_KNOWN_WIN, but smaller than TB wins. return eval; // Step 8. Null move search with verification search (~40 Elo) @@ -825,7 +829,7 @@ namespace { && (ss-1)->statScore < 23767 && eval >= beta && eval >= ss->staticEval - && ss->staticEval >= beta - 20 * depth - improvement / 15 + 168 * ss->ttPv + 177 + && ss->staticEval >= beta - 20 * depth - improvement / 15 + 204 && !excludedMove && pos.non_pawn_material(us) && (ss->ply >= thisThread->nmpMinPly || us != thisThread->nmpColor)) @@ -1050,17 +1054,21 @@ moves_loop: // When in check, search starts here } else { + int history = (*contHist[0])[movedPiece][to_sq(move)] + + (*contHist[1])[movedPiece][to_sq(move)] + + (*contHist[3])[movedPiece][to_sq(move)]; + // Continuation history based pruning (~20 Elo) - if (lmrDepth < 5 - && (*contHist[0])[movedPiece][to_sq(move)] - + (*contHist[1])[movedPiece][to_sq(move)] - + (*contHist[3])[movedPiece][to_sq(move)] < -3000 * depth + 3000) + if ( lmrDepth < 5 + && history < -3000 * depth + 3000) continue; + history += thisThread->mainHistory[us][from_to(move)]; + // Futility pruning: parent node (~5 Elo) if ( !ss->inCheck && lmrDepth < 8 - && ss->staticEval + 172 + 145 * lmrDepth <= alpha) + && ss->staticEval + 142 + 139 * lmrDepth + history / 64 <= alpha) continue; // Prune moves with negative SEE (~20 Elo) @@ -1159,16 +1167,16 @@ moves_loop: // When in check, search starts here // cases where we extend a son if it has good chances to be "interesting". if ( depth >= 3 && moveCount > 1 + 2 * rootNode - && ( !captureOrPromotion - || (cutNode && (ss-1)->moveCount > 1) - || !ss->ttPv) - && (!PvNode || ss->ply > 1 || thisThread->id() % 4 != 3)) + && ( !ss->ttPv + || !captureOrPromotion + || (cutNode && (ss-1)->moveCount > 1))) { Depth r = reduction(improving, depth, moveCount, rangeReduction > 2); - // Decrease reduction if on the PV (~2 Elo) + // Decrease reduction at some PvNodes (~2 Elo) if ( PvNode - && bestMoveCount <= 3) + && bestMoveCount <= 3 + && beta - alpha >= thisThread->rootDelta / 4) r--; // Decrease reduction if position is or has been on the PV @@ -1211,9 +1219,9 @@ moves_loop: // When in check, search starts here // are really negative and movecount is low, we allow this move to be searched // deeper than the first move (this may lead to hidden double extensions). int deeper = r >= -1 ? 0 - : moveCount <= 3 && r <= -3 ? 2 - : moveCount <= 5 ? 1 + : moveCount <= 5 ? 2 : PvNode && depth > 6 ? 1 + : cutNode && moveCount <= 7 ? 1 : 0; Depth d = std::clamp(newDepth - r, 1, newDepth + deeper); @@ -1278,6 +1286,8 @@ moves_loop: // When in check, search starts here RootMove& rm = *std::find(thisThread->rootMoves.begin(), thisThread->rootMoves.end(), move); + rm.averageScore = rm.averageScore != -VALUE_INFINITE ? (2 * value + rm.averageScore) / 3 : value; + // PV move or new best move? if (moveCount == 1 || value > alpha) { @@ -1414,13 +1424,12 @@ moves_loop: // When in check, search starts here Key posKey; Move ttMove, move, bestMove; Depth ttDepth; - Value bestValue, value, ttValue, futilityValue, futilityBase, oldAlpha; + Value bestValue, value, ttValue, futilityValue, futilityBase; bool pvHit, givesCheck, captureOrPromotion; int moveCount; if (PvNode) { - oldAlpha = alpha; // To flag BOUND_EXACT when eval above alpha and no available moves (ss+1)->pv = pv; ss->pv[0] = MOVE_NONE; } @@ -1610,8 +1619,7 @@ moves_loop: // When in check, search starts here // Save gathered info in transposition table tte->save(posKey, value_to_tt(bestValue, ss->ply), pvHit, - bestValue >= beta ? BOUND_LOWER : - PvNode && bestValue > oldAlpha ? BOUND_EXACT : BOUND_UPPER, + bestValue >= beta ? BOUND_LOWER : BOUND_UPPER, ttDepth, bestMove, ss->staticEval); assert(bestValue > -VALUE_INFINITE && bestValue < VALUE_INFINITE); @@ -1754,10 +1762,6 @@ moves_loop: // When in check, search starts here thisThread->mainHistory[us][from_to(move)] << bonus; update_continuation_histories(ss, pos.moved_piece(move), to_sq(move), bonus); - // Penalty for reversed move in case of moved piece not being a pawn - if (type_of(pos.moved_piece(move)) != PAWN) - thisThread->mainHistory[us][from_to(reverse_move(move))] << -bonus; - // Update countermove history if (is_ok((ss-1)->currentMove)) { @@ -1781,8 +1785,8 @@ moves_loop: // When in check, search starts here // RootMoves are already sorted by score in descending order Value topScore = rootMoves[0].score; int delta = std::min(topScore - rootMoves[multiPV - 1].score, PawnValueMg); - int weakness = 120 - 2 * level; int maxScore = -VALUE_INFINITE; + double weakness = 120 - 2 * level; // Choose best move. For each move score we add two terms, both dependent on // weakness. One is deterministic and bigger for weaker levels, and one is @@ -1790,8 +1794,8 @@ moves_loop: // When in check, search starts here for (size_t i = 0; i < multiPV; ++i) { // This is our magic formula - int push = ( weakness * int(topScore - rootMoves[i].score) - + delta * (rng.rand() % weakness)) / 128; + int push = int(( weakness * int(topScore - rootMoves[i].score) + + delta * (rng.rand() % int(weakness))) / 128); if (rootMoves[i].score + push >= maxScore) {