X-Git-Url: https://git.sesse.net/?p=stockfish;a=blobdiff_plain;f=src%2Fsearch.cpp;h=4b90ab1c973fc7fd60fdca3da67c4bada26648d8;hp=55df6172c64c779d890431bc6f0f42abab2cc9fb;hb=9f312c80d918c6f669dcf83df3d4332e02bfa1d9;hpb=005ad170c1dccdcd4ce73074302828ea22628b70 diff --git a/src/search.cpp b/src/search.cpp index 55df6172..4b90ab1c 100644 --- a/src/search.cpp +++ b/src/search.cpp @@ -64,24 +64,23 @@ namespace { // Razor and futility margins constexpr int RazorMargin = 661; Value futility_margin(Depth d, bool improving) { - return Value(198 * (d / ONE_PLY - improving)); + return Value(198 * (d - improving)); } // Reductions lookup table, initialized at startup int Reductions[MAX_MOVES]; // [depth or moveNumber] Depth reduction(bool i, Depth d, int mn) { - int r = Reductions[d / ONE_PLY] * Reductions[mn]; - return ((r + 520) / 1024 + (!i && r > 999)) * ONE_PLY; + int r = Reductions[d] * Reductions[mn]; + return (r + 520) / 1024 + (!i && r > 999); } - constexpr int futility_move_count(bool improving, int depth) { + constexpr int futility_move_count(bool improving, Depth depth) { return (5 + depth * depth) * (1 + improving) / 2; } // History and stats update bonus, based on depth - int stat_bonus(Depth depth) { - int d = depth / ONE_PLY; + int stat_bonus(Depth d) { return d > 17 ? -8 : 22 * d * d + 151 * d - 140; } @@ -94,7 +93,7 @@ namespace { struct Skill { explicit Skill(int l) : level(l) {} bool enabled() const { return level < 20; } - bool time_to_pick(Depth depth) const { return depth / ONE_PLY == 1 + level; } + bool time_to_pick(Depth depth) const { return depth == 1 + level; } Move pick_best(size_t multiPV); int level; @@ -148,14 +147,15 @@ namespace { Value search(Position& pos, Stack* ss, Value alpha, Value beta, Depth depth, bool cutNode); template - Value qsearch(Position& pos, Stack* ss, Value alpha, Value beta, Depth depth = DEPTH_ZERO); + Value qsearch(Position& pos, Stack* ss, Value alpha, Value beta, Depth depth = 0); Value value_to_tt(Value v, int ply); Value value_from_tt(Value v, int ply); void update_pv(Move* pv, Move move, Move* childPv); void update_continuation_histories(Stack* ss, Piece pc, Square to, int bonus); - void update_quiet_stats(const Position& pos, Stack* ss, Move move, Move* quiets, int quietCount, int bonus); - void update_capture_stats(const Position& pos, Move move, Move* captures, int captureCount, int bonus); + void update_quiet_stats(const Position& pos, Stack* ss, Move move, int bonus); + void update_all_stats(const Position& pos, Stack* ss, Move bestMove, Value bestValue, Value beta, Square prevSq, + Move* quietsSearched, int quietCount, Move* capturesSearched, int captureCount, Depth depth); // perft() is our utility to verify move generation. All the leaf nodes up // to the given depth are generated and counted, and the sum is returned. @@ -164,16 +164,16 @@ namespace { StateInfo st; uint64_t cnt, nodes = 0; - const bool leaf = (depth == 2 * ONE_PLY); + const bool leaf = (depth == 2); for (const auto& m : MoveList(pos)) { - if (Root && depth <= ONE_PLY) + if (Root && depth <= 1) cnt = 1, nodes++; else { pos.do_move(m, st); - cnt = leaf ? MoveList(pos).size() : perft(pos, depth - ONE_PLY); + cnt = leaf ? MoveList(pos).size() : perft(pos, depth - 1); nodes += cnt; pos.undo_move(m); } @@ -215,7 +215,7 @@ void MainThread::search() { if (Limits.perft) { - nodes = perft(rootPos, Limits.perft * ONE_PLY); + nodes = perft(rootPos, Limits.perft); sync_cout << "\nNodes searched: " << nodes << "\n" << sync_endl; return; } @@ -328,14 +328,15 @@ void Thread::search() { Move pv[MAX_PLY+1]; Value bestValue, alpha, beta, delta; Move lastBestMove = MOVE_NONE; - Depth lastBestMoveDepth = DEPTH_ZERO; + Depth lastBestMoveDepth = 0; MainThread* mainThread = (this == Threads.main() ? Threads.main() : nullptr); double timeReduction = 1, totBestMoveChanges = 0; Color us = rootPos.side_to_move(); std::memset(ss-7, 0, 10 * sizeof(Stack)); for (int i = 7; i > 0; i--) - (ss-i)->continuationHistory = &this->continuationHistory[NO_PIECE][0]; // Use as sentinel + (ss-i)->continuationHistory = &this->continuationHistory[0][0][NO_PIECE][0]; // Use as a sentinel + ss->pv = pv; bestValue = delta = alpha = -VALUE_INFINITE; @@ -378,9 +379,9 @@ void Thread::search() { : -make_score(ct, ct / 2)); // Iterative deepening loop until requested to stop or the target depth is reached - while ( (rootDepth += ONE_PLY) < DEPTH_MAX + while ( ++rootDepth < MAX_PLY && !Threads.stop - && !(Limits.depth && mainThread && rootDepth / ONE_PLY > Limits.depth)) + && !(Limits.depth && mainThread && rootDepth > Limits.depth)) { // Age out PV variability metric if (mainThread) @@ -409,15 +410,15 @@ void Thread::search() { selDepth = 0; // Reset aspiration window starting size - if (rootDepth >= 4 * ONE_PLY) + if (rootDepth >= 4) { Value previousScore = rootMoves[pvIdx].previousScore; - delta = Value(23); + delta = Value(21 + abs(previousScore) / 128); 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 + 86 * previousScore / (abs(previousScore) + 176); + int dct = ct + (111 - ct / 2) * previousScore / (abs(previousScore) + 176); contempt = (us == WHITE ? make_score(dct, dct / 2) : -make_score(dct, dct / 2)); @@ -429,7 +430,7 @@ void Thread::search() { int failedHighCnt = 0; while (true) { - Depth adjustedDepth = std::max(ONE_PLY, rootDepth - failedHighCnt * ONE_PLY); + Depth adjustedDepth = std::max(1, rootDepth - failedHighCnt); bestValue = ::search(rootPos, ss, alpha, beta, adjustedDepth, false); // Bring the best move to the front. It is critical that sorting @@ -519,7 +520,7 @@ void Thread::search() { fallingEval = clamp(fallingEval, 0.5, 1.5); // If the bestMove is stable over several iterations, reduce time accordingly - timeReduction = lastBestMoveDepth + 9 * ONE_PLY < completedDepth ? 1.97 : 0.98; + timeReduction = lastBestMoveDepth + 9 < 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 @@ -579,14 +580,13 @@ namespace { } // Dive into quiescence search when the depth reaches zero - if (depth < ONE_PLY) + if (depth <= 0) return qsearch(pos, ss, alpha, beta); assert(-VALUE_INFINITE <= alpha && alpha < beta && beta <= VALUE_INFINITE); assert(PvNode || (alpha == beta - 1)); - assert(DEPTH_ZERO < depth && depth < DEPTH_MAX); + assert(0 < depth && depth < MAX_PLY); assert(!(PvNode && cutNode)); - assert(depth / ONE_PLY * ONE_PLY == depth); Move pv[MAX_PLY+1], capturesSearched[32], quietsSearched[64]; StateInfo st; @@ -595,16 +595,17 @@ namespace { Move ttMove, move, excludedMove, bestMove; Depth extension, newDepth; Value bestValue, value, ttValue, eval, maxValue; - bool ttHit, ttPv, inCheck, givesCheck, improving, doLMR; - bool captureOrPromotion, doFullDepthSearch, moveCountPruning, ttCapture; + bool ttHit, ttPv, inCheck, givesCheck, improving, didLMR, priorCapture; + bool captureOrPromotion, doFullDepthSearch, moveCountPruning, ttCapture, singularLMR; Piece movedPiece; - int moveCount, captureCount, quietCount, singularLMR; + int moveCount, captureCount, quietCount; // Step 1. Initialize node Thread* thisThread = pos.this_thread(); inCheck = pos.checkers(); + priorCapture = pos.captured_piece(); Color us = pos.side_to_move(); - moveCount = captureCount = quietCount = singularLMR = ss->moveCount = 0; + moveCount = captureCount = quietCount = ss->moveCount = 0; bestValue = -VALUE_INFINITE; maxValue = VALUE_INFINITE; @@ -679,11 +680,11 @@ namespace { if (ttValue >= beta) { if (!pos.capture_or_promotion(ttMove)) - update_quiet_stats(pos, ss, ttMove, nullptr, 0, stat_bonus(depth)); + update_quiet_stats(pos, ss, ttMove, stat_bonus(depth)); // Extra penalty for early quiet moves of the previous ply - if ((ss-1)->moveCount <= 2 && !pos.captured_piece()) - update_continuation_histories(ss-1, pos.piece_on(prevSq), prevSq, -stat_bonus(depth + ONE_PLY)); + if ((ss-1)->moveCount <= 2 && !priorCapture) + update_continuation_histories(ss-1, pos.piece_on(prevSq), prevSq, -stat_bonus(depth + 1)); } // Penalty for a quiet ttMove that fails low else if (!pos.capture_or_promotion(ttMove)) @@ -730,7 +731,7 @@ namespace { || (b == BOUND_LOWER ? value >= beta : value <= alpha)) { tte->save(posKey, value_to_tt(value, ss->ply), ttPv, b, - std::min(DEPTH_MAX - ONE_PLY, depth + 6 * ONE_PLY), + std::min(MAX_PLY - 1, depth + 6), MOVE_NONE, VALUE_NONE); return value; @@ -785,7 +786,7 @@ namespace { // Step 7. Razoring (~2 Elo) if ( !rootNode // The required rootNode PV handling is not available in qsearch - && depth < 2 * ONE_PLY + && depth < 2 && eval <= alpha - RazorMargin) return qsearch(pos, ss, alpha, beta); @@ -794,7 +795,7 @@ namespace { // Step 8. Futility pruning: child node (~30 Elo) if ( !PvNode - && depth < 7 * ONE_PLY + && depth < 7 && eval - futility_margin(depth, improving) >= beta && eval < VALUE_KNOWN_WIN) // Do not return unproven wins return eval; @@ -805,7 +806,7 @@ namespace { && (ss-1)->statScore < 22661 && eval >= beta && eval >= ss->staticEval - && ss->staticEval >= beta - 33 * depth / ONE_PLY + 299 - improving * 30 + && ss->staticEval >= beta - 33 * depth + 299 - improving * 30 && !excludedMove && pos.non_pawn_material(us) && (ss->ply >= thisThread->nmpMinPly || us != thisThread->nmpColor)) @@ -813,10 +814,10 @@ namespace { assert(eval - beta >= 0); // Null move dynamic reduction based on depth and value - Depth R = ((835 + 70 * depth / ONE_PLY) / 256 + std::min(int(eval - beta) / 185, 3)) * ONE_PLY; + Depth R = (835 + 70 * depth) / 256 + std::min(int(eval - beta) / 185, 3); ss->currentMove = MOVE_NULL; - ss->continuationHistory = &thisThread->continuationHistory[NO_PIECE][0]; + ss->continuationHistory = &thisThread->continuationHistory[0][0][NO_PIECE][0]; pos.do_null_move(st); @@ -830,14 +831,14 @@ namespace { if (nullValue >= VALUE_MATE_IN_MAX_PLY) nullValue = beta; - if (thisThread->nmpMinPly || (abs(beta) < VALUE_KNOWN_WIN && depth < 13 * ONE_PLY)) + if (thisThread->nmpMinPly || (abs(beta) < VALUE_KNOWN_WIN && depth < 13)) return nullValue; assert(!thisThread->nmpMinPly); // Recursive verification is not allowed // Do verification search at high depths, with null move pruning disabled // for us, until ply exceeds nmpMinPly. - thisThread->nmpMinPly = ss->ply + 3 * (depth-R) / (4 * ONE_PLY); + thisThread->nmpMinPly = ss->ply + 3 * (depth-R) / 4; thisThread->nmpColor = us; Value v = search(pos, ss, beta-1, beta, depth-R, false); @@ -853,7 +854,7 @@ namespace { // If we have a good enough capture and a reduced search returns a value // much above beta, we can (almost) safely prune the previous move. if ( !PvNode - && depth >= 5 * ONE_PLY + && depth >= 5 && abs(beta) < VALUE_MATE_IN_MAX_PLY) { Value raisedBeta = std::min(beta + 191 - 46 * improving, VALUE_INFINITE); @@ -864,12 +865,17 @@ namespace { && probCutCount < 2 + 2 * cutNode) if (move != excludedMove && pos.legal(move)) { + assert(pos.capture_or_promotion(move)); + assert(depth >= 5); + + captureOrPromotion = true; probCutCount++; ss->currentMove = move; - ss->continuationHistory = &thisThread->continuationHistory[pos.moved_piece(move)][to_sq(move)]; - - assert(depth >= 5 * ONE_PLY); + ss->continuationHistory = &thisThread->continuationHistory[inCheck] + [captureOrPromotion] + [pos.moved_piece(move)] + [to_sq(move)]; pos.do_move(move, st); @@ -878,7 +884,7 @@ namespace { // If the qsearch held, perform the regular search if (value >= raisedBeta) - value = -search(pos, ss+1, -raisedBeta, -raisedBeta+1, depth - 4 * ONE_PLY, !cutNode); + value = -search(pos, ss+1, -raisedBeta, -raisedBeta+1, depth - 4, !cutNode); pos.undo_move(move); @@ -888,9 +894,9 @@ namespace { } // Step 11. Internal iterative deepening (~2 Elo) - if (depth >= 7 * ONE_PLY && !ttMove) + if (depth >= 7 && !ttMove) { - search(pos, ss, alpha, beta, depth - 7 * ONE_PLY, cutNode); + search(pos, ss, alpha, beta, depth - 7, cutNode); tte = TT.probe(posKey, ttHit); ttValue = ttHit ? value_from_tt(tte->value(), ss->ply) : VALUE_NONE; @@ -900,8 +906,8 @@ namespace { moves_loop: // When in check, search starts from here const PieceToHistory* contHist[] = { (ss-1)->continuationHistory, (ss-2)->continuationHistory, - nullptr, (ss-4)->continuationHistory, - nullptr, (ss-6)->continuationHistory }; + nullptr , (ss-4)->continuationHistory, + nullptr , (ss-6)->continuationHistory }; Move countermove = thisThread->counterMoves[pos.piece_on(prevSq)][prevSq]; @@ -911,8 +917,8 @@ moves_loop: // When in check, search starts from here countermove, ss->killers); - value = bestValue; // Workaround a bogus 'uninitialized' warning under gcc - moveCountPruning = false; + value = bestValue; + singularLMR = moveCountPruning = false; ttCapture = ttMove && pos.capture_or_promotion(ttMove); // Mark this node as being searched @@ -938,13 +944,13 @@ moves_loop: // When in check, search starts from here ss->moveCount = ++moveCount; if (rootNode && thisThread == Threads.main() && Time.elapsed() > 3000) - sync_cout << "info depth " << depth / ONE_PLY + sync_cout << "info depth " << depth << " currmove " << UCI::move(move, pos.is_chess960()) << " currmovenumber " << moveCount + thisThread->pvIdx << sync_endl; if (PvNode) (ss+1)->pv = nullptr; - extension = DEPTH_ZERO; + extension = 0; captureOrPromotion = pos.capture_or_promotion(move); movedPiece = pos.moved_piece(move); givesCheck = pos.gives_check(move); @@ -956,29 +962,26 @@ 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 >= 6 * ONE_PLY + if ( depth >= 6 && move == ttMove && !rootNode && !excludedMove // Avoid recursive singular search /* && ttValue != VALUE_NONE Already implicit in the next condition */ && abs(ttValue) < VALUE_KNOWN_WIN && (tte->bound() & BOUND_LOWER) - && tte->depth() >= depth - 3 * ONE_PLY + && tte->depth() >= depth - 3 && pos.legal(move)) { - Value singularBeta = ttValue - 2 * depth / ONE_PLY; - Depth halfDepth = depth / (2 * ONE_PLY) * ONE_PLY; // ONE_PLY invariant + Value singularBeta = ttValue - 2 * depth; + Depth halfDepth = depth / 2; ss->excludedMove = move; value = search(pos, ss, singularBeta - 1, singularBeta, halfDepth, cutNode); ss->excludedMove = MOVE_NONE; if (value < singularBeta) { - extension = ONE_PLY; - singularLMR++; - - if (value < singularBeta - std::min(4 * depth / ONE_PLY, 36)) - singularLMR++; + extension = 1; + singularLMR = true; } // Multi-cut pruning @@ -994,27 +997,20 @@ moves_loop: // When in check, search starts from here // Check extension (~2 Elo) else if ( givesCheck && (pos.is_discovery_check_on_king(~us, move) || pos.see_ge(move))) - extension = ONE_PLY; - - // Shuffle extension - else if ( PvNode - && pos.rule50_count() > 18 - && depth < 3 * ONE_PLY - && ++thisThread->shuffleExts < thisThread->nodes.load(std::memory_order_relaxed) / 4) // To avoid too many extensions - extension = ONE_PLY; + extension = 1; // Passed pawn extension else if ( move == ss->killers[0] && pos.advanced_pawn_push(move) && pos.pawn_passed(us, to_sq(move))) - extension = ONE_PLY; + extension = 1; // Castling extension if (type_of(move) == CASTLING) - extension = ONE_PLY; + extension = 1; // Calculate new depth for this move - newDepth = depth - ONE_PLY + extension; + newDepth = depth - 1 + extension; // Step 14. Pruning at shallow depth (~170 Elo) if ( !rootNode @@ -1022,7 +1018,7 @@ moves_loop: // When in check, search starts from here && bestValue > VALUE_MATED_IN_MAX_PLY) { // Skip quiet moves if movecount exceeds our FutilityMoveCount threshold - moveCountPruning = moveCount >= futility_move_count(improving, depth / ONE_PLY); + moveCountPruning = moveCount >= futility_move_count(improving, depth); if ( !captureOrPromotion && !givesCheck @@ -1033,8 +1029,7 @@ moves_loop: // When in check, search starts from here continue; // Reduced depth of the next LMR search - int lmrDepth = std::max(newDepth - reduction(improving, depth, moveCount), DEPTH_ZERO); - lmrDepth /= ONE_PLY; + int lmrDepth = std::max(newDepth - reduction(improving, depth, moveCount), 0); // Countermoves based pruning (~20 Elo) if ( lmrDepth < 4 + ((ss-1)->statScore > 0 || (ss-1)->moveCount == 1) @@ -1053,7 +1048,7 @@ moves_loop: // When in check, search starts from here continue; } else if ( !(givesCheck && extension) - && !pos.see_ge(move, Value(-199) * (depth / ONE_PLY))) // (~20 Elo) + && !pos.see_ge(move, Value(-199) * depth)) // (~20 Elo) continue; } @@ -1069,14 +1064,17 @@ moves_loop: // When in check, search starts from here // Update the current move (this must be done after singular extension search) ss->currentMove = move; - ss->continuationHistory = &thisThread->continuationHistory[movedPiece][to_sq(move)]; + ss->continuationHistory = &thisThread->continuationHistory[inCheck] + [captureOrPromotion] + [movedPiece] + [to_sq(move)]; // Step 15. Make the move pos.do_move(move, st, givesCheck); // Step 16. Reduced depth search (LMR). If the move fails high it will be // re-searched at full depth. - if ( depth >= 3 * ONE_PLY + if ( depth >= 3 && moveCount > 1 + 2 * rootNode && (!rootNode || thisThread->best_move_count(move) == 0) && ( !captureOrPromotion @@ -1088,35 +1086,36 @@ moves_loop: // When in check, search starts from here // Reduction if other threads are searching this position. if (th.marked()) - r += ONE_PLY; + r++; // Decrease reduction if position is or has been on the PV if (ttPv) - r -= 2 * ONE_PLY; + r -= 2; // Decrease reduction if opponent's move count is high (~10 Elo) if ((ss-1)->moveCount > 15) - r -= ONE_PLY; + r--; // Decrease reduction if ttMove has been singularly extended - r -= singularLMR * ONE_PLY; + if (singularLMR) + r -= 2; if (!captureOrPromotion) { // Increase reduction if ttMove is a capture (~0 Elo) if (ttCapture) - r += ONE_PLY; + r++; // Increase reduction for cut nodes (~5 Elo) if (cutNode) - r += 2 * ONE_PLY; + r += 2; // Decrease reduction for moves that escape a capture. Filter out // castling moves, because they are coded as "king captures rook" and // hence break make_move(). (~5 Elo) else if ( type_of(move) == NORMAL && !pos.see_ge(reverse_move(move))) - r -= 2 * ONE_PLY; + r -= 2; ss->statScore = thisThread->mainHistory[us][from_to(move)] + (*contHist[0])[movedPiece][to_sq(move)] @@ -1133,30 +1132,30 @@ moves_loop: // When in check, search starts from here // Decrease/increase reduction by comparing opponent's stat score (~10 Elo) if (ss->statScore >= -99 && (ss-1)->statScore < -116) - r -= ONE_PLY; + r--; else if ((ss-1)->statScore >= -117 && ss->statScore < -144) - r += ONE_PLY; + r++; // Decrease/increase reduction for moves with a good/bad history (~30 Elo) - r -= ss->statScore / 16384 * ONE_PLY; + r -= ss->statScore / 16384; } - Depth d = clamp(newDepth - r, ONE_PLY, newDepth); + Depth d = clamp(newDepth - r, 1, newDepth); value = -search(pos, ss+1, -(alpha+1), -alpha, d, true); - doFullDepthSearch = (value > alpha && d != newDepth), doLMR = true; + doFullDepthSearch = (value > alpha && d != newDepth), didLMR = true; } else - doFullDepthSearch = !PvNode || moveCount > 1, doLMR = false; + doFullDepthSearch = !PvNode || moveCount > 1, didLMR = 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) + if (didLMR && !captureOrPromotion) { int bonus = value > alpha ? stat_bonus(newDepth) : -stat_bonus(newDepth); @@ -1271,24 +1270,14 @@ moves_loop: // When in check, search starts from here if (!moveCount) bestValue = excludedMove ? alpha : inCheck ? mated_in(ss->ply) : VALUE_DRAW; - else if (bestMove) - { - // Quiet best move: update move sorting heuristics - if (!pos.capture_or_promotion(bestMove)) - update_quiet_stats(pos, ss, bestMove, quietsSearched, quietCount, - stat_bonus(depth + (bestValue > beta + PawnValueMg ? ONE_PLY : DEPTH_ZERO))); - - update_capture_stats(pos, bestMove, capturesSearched, captureCount, stat_bonus(depth + ONE_PLY)); - // Extra penalty for a quiet TT or main killer move in previous ply when it gets refuted - if ( ((ss-1)->moveCount == 1 || ((ss-1)->currentMove == (ss-1)->killers[0])) - && !pos.captured_piece()) - update_continuation_histories(ss-1, pos.piece_on(prevSq), prevSq, -stat_bonus(depth + ONE_PLY)); + else if (bestMove) + update_all_stats(pos, ss, bestMove, bestValue, beta, prevSq, + quietsSearched, quietCount, capturesSearched, captureCount, depth); - } // Bonus for prior countermove that caused the fail low - else if ( (depth >= 3 * ONE_PLY || PvNode) - && !pos.captured_piece()) + else if ( (depth >= 3 || PvNode) + && !priorCapture) update_continuation_histories(ss-1, pos.piece_on(prevSq), prevSq, stat_bonus(depth)); if (PvNode) @@ -1315,8 +1304,7 @@ moves_loop: // When in check, search starts from here assert(alpha >= -VALUE_INFINITE && alpha < beta && beta <= VALUE_INFINITE); assert(PvNode || (alpha == beta - 1)); - assert(depth <= DEPTH_ZERO); - assert(depth / ONE_PLY * ONE_PLY == depth); + assert(depth <= 0); Move pv[MAX_PLY+1]; StateInfo st; @@ -1325,7 +1313,7 @@ moves_loop: // When in check, search starts from here Move ttMove, move, bestMove; Depth ttDepth; Value bestValue, value, ttValue, futilityValue, futilityBase, oldAlpha; - bool ttHit, pvHit, inCheck, givesCheck, evasionPrunable; + bool ttHit, pvHit, inCheck, givesCheck, captureOrPromotion, evasionPrunable; int moveCount; if (PvNode) @@ -1409,8 +1397,8 @@ moves_loop: // When in check, search starts from here } const PieceToHistory* contHist[] = { (ss-1)->continuationHistory, (ss-2)->continuationHistory, - nullptr, (ss-4)->continuationHistory, - nullptr, (ss-6)->continuationHistory }; + nullptr , (ss-4)->continuationHistory, + nullptr , (ss-6)->continuationHistory }; // Initialize a MovePicker object for the current position, and prepare // to search the moves. Because the depth is <= 0 here, only captures, @@ -1427,6 +1415,7 @@ moves_loop: // When in check, search starts from here assert(is_ok(move)); givesCheck = pos.gives_check(move); + captureOrPromotion = pos.capture_or_promotion(move); moveCount++; @@ -1455,13 +1444,13 @@ moves_loop: // When in check, search starts from here // Detect non-capture evasions that are candidates to be pruned evasionPrunable = inCheck - && (depth != DEPTH_ZERO || moveCount > 2) + && (depth != 0 || moveCount > 2) && bestValue > VALUE_MATED_IN_MAX_PLY && !pos.capture(move); // Don't search moves with negative SEE values if ( (!inCheck || evasionPrunable) - && (!givesCheck || !(pos.blockers_for_king(~pos.side_to_move()) & from_sq(move))) + && !(givesCheck && pos.is_discovery_check_on_king(~pos.side_to_move(), move)) && !pos.see_ge(move)) continue; @@ -1476,11 +1465,14 @@ moves_loop: // When in check, search starts from here } ss->currentMove = move; - ss->continuationHistory = &thisThread->continuationHistory[pos.moved_piece(move)][to_sq(move)]; + ss->continuationHistory = &thisThread->continuationHistory[inCheck] + [captureOrPromotion] + [pos.moved_piece(move)] + [to_sq(move)]; // Make and search the move pos.do_move(move, st, givesCheck); - value = -qsearch(pos, ss+1, -beta, -alpha, depth - ONE_PLY); + value = -qsearch(pos, ss+1, -beta, -alpha, depth - 1); pos.undo_move(move); assert(value > -VALUE_INFINITE && value < VALUE_INFINITE); @@ -1556,43 +1548,65 @@ moves_loop: // When in check, search starts from here } - // update_continuation_histories() updates histories of the move pairs formed - // by moves at ply -1, -2, and -4 with current move. + // update_all_stats() updates stats at the end of search() when a bestMove is found - void update_continuation_histories(Stack* ss, Piece pc, Square to, int bonus) { + void update_all_stats(const Position& pos, Stack* ss, Move bestMove, Value bestValue, Value beta, Square prevSq, + Move* quietsSearched, int quietCount, Move* capturesSearched, int captureCount, Depth depth) { - for (int i : {1, 2, 4, 6}) - if (is_ok((ss-i)->currentMove)) - (*(ss-i)->continuationHistory)[pc][to] << bonus; - } + int bonus1, bonus2; + Color us = pos.side_to_move(); + Thread* thisThread = pos.this_thread(); + CapturePieceToHistory& captureHistory = thisThread->captureHistory; + Piece moved_piece = pos.moved_piece(bestMove); + PieceType captured = type_of(pos.piece_on(to_sq(bestMove))); + + bonus1 = stat_bonus(depth + 1); + bonus2 = bestValue > beta + PawnValueMg ? bonus1 // larger bonus + : stat_bonus(depth); // smaller bonus + if (!pos.capture_or_promotion(bestMove)) + { + update_quiet_stats(pos, ss, bestMove, bonus2); - // update_capture_stats() updates move sorting heuristics when a new capture best move is found + // Decrease all the non-best quiet moves + for (int i = 0; i < quietCount; ++i) + { + thisThread->mainHistory[us][from_to(quietsSearched[i])] << -bonus2; + update_continuation_histories(ss, pos.moved_piece(quietsSearched[i]), to_sq(quietsSearched[i]), -bonus2); + } + } + else + captureHistory[moved_piece][to_sq(bestMove)][captured] << bonus1; - void update_capture_stats(const Position& pos, Move move, - Move* captures, int captureCount, int bonus) { + // Extra penalty for a quiet TT or main killer move in previous ply when it gets refuted + if ( ((ss-1)->moveCount == 1 || ((ss-1)->currentMove == (ss-1)->killers[0])) + && !pos.captured_piece()) + update_continuation_histories(ss-1, pos.piece_on(prevSq), prevSq, -bonus1); - CapturePieceToHistory& captureHistory = pos.this_thread()->captureHistory; - Piece moved_piece = pos.moved_piece(move); - PieceType captured = type_of(pos.piece_on(to_sq(move))); + // Decrease all the non-best capture moves + for (int i = 0; i < captureCount; ++i) + { + moved_piece = pos.moved_piece(capturesSearched[i]); + captured = type_of(pos.piece_on(to_sq(capturesSearched[i]))); + captureHistory[moved_piece][to_sq(capturesSearched[i])][captured] << -bonus1; + } + } - if (pos.capture_or_promotion(move)) - captureHistory[moved_piece][to_sq(move)][captured] << bonus; - // Decrease all the other played capture moves - for (int i = 0; i < captureCount; ++i) - { - moved_piece = pos.moved_piece(captures[i]); - captured = type_of(pos.piece_on(to_sq(captures[i]))); - captureHistory[moved_piece][to_sq(captures[i])][captured] << -bonus; - } + // update_continuation_histories() updates histories of the move pairs formed + // by moves at ply -1, -2, and -4 with current move. + + void update_continuation_histories(Stack* ss, Piece pc, Square to, int bonus) { + + for (int i : {1, 2, 4, 6}) + if (is_ok((ss-i)->currentMove)) + (*(ss-i)->continuationHistory)[pc][to] << bonus; } - // update_quiet_stats() updates move sorting heuristics when a new quiet best move is found + // update_quiet_stats() updates move sorting heuristics - void update_quiet_stats(const Position& pos, Stack* ss, Move move, - Move* quiets, int quietCount, int bonus) { + void update_quiet_stats(const Position& pos, Stack* ss, Move move, int bonus) { if (ss->killers[0] != move) { @@ -1613,13 +1627,6 @@ moves_loop: // When in check, search starts from here Square prevSq = to_sq((ss-1)->currentMove); thisThread->counterMoves[pos.piece_on(prevSq)][prevSq] = move; } - - // Decrease all the other played quiet moves - for (int i = 0; i < quietCount; ++i) - { - thisThread->mainHistory[us][from_to(quiets[i])] << -bonus; - update_continuation_histories(ss, pos.moved_piece(quiets[i]), to_sq(quiets[i]), -bonus); - } } // When playing with strength handicap, choose best move among a set of RootMoves @@ -1707,10 +1714,10 @@ string UCI::pv(const Position& pos, Depth depth, Value alpha, Value beta) { { bool updated = (i <= pvIdx && rootMoves[i].score != -VALUE_INFINITE); - if (depth == ONE_PLY && !updated) + if (depth == 1 && !updated) continue; - Depth d = updated ? depth : depth - ONE_PLY; + Depth d = updated ? depth : depth - 1; Value v = updated ? rootMoves[i].score : rootMoves[i].previousScore; bool tb = TB::RootInTB && abs(v) < VALUE_MATE - MAX_PLY; @@ -1720,7 +1727,7 @@ string UCI::pv(const Position& pos, Depth depth, Value alpha, Value beta) { ss << "\n"; ss << "info" - << " depth " << d / ONE_PLY + << " depth " << d << " seldepth " << rootMoves[i].selDepth << " multipv " << i + 1 << " score " << UCI::value(v); @@ -1779,7 +1786,7 @@ void Tablebases::rank_root_moves(Position& pos, Search::RootMoves& rootMoves) { RootInTB = false; UseRule50 = bool(Options["Syzygy50MoveRule"]); - ProbeDepth = int(Options["SyzygyProbeDepth"]) * ONE_PLY; + ProbeDepth = int(Options["SyzygyProbeDepth"]); Cardinality = int(Options["SyzygyProbeLimit"]); bool dtz_available = true; @@ -1788,7 +1795,7 @@ void Tablebases::rank_root_moves(Position& pos, Search::RootMoves& rootMoves) { if (Cardinality > MaxCardinality) { Cardinality = MaxCardinality; - ProbeDepth = DEPTH_ZERO; + ProbeDepth = 0; } if (Cardinality >= popcount(pos.pieces()) && !pos.can_castle(ANY_CASTLING))