X-Git-Url: https://git.sesse.net/?a=blobdiff_plain;f=src%2Fsearch.cpp;h=c81496d17a35aa6a00374c9ec9be9115ea720c49;hb=7678d63cf2323e51c01e60cdff4ac3d685313790;hp=e7e33edef8f7acd4b1b41e9861e7a78e36158c03;hpb=b37054c310876850f6ff65b19f6cdb5f941c57dc;p=stockfish diff --git a/src/search.cpp b/src/search.cpp index e7e33ede..c81496d1 100644 --- a/src/search.cpp +++ b/src/search.cpp @@ -1,6 +1,6 @@ /* Stockfish, a UCI chess playing engine derived from Glaurung 2.1 - Copyright (C) 2004-2021 The Stockfish developers (see AUTHORS file) + Copyright (C) 2004-2022 The Stockfish developers (see AUTHORS file) Stockfish is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by @@ -69,9 +69,9 @@ namespace { // Reductions lookup table, initialized at startup int Reductions[MAX_MOVES]; // [depth or moveNumber] - Depth reduction(bool i, Depth d, int mn, bool rangeReduction) { + Depth reduction(bool i, Depth d, int mn, Value delta, Value rootDelta) { int r = Reductions[d] * Reductions[mn]; - return (r + 534) / 1024 + (!i && r > 904) + rangeReduction; + return (r + 1358 - int(delta) * 1024 / int(rootDelta)) / 1024 + (!i && r > 904); } constexpr int futility_move_count(bool improving, Depth depth) { @@ -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; }; @@ -133,7 +141,7 @@ namespace { Value value_from_tt(Value v, int ply, int r50c); 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, int bonus, int depth); + 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); @@ -243,14 +251,16 @@ 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(); bestPreviousScore = bestThread->rootMoves[0].score; + bestPreviousAverageScore = bestThread->rootMoves[0].averageScore; // Send again PV info if we have a new best thread if (bestThread != this) @@ -277,7 +287,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); @@ -307,23 +317,8 @@ void Thread::search() { mainThread->iterValue[i] = mainThread->bestPreviousScore; } - std::copy(&lowPlyHistory[2][0], &lowPlyHistory.back().back() + 1, &lowPlyHistory[0][0]); - 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 +332,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 +376,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 @@ -475,25 +475,25 @@ void Thread::search() { if (skill.enabled() && skill.time_to_pick(rootDepth)) skill.pick_best(multiPV); + // Use part of the gained time from a previous stable move for the current move + for (Thread* th : Threads) + { + totBestMoveChanges += th->bestMoveChanges; + th->bestMoveChanges = 0; + } + // Do we have time for the next iteration? Can we stop searching now? if ( Limits.use_time_management() && !Threads.stop && !mainThread->stopOnPonderhit) { - double fallingEval = (318 + 6 * (mainThread->bestPreviousScore - bestValue) - + 6 * (mainThread->iterValue[iterIdx] - bestValue)) / 825.0; + double fallingEval = (142 + 12 * (mainThread->bestPreviousAverageScore - bestValue) + + 6 * (mainThread->iterValue[iterIdx] - bestValue)) / 825.0; fallingEval = std::clamp(fallingEval, 0.5, 1.5); // If the bestMove is stable over several iterations, reduce time accordingly timeReduction = lastBestMoveDepth + 9 < completedDepth ? 1.92 : 0.95; double reduction = (1.47 + mainThread->previousTimeReduction) / (2.32 * timeReduction); - - // Use part of the gained time from a previous stable move for the current move - for (Thread* th : Threads) - { - totBestMoveChanges += th->bestMoveChanges; - th->bestMoveChanges = 0; - } double bestMoveInstability = 1.073 + std::max(1.0, 2.25 - 9.9 / rootDepth) * totBestMoveChanges / Threads.size(); double totalTime = Time.optimum() * fallingEval * reduction * bestMoveInstability; @@ -550,7 +550,7 @@ namespace { if ( ss->ply > 10 && search_explosion(thisThread) == MUST_CALM_DOWN && depth > (ss-1)->depth) - depth = (ss-1)->depth; + depth = (ss-1)->depth; constexpr bool PvNode = nodeType != NonPV; constexpr bool rootNode = nodeType == Root; @@ -587,10 +587,9 @@ namespace { Depth extension, newDepth; Value bestValue, value, ttValue, eval, maxValue, probCutBeta; bool givesCheck, improving, didLMR, priorCapture; - bool captureOrPromotion, doFullDepthSearch, moveCountPruning, - ttCapture, singularQuietLMR; + bool captureOrPromotion, doFullDepthSearch, moveCountPruning, ttCapture; Piece movedPiece; - int moveCount, captureCount, quietCount, bestMoveCount, improvement; + int moveCount, captureCount, quietCount, bestMoveCount, improvement, complexity; // Step 1. Initialize node ss->inCheck = pos.checkers(); @@ -628,6 +627,8 @@ namespace { if (alpha >= beta) return alpha; } + else + thisThread->rootDelta = beta - alpha; assert(0 <= ss->ply && ss->ply < MAX_PLY); @@ -662,36 +663,28 @@ namespace { if (!excludedMove) ss->ttPv = PvNode || (ss->ttHit && tte->is_pv()); - // Update low ply history for previous move if we are near root and position is or has been in PV - if ( ss->ttPv - && depth > 12 - && ss->ply - 1 < MAX_LPH - && !priorCapture - && is_ok((ss-1)->currentMove)) - thisThread->lowPlyHistory[ss->ply - 1][from_to((ss-1)->currentMove)] << stat_bonus(depth - 5); - // 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))) { - // If ttMove is quiet, update move sorting heuristics on TT hit + // If ttMove is quiet, update move sorting heuristics on TT hit (~1 Elo) if (ttMove) { if (ttValue >= beta) { - // Bonus for a quiet ttMove that fails high + // Bonus for a quiet ttMove that fails high (~3 Elo) if (!ttCapture) - update_quiet_stats(pos, ss, ttMove, stat_bonus(depth), depth); + update_quiet_stats(pos, ss, ttMove, stat_bonus(depth)); - // Extra penalty for early quiet moves of the previous ply + // Extra penalty for early quiet moves of the previous ply (~0 Elo) 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 + // Penalty for a quiet ttMove that fails low (~1 Elo) else if (!ttCapture) { int penalty = -stat_bonus(depth); @@ -767,6 +760,7 @@ namespace { ss->staticEval = eval = VALUE_NONE; improving = false; improvement = 0; + complexity = 0; goto moves_loop; } else if (ss->ttHit) @@ -780,7 +774,7 @@ namespace { if (eval == VALUE_DRAW) eval = value_draw(thisThread); - // Can ttValue be used as a better position evaluation? + // ttValue can be used as a better position evaluation (~4 Elo) if ( ttValue != VALUE_NONE && (tte->bound() & (ttValue > eval ? BOUND_LOWER : BOUND_UPPER))) eval = ttValue; @@ -790,14 +784,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 + // Use static evaluation difference to improve quiet move ordering (~3 Elo) 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; } @@ -810,22 +804,23 @@ namespace { : 200; improving = improvement > 0; + complexity = abs(ss->staticEval - (us == WHITE ? eg_value(pos.psq_score()) : -eg_value(pos.psq_score()))); - // Step 7. Futility pruning: child node (~50 Elo). + // Step 7. Futility pruning: child node (~25 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) + // Step 8. Null move search with verification search (~22 Elo) if ( !PvNode && (ss-1)->currentMove != MOVE_NULL && (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 + complexity / 25 && !excludedMove && pos.non_pawn_material(us) && (ss->ply >= thisThread->nmpMinPly || us != thisThread->nmpColor)) @@ -932,7 +927,7 @@ namespace { ss->ttPv = ttPv; } - // Step 10. If the position is not in TT, decrease depth by 2 or 1 depending on node type + // Step 10. If the position is not in TT, decrease depth by 2 or 1 depending on node type (~3 Elo) if ( PvNode && depth >= 6 && !ttMove) @@ -945,9 +940,7 @@ namespace { moves_loop: // When in check, search starts here - int rangeReduction = 0; - - // Step 11. A small Probcut idea, when we are in check + // Step 11. A small Probcut idea, when we are in check (~0 Elo) probCutBeta = beta + 409; if ( ss->inCheck && !PvNode @@ -969,15 +962,13 @@ moves_loop: // When in check, search starts here Move countermove = thisThread->counterMoves[pos.piece_on(prevSq)][prevSq]; MovePicker mp(pos, ttMove, depth, &thisThread->mainHistory, - &thisThread->lowPlyHistory, &captureHistory, contHist, countermove, - ss->killers, - ss->ply); + ss->killers); value = bestValue; - singularQuietLMR = moveCountPruning = false; + moveCountPruning = 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. @@ -1024,60 +1015,70 @@ moves_loop: // When in check, search starts here // Calculate new depth for this move newDepth = depth - 1; - // Step 13. Pruning at shallow depth (~200 Elo). Depth conditions are important for mate finding. + Value delta = beta - alpha; + + // Step 13. Pruning at shallow depth (~98 Elo). Depth conditions are important for mate finding. if ( !rootNode && pos.non_pawn_material(us) && bestValue > VALUE_TB_LOSS_IN_MAX_PLY) { - // Skip quiet moves if movecount exceeds our FutilityMoveCount threshold + // Skip quiet moves if movecount exceeds our FutilityMoveCount threshold (~7 Elo) moveCountPruning = moveCount >= futility_move_count(improving, depth); // Reduced depth of the next LMR search - int lmrDepth = std::max(newDepth - reduction(improving, depth, moveCount, rangeReduction > 2), 0); + int lmrDepth = std::max(newDepth - reduction(improving, depth, moveCount, delta, thisThread->rootDelta), 0); if ( captureOrPromotion || givesCheck) { - // Capture history based pruning when the move doesn't give check - if ( !givesCheck - && lmrDepth < 1 - && captureHistory[movedPiece][to_sq(move)][type_of(pos.piece_on(to_sq(move)))] < 0) + // Futility pruning for captures (~0 Elo) + if ( !pos.empty(to_sq(move)) + && !givesCheck + && !PvNode + && lmrDepth < 6 + && !ss->inCheck + && ss->staticEval + 342 + 238 * lmrDepth + PieceValue[EG][pos.piece_on(to_sq(move))] + + captureHistory[movedPiece][to_sq(move)][type_of(pos.piece_on(to_sq(move)))] / 8 < alpha) continue; - // SEE based pruning - if (!pos.see_ge(move, Value(-218) * depth)) // (~25 Elo) + // SEE based pruning (~9 Elo) + if (!pos.see_ge(move, Value(-217) * depth)) continue; } else { - // 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) + int history = (*contHist[0])[movedPiece][to_sq(move)] + + (*contHist[1])[movedPiece][to_sq(move)] + + (*contHist[3])[movedPiece][to_sq(move)]; + + // Continuation history based pruning (~2 Elo) + if ( lmrDepth < 5 + && history < -3875 * (depth - 1)) continue; - // Futility pruning: parent node (~5 Elo) + history += thisThread->mainHistory[us][from_to(move)]; + + // Futility pruning: parent node (~9 Elo) if ( !ss->inCheck && lmrDepth < 8 - && ss->staticEval + 172 + 145 * lmrDepth <= alpha) + && ss->staticEval + 138 + 137 * lmrDepth + history / 64 <= alpha) continue; - // Prune moves with negative SEE (~20 Elo) + // Prune moves with negative SEE (~3 Elo) if (!pos.see_ge(move, Value(-21 * lmrDepth * lmrDepth - 21 * lmrDepth))) continue; } } - // Step 14. Extensions (~75 Elo) + // Step 14. Extensions (~66 Elo) - // Singular extension search (~70 Elo). If all moves but one fail low on a + // Singular extension search (~58 Elo). If all moves but one fail low on a // search of (alpha-s, beta-s), and just one fails high on (alpha, beta), // 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 ( !rootNode - && depth >= 7 + && depth >= 6 + 2 * (PvNode && tte->is_pv()) && move == ttMove && !excludedMove // Avoid recursive singular search /* && ttValue != VALUE_NONE Already implicit in the next condition */ @@ -1095,7 +1096,6 @@ moves_loop: // When in check, search starts here if (value < singularBeta) { extension = 1; - singularQuietLMR = !ttCapture; // Avoid search explosion by limiting the number of double extensions if ( !PvNode @@ -1117,19 +1117,13 @@ moves_loop: // When in check, search starts here extension = -2; } - // Capture extensions for PvNodes and cutNodes - else if ( (PvNode || cutNode) - && captureOrPromotion - && moveCount != 1) - extension = 1; - - // Check extensions + // Check extensions (~1 Elo) else if ( givesCheck && depth > 6 && abs(ss->staticEval) > 100) extension = 1; - // Quiet ttMove extensions + // Quiet ttMove extensions (~0 Elo) else if ( PvNode && move == ttMove && move == ss->killers[0] @@ -1153,20 +1147,21 @@ moves_loop: // When in check, search starts here // Step 15. Make the move pos.do_move(move, st, givesCheck); - // Step 16. Late moves reduction / extension (LMR, ~200 Elo) + bool doDeeperSearch = false; + + // Step 16. Late moves reduction / extension (LMR, ~98 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 // 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); + Depth r = reduction(improving, depth, moveCount, delta, thisThread->rootDelta); - // Decrease reduction if on the PV (~2 Elo) + // Decrease reduction at some PvNodes (~2 Elo) if ( PvNode && bestMoveCount <= 3) r--; @@ -1177,19 +1172,10 @@ moves_loop: // When in check, search starts here && !likelyFailLow) r -= 2; - // Increase reduction at root and non-PV nodes when the best move does not change frequently - if ( (rootNode || !PvNode) - && thisThread->bestMoveChanges <= 2) - r++; - // Decrease reduction if opponent's move count is high (~1 Elo) if ((ss-1)->moveCount > 13) r--; - // Decrease reduction if ttMove has been singularly extended (~1 Elo) - if (singularQuietLMR) - r--; - // Increase reduction for cut nodes (~3 Elo) if (cutNode && move != ss->killers[0]) r += 2; @@ -1211,21 +1197,18 @@ 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); value = -search(pos, ss+1, -(alpha+1), -alpha, d, true); - // Range reductions (~3 Elo) - if (ss->staticEval - value < 30 && depth > 7) - rangeReduction++; - // If the son is reduced and fails high it will be re-searched at full depth doFullDepthSearch = value > alpha && d < newDepth; + doDeeperSearch = value > (alpha + 62 + 20 * (newDepth - d)); didLMR = true; } else @@ -1237,7 +1220,7 @@ moves_loop: // When in check, search starts here // Step 17. Full depth search when LMR is skipped or fails high if (doFullDepthSearch) { - value = -search(pos, ss+1, -(alpha+1), -alpha, newDepth, !cutNode); + value = -search(pos, ss+1, -(alpha+1), -alpha, newDepth + doDeeperSearch, !cutNode); // If the move passed LMR update its stats if (didLMR && !captureOrPromotion) @@ -1278,6 +1261,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) { @@ -1291,7 +1276,7 @@ moves_loop: // When in check, search starts here rm.pv.push_back(*m); // We record how often the best move has been changed in each iteration. - // This information is used for time management and LMR. In MultiPV mode, + // This information is used for time management. In MultiPV mode, // we must take care to only do this for the first PV line. if ( moveCount > 1 && !thisThread->pvIdx) @@ -1367,7 +1352,15 @@ moves_loop: // When in check, search starts here // Bonus for prior countermove that caused the fail low else if ( (depth >= 3 || PvNode) && !priorCapture) - update_continuation_histories(ss-1, pos.piece_on(prevSq), prevSq, stat_bonus(depth) * (1 + (PvNode || cutNode))); + { + //Assign extra bonus if current node is PvNode or cutNode + //or fail low was really bad + bool extraBonus = PvNode + || cutNode + || bestValue < alpha - 94 * depth; + + update_continuation_histories(ss-1, pos.piece_on(prevSq), prevSq, stat_bonus(depth) * (1 + extraBonus)); + } if (PvNode) bestValue = std::min(bestValue, maxValue); @@ -1414,13 +1407,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; } @@ -1471,7 +1463,7 @@ moves_loop: // When in check, search starts here if ((ss->staticEval = bestValue = tte->eval()) == VALUE_NONE) ss->staticEval = bestValue = evaluate(pos); - // Can ttValue be used as a better position evaluation? + // ttValue can be used as a better position evaluation (~7 Elo) if ( ttValue != VALUE_NONE && (tte->bound() & (ttValue > bestValue ? BOUND_LOWER : BOUND_UPPER))) bestValue = ttValue; @@ -1507,10 +1499,11 @@ 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 = to_sq((ss-1)->currentMove); MovePicker mp(pos, ttMove, depth, &thisThread->mainHistory, &thisThread->captureHistory, contHist, - to_sq((ss-1)->currentMove)); + prevSq); // Loop through the moves until no moves remain or a beta cutoff occurs while ((move = mp.next_move()) != MOVE_NONE) @@ -1526,9 +1519,10 @@ moves_loop: // When in check, search starts here moveCount++; - // Futility pruning and moveCount pruning + // Futility pruning and moveCount pruning (~5 Elo) if ( bestValue > VALUE_TB_LOSS_IN_MAX_PLY && !givesCheck + && to_sq(move) != prevSq && futilityBase > -VALUE_KNOWN_WIN && type_of(move) != PROMOTION) { @@ -1551,7 +1545,7 @@ moves_loop: // When in check, search starts here } } - // Do not search moves with negative SEE values + // Do not search moves with negative SEE values (~5 Elo) if ( bestValue > VALUE_TB_LOSS_IN_MAX_PLY && !pos.see_ge(move)) continue; @@ -1565,7 +1559,7 @@ moves_loop: // When in check, search starts here [pos.moved_piece(move)] [to_sq(move)]; - // Continuation history based pruning + // Continuation history based pruning (~2 Elo) if ( !captureOrPromotion && bestValue > VALUE_TB_LOSS_IN_MAX_PLY && (*contHist[0])[pos.moved_piece(move)][to_sq(move)] < CounterMovePruneThreshold @@ -1610,8 +1604,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); @@ -1693,7 +1686,7 @@ moves_loop: // When in check, search starts here if (!pos.capture_or_promotion(bestMove)) { // Increase stats for the best move in case it was a quiet move - update_quiet_stats(pos, ss, bestMove, bonus2, depth); + update_quiet_stats(pos, ss, bestMove, bonus2); // Decrease stats for all non-best quiet moves for (int i = 0; i < quietCount; ++i) @@ -1740,7 +1733,7 @@ moves_loop: // When in check, search starts here // update_quiet_stats() updates move sorting heuristics - void update_quiet_stats(const Position& pos, Stack* ss, Move move, int bonus, int depth) { + void update_quiet_stats(const Position& pos, Stack* ss, Move move, int bonus) { // Update killers if (ss->killers[0] != move) @@ -1754,20 +1747,12 @@ 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)) { Square prevSq = to_sq((ss-1)->currentMove); thisThread->counterMoves[pos.piece_on(prevSq)][prevSq] = move; } - - // Update low ply history - if (depth > 11 && ss->ply < MAX_LPH) - thisThread->lowPlyHistory[ss->ply][from_to(move)] << stat_bonus(depth - 7); } // When playing with strength handicap, choose best move among a set of RootMoves @@ -1781,8 +1766,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 +1775,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) {