X-Git-Url: https://git.sesse.net/?p=stockfish;a=blobdiff_plain;f=src%2Fsearch.cpp;h=ea1ed57ab0846068d1d9d182c4115837a3b15e98;hp=03af5d66d96bc393bb1106dd56694d32f560a48a;hb=d9caede3249698440b7579e31d92aaa9984a128b;hpb=ef43e6b05d0c79bf2ec7be291866449eba2ef576 diff --git a/src/search.cpp b/src/search.cpp index 03af5d66..ea1ed57a 100644 --- a/src/search.cpp +++ b/src/search.cpp @@ -19,22 +19,20 @@ #include #include -#include #include #include #include #include -#include "book.h" #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 { @@ -42,10 +40,8 @@ namespace Search { LimitsType Limits; std::vector RootMoves; Position RootPos; - Color RootColor; Time::point SearchTime; StateStackPtr SetupStates; - Value Contempt[2]; // [bestValue > VALUE_DRAW] } using std::string; @@ -54,31 +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, SplitPointRoot, SplitPointPV, SplitPointNonPV }; + enum NodeType { Root, PV, NonPV }; // Dynamic razoring margin based on depth - inline Value razor_margin(Depth d) { return Value(512 + 16 * int(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 * int(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)]; } - size_t MultiPV, PVIdx; + size_t PVIdx; TimeManager TimeMgr; double BestMoveChanges; Value DrawValue[COLOR_NB]; @@ -86,7 +78,7 @@ namespace { GainsStats Gains; MovesStats Countermoves, Followupmoves; - template + template Value search(Position& pos, Stack* ss, Value alpha, Value beta, Depth depth, bool cutNode); template @@ -95,22 +87,25 @@ namespace { void id_loop(Position& pos); Value value_to_tt(Value v, int ply); Value value_from_tt(Value v, int ply); - void update_stats(Position& pos, Stack* ss, Move move, Depth depth, Move* quiets, int quietsCnt); + void update_stats(const Position& pos, Stack* ss, Move move, Depth depth, Move* quiets, int quietsCnt); 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; }; @@ -130,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 ? floor( pvRed * int(ONE_PLY)) : 0); - Reductions[0][1][hd][mc] = (int8_t) (nonPVRed >= 1.0 ? floor(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 @@ -181,74 +181,32 @@ uint64_t Search::perft(Position& pos, Depth depth) { void Search::think() { - static PolyglotBook book; // Defined static to initialize the PRNG only once + TimeMgr.init(Limits, RootPos.game_ply(), RootPos.side_to_move()); - RootColor = RootPos.side_to_move(); - TimeMgr.init(Limits, RootPos.game_ply(), RootColor); - - Contempt[0] = Options["Contempt Factor"] * PawnValueEg / 100; // From centipawns - Contempt[1] = (Options["Contempt Factor"] + 12) * PawnValueEg / 100; + 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); if (RootMoves.empty()) { 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["OwnBook"] && !Limits.infinite && !Limits.mate) - { - Move bookMove = book.probe(RootPos, Options["Book File"], Options["Best Book Move"]); - - if (bookMove && std::count(RootMoves.begin(), RootMoves.end(), bookMove)) - { - std::swap(RootMoves[0], *std::find(RootMoves.begin(), RootMoves.end(), bookMove)); - 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[RootColor] - << " increment: " << Limits.inc[RootColor] - << " 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; - Threads.sleepWhileIdle = Options["Idle Threads Sleep"]; Threads.timer->run = true; Threads.timer->notify_one(); // Wake up the recurring timer id_loop(RootPos); // Let's start searching ! Threads.timer->run = false; // Stop the timer - Threads.sleepWhileIdle = true; // Send idle threads to sleep - - 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: @@ -268,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; } @@ -287,7 +245,6 @@ namespace { 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; @@ -300,15 +257,12 @@ 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)) @@ -322,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) @@ -337,10 +291,7 @@ namespace { // high/low anymore. while (true) { - bestValue = search(pos, ss, alpha, beta, depth * ONE_PLY, false); - - DrawValue[ RootColor] = VALUE_DRAW - Contempt[bestValue > VALUE_DRAW]; - DrawValue[~RootColor] = VALUE_DRAW + Contempt[bestValue > VALUE_DRAW]; + bestValue = search(pos, ss, alpha, beta, depth * ONE_PLY, false); // Bring the best move to the front. It is critical that sorting // is done with a stable algorithm because all the values but the @@ -382,7 +333,7 @@ namespace { else break; - delta += delta / 2; + delta += 3 * delta / 8; assert(alpha >= -VALUE_INFINITE && beta <= VALUE_INFINITE); } @@ -390,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 @@ -419,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 @@ -446,12 +388,11 @@ namespace { // repeat all this work again. 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. - template + template Value search(Position& pos, Stack* ss, Value alpha, Value beta, Depth depth, bool cutNode) { - const bool PvNode = (NT == PV || NT == Root || NT == SplitPointPV || NT == SplitPointRoot); - const bool SpNode = (NT == SplitPointPV || NT == SplitPointNonPV || NT == SplitPointRoot); - const bool RootNode = (NT == Root || NT == SplitPointRoot); + const bool RootNode = NT == Root; + const bool PvNode = NT == PV || NT == Root; assert(-VALUE_INFINITE <= alpha && alpha < beta && beta <= VALUE_INFINITE); assert(PvNode || (alpha == beta - 1)); @@ -566,7 +507,9 @@ namespace { } else { - eval = ss->staticEval = evaluate(pos); + 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); } @@ -574,6 +517,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); @@ -585,9 +529,12 @@ 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 + && eval + razor_margin(3 * ONE_PLY) <= alpha) + return qsearch(pos, ss, alpha, beta, DEPTH_ZERO); + Value ralpha = alpha - razor_margin(depth); Value v = qsearch(pos, ss, ralpha, ralpha+1, DEPTH_ZERO); if (v <= ralpha) @@ -599,8 +546,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); @@ -609,7 +555,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; @@ -617,14 +562,12 @@ 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 = 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); + : - search(pos, ss+1, -beta, -beta+1, depth-R, !cutNode); (ss+1)->skipNullMove = false; pos.undo_null_move(); @@ -634,13 +577,13 @@ 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 ss->skipNullMove = true; Value v = depth-R < ONE_PLY ? qsearch(pos, ss, beta-1, beta, DEPTH_ZERO) - : search(pos, ss, beta-1, beta, depth-R, false); + : search(pos, ss, beta-1, beta, depth-R, false); ss->skipNullMove = false; if (v >= beta) @@ -672,7 +615,7 @@ namespace { { ss->currentMove = move; pos.do_move(move, st, ci, pos.gives_check(move, ci)); - value = -search(pos, ss+1, -rbeta, -rbeta+1, rdepth, !cutNode); + value = -search(pos, ss+1, -rbeta, -rbeta+1, rdepth, !cutNode); pos.undo_move(move); if (value >= rbeta) return value; @@ -682,12 +625,11 @@ namespace { // Step 10. Internal iterative deepening (skipped when in check) if ( depth >= (PvNode ? 5 * ONE_PLY : 8 * ONE_PLY) && !ttMove - && (PvNode || ss->staticEval + Value(256) >= beta)) + && (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); @@ -715,6 +657,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; @@ -751,8 +695,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; } @@ -779,15 +723,12 @@ 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); + value = search(pos, ss, rBeta - 1, rBeta, depth / 2, cutNode); ss->skipNullMove = false; ss->excludedMove = MOVE_NONE; @@ -808,7 +749,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(); @@ -821,8 +762,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) - + Value(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) { @@ -848,6 +789,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)) { @@ -874,26 +818,31 @@ 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); + // Decrease reduction for moves that escape a capture + if ( ss->reduction + && type_of(move) == NORMAL + && type_of(pos.piece_on(to_sq(move))) != PAWN + && pos.see(make_move(to_sq(move), from_sq(move))) < 0) + ss->reduction = std::max(DEPTH_ZERO, ss->reduction - ONE_PLY); + Depth d = std::max(newDepth - ss->reduction, ONE_PLY); if (SpNode) alpha = splitPoint->alpha; - value = -search(pos, ss+1, -(alpha+1), -alpha, d, true); + value = -search(pos, ss+1, -(alpha+1), -alpha, d, true); - // Research at intermediate depth if reduction is very high + // Re-search at intermediate depth if reduction is very high if (value > alpha && ss->reduction >= 4 * ONE_PLY) { Depth d2 = std::max(newDepth - 2 * ONE_PLY, ONE_PLY); - value = -search(pos, ss+1, -(alpha+1), -alpha, d2, true); + value = -search(pos, ss+1, -(alpha+1), -alpha, d2, true); } doFullDepthSearch = (value > alpha && ss->reduction != DEPTH_ZERO); @@ -908,20 +857,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); @@ -935,12 +884,11 @@ moves_loop: // When in check and at SpNode search starts from here alpha = splitPoint->alpha; } - // Finished searching the move. If Signals.stop is true, the search - // was aborted because the user interrupted the search or because we - // ran out of time. In this case, the return value of the search cannot - // be trusted, and we don't update the best move and/or PV. + // Finished searching the move. If a stop or a cutoff occurred, the return + // value of the search cannot be trusted, and we return immediately without + // updating best move, PV and TT. if (Signals.stop || thisThread->cutoff_occurred()) - return value; // To avoid returning VALUE_INFINITE + return VALUE_ZERO; if (RootNode) { @@ -989,14 +937,20 @@ moves_loop: // When in check and at SpNode search starts from here // Step 19. Check for splitting the search if ( !SpNode + && Threads.size() >= 2 && depth >= Threads.minimumSplitDepth - && Threads.available_slave(thisThread) + && ( !thisThread->activeSplitPoint + || !thisThread->activeSplitPoint->allSlavesSearching) && thisThread->splitPointsSize < MAX_SPLITPOINTS_PER_THREAD) { - assert(bestValue < beta); + assert(bestValue > -VALUE_INFINITE && bestValue < beta); + + thisThread->split(pos, ss, alpha, beta, &bestValue, &bestMove, + depth, moveCount, &mp, NT, cutNode); + + if (Signals.stop || thisThread->cutoff_occurred()) + return VALUE_ZERO; - thisThread->split(pos, ss, alpha, beta, &bestValue, &bestMove, - depth, moveCount, &mp, NT, cutNode); if (bestValue >= beta) break; } @@ -1005,30 +959,31 @@ moves_loop: // When in check and at SpNode search starts from here if (SpNode) return bestValue; + // Following condition would detect a stop or a cutoff set only after move + // loop has been completed. But in this case bestValue is valid because we + // have fully searched our subtree, and we can anyhow save the result in TT. + /* + if (Signals.stop || thisThread->cutoff_occurred()) + return VALUE_DRAW; + */ + // Step 20. Check for mate and stalemate // All legal moves have been searched and if there are no legal moves, it - // must be mate or stalemate. Note that we can have a false positive in - // case of Signals.stop or thread.cutoff_occurred() are set, but this is - // harmless because return value is discarded anyhow in the parent nodes. - // If we are in a singular extension search then return a fail low score. - // A split node has at least one move - the one tried before to be split. + // must be mate or stalemate. If we are in a singular extension search then + // return a fail low score. if (!moveCount) - return excludedMove ? alpha - : inCheck ? mated_in(ss->ply) : DrawValue[pos.side_to_move()]; + bestValue = excludedMove ? alpha + : inCheck ? mated_in(ss->ply) : DrawValue[pos.side_to_move()]; - // If we have pruned all the moves without searching return a fail-low score - if (bestValue == -VALUE_INFINITE) - bestValue = alpha; + // Quiet best move: update killers, history, countermoves and followupmoves + else if (bestValue >= beta && !pos.capture_or_promotion(bestMove) && !inCheck) + update_stats(pos, ss, bestMove, depth, quietsSearched, quietCount - 1); TT.store(posKey, value_to_tt(bestValue, ss->ply), bestValue >= beta ? BOUND_LOWER : PvNode && bestMove ? BOUND_EXACT : BOUND_UPPER, depth, bestMove, ss->staticEval); - // Quiet best move: update killers, history, countermoves and followupmoves - if (bestValue >= beta && !pos.capture_or_promotion(bestMove) && !inCheck) - update_stats(pos, ss, bestMove, depth, quietsSearched, quietCount - 1); - assert(bestValue > -VALUE_INFINITE && bestValue < VALUE_INFINITE); return bestValue; @@ -1042,7 +997,7 @@ moves_loop: // When in check and at SpNode search starts from here template Value qsearch(Position& pos, Stack* ss, Value alpha, Value beta, Depth depth) { - const bool PvNode = (NT == PV); + const bool PvNode = NT == PV; assert(NT == PV || NT == NonPV); assert(InCheck == !!pos.checkers()); @@ -1112,7 +1067,8 @@ moves_loop: // When in check and at SpNode search starts from here bestValue = ttValue; } else - ss->staticEval = bestValue = evaluate(pos); + 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) @@ -1127,7 +1083,7 @@ moves_loop: // When in check and at SpNode search starts from here if (PvNode && bestValue > alpha) alpha = bestValue; - futilityBase = bestValue + Value(128); + futilityBase = bestValue + 128; } // Initialize a MovePicker object for the current position, and prepare @@ -1185,6 +1141,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; @@ -1265,7 +1224,7 @@ moves_loop: // When in check and at SpNode search starts from here // update_stats() updates killers, history, countermoves and followupmoves stats after a fail-high // of a quiet move. - void update_stats(Position& pos, Stack* ss, Move move, Depth depth, Move* quiets, int quietsCnt) { + void update_stats(const Position& pos, Stack* ss, Move move, Depth depth, Move* quiets, int quietsCnt) { if (ss->killers[0] != move) { @@ -1275,7 +1234,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) { @@ -1297,8 +1256,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() { @@ -1309,7 +1268,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; @@ -1317,12 +1276,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 @@ -1369,15 +1328,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(); @@ -1395,28 +1354,31 @@ void RootMove::extract_pv_from_tt(Position& pos) { StateInfo state[MAX_PLY_PLUS_6], *st = state; const TTEntry* tte; - int ply = 0; - Move m = pv[0]; + int ply = 1; // At root ply is 1... + Move m = pv[0]; // ...instead pv[] array starts from 0 + Value expectedScore = score; pv.clear(); do { pv.push_back(m); - assert(MoveList(pos).contains(pv[ply])); + assert(MoveList(pos).contains(pv[ply - 1])); - pos.do_move(pv[ply++], *st++); + pos.do_move(pv[ply++ - 1], *st++); tte = TT.probe(pos.key()); + expectedScore = -expectedScore; } while ( tte + && expectedScore == value_from_tt(tte->value(), ply) && pos.pseudo_legal(m = tte->move()) // Local copy, TT could change && pos.legal(m, pos.pinned_pieces(pos.side_to_move())) && ply < MAX_PLY - && (!pos.is_draw() || ply < 2)); + && (!pos.is_draw() || ply <= 2)); pv.push_back(MOVE_NONE); // Must be zero-terminating - while (ply) pos.undo_move(pv[--ply]); + while (--ply) pos.undo_move(pv[ply - 1]); } @@ -1428,21 +1390,21 @@ void RootMove::insert_pv_in_tt(Position& pos) { StateInfo state[MAX_PLY_PLUS_6], *st = state; const TTEntry* tte; - int ply = 0; + int idx = 0; // Ply starts from 1, we need to start from 0 do { tte = TT.probe(pos.key()); - if (!tte || tte->move() != pv[ply]) // Don't overwrite correct entries - TT.store(pos.key(), VALUE_NONE, BOUND_NONE, DEPTH_NONE, pv[ply], VALUE_NONE); + if (!tte || tte->move() != pv[idx]) // Don't overwrite correct entries + TT.store(pos.key(), VALUE_NONE, BOUND_NONE, DEPTH_NONE, pv[idx], VALUE_NONE); - assert(MoveList(pos).contains(pv[ply])); + assert(MoveList(pos).contains(pv[idx])); - pos.do_move(pv[ply++], *st++); + pos.do_move(pv[idx++], *st++); - } while (pv[ply] != MOVE_NONE); + } while (pv[idx] != MOVE_NONE); - while (ply) pos.undo_move(pv[--ply]); + while (idx) pos.undo_move(pv[--idx]); } @@ -1456,46 +1418,13 @@ 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 && Threads.sleepWhileIdle) || 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; @@ -1513,31 +1442,29 @@ void Thread::idle_loop() { activePosition = &pos; - switch (sp->nodeType) { - case Root: - search(pos, ss, sp->alpha, sp->beta, sp->depth, sp->cutNode); - break; - case PV: - search(pos, ss, sp->alpha, sp->beta, sp->depth, sp->cutNode); - break; - case NonPV: - search(pos, ss, sp->alpha, sp->beta, sp->depth, sp->cutNode); - break; - default: + if (sp->nodeType == NonPV) + search(pos, ss, sp->alpha, sp->beta, sp->depth, sp->cutNode); + + else if (sp->nodeType == PV) + search(pos, ss, sp->alpha, sp->beta, sp->depth, sp->cutNode); + + else if (sp->nodeType == Root) + search(pos, ss, sp->alpha, sp->beta, sp->depth, sp->cutNode); + + else assert(false); - } assert(searching); searching = false; activePosition = NULL; sp->slavesMask.reset(idx); + sp->allSlavesSearching = false; sp->nodes += pos.nodes_searched(); // Wake up the master thread so to allow it to return from the idle // loop in case we are the last slave of the split point. - if ( Threads.sleepWhileIdle - && this != sp->masterThread + if ( this != sp->masterThread && sp->slavesMask.none()) { assert(!sp->masterThread->searching); @@ -1546,21 +1473,58 @@ void Thread::idle_loop() { // After releasing the lock we can't access any SplitPoint related data // in a safe way because it could have been released under our feet by - // the sp master. Also accessing other Thread objects is unsafe because - // if we are exiting there is a chance that they are already freed. + // the sp master. sp->mutex.unlock(); + + // Try to late join to another split point if none of its slaves has + // already finished. + if (Threads.size() > 2) + for (size_t i = 0; i < Threads.size(); ++i) + { + const int size = Threads[i]->splitPointsSize; // Local copy + sp = size ? &Threads[i]->splitPoints[size - 1] : NULL; + + if ( sp + && sp->allSlavesSearching + && available_to(Threads[i])) + { + // Recheck the conditions under lock protection + Threads.mutex.lock(); + sp->mutex.lock(); + + if ( sp->allSlavesSearching + && available_to(Threads[i])) + { + sp->slavesMask.set(idx); + activeSplitPoint = sp; + searching = true; + } + + sp->mutex.unlock(); + Threads.mutex.unlock(); + + break; // Just a single attempt + } + } } - // 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(); } }