X-Git-Url: https://git.sesse.net/?p=stockfish;a=blobdiff_plain;f=src%2Fsearch.cpp;h=8099787ec71980751e8fa826f641e058326e0609;hp=37a962663fd241434642d09c89c760682483a8b1;hb=d29a68f5854d0b529f2e0447fddcc6a61200c5aa;hpb=adeded29fb6ce483bbbafaa0f67aa086cad968f9 diff --git a/src/search.cpp b/src/search.cpp index 37a96266..8099787e 100644 --- a/src/search.cpp +++ b/src/search.cpp @@ -19,7 +19,6 @@ #include #include -#include #include #include #include @@ -28,13 +27,12 @@ #include "evaluate.h" #include "movegen.h" #include "movepick.h" -#include "notation.h" #include "rkiss.h" #include "search.h" #include "timeman.h" #include "thread.h" #include "tt.h" -#include "ucioption.h" +#include "uci.h" namespace Search { @@ -52,34 +50,27 @@ using namespace Search; namespace { - // Set to true to force running with one thread. Used for debugging - const bool FakeSplit = false; - // Different node types, used as template parameter enum NodeType { Root, PV, NonPV }; // Dynamic razoring margin based on depth - inline Value razor_margin(Depth d) { return Value(512 + 16 * d); } + inline Value razor_margin(Depth d) { return Value(512 + 32 * d); } // Futility lookup tables (initialized at startup) and their access functions int FutilityMoveCounts[2][32]; // [improving][depth] inline Value futility_margin(Depth d) { - return Value(100 * d); + return Value(200 * d); } // Reduction lookup tables (initialized at startup) and their access function int8_t Reductions[2][2][64][64]; // [pv][improving][depth][moveNumber] template inline Depth reduction(bool i, Depth d, int mn) { - - return (Depth) Reductions[PvNode][i][std::min(int(d) / ONE_PLY, 63)][std::min(mn, 63)]; + return (Depth) Reductions[PvNode][i][std::min(int(d), 63)][std::min(mn, 63)]; } - // Tempo bonus. Must be handled by search to preserve eval symmetry. - const int Tempo = 17; - - size_t MultiPV, PVIdx; + size_t PVIdx; TimeManager TimeMgr; double BestMoveChanges; Value DrawValue[COLOR_NB]; @@ -100,18 +91,21 @@ namespace { string uci_pv(const Position& pos, int depth, Value alpha, Value beta); struct Skill { - Skill(int l) : level(l), best(MOVE_NONE) {} + Skill(int l, size_t rootSize) : level(l), + candidates(l < 20 ? std::min(4, (int)rootSize) : 0), + best(MOVE_NONE) {} ~Skill() { - if (enabled()) // Swap best PV line with the sub-optimal one + if (candidates) // Swap best PV line with the sub-optimal one std::swap(RootMoves[0], *std::find(RootMoves.begin(), RootMoves.end(), best ? best : pick_move())); } - bool enabled() const { return level < 20; } + size_t candidates_size() const { return candidates; } bool time_to_pick(int depth) const { return depth == 1 + level; } Move pick_move(); int level; + size_t candidates; Move best; }; @@ -131,50 +125,55 @@ void Search::init() { { double pvRed = 0.00 + log(double(hd)) * log(double(mc)) / 3.00; double nonPVRed = 0.33 + log(double(hd)) * log(double(mc)) / 2.25; - Reductions[1][1][hd][mc] = int8_t( pvRed >= 1.0 ? pvRed * int(ONE_PLY) : 0); - Reductions[0][1][hd][mc] = int8_t(nonPVRed >= 1.0 ? nonPVRed * int(ONE_PLY) : 0); + + Reductions[1][1][hd][mc] = int8_t( pvRed >= 1.0 ? pvRed + 0.5: 0); + Reductions[0][1][hd][mc] = int8_t(nonPVRed >= 1.0 ? nonPVRed + 0.5: 0); Reductions[1][0][hd][mc] = Reductions[1][1][hd][mc]; Reductions[0][0][hd][mc] = Reductions[0][1][hd][mc]; - if (Reductions[0][0][hd][mc] > 2 * ONE_PLY) - Reductions[0][0][hd][mc] += ONE_PLY; - - else if (Reductions[0][0][hd][mc] > 1 * ONE_PLY) - Reductions[0][0][hd][mc] += ONE_PLY / 2; + if (Reductions[0][0][hd][mc] >= 2) + Reductions[0][0][hd][mc] += 1; } // Init futility move count array for (d = 0; d < 32; ++d) { - FutilityMoveCounts[0][d] = int(2.4 + 0.222 * pow(d + 0.00, 1.8)); - FutilityMoveCounts[1][d] = int(3.0 + 0.300 * pow(d + 0.98, 1.8)); + FutilityMoveCounts[0][d] = int(2.4 + 0.773 * pow(d + 0.00, 1.8)); + FutilityMoveCounts[1][d] = int(2.9 + 1.045 * pow(d + 0.49, 1.8)); } } /// Search::perft() is our utility to verify move generation. All the leaf nodes /// up to the given depth are generated and counted and the sum returned. - -static uint64_t perft(Position& pos, Depth depth) { +template +uint64_t Search::perft(Position& pos, Depth depth) { StateInfo st; - uint64_t cnt = 0; + uint64_t cnt, nodes = 0; CheckInfo ci(pos); - const bool leaf = depth == 2 * ONE_PLY; + const bool leaf = (depth == 2 * ONE_PLY); for (MoveList it(pos); *it; ++it) { - pos.do_move(*it, st, ci, pos.gives_check(*it, ci)); - cnt += leaf ? MoveList(pos).size() : ::perft(pos, depth - ONE_PLY); - pos.undo_move(*it); + if (Root && depth <= ONE_PLY) + cnt = 1, nodes++; + else + { + pos.do_move(*it, st, ci, pos.gives_check(*it, ci)); + cnt = leaf ? MoveList(pos).size() : perft(pos, depth - ONE_PLY); + nodes += cnt; + pos.undo_move(*it); + } + if (Root) + sync_cout << UCI::format_move(*it, pos.is_chess960()) << ": " << cnt << sync_endl; } - return cnt; + return nodes; } -uint64_t Search::perft(Position& pos, Depth depth) { - return depth > ONE_PLY ? ::perft(pos, depth) : MoveList(pos).size(); -} +template uint64_t Search::perft(Position& pos, Depth depth); + /// Search::think() is the external interface to Stockfish's search, and is /// called by the main thread when the program receives the UCI 'go' command. It @@ -184,7 +183,7 @@ void Search::think() { TimeMgr.init(Limits, RootPos.game_ply(), RootPos.side_to_move()); - int cf = Options["Contempt Factor"] * PawnValueEg / 100; // From centipawns + int cf = Options["Contempt"] * PawnValueEg / 100; // From centipawns DrawValue[ RootPos.side_to_move()] = VALUE_DRAW - Value(cf); DrawValue[~RootPos.side_to_move()] = VALUE_DRAW + Value(cf); @@ -192,24 +191,12 @@ void Search::think() { { RootMoves.push_back(MOVE_NONE); sync_cout << "info depth 0 score " - << score_to_uci(RootPos.checkers() ? -VALUE_MATE : VALUE_DRAW) + << UCI::format_value(RootPos.checkers() ? -VALUE_MATE : VALUE_DRAW) << sync_endl; goto finalize; } - if (Options["Write Search Log"]) - { - Log log(Options["Search Log Filename"]); - log << "\nSearching: " << RootPos.fen() - << "\ninfinite: " << Limits.infinite - << " ponder: " << Limits.ponder - << " time: " << Limits.time[RootPos.side_to_move()] - << " increment: " << Limits.inc[RootPos.side_to_move()] - << " moves to go: " << Limits.movestogo - << "\n" << std::endl; - } - // Reset the threads, still sleeping: will wake up at split time for (size_t i = 0; i < Threads.size(); ++i) Threads[i]->maxPly = 0; @@ -221,21 +208,6 @@ void Search::think() { Threads.timer->run = false; // Stop the timer - if (Options["Write Search Log"]) - { - Time::point elapsed = Time::now() - SearchTime + 1; - - Log log(Options["Search Log Filename"]); - log << "Nodes: " << RootPos.nodes_searched() - << "\nNodes/second: " << RootPos.nodes_searched() * 1000 / elapsed - << "\nBest move: " << move_to_san(RootPos, RootMoves[0].pv[0]); - - StateInfo st; - RootPos.do_move(RootMoves[0].pv[0], st); - log << "\nPonder move: " << move_to_san(RootPos, RootMoves[0].pv[1]) << std::endl; - RootPos.undo_move(RootMoves[0].pv[0]); - } - finalize: // When search is stopped this info is not printed @@ -254,8 +226,8 @@ finalize: } // Best move could be MOVE_NONE when searching on a stalemate position - sync_cout << "bestmove " << move_to_uci(RootMoves[0].pv[0], RootPos.is_chess960()) - << " ponder " << move_to_uci(RootMoves[0].pv[1], RootPos.is_chess960()) + sync_cout << "bestmove " << UCI::format_move(RootMoves[0].pv[0], RootPos.is_chess960()) + << " ponder " << UCI::format_move(RootMoves[0].pv[1], RootPos.is_chess960()) << sync_endl; } @@ -268,12 +240,11 @@ namespace { void id_loop(Position& pos) { - Stack stack[MAX_PLY_PLUS_6], *ss = stack+2; // To allow referencing (ss-2) + Stack stack[MAX_PLY+4], *ss = stack+2; // To allow referencing (ss-2) and (ss+2) int depth; Value bestValue, alpha, beta, delta; std::memset(ss-2, 0, 5 * sizeof(Stack)); - (ss-1)->currentMove = MOVE_NULL; // Hack to skip update gains depth = 0; BestMoveChanges = 0; @@ -286,18 +257,15 @@ namespace { Countermoves.clear(); Followupmoves.clear(); - MultiPV = Options["MultiPV"]; - Skill skill(Options["Skill Level"]); + size_t multiPV = Options["MultiPV"]; + Skill skill(Options["Skill Level"], RootMoves.size()); // Do we have to play with skill handicap? In this case enable MultiPV search // that we will use behind the scenes to retrieve a set of possible moves. - if (skill.enabled() && MultiPV < 4) - MultiPV = 4; - - MultiPV = std::min(MultiPV, RootMoves.size()); + multiPV = std::max(multiPV, skill.candidates_size()); // Iterative deepening loop until requested to stop or target depth reached - while (++depth <= MAX_PLY && !Signals.stop && (!Limits.depth || depth <= Limits.depth)) + while (++depth < MAX_PLY && !Signals.stop && (!Limits.depth || depth <= Limits.depth)) { // Age out PV variability metric BestMoveChanges *= 0.5; @@ -308,7 +276,7 @@ namespace { RootMoves[i].prevScore = RootMoves[i].score; // MultiPV loop. We perform a full root search for each PV line - for (PVIdx = 0; PVIdx < MultiPV && !Signals.stop; ++PVIdx) + for (PVIdx = 0; PVIdx < std::min(multiPV, RootMoves.size()) && !Signals.stop; ++PVIdx) { // Reset aspiration window starting size if (depth >= 5) @@ -365,7 +333,7 @@ namespace { else break; - delta += delta / 2; + delta += 3 * delta / 8; assert(alpha >= -VALUE_INFINITE && beta <= VALUE_INFINITE); } @@ -373,25 +341,16 @@ namespace { // Sort the PV lines searched so far and update the GUI std::stable_sort(RootMoves.begin(), RootMoves.begin() + PVIdx + 1); - if (PVIdx + 1 == MultiPV || Time::now() - SearchTime > 3000) + if ( !Signals.stop + && ( PVIdx + 1 == std::min(multiPV, RootMoves.size()) + || Time::now() - SearchTime > 3000)) sync_cout << uci_pv(pos, depth, alpha, beta) << sync_endl; } // If skill levels are enabled and time is up, pick a sub-optimal best move - if (skill.enabled() && skill.time_to_pick(depth)) + if (skill.candidates_size() && skill.time_to_pick(depth)) skill.pick_move(); - if (Options["Write Search Log"]) - { - RootMove& rm = RootMoves[0]; - if (skill.best != MOVE_NONE) - rm = *std::find(RootMoves.begin(), RootMoves.end(), skill.best); - - Log log(Options["Search Log Filename"]); - log << pretty_pv(pos, depth, rm.score, Time::now() - SearchTime, &rm.pv[0]) - << std::endl; - } - // Have we found a "mate in x"? if ( Limits.mate && bestValue >= VALUE_MATE_IN_MAX_PLY @@ -402,7 +361,7 @@ namespace { if (Limits.use_time_management() && !Signals.stop && !Signals.stopOnPonderhit) { // Take some extra time if the best move has changed - if (depth > 4 && depth < 50 && MultiPV == 1) + if (depth > 4 && multiPV == 1) TimeMgr.pv_instability(BestMoveChanges); // Stop the search if only one legal move is available or all @@ -471,10 +430,7 @@ namespace { moveCount = quietCount = 0; bestValue = -VALUE_INFINITE; - ss->currentMove = ss->ttMove = (ss+1)->excludedMove = bestMove = MOVE_NONE; ss->ply = (ss-1)->ply + 1; - (ss+1)->skipNullMove = (ss+1)->nullChild = false; (ss+1)->reduction = DEPTH_ZERO; - (ss+2)->killers[0] = (ss+2)->killers[1] = MOVE_NONE; // Used to send selDepth info to GUI if (PvNode && thisThread->maxPly < ss->ply) @@ -483,8 +439,8 @@ namespace { if (!RootNode) { // Step 2. Check for aborted search and immediate draw - if (Signals.stop || pos.is_draw() || ss->ply > MAX_PLY) - return ss->ply > MAX_PLY && !inCheck ? evaluate(pos) + Tempo : DrawValue[pos.side_to_move()]; + if (Signals.stop || pos.is_draw() || ss->ply >= MAX_PLY) + return ss->ply >= MAX_PLY && !inCheck ? evaluate(pos) : DrawValue[pos.side_to_move()]; // Step 3. Mate distance pruning. Even if we mate at the next move our score // would be at best mate_in(ss->ply+1), but if alpha is already bigger because @@ -498,6 +454,12 @@ namespace { return alpha; } + assert(0 <= ss->ply && ss->ply < MAX_PLY); + + ss->currentMove = ss->ttMove = (ss+1)->excludedMove = bestMove = MOVE_NONE; + (ss+1)->skipNullMove = false; (ss+1)->reduction = DEPTH_ZERO; + (ss+2)->killers[0] = (ss+2)->killers[1] = MOVE_NONE; + // 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. @@ -539,7 +501,7 @@ namespace { { // Never assume anything on values stored in TT if ((ss->staticEval = eval = tte->eval_value()) == VALUE_NONE) - eval = ss->staticEval = evaluate(pos) + Tempo; + eval = ss->staticEval = evaluate(pos); // Can ttValue be used as a better position evaluation? if (ttValue != VALUE_NONE) @@ -548,7 +510,9 @@ namespace { } else { - eval = ss->staticEval = ss->nullChild ? -(ss-1)->staticEval + 2 * Tempo : evaluate(pos) + Tempo; + eval = ss->staticEval = + (ss-1)->currentMove != MOVE_NULL ? evaluate(pos) : -(ss-1)->staticEval + 2 * Eval::Tempo; + TT.store(posKey, VALUE_NONE, BOUND_NONE, DEPTH_NONE, MOVE_NONE, ss->staticEval); } @@ -556,6 +520,7 @@ namespace { && ss->staticEval != VALUE_NONE && (ss-1)->staticEval != VALUE_NONE && (move = (ss-1)->currentMove) != MOVE_NULL + && move != MOVE_NONE && type_of(move) == NORMAL) { Square to = to_sq(move); @@ -567,7 +532,6 @@ namespace { && depth < 4 * ONE_PLY && eval + razor_margin(depth) <= alpha && ttMove == MOVE_NONE - && abs(beta) < VALUE_MATE_IN_MAX_PLY && !pos.pawn_on_7th(pos.side_to_move())) { if ( depth <= ONE_PLY @@ -585,8 +549,7 @@ namespace { && !ss->skipNullMove && depth < 7 * ONE_PLY && eval - futility_margin(depth) >= beta - && abs(beta) < VALUE_MATE_IN_MAX_PLY - && abs(eval) < VALUE_KNOWN_WIN + && eval < VALUE_KNOWN_WIN // Do not return unproven wins && pos.non_pawn_material(pos.side_to_move())) return eval - futility_margin(depth); @@ -595,7 +558,6 @@ namespace { && !ss->skipNullMove && depth >= 2 * ONE_PLY && eval >= beta - && abs(beta) < VALUE_MATE_IN_MAX_PLY && pos.non_pawn_material(pos.side_to_move())) { ss->currentMove = MOVE_NULL; @@ -603,15 +565,13 @@ namespace { assert(eval - beta >= 0); // Null move dynamic reduction based on depth and value - Depth R = 3 * ONE_PLY - + depth / 4 - + int(eval - beta) / PawnValueMg * ONE_PLY; + Depth R = (3 + depth / 4 + std::min(int(eval - beta) / PawnValueMg, 3)) * ONE_PLY; pos.do_null_move(st); - (ss+1)->skipNullMove = (ss+1)->nullChild = true; + (ss+1)->skipNullMove = true; nullValue = depth-R < ONE_PLY ? -qsearch(pos, ss+1, -beta, -beta+1, DEPTH_ZERO) : - search(pos, ss+1, -beta, -beta+1, depth-R, !cutNode); - (ss+1)->skipNullMove = (ss+1)->nullChild = false; + (ss+1)->skipNullMove = false; pos.undo_null_move(); if (nullValue >= beta) @@ -620,7 +580,7 @@ namespace { if (nullValue >= VALUE_MATE_IN_MAX_PLY) nullValue = beta; - if (depth < 12 * ONE_PLY) + if (depth < 12 * ONE_PLY && abs(beta) < VALUE_KNOWN_WIN) return nullValue; // Do verification search at high depths @@ -670,10 +630,9 @@ namespace { && !ttMove && (PvNode || ss->staticEval + 256 >= beta)) { - Depth d = depth - 2 * ONE_PLY - (PvNode ? DEPTH_ZERO : depth / 4); - + Depth d = 2 * (depth - 2 * ONE_PLY) - (PvNode ? DEPTH_ZERO : depth / 2); ss->skipNullMove = true; - search(pos, ss, alpha, beta, d, true); + search(pos, ss, alpha, beta, d / 2, true); ss->skipNullMove = false; tte = TT.probe(posKey); @@ -701,6 +660,8 @@ moves_loop: // When in check and at SpNode search starts from here && !SpNode && depth >= 8 * ONE_PLY && ttMove != MOVE_NONE + /* && ttValue != VALUE_NONE Already implicit in the next condition */ + && abs(ttValue) < VALUE_KNOWN_WIN && !excludedMove // Recursive singular search is not allowed && (tte->bound() & BOUND_LOWER) && tte->depth() >= depth - 3 * ONE_PLY; @@ -737,8 +698,8 @@ moves_loop: // When in check and at SpNode search starts from here Signals.firstRootMove = (moveCount == 1); if (thisThread == Threads.main() && Time::now() - SearchTime > 3000) - sync_cout << "info depth " << depth / ONE_PLY - << " currmove " << move_to_uci(move, pos.is_chess960()) + sync_cout << "info depth " << depth + << " currmove " << UCI::format_move(move, pos.is_chess960()) << " currmovenumber " << moveCount + PVIdx << sync_endl; } @@ -765,12 +726,9 @@ moves_loop: // When in check and at SpNode search starts from here if ( singularExtensionNode && move == ttMove && !ext - && pos.legal(move, ci.pinned) - && abs(ttValue) < VALUE_KNOWN_WIN) + && pos.legal(move, ci.pinned)) { - assert(ttValue != VALUE_NONE); - - Value rBeta = ttValue - int(depth); + Value rBeta = ttValue - int(2 * depth); ss->excludedMove = move; ss->skipNullMove = true; value = search(pos, ss, rBeta - 1, rBeta, depth / 2, cutNode); @@ -794,7 +752,7 @@ moves_loop: // When in check and at SpNode search starts from here { // Move count based pruning if ( depth < 16 * ONE_PLY - && moveCount >= FutilityMoveCounts[improving][depth] ) + && moveCount >= FutilityMoveCounts[improving][depth]) { if (SpNode) splitPoint->mutex.lock(); @@ -807,8 +765,8 @@ moves_loop: // When in check and at SpNode search starts from here // Futility pruning: parent node if (predictedDepth < 7 * ONE_PLY) { - futilityValue = ss->staticEval + futility_margin(predictedDepth) - + 128 + Gains[pos.moved_piece(move)][to_sq(move)]; + futilityValue = ss->staticEval + futility_margin(predictedDepth) + + 128 + Gains[pos.moved_piece(move)][to_sq(move)]; if (futilityValue <= alpha) { @@ -834,6 +792,9 @@ moves_loop: // When in check and at SpNode search starts from here } } + // Speculative prefetch as early as possible + prefetch((char*)TT.first_entry(pos.key_after(move))); + // Check for legality just before making the move if (!RootNode && !SpNode && !pos.legal(move, ci.pinned)) { @@ -860,12 +821,10 @@ moves_loop: // When in check and at SpNode search starts from here { ss->reduction = reduction(improving, depth, moveCount); - if (!PvNode && cutNode) + if ( (!PvNode && cutNode) + || History[pos.piece_on(to_sq(move))][to_sq(move)] < 0) ss->reduction += ONE_PLY; - else if (History[pos.piece_on(to_sq(move))][to_sq(move)] < 0) - ss->reduction += ONE_PLY / 2; - if (move == countermoves[0] || move == countermoves[1]) ss->reduction = std::max(DEPTH_ZERO, ss->reduction - ONE_PLY); @@ -901,20 +860,20 @@ moves_loop: // When in check and at SpNode search starts from here if (SpNode) alpha = splitPoint->alpha; - value = newDepth < ONE_PLY ? - givesCheck ? -qsearch(pos, ss+1, -(alpha+1), -alpha, DEPTH_ZERO) - : -qsearch(pos, ss+1, -(alpha+1), -alpha, DEPTH_ZERO) - : - search(pos, ss+1, -(alpha+1), -alpha, newDepth, !cutNode); + value = newDepth < ONE_PLY ? + givesCheck ? -qsearch(pos, ss+1, -(alpha+1), -alpha, DEPTH_ZERO) + : -qsearch(pos, ss+1, -(alpha+1), -alpha, DEPTH_ZERO) + : - search(pos, ss+1, -(alpha+1), -alpha, newDepth, !cutNode); } // For PV nodes only, do a full PV search on the first move or after a fail // high (in the latter case search only if value < beta), otherwise let the // parent node fail low with value <= alpha and to try another move. if (PvNode && (pvMove || (value > alpha && (RootNode || value < beta)))) - value = newDepth < ONE_PLY ? - givesCheck ? -qsearch(pos, ss+1, -beta, -alpha, DEPTH_ZERO) - : -qsearch(pos, ss+1, -beta, -alpha, DEPTH_ZERO) - : - search(pos, ss+1, -beta, -alpha, newDepth, false); + value = newDepth < ONE_PLY ? + givesCheck ? -qsearch(pos, ss+1, -beta, -alpha, DEPTH_ZERO) + : -qsearch(pos, ss+1, -beta, -alpha, DEPTH_ZERO) + : - search(pos, ss+1, -beta, -alpha, newDepth, false); // Step 17. Undo move pos.undo_move(move); @@ -989,8 +948,8 @@ moves_loop: // When in check and at SpNode search starts from here { assert(bestValue > -VALUE_INFINITE && bestValue < beta); - thisThread->split(pos, ss, alpha, beta, &bestValue, &bestMove, - depth, moveCount, &mp, NT, cutNode); + thisThread->split(pos, ss, alpha, beta, &bestValue, &bestMove, + depth, moveCount, &mp, NT, cutNode); if (Signals.stop || thisThread->cutoff_occurred()) return VALUE_ZERO; @@ -1065,8 +1024,10 @@ moves_loop: // When in check and at SpNode search starts from here ss->ply = (ss-1)->ply + 1; // Check for an instant draw or if the maximum ply has been reached - if (pos.is_draw() || ss->ply > MAX_PLY) - return ss->ply > MAX_PLY && !InCheck ? evaluate(pos) + Tempo : DrawValue[pos.side_to_move()]; + if (pos.is_draw() || ss->ply >= MAX_PLY) + return ss->ply >= MAX_PLY && !InCheck ? evaluate(pos) : DrawValue[pos.side_to_move()]; + + assert(0 <= ss->ply && ss->ply < MAX_PLY); // Decide whether or not to include checks: this fixes also the type of // TT entry depth that we are going to use. Note that in qsearch we use @@ -1103,7 +1064,7 @@ moves_loop: // When in check and at SpNode search starts from here { // Never assume anything on values stored in TT if ((ss->staticEval = bestValue = tte->eval_value()) == VALUE_NONE) - ss->staticEval = bestValue = evaluate(pos) + Tempo; + ss->staticEval = bestValue = evaluate(pos); // Can ttValue be used as a better position evaluation? if (ttValue != VALUE_NONE) @@ -1111,7 +1072,8 @@ moves_loop: // When in check and at SpNode search starts from here bestValue = ttValue; } else - ss->staticEval = bestValue = ss->nullChild ? -(ss-1)->staticEval + 2 * Tempo : evaluate(pos) + Tempo; + ss->staticEval = bestValue = + (ss-1)->currentMove != MOVE_NULL ? evaluate(pos) : -(ss-1)->staticEval + 2 * Eval::Tempo; // Stand pat. Return immediately if static value is at least beta if (bestValue >= beta) @@ -1184,6 +1146,9 @@ moves_loop: // When in check and at SpNode search starts from here && pos.see_sign(move) < VALUE_ZERO) continue; + // Speculative prefetch as early as possible + prefetch((char*)TT.first_entry(pos.key_after(move))); + // Check for legality just before making the move if (!pos.legal(move, ci.pinned)) continue; @@ -1274,7 +1239,7 @@ moves_loop: // When in check and at SpNode search starts from here // Increase history value of the cut-off move and decrease all the other // played quiet moves. - Value bonus = Value(int(depth) * int(depth)); + Value bonus = Value(4 * int(depth) * int(depth)); History.update(pos.moved_piece(move), to_sq(move), bonus); for (int i = 0; i < quietsCnt; ++i) { @@ -1296,8 +1261,8 @@ moves_loop: // When in check and at SpNode search starts from here } - // When playing with a strength handicap, choose best move among the MultiPV - // set using a statistical rule dependent on 'level'. Idea by Heinz van Saanen. + // When playing with a strength handicap, choose best move among the first 'candidates' + // RootMoves using a statistical rule dependent on 'level'. Idea by Heinz van Saanen. Move Skill::pick_move() { @@ -1308,7 +1273,7 @@ moves_loop: // When in check and at SpNode search starts from here rk.rand(); // RootMoves are already sorted by score in descending order - int variance = std::min(RootMoves[0].score - RootMoves[MultiPV - 1].score, PawnValueMg); + int variance = std::min(RootMoves[0].score - RootMoves[candidates - 1].score, PawnValueMg); int weakness = 120 - 2 * level; int max_s = -VALUE_INFINITE; best = MOVE_NONE; @@ -1316,12 +1281,12 @@ moves_loop: // When in check and at SpNode search starts from here // Choose best move. For each move score we add two terms both dependent on // weakness. One deterministic and bigger for weaker moves, and one random, // then we choose the move with the resulting highest score. - for (size_t i = 0; i < MultiPV; ++i) + for (size_t i = 0; i < candidates; ++i) { int s = RootMoves[i].score; // Don't allow crazy blunders even at very low skills - if (i > 0 && RootMoves[i-1].score > s + 2 * PawnValueMg) + if (i > 0 && RootMoves[i - 1].score > s + 2 * PawnValueMg) break; // This is our magic formula @@ -1368,15 +1333,15 @@ moves_loop: // When in check and at SpNode search starts from here ss << "info depth " << d << " seldepth " << selDepth - << " score " << (i == PVIdx ? score_to_uci(v, alpha, beta) : score_to_uci(v)) + << " multipv " << i + 1 + << " score " << (i == PVIdx ? UCI::format_value(v, alpha, beta) : UCI::format_value(v)) << " nodes " << pos.nodes_searched() << " nps " << pos.nodes_searched() * 1000 / elapsed << " time " << elapsed - << " multipv " << i + 1 << " pv"; for (size_t j = 0; RootMoves[i].pv[j] != MOVE_NONE; ++j) - ss << " " << move_to_uci(RootMoves[i].pv[j], pos.is_chess960()); + ss << " " << UCI::format_move(RootMoves[i].pv[j], pos.is_chess960()); } return ss.str(); @@ -1392,7 +1357,7 @@ moves_loop: // When in check and at SpNode search starts from here void RootMove::extract_pv_from_tt(Position& pos) { - StateInfo state[MAX_PLY_PLUS_6], *st = state; + StateInfo state[MAX_PLY], *st = state; const TTEntry* tte; int ply = 1; // At root ply is 1... Move m = pv[0]; // ...instead pv[] array starts from 0 @@ -1428,7 +1393,7 @@ void RootMove::extract_pv_from_tt(Position& pos) { void RootMove::insert_pv_in_tt(Position& pos) { - StateInfo state[MAX_PLY_PLUS_6], *st = state; + StateInfo state[MAX_PLY], *st = state; const TTEntry* tte; int idx = 0; // Ply starts from 1, we need to start from 0 @@ -1458,52 +1423,19 @@ void Thread::idle_loop() { assert(!this_sp || (this_sp->masterThread == this && searching)); - while (true) + while (!exit) { - // If we are not searching, wait for a condition to be signaled instead of - // wasting CPU time polling for work. - while (!searching || exit) - { - if (exit) - { - assert(!this_sp); - return; - } - - // Grab the lock to avoid races with Thread::notify_one() - mutex.lock(); - - // If we are master and all slaves have finished then exit idle_loop - if (this_sp && this_sp->slavesMask.none()) - { - mutex.unlock(); - break; - } - - // Do sleep after retesting sleep conditions under lock protection. In - // particular we need to avoid a deadlock in case a master thread has, - // in the meanwhile, allocated us and sent the notify_one() call before - // we had the chance to grab the lock. - if (!searching && !exit) - sleepCondition.wait(mutex); - - mutex.unlock(); - } - // If this thread has been assigned work, launch a search - if (searching) + while (searching) { - assert(!exit); - Threads.mutex.lock(); - assert(searching); assert(activeSplitPoint); SplitPoint* sp = activeSplitPoint; Threads.mutex.unlock(); - Stack stack[MAX_PLY_PLUS_6], *ss = stack+2; // To allow referencing (ss-2) + Stack stack[MAX_PLY+4], *ss = stack+2; // To allow referencing (ss-2) and (ss+2) Position pos(*sp->pos, this); std::memcpy(ss-2, sp->ss-2, 5 * sizeof(Stack)); @@ -1581,16 +1513,23 @@ void Thread::idle_loop() { } } - // If this thread is the master of a split point and all slaves have finished - // their work at this split point, return from the idle loop. + // Grab the lock to avoid races with Thread::notify_one() + mutex.lock(); + + // If we are master and all slaves have finished then exit idle_loop if (this_sp && this_sp->slavesMask.none()) { - this_sp->mutex.lock(); - bool finished = this_sp->slavesMask.none(); // Retest under lock protection - this_sp->mutex.unlock(); - if (finished) - return; + assert(!searching); + mutex.unlock(); + break; } + + // If we are not searching, wait for a condition to be signaled instead of + // wasting CPU time polling for work. + if (!searching && !exit) + sleepCondition.wait(mutex); + + mutex.unlock(); } } @@ -1602,7 +1541,7 @@ void Thread::idle_loop() { void check_time() { static Time::point lastInfoTime = Time::now(); - int64_t nodes = 0; // Workaround silly 'uninitialized' gcc warning + Time::point elapsed = Time::now() - SearchTime; if (Time::now() - lastInfoTime >= 1000) { @@ -1610,14 +1549,24 @@ void check_time() { dbg_print(); } - if (Limits.ponder) - return; + if (Limits.use_time_management() && !Limits.ponder) + { + bool stillAtFirstMove = Signals.firstRootMove + && !Signals.failedLowAtRoot + && elapsed > TimeMgr.available_time() * 75 / 100; + + if ( stillAtFirstMove + || elapsed > TimeMgr.maximum_time() - 2 * TimerThread::Resolution) + Signals.stop = true; + } + else if (Limits.movetime && elapsed >= Limits.movetime) + Signals.stop = true; - if (Limits.nodes) + else if (Limits.nodes) { Threads.mutex.lock(); - nodes = RootPos.nodes_searched(); + int nodes = RootPos.nodes_searched(); // Loop across all split points and sum accumulated SplitPoint nodes plus // all the currently active positions nodes. @@ -1638,18 +1587,8 @@ void check_time() { } Threads.mutex.unlock(); - } - Time::point elapsed = Time::now() - SearchTime; - bool stillAtFirstMove = Signals.firstRootMove - && !Signals.failedLowAtRoot - && elapsed > TimeMgr.available_time() * 75 / 100; - - bool noMoreTime = elapsed > TimeMgr.maximum_time() - 2 * TimerThread::Resolution - || stillAtFirstMove; - - if ( (Limits.use_time_management() && noMoreTime) - || (Limits.movetime && elapsed >= Limits.movetime) - || (Limits.nodes && nodes >= Limits.nodes)) - Signals.stop = true; + if (nodes >= Limits.nodes) + Signals.stop = true; + } }