X-Git-Url: https://git.sesse.net/?a=blobdiff_plain;f=src%2Fsearch.cpp;h=5cb9750c3235a72d6c33fc99943c379c85ac4380;hb=08385527dd470ece814ac85013802995a0e7f6ca;hp=f5eeb23b43f5c84cbfb81da457bc00726ac71027;hpb=4101893a28b4d34262ed1fba10f2365e964b6537;p=stockfish diff --git a/src/search.cpp b/src/search.cpp index f5eeb23b..5cb9750c 100644 --- a/src/search.cpp +++ b/src/search.cpp @@ -81,7 +81,7 @@ namespace { // History and stats update bonus, based on depth int stat_bonus(Depth d) { - return std::min((11 * d + 284) * d - 363 , 1650); + return std::min(350 * d - 400, 1650); } // Add a small random component to draw evaluations to avoid 3-fold blindness @@ -96,7 +96,10 @@ namespace { struct Skill { 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); + { + double e = double(uci_elo - 1320) / (3190 - 1320); + level = std::clamp((((37.2473 * e - 40.8525) * e + 22.2943) * e - 0.311438), 0.0, 19.0); + } else level = double(skill_level); } @@ -239,9 +242,6 @@ void MainThread::search() { bestPreviousScore = bestThread->rootMoves[0].score; bestPreviousAverageScore = bestThread->rootMoves[0].averageScore; - for (Thread* th : Threads) - th->previousDepth = bestThread->completedDepth; - // Send again PV info if we have a new best thread if (bestThread != this) sync_cout << UCI::pv(bestThread->rootPos, bestThread->completedDepth) << sync_endl; @@ -522,7 +522,6 @@ namespace { constexpr bool PvNode = nodeType != NonPV; constexpr bool rootNode = nodeType == Root; - const Depth maxNextDepth = rootNode ? depth : depth + 1; // Check if we have an upcoming move which draws by repetition, or // if the opponent had an alternative move earlier to this position. @@ -616,22 +615,24 @@ namespace { if (!rootNode) (ss+2)->statScore = 0; - // Step 4. Transposition table lookup. We don't want the score of a partial - // search to overwrite a previous full search TT value, so we use a different - // position key in case of an excluded move. + // Step 4. Transposition table lookup. excludedMove = ss->excludedMove; - posKey = excludedMove == MOVE_NONE ? pos.key() : pos.key() ^ make_key(excludedMove); + posKey = pos.key(); tte = TT.probe(posKey, ss->ttHit); ttValue = ss->ttHit ? value_from_tt(tte->value(), ss->ply, pos.rule50_count()) : VALUE_NONE; ttMove = rootNode ? thisThread->rootMoves[thisThread->pvIdx].pv[0] : ss->ttHit ? tte->move() : MOVE_NONE; ttCapture = ttMove && pos.capture(ttMove); + + // At this point, if excluded, skip straight to step 6, static eval. However, + // to save indentation, we list the condition in all code between here and there. if (!excludedMove) ss->ttPv = PvNode || (ss->ttHit && tte->is_pv()); // At non-PV nodes we check for an early TT cutoff if ( !PvNode && ss->ttHit + && !excludedMove && tte->depth() > depth - (tte->bound() == BOUND_EXACT) && ttValue != VALUE_NONE // Possible in case of TT access race && (tte->bound() & (ttValue >= beta ? BOUND_LOWER : BOUND_UPPER))) @@ -665,7 +666,7 @@ namespace { } // Step 5. Tablebases probe - if (!rootNode && TB::Cardinality) + if (!rootNode && !excludedMove && TB::Cardinality) { int piecesCount = pos.count(); @@ -728,6 +729,12 @@ namespace { complexity = 0; goto moves_loop; } + else if (excludedMove) { + // Providing the hint that this node's accumulator will be used often brings significant Elo gain (13 elo) + Eval::NNUE::hint_common_parent_position(pos); + eval = ss->staticEval; + complexity = abs(ss->staticEval - pos.psq_eg_stm()); + } else if (ss->ttHit) { // Never assume anything about values stored in TT @@ -745,12 +752,9 @@ namespace { else { ss->staticEval = eval = evaluate(pos, &complexity); - // Save static evaluation into transposition table - if (!excludedMove) - tte->save(posKey, VALUE_NONE, ss->ttPv, BOUND_NONE, DEPTH_NONE, MOVE_NONE, eval); + tte->save(posKey, VALUE_NONE, ss->ttPv, BOUND_NONE, DEPTH_NONE, MOVE_NONE, eval); } - thisThread->complexityAverage.update(complexity); // Use static evaluation difference to improve quiet move ordering (~4 Elo) @@ -983,6 +987,8 @@ moves_loop: // When in check, search starts here Value delta = beta - alpha; + Depth r = reduction(improving, depth, moveCount, delta, thisThread->rootDelta); + // Step 14. Pruning at shallow depth (~120 Elo). Depth conditions are important for mate finding. if ( !rootNode && pos.non_pawn_material(us) @@ -992,7 +998,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, delta, thisThread->rootDelta), 0); + int lmrDepth = std::max(newDepth - r, 0); if ( capture || givesCheck) @@ -1023,12 +1029,17 @@ moves_loop: // When in check, search starts here history += 2 * thisThread->mainHistory[us][from_to(move)]; + lmrDepth += history / 7208; + lmrDepth = std::max(lmrDepth, -2); + // Futility pruning: parent node (~13 Elo) if ( !ss->inCheck && lmrDepth < 13 - && ss->staticEval + 103 + 136 * lmrDepth + history / 53 <= alpha) + && ss->staticEval + 103 + 136 * lmrDepth <= alpha) continue; + lmrDepth = std::max(lmrDepth, 0); + // Prune moves with negative SEE (~4 Elo) if (!pos.see_ge(move, Value(-25 * lmrDepth * lmrDepth - 16 * lmrDepth))) continue; @@ -1045,7 +1056,7 @@ moves_loop: // When in check, search starts here // 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 >= 4 - (thisThread->previousDepth > 24) + 2 * (PvNode && tte->is_pv()) + && depth >= 4 - (thisThread->completedDepth > 22) + 2 * (PvNode && tte->is_pv()) && move == ttMove && !excludedMove // Avoid recursive singular search /* && ttValue != VALUE_NONE Already implicit in the next condition */ @@ -1057,6 +1068,7 @@ moves_loop: // When in check, search starts here Depth singularDepth = (depth - 1) / 2; ss->excludedMove = move; + // the search with excludedMove will update ss->staticEval value = search(pos, ss, singularBeta - 1, singularBeta, singularDepth, cutNode); ss->excludedMove = MOVE_NONE; @@ -1123,8 +1135,6 @@ moves_loop: // When in check, search starts here // Step 16. Make the move pos.do_move(move, st, givesCheck); - Depth r = reduction(improving, depth, moveCount, delta, thisThread->rootDelta); - // Decrease reduction if position is or has been on the PV // and node is not likely to fail low. (~3 Elo) if ( ss->ttPv @@ -1160,6 +1170,11 @@ moves_loop: // When in check, search starts here if ((ss+1)->cutoffCnt > 3) r++; + // Decrease reduction if move is a killer and we have a good history + if (move == ss->killers[0] + && (*contHist[0])[movedPiece][to_sq(move)] >= 3600) + r--; + ss->statScore = 2 * thisThread->mainHistory[us][from_to(move)] + (*contHist[0])[movedPiece][to_sq(move)] + (*contHist[1])[movedPiece][to_sq(move)] @@ -1205,9 +1220,6 @@ moves_loop: // When in check, search starts here int bonus = value > alpha ? stat_bonus(newDepth) : -stat_bonus(newDepth); - if (capture) - bonus /= 6; - update_continuation_histories(ss, movedPiece, to_sq(move), bonus); } } @@ -1230,8 +1242,7 @@ moves_loop: // When in check, search starts here (ss+1)->pv = pv; (ss+1)->pv[0] = MOVE_NONE; - value = -search(pos, ss+1, -beta, -alpha, - std::min(maxNextDepth, newDepth), false); + value = -search(pos, ss+1, -beta, -alpha, newDepth, false); } // Step 19. Undo move @@ -1360,11 +1371,10 @@ moves_loop: // When in check, search starts here quietsSearched, quietCount, capturesSearched, captureCount, depth); // Bonus for prior countermove that caused the fail low - else if ( (depth >= 5 || PvNode || bestValue < alpha - 65 * depth) - && !priorCapture) + else if (!priorCapture) { // Extra bonuses for PV/Cut nodes or bad fail lows - int bonus = 1 + (PvNode || cutNode) + (bestValue < alpha - 88 * depth); + int bonus = (depth > 4) + (PvNode || cutNode) + (bestValue < alpha - 88 * depth); update_continuation_histories(ss-1, pos.piece_on(prevSq), prevSq, stat_bonus(depth) * bonus); } @@ -1414,6 +1424,7 @@ moves_loop: // When in check, search starts here bool pvHit, givesCheck, capture; int moveCount; + // Step 1. Initialize node if (PvNode) { (ss+1)->pv = pv; @@ -1425,7 +1436,7 @@ moves_loop: // When in check, search starts here ss->inCheck = pos.checkers(); moveCount = 0; - // Check for an immediate draw or maximum ply reached + // Step 2. Check for an immediate draw or maximum ply reached if ( pos.is_draw(ss->ply) || ss->ply >= MAX_PLY) return (ss->ply >= MAX_PLY && !ss->inCheck) ? evaluate(pos) : VALUE_DRAW; @@ -1437,13 +1448,14 @@ moves_loop: // When in check, search starts here // only two types of depth in TT: DEPTH_QS_CHECKS or DEPTH_QS_NO_CHECKS. ttDepth = ss->inCheck || depth >= DEPTH_QS_CHECKS ? DEPTH_QS_CHECKS : DEPTH_QS_NO_CHECKS; - // Transposition table lookup + // Step 3. Transposition table lookup posKey = pos.key(); tte = TT.probe(posKey, ss->ttHit); ttValue = ss->ttHit ? value_from_tt(tte->value(), ss->ply, pos.rule50_count()) : VALUE_NONE; ttMove = ss->ttHit ? tte->move() : MOVE_NONE; pvHit = ss->ttHit && tte->is_pv(); + // At non-PV nodes we check for an early TT cutoff if ( !PvNode && ss->ttHit && tte->depth() >= ttDepth @@ -1451,7 +1463,7 @@ moves_loop: // When in check, search starts here && (tte->bound() & (ttValue >= beta ? BOUND_LOWER : BOUND_UPPER))) return ttValue; - // Evaluate the position statically + // Step 4. Static evaluation of the position if (ss->inCheck) { ss->staticEval = VALUE_NONE; @@ -1509,7 +1521,8 @@ moves_loop: // When in check, search starts here int quietCheckEvasions = 0; - // Loop through the moves until no moves remain or a beta cutoff occurs + // Step 5. Loop through all pseudo-legal moves until no moves remain + // or a beta cutoff occurs. while ((move = mp.next_move()) != MOVE_NONE) { assert(is_ok(move)); @@ -1523,9 +1536,11 @@ moves_loop: // When in check, search starts here moveCount++; + // Step 6. Pruning. + if (bestValue > VALUE_TB_LOSS_IN_MAX_PLY) + { // Futility pruning and moveCount pruning (~10 Elo) - if ( bestValue > VALUE_TB_LOSS_IN_MAX_PLY - && !givesCheck + if ( !givesCheck && to_sq(move) != prevSq && futilityBase > -VALUE_KNOWN_WIN && type_of(move) != PROMOTION) @@ -1548,43 +1563,43 @@ moves_loop: // When in check, search starts here } } - // Do not search moves with negative SEE values (~5 Elo) - if ( bestValue > VALUE_TB_LOSS_IN_MAX_PLY - && !pos.see_ge(move)) + // We prune after 2nd quiet check evasion where being 'in check' is implicitly checked through the counter + // and being a 'quiet' apart from being a tt move is assumed after an increment because captures are pushed ahead. + if (quietCheckEvasions > 1) + break; + + // Continuation history based pruning (~3 Elo) + if ( !capture + && (*contHist[0])[pos.moved_piece(move)][to_sq(move)] < 0 + && (*contHist[1])[pos.moved_piece(move)][to_sq(move)] < 0) continue; + // Do not search moves with bad enough SEE values (~5 Elo) + if (!pos.see_ge(move, Value(-108))) + continue; + + } + // Speculative prefetch as early as possible prefetch(TT.first_entry(pos.key_after(move))); + // Update the current move ss->currentMove = move; ss->continuationHistory = &thisThread->continuationHistory[ss->inCheck] [capture] [pos.moved_piece(move)] [to_sq(move)]; - // Continuation history based pruning (~3 Elo) - if ( !capture - && bestValue > VALUE_TB_LOSS_IN_MAX_PLY - && (*contHist[0])[pos.moved_piece(move)][to_sq(move)] < 0 - && (*contHist[1])[pos.moved_piece(move)][to_sq(move)] < 0) - continue; - - // We prune after 2nd quiet check evasion where being 'in check' is implicitly checked through the counter - // and being a 'quiet' apart from being a tt move is assumed after an increment because captures are pushed ahead. - if ( bestValue > VALUE_TB_LOSS_IN_MAX_PLY - && quietCheckEvasions > 1) - break; - quietCheckEvasions += !capture && ss->inCheck; - // Make and search the move + // Step 7. Make and search the move pos.do_move(move, st, givesCheck); value = -qsearch(pos, ss+1, -beta, -alpha, depth - 1); pos.undo_move(move); assert(value > -VALUE_INFINITE && value < VALUE_INFINITE); - // Check for a new best move + // Step 8. Check for a new best move if (value > bestValue) { bestValue = value; @@ -1604,6 +1619,7 @@ moves_loop: // When in check, search starts here } } + // Step 9. Check for mate // All legal moves have been searched. A special case: if we're in check // and no legal moves were found, it is checkmate. if (ss->inCheck && bestValue == -VALUE_INFINITE)