X-Git-Url: https://git.sesse.net/?p=stockfish;a=blobdiff_plain;f=src%2Fsearch.cpp;h=c369bac3a98d0f64c2336f3cab725e380bc384ed;hp=f981664dbb9255fd2efb75c7ef13b11e3d90e112;hb=14dbeb22dd04f0954322a58c26833506fb4532a9;hpb=7bcd97933a20b649964bf96eb840a6190e777428 diff --git a/src/search.cpp b/src/search.cpp index f981664d..c369bac3 100644 --- a/src/search.cpp +++ b/src/search.cpp @@ -158,56 +158,80 @@ namespace { }; - /// Constants + /// Adjustments - // Search depth at iteration 1 - const Depth InitialDepth = OnePly; + // Step 6. Razoring - // Use internal iterative deepening? - const bool UseIIDAtPVNodes = true; - const bool UseIIDAtNonPVNodes = true; + // Maximum depth for razoring + const Depth RazorDepth = 4 * OnePly; - // Internal iterative deepening margin. At Non-PV moves, when - // UseIIDAtNonPVNodes is true, we do an internal iterative deepening - // search when the static evaluation is at most IIDMargin below beta. - const Value IIDMargin = Value(0x100); + // Dynamic razoring margin based on depth + inline Value razor_margin(Depth d) { return Value(0x200 + 0x10 * d); } - // Easy move margin. An easy move candidate must be at least this much - // better than the second best move. - const Value EasyMoveMargin = Value(0x200); + // Step 8. Null move search with verification search // Null move margin. A null move search will not be done if the static // evaluation of the position is more than NullMoveMargin below beta. const Value NullMoveMargin = Value(0x200); - // If the TT move is at least SingleReplyMargin better then the - // remaining ones we will extend it. - const Value SingleReplyMargin = Value(0x20); + // Maximum depth for use of dynamic threat detection when null move fails low + const Depth ThreatDepth = 5 * OnePly; - // Depth limit for razoring - const Depth RazorDepth = 4 * OnePly; + // Step 9. Internal iterative deepening - /// Lookup tables initialized at startup + // Minimum depth for use of internal iterative deepening + const Depth IIDDepthAtPVNodes = 5 * OnePly; + const Depth IIDDepthAtNonPVNodes = 8 * OnePly; - // Reduction lookup tables and their getter functions - int8_t PVReductionMatrix[64][64]; // [depth][moveNumber] - int8_t NonPVReductionMatrix[64][64]; // [depth][moveNumber] + // Internal iterative deepening margin. At Non-PV nodes + // we do an internal iterative deepening + // search when the static evaluation is at most IIDMargin below beta. + const Value IIDMargin = Value(0x100); - inline Depth pv_reduction(Depth d, int mn) { return (Depth) PVReductionMatrix[Min(d / 2, 63)][Min(mn, 63)]; } - inline Depth nonpv_reduction(Depth d, int mn) { return (Depth) NonPVReductionMatrix[Min(d / 2, 63)][Min(mn, 63)]; } + // Step 11. Decide the new search depth + + // Extensions. Configurable UCI options. + // Array index 0 is used at non-PV nodes, index 1 at PV nodes. + Depth CheckExtension[2], SingleEvasionExtension[2], PawnPushTo7thExtension[2]; + Depth PassedPawnExtension[2], PawnEndgameExtension[2], MateThreatExtension[2]; + + // Minimum depth for use of singular extension + const Depth SingularExtensionDepthAtPVNodes = 6 * OnePly; + const Depth SingularExtensionDepthAtNonPVNodes = 8 * OnePly; + + // If the TT move is at least SingularExtensionMargin better then the + // remaining ones we will extend it. + const Value SingularExtensionMargin = Value(0x20); + + // Step 12. Futility pruning - // Futility lookup tables and their getter functions + // Futility margin for quiescence search const Value FutilityMarginQS = Value(0x80); + + // Futility lookup tables (initialized at startup) and their getter functions int32_t FutilityMarginsMatrix[14][64]; // [depth][moveNumber] int FutilityMoveCountArray[32]; // [depth] inline Value futility_margin(Depth d, int mn) { return Value(d < 7*OnePly ? FutilityMarginsMatrix[Max(d, 0)][Min(mn, 63)] : 2 * VALUE_INFINITE); } inline int futility_move_count(Depth d) { return d < 16*OnePly ? FutilityMoveCountArray[d] : 512; } - /// Variables initialized by UCI options + // Step 14. Reduced search + + // Reduction lookup tables (initialized at startup) and their getter functions + int8_t PVReductionMatrix[64][64]; // [depth][moveNumber] + int8_t NonPVReductionMatrix[64][64]; // [depth][moveNumber] + + inline Depth pv_reduction(Depth d, int mn) { return (Depth) PVReductionMatrix[Min(d / 2, 63)][Min(mn, 63)]; } + inline Depth nonpv_reduction(Depth d, int mn) { return (Depth) NonPVReductionMatrix[Min(d / 2, 63)][Min(mn, 63)]; } - // Depth limit for use of dynamic threat detection - Depth ThreatDepth; + // Step. Common adjustments + + // Search depth at iteration 1 + const Depth InitialDepth = OnePly; + + // Easy move margin. An easy move candidate must be at least this much + // better than the second best move. + const Value EasyMoveMargin = Value(0x200); // Last seconds noise filtering (LSN) const bool UseLSNFiltering = true; @@ -215,9 +239,8 @@ namespace { const Value LSNValue = value_from_centipawns(200); bool loseOnTime = false; - // Extensions. Array index 0 is used at non-PV nodes, index 1 at PV nodes. - Depth CheckExtension[2], SingleEvasionExtension[2], PawnPushTo7thExtension[2]; - Depth PassedPawnExtension[2], PawnEndgameExtension[2], MateThreatExtension[2]; + + /// Global variables // Iteration counters int Iteration; @@ -413,8 +436,6 @@ bool think(const Position& pos, bool infinite, bool ponder, int side_to_move, MateThreatExtension[1] = Depth(get_option_value_int("Mate Threat Extension (PV nodes)")); MateThreatExtension[0] = Depth(get_option_value_int("Mate Threat Extension (non-PV nodes)")); - ThreatDepth = get_option_value_int("Threat Depth") * OnePly; - Chess960 = get_option_value_bool("UCI_Chess960"); ShowCurrentLine = get_option_value_bool("UCI_ShowCurrLine"); UseLogFile = get_option_value_bool("Use Search Log"); @@ -1039,14 +1060,16 @@ namespace { assert(threadID >= 0 && threadID < TM.active_threads()); Move movesSearched[256]; + EvalInfo ei; StateInfo st; const TTEntry* tte; Move ttMove, move; Depth ext, newDepth; - Value oldAlpha, value; - bool isCheck, mateThreat, singleEvasion, moveIsCheck, captureOrPromotion, dangerous; + Value bestValue, value, oldAlpha; + bool isCheck, singleEvasion, moveIsCheck, captureOrPromotion, dangerous; + bool mateThreat = false; int moveCount = 0; - Value bestValue = value = -VALUE_INFINITE; + bestValue = value = -VALUE_INFINITE; if (depth < OnePly) return qsearch(pos, ss, alpha, beta, Depth(0), ply, threadID); @@ -1085,7 +1108,6 @@ namespace { isCheck = pos.is_check(); if (!isCheck) { - EvalInfo ei; ss[ply].eval = evaluate(pos, ei, threadID); update_gains(pos, ss[ply - 1].currentMove, ss[ply - 1].eval, ss[ply].eval); } @@ -1095,8 +1117,7 @@ namespace { // Step 8. Null move search with verification search (is omitted in PV nodes) // Step 9. Internal iterative deepening - if ( UseIIDAtPVNodes - && depth >= 5*OnePly + if ( depth >= IIDDepthAtPVNodes && ttMove == MOVE_NONE) { search_pv(pos, ss, alpha, beta, depth-2*OnePly, ply, threadID); @@ -1128,7 +1149,7 @@ namespace { // Singular extension search. We extend the TT move if its value is much better than // its siblings. To verify this we do a reduced search on all the other moves but the // ttMove, if result is lower then ttValue minus a margin then we extend ttMove. - if ( depth >= 6 * OnePly + if ( depth >= SingularExtensionDepthAtPVNodes && tte && move == tte->move() && ext < OnePly @@ -1139,9 +1160,9 @@ namespace { if (abs(ttValue) < VALUE_KNOWN_WIN) { - Value excValue = search(pos, ss, ttValue - SingleReplyMargin, depth / 2, ply, false, threadID, move); + Value excValue = search(pos, ss, ttValue - SingularExtensionMargin, depth / 2, ply, false, threadID, move); - if (excValue < ttValue - SingleReplyMargin) + if (excValue < ttValue - SingularExtensionMargin) ext = OnePly; } } @@ -1331,15 +1352,15 @@ namespace { if ( !value_is_mate(beta) && !isCheck && depth < RazorDepth - && refinedValue < beta - (0x200 + 16 * depth) + && refinedValue < beta - razor_margin(depth) && ss[ply - 1].currentMove != MOVE_NULL && ttMove == MOVE_NONE && !pos.has_pawn_on_7th(pos.side_to_move())) { - Value rbeta = beta - (0x200 + 16 * depth); + Value rbeta = beta - razor_margin(depth); Value v = qsearch(pos, ss, rbeta-1, rbeta, Depth(0), ply, threadID); if (v < rbeta) - return v; //FIXME: Logically should be: return (v + 0x200 + 16 * depth); + return v; //FIXME: Logically should be: return (v + razor_margin(depth)); } // Step 7. Static null move pruning @@ -1405,8 +1426,10 @@ namespace { } // Step 9. Internal iterative deepening - if (UseIIDAtNonPVNodes && ttMove == MOVE_NONE && depth >= 8*OnePly && - !isCheck && ss[ply].eval >= beta - IIDMargin) + if ( depth >= IIDDepthAtNonPVNodes + && ttMove == MOVE_NONE + && !isCheck + && ss[ply].eval >= beta - IIDMargin) { search(pos, ss, beta, depth/2, ply, false, threadID); ttMove = ss[ply].pv[ply]; @@ -1417,7 +1440,7 @@ namespace { // Loop through all legal moves until no moves remain or a beta cutoff occurs // Initialize a MovePicker object for the current position - MovePicker mp = MovePicker(pos, ttMove, depth, H, &ss[ply]); + MovePicker mp = MovePicker(pos, ttMove, depth, H, &ss[ply], beta); CheckInfo ci(pos); while ( bestValue < beta @@ -1439,7 +1462,7 @@ namespace { // Singular extension search. We extend the TT move if its value is much better than // its siblings. To verify this we do a reduced search on all the other moves but the // ttMove, if result is lower then ttValue minus a margin then we extend ttMove. - if ( depth >= 8 * OnePly + if ( depth >= SingularExtensionDepthAtNonPVNodes && tte && move == tte->move() && !excludedMove // Do not allow recursive single-reply search @@ -1451,9 +1474,9 @@ namespace { if (abs(ttValue) < VALUE_KNOWN_WIN) { - Value excValue = search(pos, ss, ttValue - SingleReplyMargin, depth / 2, ply, false, threadID, move); + Value excValue = search(pos, ss, ttValue - SingularExtensionMargin, depth / 2, ply, false, threadID, move); - if (excValue < ttValue - SingleReplyMargin) + if (excValue < ttValue - SingularExtensionMargin) ext = OnePly; } } @@ -1477,7 +1500,7 @@ namespace { continue; // Value based pruning - Depth predictedDepth = newDepth - nonpv_reduction(depth, moveCount); //FIXME: We are ignoring condition: depth >= 3*OnePly, BUG?? + Depth predictedDepth = newDepth - nonpv_reduction(depth, moveCount); // We illogically ignore reduction condition depth >= 3*OnePly futilityValueScaled = ss[ply].eval + futility_margin(predictedDepth, moveCount) + H.gain(pos.piece_on(move_from(move)), move_to(move)) + 45; @@ -1778,20 +1801,25 @@ namespace { // splitting, we don't have to repeat all this work in sp_search(). We // also don't need to store anything to the hash table here: This is taken // care of after we return from the split point. + // FIXME: We are currently ignoring mateThreat flag here void sp_search(SplitPoint* sp, int threadID) { assert(threadID >= 0 && threadID < TM.active_threads()); assert(TM.active_threads() > 1); - Position pos(*sp->pos); - CheckInfo ci(pos); - SearchStack* ss = sp->sstack[threadID]; StateInfo st; - Value value = -VALUE_INFINITE; Move move; + Depth ext, newDepth; + Value value, futilityValueScaled; + bool isCheck, moveIsCheck, captureOrPromotion, dangerous; int moveCount; - bool isCheck = pos.is_check(); + value = -VALUE_INFINITE; + + Position pos(*sp->pos); + CheckInfo ci(pos); + SearchStack* ss = sp->sstack[threadID]; + isCheck = pos.is_check(); // Step 10. Loop through moves // Loop through all legal moves until no moves remain or a beta cutoff occurs @@ -1806,13 +1834,12 @@ namespace { assert(move_is_ok(move)); - bool moveIsCheck = pos.move_is_check(move, ci); - bool captureOrPromotion = pos.move_is_capture_or_promotion(move); + moveIsCheck = pos.move_is_check(move, ci); + captureOrPromotion = pos.move_is_capture_or_promotion(move); // Step 11. Decide the new search depth - bool dangerous; - Depth ext = extension(pos, move, false, captureOrPromotion, moveIsCheck, false, false, &dangerous); - Depth newDepth = sp->depth - OnePly + ext; + ext = extension(pos, move, false, captureOrPromotion, moveIsCheck, false, false, &dangerous); + newDepth = sp->depth - OnePly + ext; // Update current move ss[sp->ply].currentMove = move; @@ -1834,7 +1861,7 @@ namespace { // Value based pruning Depth predictedDepth = newDepth - nonpv_reduction(sp->depth, moveCount); - Value futilityValueScaled = ss[sp->ply].eval + futility_margin(predictedDepth, moveCount) + futilityValueScaled = ss[sp->ply].eval + futility_margin(predictedDepth, moveCount) + H.gain(pos.piece_on(move_from(move)), move_to(move)) + 45; if (futilityValueScaled < sp->beta) @@ -1909,19 +1936,24 @@ namespace { // don't have to repeat all this work in sp_search_pv(). We also don't // need to store anything to the hash table here: This is taken care of // after we return from the split point. + // FIXME: We are ignoring mateThreat flag! void sp_search_pv(SplitPoint* sp, int threadID) { assert(threadID >= 0 && threadID < TM.active_threads()); assert(TM.active_threads() > 1); + StateInfo st; + Move move; + Depth ext, newDepth; + Value value; + bool moveIsCheck, captureOrPromotion, dangerous; + int moveCount; + value = -VALUE_INFINITE; + Position pos(*sp->pos); CheckInfo ci(pos); SearchStack* ss = sp->sstack[threadID]; - StateInfo st; - Value value = -VALUE_INFINITE; - int moveCount; - Move move; // Step 10. Loop through moves // Loop through all legal moves until no moves remain or a beta cutoff occurs @@ -1936,13 +1968,12 @@ namespace { assert(move_is_ok(move)); - bool moveIsCheck = pos.move_is_check(move, ci); - bool captureOrPromotion = pos.move_is_capture_or_promotion(move); + moveIsCheck = pos.move_is_check(move, ci); + captureOrPromotion = pos.move_is_capture_or_promotion(move); // Step 11. Decide the new search depth - bool dangerous; - Depth ext = extension(pos, move, true, captureOrPromotion, moveIsCheck, false, false, &dangerous); - Depth newDepth = sp->depth - OnePly + ext; + ext = extension(pos, move, true, captureOrPromotion, moveIsCheck, false, false, &dangerous); + newDepth = sp->depth - OnePly + ext; // Update current move ss[sp->ply].currentMove = move; @@ -2968,9 +2999,6 @@ namespace { if (ActiveThreads == 1) return; - for (int i = 1; i < ActiveThreads; i++) - assert(threads[i].state == THREAD_SLEEPING); - #if !defined(_MSC_VER) pthread_mutex_lock(&WaitLock); pthread_cond_broadcast(&WaitCond);