X-Git-Url: https://git.sesse.net/?a=blobdiff_plain;f=src%2Fsearch.cpp;h=76d055e3039e3b3a8245eeee9a8520343d75d392;hb=9cd563cb54b4091c48e16b524b3c9c15b7824c4f;hp=bc495c0e5ded6e0fdddf786774ab6283a55cc465;hpb=65e2150501b87e6ce00fae4e3f056444f39462fd;p=stockfish diff --git a/src/search.cpp b/src/search.cpp index bc495c0e..76d055e3 100644 --- a/src/search.cpp +++ b/src/search.cpp @@ -64,15 +64,15 @@ namespace { // Futility margin Value futility_margin(Depth d, bool improving) { - return Value(154 * (d - improving)); + return Value(140 * (d - improving)); } - // Reductions lookup table, initialized at startup + // Reductions lookup table initialized at startup int Reductions[MAX_MOVES]; // [depth or moveNumber] Depth reduction(bool i, Depth d, int mn, Value delta, Value rootDelta) { int r = Reductions[d] * Reductions[mn]; - return (r + 1449 - int(delta) * 937 / int(rootDelta)) / 1024 + (!i && r > 941); + return (r + 1372 - int(delta) * 1073 / int(rootDelta)) / 1024 + (!i && r > 936); } constexpr int futility_move_count(bool improving, Depth depth) { @@ -82,7 +82,7 @@ namespace { // History and stats update bonus, based on depth int stat_bonus(Depth d) { - return std::min(341 * d - 470, 1710); + return std::min(336 * d - 547, 1561); } // Add a small random component to draw evaluations to avoid 3-fold blindness @@ -92,7 +92,7 @@ namespace { // 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) + // (goldfish 1.13 = 2000) and a fit through Ordo derived Elo for a match (TC 60+0.6) // results spanning a wide range of k values. struct Skill { Skill(int skill_level, int uci_elo) { @@ -162,7 +162,7 @@ namespace { void Search::init() { for (int i = 1; i < MAX_MOVES; ++i) - Reductions[i] = int((19.47 + std::log(Threads.size()) / 2) * std::log(i)); + Reductions[i] = int((20.57 + std::log(Threads.size()) / 2) * std::log(i)); } @@ -304,7 +304,7 @@ void Thread::search() { 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. + // use behind-the-scenes to retrieve a set of possible moves. if (skill.enabled()) multiPV = std::max(multiPV, (size_t)4); @@ -321,7 +321,7 @@ void Thread::search() { if (mainThread) totBestMoveChanges /= 2; - // Save the last iteration's scores before first PV line is searched and + // Save the last iteration's scores before the first PV line is searched and // all the move scores except the (new) PV are set to -VALUE_INFINITE. for (RootMove& rm : rootMoves) rm.previousScore = rm.score; @@ -348,12 +348,12 @@ void Thread::search() { // Reset aspiration window starting size Value prev = rootMoves[pvIdx].averageScore; - delta = Value(10) + int(prev) * prev / 16502; + delta = Value(10) + int(prev) * prev / 15799; alpha = std::max(prev - delta,-VALUE_INFINITE); beta = std::min(prev + delta, VALUE_INFINITE); // Adjust optimism based on root move's previousScore - int opt = 102 * prev / (std::abs(prev) + 147); + int opt = 109 * prev / (std::abs(prev) + 141); optimism[ us] = Value(opt); optimism[~us] = -optimism[us]; @@ -363,16 +363,16 @@ void Thread::search() { int failedHighCnt = 0; while (true) { - // Adjust the effective depth searched, but ensuring at least one effective increment for every + // Adjust the effective depth searched, but ensure at least one effective increment for every // four searchAgain steps (see issue #2717). Depth adjustedDepth = std::max(1, rootDepth - failedHighCnt - 3 * (searchAgainCounter + 1) / 4); bestValue = Stockfish::search(rootPos, ss, alpha, beta, adjustedDepth, false); // Bring the best move to the front. It is critical that sorting // is done with a stable algorithm because all the values but the - // first and eventually the new best one are set to -VALUE_INFINITE + // first and eventually the new best one is set to -VALUE_INFINITE // and we want to keep the same order for all the moves except the - // new PV that goes to the front. Note that in case of MultiPV + // new PV that goes to the front. Note that in the case of MultiPV // search the already searched PV lines are preserved. std::stable_sort(rootMoves.begin() + pvIdx, rootMoves.begin() + pvLast); @@ -409,7 +409,7 @@ void Thread::search() { else break; - delta += delta / 4 + 2; + delta += delta / 3; assert(alpha >= -VALUE_INFINITE && beta <= VALUE_INFINITE); } @@ -440,7 +440,7 @@ void Thread::search() { if (!mainThread) continue; - // If skill level is enabled and time is up, pick a sub-optimal best move + // If the skill level is enabled and time is up, pick a sub-optimal best move if (skill.enabled() && skill.time_to_pick(rootDepth)) skill.pick_best(multiPV); @@ -498,7 +498,7 @@ void Thread::search() { mainThread->previousTimeReduction = timeReduction; - // If skill level is enabled, swap best PV line with the sub-optimal one + // If the skill level is enabled, swap the best PV line with the sub-optimal one if (skill.enabled()) std::swap(rootMoves[0], *std::find(rootMoves.begin(), rootMoves.end(), skill.best ? skill.best : skill.pick_best(multiPV))); @@ -515,7 +515,7 @@ namespace { constexpr bool PvNode = nodeType != NonPV; constexpr bool rootNode = nodeType == Root; - // Check if we have an upcoming move which draws by repetition, or + // Check if we have an upcoming move that draws by repetition, or // if the opponent had an alternative move earlier to this position. if ( !rootNode && pos.rule50_count() >= 3 @@ -580,8 +580,8 @@ namespace { // would be at best mate_in(ss->ply+1), but if alpha is already bigger because // a shorter mate was found upward in the tree then there is no need to search // because we will never beat the current alpha. Same logic but with reversed - // signs applies also in the opposite condition of being mated instead of giving - // mate. In this case return a fail-high score. + // signs apply also in the opposite condition of being mated instead of giving + // mate. In this case, return a fail-high score. alpha = std::max(mated_in(ss->ply), alpha); beta = std::min(mate_in(ss->ply+1), beta); if (alpha >= beta) @@ -615,10 +615,9 @@ namespace { // 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 + && ttValue != VALUE_NONE // Possible in case of TT access race or if !ttHit && (tte->bound() & (ttValue >= beta ? BOUND_LOWER : BOUND_UPPER))) { // If ttMove is quiet, update move sorting heuristics on TT hit (~2 Elo) @@ -735,14 +734,14 @@ namespace { else { ss->staticEval = eval = evaluate(pos); - // Save static evaluation into transposition table + // Save static evaluation into the transposition table tte->save(posKey, VALUE_NONE, ss->ttPv, BOUND_NONE, DEPTH_NONE, MOVE_NONE, eval); } // Use static evaluation difference to improve quiet move ordering (~4 Elo) if (is_ok((ss-1)->currentMove) && !(ss-1)->inCheck && !priorCapture) { - int bonus = std::clamp(-19 * int((ss-1)->staticEval + ss->staticEval), -1920, 1920); + int bonus = std::clamp(-18 * int((ss-1)->staticEval + ss->staticEval), -1817, 1817); thisThread->mainHistory[~us][from_to((ss-1)->currentMove)] << bonus; } @@ -752,13 +751,13 @@ namespace { // margin and the improving flag are used in various pruning heuristics. improvement = (ss-2)->staticEval != VALUE_NONE ? ss->staticEval - (ss-2)->staticEval : (ss-4)->staticEval != VALUE_NONE ? ss->staticEval - (ss-4)->staticEval - : 156; + : 173; improving = improvement > 0; // Step 7. Razoring (~1 Elo). // If eval is really low check with qsearch if it can exceed alpha, if it can't, // return a fail low. - if (eval < alpha - 426 - 256 * depth * depth) + if (eval < alpha - 456 - 252 * depth * depth) { value = qsearch(pos, ss, alpha - 1, alpha); if (value < alpha) @@ -769,26 +768,27 @@ namespace { // The depth condition is important for mate finding. if ( !ss->ttPv && depth < 9 - && eval - futility_margin(depth, improving) - (ss-1)->statScore / 280 >= beta + && eval - futility_margin(depth, improving) - (ss-1)->statScore / 306 >= beta && eval >= beta - && eval < 25128) // larger than VALUE_KNOWN_WIN, but smaller than TB wins + && eval < 24923) // larger than VALUE_KNOWN_WIN, but smaller than TB wins return eval; // Step 9. Null move search with verification search (~35 Elo) if ( !PvNode && (ss-1)->currentMove != MOVE_NULL - && (ss-1)->statScore < 18755 + && (ss-1)->statScore < 17329 && eval >= beta && eval >= ss->staticEval - && ss->staticEval >= beta - 20 * depth - improvement / 13 + 253 + && ss->staticEval >= beta - 21 * depth + 258 && !excludedMove && pos.non_pawn_material(us) - && (ss->ply >= thisThread->nmpMinPly)) + && ss->ply >= thisThread->nmpMinPly + && beta > VALUE_TB_LOSS_IN_MAX_PLY) { assert(eval - beta >= 0); // Null move dynamic reduction based on depth and eval - Depth R = std::min(int(eval - beta) / 172, 6) + depth / 3 + 4; + Depth R = std::min(int(eval - beta) / 173, 6) + depth / 3 + 4; ss->currentMove = MOVE_NULL; ss->continuationHistory = &thisThread->continuationHistory[0][0][NO_PIECE][0]; @@ -802,10 +802,9 @@ namespace { if (nullValue >= beta) { // Do not return unproven mate or TB scores - if (nullValue >= VALUE_TB_WIN_IN_MAX_PLY) - nullValue = beta; + nullValue = std::min(nullValue, VALUE_TB_WIN_IN_MAX_PLY-1); - if (thisThread->nmpMinPly || (abs(beta) < VALUE_KNOWN_WIN && depth < 14)) + if (thisThread->nmpMinPly || depth < 14) return nullValue; assert(!thisThread->nmpMinPly); // Recursive verification is not allowed @@ -823,20 +822,34 @@ namespace { } } - probCutBeta = beta + 186 - 54 * improving; + // Step 10. If the position doesn't have a ttMove, decrease depth by 2 + // (or by 4 if the TT entry for the current position was hit and the stored depth is greater than or equal to the current depth). + // Use qsearch if depth is equal or below zero (~9 Elo) + if ( PvNode + && !ttMove) + depth -= 2 + 2 * (ss->ttHit && tte->depth() >= depth); + + if (depth <= 0) + return qsearch(pos, ss, alpha, beta); - // Step 10. ProbCut (~10 Elo) + if ( cutNode + && depth >= 8 + && !ttMove) + depth -= 2; + + probCutBeta = beta + 168 - 61 * improving; + + // Step 11. ProbCut (~10 Elo) // If we have a good enough capture (or queen promotion) and a reduced search returns a value // much above beta, we can (almost) safely prune the previous move. if ( !PvNode - && depth > 4 + && depth > 3 && abs(beta) < VALUE_TB_WIN_IN_MAX_PLY - // if value from transposition table is lower than probCutBeta, don't attempt probCut + // If value from transposition table is lower than probCutBeta, don't attempt probCut // there and in further interactions with transposition table cutoff depth is set to depth - 3 // because probCut search has depth set to depth - 4 but we also do a move before it - // so effective depth is equal to depth - 3 - && !( ss->ttHit - && tte->depth() >= depth - 3 + // So effective depth is equal to depth - 3 + && !( tte->depth() >= depth - 3 && ttValue != VALUE_NONE && ttValue < probCutBeta)) { @@ -877,30 +890,15 @@ namespace { Eval::NNUE::hint_common_parent_position(pos); } - // Step 11. If the position is not in TT, decrease depth by 2 (or by 4 if the TT entry for the current position was hit and the stored depth is greater than or equal to the current depth). - // Use qsearch if depth is equal or below zero (~9 Elo) - if ( PvNode - && !ttMove) - depth -= 2 + 2 * (ss->ttHit && tte->depth() >= depth); - - if (depth <= 0) - return qsearch(pos, ss, alpha, beta); - - if ( cutNode - && depth >= 7 - && !ttMove) - depth -= 2; - moves_loop: // When in check, search starts here // Step 12. A small Probcut idea, when we are in check (~4 Elo) - probCutBeta = beta + 391; + probCutBeta = beta + 413; if ( ss->inCheck && !PvNode - && depth >= 2 && ttCapture && (tte->bound() & BOUND_LOWER) - && tte->depth() >= depth - 3 + && tte->depth() >= depth - 4 && ttValue >= probCutBeta && abs(ttValue) <= VALUE_KNOWN_WIN && abs(beta) <= VALUE_KNOWN_WIN) @@ -922,7 +920,7 @@ moves_loop: // When in check, search starts here moveCountPruning = singularQuietLMR = 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. + // at a depth equal to or greater than the current depth, and the result of this search was a fail low. bool likelyFailLow = PvNode && ttMove && (tte->bound() & BOUND_UPPER) @@ -938,8 +936,8 @@ moves_loop: // When in check, search starts here continue; // At root obey the "searchmoves" option and skip moves not listed in Root - // Move List. As a consequence any illegal move is also skipped. In MultiPV - // mode we also skip PV moves which have been already searched and those + // Move List. As a consequence, any illegal move is also skipped. In MultiPV + // mode we also skip PV moves that have been already searched and those // of lower "TB rank" if we are in a TB root position. if (rootNode && !std::count(thisThread->rootMoves.begin() + thisThread->pvIdx, thisThread->rootMoves.begin() + thisThread->pvLast, move)) @@ -979,39 +977,40 @@ 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 - r, 0); + int lmrDepth = newDepth - r; if ( capture || givesCheck) { // Futility pruning for captures (~2 Elo) if ( !givesCheck - && lmrDepth < 6 + && lmrDepth < 7 && !ss->inCheck - && ss->staticEval + 182 + 230 * lmrDepth + PieceValue[EG][pos.piece_on(to_sq(move))] + && ss->staticEval + 197 + 248 * lmrDepth + PieceValue[EG][pos.piece_on(to_sq(move))] + captureHistory[movedPiece][to_sq(move)][type_of(pos.piece_on(to_sq(move)))] / 7 < alpha) continue; Bitboard occupied; // SEE based pruning (~11 Elo) - if (!pos.see_ge(move, occupied, Value(-206) * depth)) + if (!pos.see_ge(move, occupied, Value(-205) * depth)) { - if (depth < 2 - capture) - continue; - // Don't prune the move if opp. King/Queen/Rook gets a discovered attack during or after the exchanges - Bitboard leftEnemies = pos.pieces(~us, KING, QUEEN, ROOK); - Bitboard attacks = 0; - occupied |= to_sq(move); - while (leftEnemies && !attacks) - { + if (depth < 2 - capture) + continue; + // Don't prune the move if opponent Queen/Rook is under discovered attack after the exchanges + // Don't prune the move if opponent King is under discovered attack after or during the exchanges + Bitboard leftEnemies = (pos.pieces(~us, KING, QUEEN, ROOK)) & occupied; + Bitboard attacks = 0; + occupied |= to_sq(move); + while (leftEnemies && !attacks) + { Square sq = pop_lsb(leftEnemies); - attacks = pos.attackers_to(sq, occupied) & pos.pieces(us) & occupied; - // Exclude Queen/Rook(s) which were already threatened before SEE (opp King can't be in check when it's our turn) - if (attacks && sq != pos.square(~us) && (pos.attackers_to(sq, pos.pieces()) & pos.pieces(us))) - attacks = 0; - } - if (!attacks) - continue; + attacks |= pos.attackers_to(sq, occupied) & pos.pieces(us) & occupied; + // Don't consider pieces that were already threatened/hanging before SEE exchanges + if (attacks && (sq != pos.square(~us) && (pos.attackers_to(sq, pos.pieces()) & pos.pieces(us)))) + attacks = 0; + } + if (!attacks) + continue; } } else @@ -1021,25 +1020,25 @@ moves_loop: // When in check, search starts here + (*contHist[3])[movedPiece][to_sq(move)]; // Continuation history based pruning (~2 Elo) - if ( lmrDepth < 5 - && history < -4405 * (depth - 1)) + if ( lmrDepth < 6 + && history < -3832 * depth) continue; history += 2 * thisThread->mainHistory[us][from_to(move)]; - lmrDepth += history / 7278; + lmrDepth += history / 7011; lmrDepth = std::max(lmrDepth, -2); // Futility pruning: parent node (~13 Elo) if ( !ss->inCheck - && lmrDepth < 13 - && ss->staticEval + 103 + 138 * lmrDepth <= alpha) + && lmrDepth < 12 + && ss->staticEval + 112 + 138 * lmrDepth <= alpha) continue; lmrDepth = std::max(lmrDepth, 0); // Prune moves with negative SEE (~4 Elo) - if (!pos.see_ge(move, Value(-24 * lmrDepth * lmrDepth - 16 * lmrDepth))) + if (!pos.see_ge(move, Value(-27 * lmrDepth * lmrDepth - 16 * lmrDepth))) continue; } } @@ -1053,8 +1052,11 @@ moves_loop: // When in check, search starts 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. + // Depth margin and singularBeta margin are known for having non-linear scaling. + // Their values are optimized to time controls of 180+1.8 and longer + // so changing them requires tests at this type of time controls. if ( !rootNode - && depth >= 4 - (thisThread->completedDepth > 21) + 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 */ @@ -1062,7 +1064,7 @@ moves_loop: // When in check, search starts here && (tte->bound() & BOUND_LOWER) && tte->depth() >= depth - 3) { - Value singularBeta = ttValue - (3 + 2 * (ss->ttPv && !PvNode)) * depth / 2; + Value singularBeta = ttValue - (82 + 65 * (ss->ttPv && !PvNode)) * depth / 64; Depth singularDepth = (depth - 1) / 2; ss->excludedMove = move; @@ -1076,8 +1078,8 @@ moves_loop: // When in check, search starts here // Avoid search explosion by limiting the number of double extensions if ( !PvNode - && value < singularBeta - 25 - && ss->doubleExtensions <= 10) + && value < singularBeta - 21 + && ss->doubleExtensions <= 11) { extension = 2; depth += depth < 13; @@ -1088,7 +1090,7 @@ moves_loop: // When in check, search starts here // 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. + // a softbound. else if (singularBeta >= beta) return singularBeta; @@ -1096,6 +1098,10 @@ moves_loop: // When in check, search starts here else if (ttValue >= beta) extension = -2 - !PvNode; + // If we are on a cutNode, reduce it based on depth (negative extension) (~1 Elo) + else if (cutNode) + extension = depth > 8 && depth < 17 ? -3 : -1; + // If the eval of ttMove is less than value, we reduce it (negative extension) (~1 Elo) else if (ttValue <= value) extension = -1; @@ -1107,15 +1113,14 @@ moves_loop: // When in check, search starts here // Check extensions (~1 Elo) else if ( givesCheck - && depth > 10 - && abs(ss->staticEval) > 88) + && depth > 9) extension = 1; // Quiet ttMove extensions (~1 Elo) else if ( PvNode && move == ttMove && move == ss->killers[0] - && (*contHist[0])[movedPiece][to_sq(move)] >= 5705) + && (*contHist[0])[movedPiece][to_sq(move)] >= 5168) extension = 1; } @@ -1144,7 +1149,7 @@ moves_loop: // When in check, search starts here r -= cutNode && tte->depth() >= depth + 3 ? 3 : 2; // Decrease reduction if opponent's move count is high (~1 Elo) - if ((ss-1)->moveCount > 7) + if ((ss-1)->moveCount > 8) r--; // Increase reduction for cut nodes (~3 Elo) @@ -1174,14 +1179,14 @@ moves_loop: // When in check, search starts here + (*contHist[0])[movedPiece][to_sq(move)] + (*contHist[1])[movedPiece][to_sq(move)] + (*contHist[3])[movedPiece][to_sq(move)] - - 4082; + - 4006; // Decrease/increase reduction for moves with a good/bad history (~25 Elo) - r -= ss->statScore / (11079 + 4626 * (depth > 6 && depth < 19)); + r -= ss->statScore / (11124 + 4740 * (depth > 5 && depth < 22)); // Step 17. Late moves reduction / extension (LMR, ~117 Elo) // We use various heuristics for the sons of a node after the first son has - // been searched. In general we would like to reduce them, but there are many + // been searched. In general, we would like to reduce them, but there are many // cases where we extend a son if it has good chances to be "interesting". if ( depth >= 2 && moveCount > 1 + (PvNode && ss->ply <= 1) @@ -1196,13 +1201,13 @@ moves_loop: // When in check, search starts here value = -search(pos, ss+1, -(alpha+1), -alpha, d, true); - // Do full depth search when reduced LMR search fails high + // Do a full-depth search when reduced LMR search fails high if (value > alpha && d < newDepth) { - // Adjust full depth search based on LMR results - if result + // Adjust full-depth search based on LMR results - if the result // was good enough search deeper, if it was bad enough search shallower - const bool doDeeperSearch = value > (bestValue + 68 + 12 * (newDepth - d)); - const bool doEvenDeeperSearch = value > alpha + 588 && ss->doubleExtensions <= 5; + const bool doDeeperSearch = value > (bestValue + 64 + 11 * (newDepth - d)); + const bool doEvenDeeperSearch = value > alpha + 711 && ss->doubleExtensions <= 6; const bool doShallowerSearch = value < bestValue + newDepth; ss->doubleExtensions = ss->doubleExtensions + doEvenDeeperSearch; @@ -1220,14 +1225,14 @@ moves_loop: // When in check, search starts here } } - // Step 18. Full depth search when LMR is skipped. If expected reduction is high, reduce its depth by 1. + // Step 18. Full-depth search when LMR is skipped. If expected reduction is high, reduce its depth by 1. else if (!PvNode || moveCount > 1) { // Increase reduction for cut nodes and not ttMove (~1 Elo) if (!ttMove && cutNode) r += 2; - value = -search(pos, ss+1, -(alpha+1), -alpha, newDepth - (r > 4), !cutNode); + value = -search(pos, ss+1, -(alpha+1), -alpha, newDepth - (r > 3), !cutNode); } // For PV nodes only, do a full PV search on the first move or after a fail @@ -1293,7 +1298,7 @@ moves_loop: // When in check, search starts here ++thisThread->bestMoveChanges; } else - // All other moves but the PV are set to the lowest value: this + // All other moves but the PV, are set to the lowest value: this // is not a problem when sorting because the sort is stable and the // move position in the list is preserved - just the PV is pushed up. rm.score = -VALUE_INFINITE; @@ -1318,11 +1323,12 @@ moves_loop: // When in check, search starts here } else { - // Reduce other moves if we have found at least one score improvement (~1 Elo) - if ( depth > 1 - && beta < 12535 - && value > -12535) - depth -= 1; + // Reduce other moves if we have found at least one score improvement (~2 Elo) + if ( depth > 2 + && depth < 12 + && beta < 14362 + && value > -12393) + depth -= 2; assert(depth > 0); alpha = value; // Update alpha! Always alpha < beta @@ -1331,7 +1337,7 @@ moves_loop: // When in check, search starts here } - // If the move is worse than some previously searched move, remember it to update its stats later + // If the move is worse than some previously searched move, remember it, to update its stats later if (move != bestMove) { if (capture && captureCount < 32) @@ -1343,7 +1349,7 @@ moves_loop: // When in check, search starts here } // The following condition would detect a stop only after move loop has been - // completed. But in this case bestValue is valid because we have fully + // completed. But in this case, bestValue is valid because we have fully // searched our subtree, and we can anyhow save the result in TT. /* if (Threads.stop) @@ -1362,7 +1368,7 @@ moves_loop: // When in check, search starts here ss->inCheck ? mated_in(ss->ply) : VALUE_DRAW; - // If there is a move which produces search value greater than alpha we update stats of searched moves + // If there is a move that produces search value greater than alpha we update the stats of searched moves else if (bestMove) update_all_stats(pos, ss, bestMove, bestValue, beta, prevSq, quietsSearched, quietCount, capturesSearched, captureCount, depth); @@ -1370,7 +1376,7 @@ moves_loop: // When in check, search starts here // Bonus for prior countermove that caused the fail low else if (!priorCapture && prevSq != SQ_NONE) { - int bonus = (depth > 5) + (PvNode || cutNode) + (bestValue < alpha - 97 * depth) + ((ss-1)->moveCount > 10); + int bonus = (depth > 5) + (PvNode || cutNode) + (bestValue < alpha - 113 * depth) + ((ss-1)->moveCount > 12); update_continuation_histories(ss-1, pos.piece_on(prevSq), prevSq, stat_bonus(depth) * bonus); } @@ -1454,18 +1460,14 @@ moves_loop: // When in check, search starts here // At non-PV nodes we check for an early TT cutoff if ( !PvNode - && ss->ttHit && tte->depth() >= ttDepth - && ttValue != VALUE_NONE // Only in case of TT access race + && ttValue != VALUE_NONE // Only in case of TT access race or if !ttHit && (tte->bound() & (ttValue >= beta ? BOUND_LOWER : BOUND_UPPER))) return ttValue; // Step 4. Static evaluation of the position if (ss->inCheck) - { - ss->staticEval = VALUE_NONE; bestValue = futilityBase = -VALUE_INFINITE; - } else { if (ss->ttHit) @@ -1481,9 +1483,8 @@ moves_loop: // When in check, search starts here } else // In case of null move search use previous static eval with a different sign - ss->staticEval = bestValue = - (ss-1)->currentMove != MOVE_NULL ? evaluate(pos) - : -(ss-1)->staticEval; + ss->staticEval = bestValue = (ss-1)->currentMove != MOVE_NULL ? evaluate(pos) + : -(ss-1)->staticEval; // Stand pat. Return immediately if static value is at least beta if (bestValue >= beta) @@ -1499,7 +1500,7 @@ moves_loop: // When in check, search starts here if (PvNode && bestValue > alpha) alpha = bestValue; - futilityBase = bestValue + 168; + futilityBase = bestValue + 200; } const PieceToHistory* contHist[] = { (ss-1)->continuationHistory, (ss-2)->continuationHistory, @@ -1510,7 +1511,7 @@ moves_loop: // When in check, search starts here // to search the moves. Because the depth is <= 0 here, only captures, // queen promotions, and other checks (only if depth >= DEPTH_QS_CHECKS) // will be generated. - Square prevSq = (ss-1)->currentMove != MOVE_NULL ? to_sq((ss-1)->currentMove) : SQ_NONE; + Square prevSq = is_ok((ss-1)->currentMove) ? to_sq((ss-1)->currentMove) : SQ_NONE; MovePicker mp(pos, ttMove, depth, &thisThread->mainHistory, &thisThread->captureHistory, contHist, @@ -1522,97 +1523,98 @@ moves_loop: // When in check, search starts here // or a beta cutoff occurs. while ((move = mp.next_move()) != MOVE_NONE) { - assert(is_ok(move)); + assert(is_ok(move)); - // Check for legality - if (!pos.legal(move)) - continue; + // Check for legality + if (!pos.legal(move)) + continue; - givesCheck = pos.gives_check(move); - capture = pos.capture_stage(move); - - moveCount++; - - // Step 6. Pruning. - if (bestValue > VALUE_TB_LOSS_IN_MAX_PLY) - { - // Futility pruning and moveCount pruning (~10 Elo) - if ( !givesCheck - && to_sq(move) != prevSq - && futilityBase > -VALUE_KNOWN_WIN - && type_of(move) != PROMOTION) - { - if (moveCount > 2) - continue; + givesCheck = pos.gives_check(move); + capture = pos.capture_stage(move); - futilityValue = futilityBase + PieceValue[EG][pos.piece_on(to_sq(move))]; + moveCount++; - if (futilityValue <= alpha) - { - bestValue = std::max(bestValue, futilityValue); - continue; - } + // Step 6. Pruning. + if (bestValue > VALUE_TB_LOSS_IN_MAX_PLY) + { + // Futility pruning and moveCount pruning (~10 Elo) + if ( !givesCheck + && to_sq(move) != prevSq + && futilityBase > -VALUE_KNOWN_WIN + && type_of(move) != PROMOTION) + { + if (moveCount > 2) + continue; - if (futilityBase <= alpha && !pos.see_ge(move, VALUE_ZERO + 1)) - { - bestValue = std::max(bestValue, futilityBase); - continue; - } - } + futilityValue = futilityBase + PieceValue[EG][pos.piece_on(to_sq(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; + if (futilityValue <= alpha) + { + bestValue = std::max(bestValue, futilityValue); + continue; + } - // 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; + if (futilityBase <= alpha && !pos.see_ge(move, VALUE_ZERO + 1)) + { + bestValue = std::max(bestValue, futilityBase); + continue; + } + } - // Do not search moves with bad enough SEE values (~5 Elo) - if (!pos.see_ge(move, Value(-110))) - continue; - } + // We prune after the second quiet check evasion move, where being 'in check' is + // implicitly checked through the counter, and being a 'quiet move' 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(-95))) + continue; + } - // Speculative prefetch as early as possible - prefetch(TT.first_entry(pos.key_after(move))); + // 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)]; + // Update the current move + ss->currentMove = move; + ss->continuationHistory = &thisThread->continuationHistory[ss->inCheck] + [capture] + [pos.moved_piece(move)] + [to_sq(move)]; - quietCheckEvasions += !capture && ss->inCheck; + quietCheckEvasions += !capture && ss->inCheck; - // 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); + // 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); + assert(value > -VALUE_INFINITE && value < VALUE_INFINITE); - // Step 8. Check for a new best move - if (value > bestValue) - { - bestValue = value; + // Step 8. Check for a new best move + if (value > bestValue) + { + bestValue = value; - if (value > alpha) - { - bestMove = move; + if (value > alpha) + { + bestMove = move; - if (PvNode) // Update pv even in fail-high case - update_pv(ss->pv, move, (ss+1)->pv); + if (PvNode) // Update pv even in fail-high case + update_pv(ss->pv, move, (ss+1)->pv); - if (PvNode && value < beta) // Update alpha here! - alpha = value; - else - break; // Fail high - } - } + if (PvNode && value < beta) // Update alpha here! + alpha = value; + else + break; // Fail high + } + } } // Step 9. Check for mate @@ -1705,7 +1707,7 @@ moves_loop: // When in check, search starts here if (!pos.capture_stage(bestMove)) { - int bonus2 = bestValue > beta + 153 ? bonus1 // larger bonus + int bonus2 = bestValue > beta + 145 ? bonus1 // larger bonus : stat_bonus(depth); // smaller bonus // Increase stats for the best move in case it was a quiet move @@ -1749,7 +1751,7 @@ moves_loop: // When in check, search starts here for (int i : {1, 2, 4, 6}) { - // Only update first 2 continuation histories if we are in check + // Only update the first 2 continuation histories if we are in check if (ss->inCheck && i > 2) break; if (is_ok((ss-i)->currentMove)) @@ -1782,7 +1784,7 @@ moves_loop: // When in check, search starts here } } - // When playing with strength handicap, choose best move among a set of RootMoves + // When playing with strength handicap, choose the best move among a set of RootMoves // using a statistical rule dependent on 'level'. Idea by Heinz van Saanen. Move Skill::pick_best(size_t multiPV) { @@ -1913,7 +1915,7 @@ string UCI::pv(const Position& pos, Depth depth) { /// RootMove::extract_ponder_from_tt() is called in case we have no ponder move /// before exiting the search, for instance, in case we stop the search during a /// fail high at root. We try hard to have a ponder move to return to the GUI, -/// otherwise in case of 'ponder on' we have nothing to think on. +/// otherwise in case of 'ponder on' we have nothing to think about. bool RootMove::extract_ponder_from_tt(Position& pos) {