X-Git-Url: https://git.sesse.net/?a=blobdiff_plain;f=src%2Fsearch.cpp;h=5cb9750c3235a72d6c33fc99943c379c85ac4380;hb=08385527dd470ece814ac85013802995a0e7f6ca;hp=f6bc0aa9a8098a7250037749b3c81f231b277307;hpb=d2f79ff0e0efc33797120f59355c2a5571b4ab80;p=stockfish diff --git a/src/search.cpp b/src/search.cpp index f6bc0aa9..5cb9750c 100644 --- a/src/search.cpp +++ b/src/search.cpp @@ -615,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))) @@ -664,7 +666,7 @@ namespace { } // Step 5. Tablebases probe - if (!rootNode && TB::Cardinality) + if (!rootNode && !excludedMove && TB::Cardinality) { int piecesCount = pos.count(); @@ -727,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 @@ -744,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) @@ -982,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) @@ -991,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) @@ -1061,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; @@ -1127,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 @@ -1365,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); } @@ -1419,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; @@ -1430,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; @@ -1442,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 @@ -1456,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; @@ -1514,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)); @@ -1528,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) @@ -1553,43 +1563,43 @@ moves_loop: // When in check, search starts here } } + // 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 ( bestValue > VALUE_TB_LOSS_IN_MAX_PLY - && !pos.see_ge(move, Value(-108))) + 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; @@ -1609,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)