X-Git-Url: https://git.sesse.net/?p=stockfish;a=blobdiff_plain;f=src%2Fsearch.cpp;h=a4bf172a99e7442f50109bc8d9b82dfa51c063b0;hp=78e4748f5ce64a51efbd2b33821f3579b8d87097;hb=356147d99ae6783d79861c32f128a98685024c58;hpb=307a5a4f63169fd215860dc478dcf2a9db2c46e8 diff --git a/src/search.cpp b/src/search.cpp index 78e4748f..a4bf172a 100644 --- a/src/search.cpp +++ b/src/search.cpp @@ -2,6 +2,7 @@ Stockfish, a UCI chess playing engine derived from Glaurung 2.1 Copyright (C) 2004-2008 Tord Romstad (Glaurung author) Copyright (C) 2008-2015 Marco Costalba, Joona Kiiski, Tord Romstad + Copyright (C) 2015-2016 Marco Costalba, Joona Kiiski, Gary Linscott, Tord Romstad Stockfish is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by @@ -37,7 +38,7 @@ namespace Search { - volatile SignalsType Signals; + SignalsType Signals; LimitsType Limits; StateStackPtr SetupStates; } @@ -60,7 +61,7 @@ using namespace Search; namespace { - // Different node types, used as template parameter + // Different node types, used as a template parameter enum NodeType { Root, PV, NonPV }; // Razoring and futility margin based on depth @@ -75,7 +76,7 @@ namespace { return Reductions[PvNode][i][std::min(d, 63 * ONE_PLY)][std::min(mn, 63)]; } - // Skill struct is used to implement strength limiting + // Skill structure is used to implement strength limit struct Skill { Skill(int l) : level(l) {} bool enabled() const { return level < 20; } @@ -87,8 +88,8 @@ namespace { Move best = MOVE_NONE; }; - // EasyMoveManager struct is used to detect a so called 'easy move'; when PV is - // stable across multiple search iterations we can fast return the best move. + // EasyMoveManager structure is used to detect an 'easy move'. When the PV is + // stable across multiple search iterations, we can quickly return the best move. struct EasyMoveManager { void clear() { @@ -105,7 +106,7 @@ namespace { assert(newPv.size() >= 3); - // Keep track of how many times in a row 3rd ply remains stable + // Keep track of how many times in a row the 3rd ply remains stable stableCnt = (newPv[2] == pv[2]) ? stableCnt + 1 : 0; if (!std::equal(newPv.begin(), newPv.begin() + 3, pv)) @@ -127,9 +128,8 @@ namespace { }; EasyMoveManager EasyMove; - double BestMoveChanges; Value DrawValue[COLOR_NB]; - CounterMovesHistoryStats CounterMovesHistory; + CounterMoveHistoryStats CounterMoveHistory; template Value search(Position& pos, Stack* ss, Value alpha, Value beta, Depth depth, bool cutNode); @@ -141,6 +141,7 @@ namespace { Value value_from_tt(Value v, int ply); void update_pv(Move* pv, Move move, Move* childPv); void update_stats(const Position& pos, Stack* ss, Move move, Depth depth, Move* quiets, int quietsCnt); + void check_time(); } // namespace @@ -174,23 +175,25 @@ void Search::init() { } -/// Search::reset() clears all search memory, to obtain reproducible search results +/// Search::clear() resets search state to zero, to obtain reproducible results -void Search::reset () { +void Search::clear() { TT.clear(); - CounterMovesHistory.clear(); + CounterMoveHistory.clear(); for (Thread* th : Threads) { th->history.clear(); th->counterMoves.clear(); } + + Threads.main()->previousScore = VALUE_INFINITE; } /// 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. +/// up to the given depth are generated and counted, and the sum is returned. template uint64_t Search::perft(Position& pos, Depth depth) { @@ -216,14 +219,13 @@ uint64_t Search::perft(Position& pos, Depth depth) { return nodes; } -template uint64_t Search::perft(Position& pos, Depth depth); +template uint64_t Search::perft(Position&, Depth); -/// MainThread::think() is called by the main thread when the program receives -/// the UCI 'go' command. It searches from root position and at the end prints -/// the "bestmove" to output. +/// MainThread::search() is called by the main thread when the program receives +/// the UCI 'go' command. It searches from the root position and outputs the "bestmove". -void MainThread::think() { +void MainThread::search() { Color us = rootPos.side_to_move(); Time.init(Limits, us, rootPos.game_ply()); @@ -257,8 +259,8 @@ void MainThread::think() { if (TB::Cardinality >= rootPos.count(WHITE) + rootPos.count(BLACK)) { - // If the current root position is in the tablebases then RootMoves - // contains only moves that preserve the draw or win. + // If the current root position is in the tablebases, then RootMoves + // contains only moves that preserve the draw or the win. TB::RootInTB = Tablebases::root_probe(rootPos, rootMoves, TB::Score); if (TB::RootInTB) @@ -266,7 +268,7 @@ void MainThread::think() { else // If DTZ tables are missing, use WDL tables as a fallback { - // Filter out moves that do not preserve a draw or win + // Filter out moves that do not preserve the draw or the win. TB::RootInTB = Tablebases::root_probe_wdl(rootPos, rootMoves, TB::Score); // Only probe during search if winning @@ -289,32 +291,19 @@ void MainThread::think() { { th->maxPly = 0; th->rootDepth = DEPTH_ZERO; - th->searching = true; if (th != this) { th->rootPos = Position(rootPos, th); th->rootMoves = rootMoves; - th->notify_one(); // Wake up the thread and start searching + th->start_searching(); } } - Threads.timer->run = true; - Threads.timer->notify_one(); // Start the recurring timer - - search(true); // Let's start searching! - - // Stop the threads and the timer - Signals.stop = true; - Threads.timer->run = false; - - // Wait until all threads have finished - for (Thread* th : Threads) - if (th != this) - th->wait_while(th->searching); + Thread::search(); // Let's start searching! } // When playing in 'nodes as time' mode, subtract the searched nodes from - // the available ones before to exit. + // the available ones before exiting. if (Limits.npmsec) Time.availableNodes += Limits.inc[us] - Threads.nodes_searched(); @@ -329,10 +318,36 @@ void MainThread::think() { wait(Signals.stop); } - sync_cout << "bestmove " << UCI::move(rootMoves[0].pv[0], rootPos.is_chess960()); + // Stop the threads if not already stopped + Signals.stop = true; + + // Wait until all threads have finished + for (Thread* th : Threads) + if (th != this) + th->wait_for_search_finished(); + + // Check if there are threads with a better score than main thread + Thread* bestThread = this; + if ( !this->easyMovePlayed + && Options["MultiPV"] == 1 + && !Skill(Options["Skill Level"]).enabled()) + { + for (Thread* th : Threads) + if ( th->completedDepth > bestThread->completedDepth + && th->rootMoves[0].score > bestThread->rootMoves[0].score) + bestThread = th; + } + + previousScore = bestThread->rootMoves[0].score; + + // Send new PV when needed + if (bestThread != this) + sync_cout << UCI::pv(bestThread->rootPos, bestThread->completedDepth, -VALUE_INFINITE, VALUE_INFINITE) << sync_endl; + + sync_cout << "bestmove " << UCI::move(bestThread->rootMoves[0].pv[0], rootPos.is_chess960()); - if (rootMoves[0].pv.size() > 1 || rootMoves[0].extract_ponder_from_tt(rootPos)) - std::cout << " ponder " << UCI::move(rootMoves[0].pv[1], rootPos.is_chess960()); + if (bestThread->rootMoves[0].pv.size() > 1 || bestThread->rootMoves[0].extract_ponder_from_tt(rootPos)) + std::cout << " ponder " << UCI::move(bestThread->rootMoves[0].pv[1], rootPos.is_chess960()); std::cout << sync_endl; } @@ -340,24 +355,27 @@ void MainThread::think() { // Thread::search() is the main iterative deepening loop. It calls search() // repeatedly with increasing depth until the allocated thinking time has been -// consumed, user stops the search, or the maximum search depth is reached. +// consumed, the user stops the search, or the maximum search depth is reached. -void Thread::search(bool isMainThread) { +void Thread::search() { - Stack* ss = stack + 2; // To allow referencing (ss-2) and (ss+2) + Stack stack[MAX_PLY+4], *ss = stack+2; // To allow referencing (ss-2) and (ss+2) Value bestValue, alpha, beta, delta; Move easyMove = MOVE_NONE; + MainThread* mainThread = (this == Threads.main() ? Threads.main() : nullptr); std::memset(ss-2, 0, 5 * sizeof(Stack)); bestValue = delta = alpha = -VALUE_INFINITE; beta = VALUE_INFINITE; + completedDepth = DEPTH_ZERO; - if (isMainThread) + if (mainThread) { easyMove = EasyMove.get(rootPos.key()); EasyMove.clear(); - BestMoveChanges = 0; + mainThread->easyMovePlayed = mainThread->failedLow = false; + mainThread->bestMoveChanges = 0; TT.new_search(); } @@ -371,16 +389,36 @@ void Thread::search(bool isMainThread) { multiPV = std::min(multiPV, rootMoves.size()); - // Iterative deepening loop until requested to stop or target depth reached + // Iterative deepening loop until requested to stop or the target depth is reached. while (++rootDepth < DEPTH_MAX && !Signals.stop && (!Limits.depth || rootDepth <= Limits.depth)) { - // Set up the new depth for the helper threads - if (!isMainThread) - rootDepth = Threads.main()->rootDepth + Depth(int(3 * log(1 + this->idx))); + // Set up the new depths for the helper threads skipping on average every + // 2nd ply (using a half-density map similar to a Hadamard matrix). + if (!mainThread) + { + int d = rootDepth + rootPos.game_ply(); + + if (idx <= 6 || idx > 24) + { + if (((d + idx) >> (msb(idx + 1) - 1)) % 2) + continue; + } + else + { + // Table of values of 6 bits with 3 of them set + static const int HalfDensityMap[] = { + 0x07, 0x0b, 0x0d, 0x0e, 0x13, 0x16, 0x19, 0x1a, 0x1c, + 0x23, 0x25, 0x26, 0x29, 0x2c, 0x31, 0x32, 0x34, 0x38 + }; + + if ((HalfDensityMap[idx - 7] >> (d % 6)) & 1) + continue; + } + } // Age out PV variability metric - if (isMainThread) - BestMoveChanges *= 0.5; + if (mainThread) + mainThread->bestMoveChanges *= 0.505, mainThread->failedLow = false; // Save the last iteration's scores before first PV line is searched and // all the move scores except the (new) PV are set to -VALUE_INFINITE. @@ -413,20 +451,20 @@ void Thread::search(bool isMainThread) { // search the already searched PV lines are preserved. std::stable_sort(rootMoves.begin() + PVIdx, rootMoves.end()); - // Write PV back to transposition table in case the relevant + // Write PV back to the transposition table in case the relevant // entries have been overwritten during the search. for (size_t i = 0; i <= PVIdx; ++i) rootMoves[i].insert_pv_in_tt(rootPos); - // If search has been stopped break immediately. Sorting and + // If search has been stopped, break immediately. Sorting and // writing PV back to TT is safe because RootMoves is still - // valid, although it refers to previous iteration. + // valid, although it refers to the previous iteration. if (Signals.stop) break; // When failing high/low give some update (without cluttering // the UI) before a re-search. - if ( isMainThread + if ( mainThread && multiPV == 1 && (bestValue <= alpha || bestValue >= beta) && Time.elapsed() > 3000) @@ -439,9 +477,9 @@ void Thread::search(bool isMainThread) { beta = (alpha + beta) / 2; alpha = std::max(bestValue - delta, -VALUE_INFINITE); - if (isMainThread) + if (mainThread) { - Signals.failedLowAtRoot = true; + mainThread->failedLow = true; Signals.stopOnPonderhit = false; } } @@ -461,7 +499,7 @@ void Thread::search(bool isMainThread) { // Sort the PV lines searched so far and update the GUI std::stable_sort(rootMoves.begin(), rootMoves.begin() + PVIdx + 1); - if (!isMainThread) + if (!mainThread) break; if (Signals.stop) @@ -472,7 +510,10 @@ void Thread::search(bool isMainThread) { sync_cout << UCI::pv(rootPos, rootDepth, alpha, beta) << sync_endl; } - if (!isMainThread) + if (!Signals.stop) + completedDepth = rootDepth; + + if (!mainThread) continue; // If skill level is enabled and time is up, pick a sub-optimal best move @@ -492,16 +533,23 @@ void Thread::search(bool isMainThread) { { // Take some extra time if the best move has changed if (rootDepth > 4 * ONE_PLY && multiPV == 1) - Time.pv_instability(BestMoveChanges); + Time.pv_instability(mainThread->bestMoveChanges); - // Stop the search if only one legal move is available or all - // of the available time has been used or we matched an easyMove + // Stop the search if only one legal move is available, or if all + // of the available time has been used, or if we matched an easyMove // from the previous search and just did a fast verification. + const bool F[] = { !mainThread->failedLow, + bestValue >= mainThread->previousScore }; + + int improvingFactor = 640 - 160*F[0] - 126*F[1] - 124*F[0]*F[1]; + + bool doEasyMove = rootMoves[0].pv[0] == easyMove + && mainThread->bestMoveChanges < 0.03 + && Time.elapsed() > Time.available() * 25 / 206; + if ( rootMoves.size() == 1 - || Time.elapsed() > Time.available() - || ( rootMoves[0].pv[0] == easyMove - && BestMoveChanges < 0.03 - && Time.elapsed() > Time.available() / 10)) + || Time.elapsed() > Time.available() * improvingFactor / 640 + || (mainThread->easyMovePlayed = doEasyMove)) { // If we are allowed to ponder do not stop the search now but // keep pondering until the GUI sends "ponderhit" or "stop". @@ -519,15 +567,12 @@ void Thread::search(bool isMainThread) { } } - searching = false; - notify_one(); // Wake up main thread if is sleeping waiting for us - - if (!isMainThread) + if (!mainThread) return; // Clear any candidate easy move that wasn't stable for the last search // iterations; the second condition prevents consecutive fast moves. - if (EasyMove.stableCnt < 6 || Time.elapsed() < Time.available()) + if (EasyMove.stableCnt < 6 || mainThread->easyMovePlayed) EasyMove.clear(); // If skill level is enabled, swap best PV line with the sub-optimal one @@ -539,12 +584,7 @@ void Thread::search(bool isMainThread) { namespace { - // search<>() is the main search function for both PV and non-PV nodes and for - // normal and SplitPoint nodes. When called just after a split point the search - // is simpler because we have already probed the hash table, done a null move - // search, and searched the first move before splitting, so we don't have to - // 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. + // search<>() is the main search function for both PV and non-PV nodes template Value search(Position& pos, Stack* ss, Value alpha, Value beta, Depth depth, bool cutNode) { @@ -554,7 +594,7 @@ namespace { assert(-VALUE_INFINITE <= alpha && alpha < beta && beta <= VALUE_INFINITE); assert(PvNode || (alpha == beta - 1)); - assert(depth > DEPTH_ZERO); + assert(DEPTH_ZERO < depth && depth < DEPTH_MAX); Move pv[MAX_PLY+1], quietsSearched[64]; StateInfo st; @@ -574,6 +614,20 @@ namespace { bestValue = -VALUE_INFINITE; ss->ply = (ss-1)->ply + 1; + // Check for the available remaining time + if (thisThread->resetCalls.load(std::memory_order_relaxed)) + { + thisThread->resetCalls = false; + thisThread->callsCnt = 0; + } + if (++thisThread->callsCnt > 4096) + { + for (Thread* th : Threads) + th->resetCalls = true; + + check_time(); + } + // Used to send selDepth info to GUI if (PvNode && thisThread->maxPly < ss->ply) thisThread->maxPly = ss->ply; @@ -581,7 +635,7 @@ namespace { if (!RootNode) { // Step 2. Check for aborted search and immediate draw - if (Signals.stop || pos.is_draw() || ss->ply >= MAX_PLY) + if (Signals.stop.load(std::memory_order_relaxed) || pos.is_draw() || ss->ply >= MAX_PLY) return ss->ply >= MAX_PLY && !inCheck ? evaluate(pos) : DrawValue[pos.side_to_move()]; @@ -599,8 +653,8 @@ namespace { assert(0 <= ss->ply && ss->ply < MAX_PLY); - ss->currentMove = ss->ttMove = (ss+1)->excludedMove = bestMove = MOVE_NONE; - (ss+1)->skipEarlyPruning = false; (ss+1)->reduction = DEPTH_ZERO; + ss->currentMove = (ss+1)->excludedMove = bestMove = MOVE_NONE; + (ss+1)->skipEarlyPruning = false; (ss+2)->killers[0] = (ss+2)->killers[1] = MOVE_NONE; // Step 4. Transposition table lookup. We don't want the score of a partial @@ -610,8 +664,8 @@ namespace { posKey = excludedMove ? pos.exclusion_key() : pos.key(); tte = TT.probe(posKey, ttHit); ttValue = ttHit ? value_from_tt(tte->value(), ss->ply) : VALUE_NONE; - ss->ttMove = ttMove = RootNode ? thisThread->rootMoves[thisThread->PVIdx].pv[0] - : ttHit ? tte->move() : MOVE_NONE; + ttMove = RootNode ? thisThread->rootMoves[thisThread->PVIdx].pv[0] + : ttHit ? tte->move() : MOVE_NONE; // At non-PV nodes we check for an early TT cutoff if ( !PvNode @@ -803,7 +857,7 @@ moves_loop: // When in check search starts from here Square prevSq = to_sq((ss-1)->currentMove); Move cm = thisThread->counterMoves[pos.piece_on(prevSq)][prevSq]; - const CounterMovesStats& cmh = CounterMovesHistory[pos.piece_on(prevSq)][prevSq]; + const CounterMoveStats& cmh = CounterMoveHistory[pos.piece_on(prevSq)][prevSq]; MovePicker mp(pos, ttMove, depth, thisThread->history, cmh, cm, ss); CheckInfo ci(pos); @@ -839,15 +893,10 @@ moves_loop: // When in check search starts from here ss->moveCount = ++moveCount; - if (RootNode && thisThread == Threads.main()) - { - Signals.firstRootMove = (moveCount == 1); - - if (Time.elapsed() > 3000) - sync_cout << "info depth " << depth / ONE_PLY - << " currmove " << UCI::move(move, pos.is_chess960()) - << " currmovenumber " << moveCount + thisThread->PVIdx << sync_endl; - } + if (RootNode && thisThread == Threads.main() && Time.elapsed() > 3000) + sync_cout << "info depth " << depth / ONE_PLY + << " currmove " << UCI::move(move, pos.is_chess960()) + << " currmovenumber " << moveCount + thisThread->PVIdx << sync_endl; if (PvNode) (ss+1)->pv = nullptr; @@ -901,7 +950,8 @@ moves_loop: // When in check search starts from here continue; // History based pruning - if ( depth <= 3 * ONE_PLY + if ( depth <= 4 * ONE_PLY + && move != ss->killers[0] && thisThread->history[pos.moved_piece(move)][to_sq(move)] < VALUE_ZERO && cmh[pos.moved_piece(move)][to_sq(move)] < VALUE_ZERO) continue; @@ -944,41 +994,41 @@ moves_loop: // When in check search starts from here // re-searched at full depth. if ( depth >= 3 * ONE_PLY && moveCount > 1 - && !captureOrPromotion - && move != ss->killers[0] - && move != ss->killers[1]) + && !captureOrPromotion) { - ss->reduction = reduction(improving, depth, moveCount); + Depth r = reduction(improving, depth, moveCount); // Increase reduction for cut nodes and moves with a bad history if ( (!PvNode && cutNode) || ( thisThread->history[pos.piece_on(to_sq(move))][to_sq(move)] < VALUE_ZERO && cmh[pos.piece_on(to_sq(move))][to_sq(move)] <= VALUE_ZERO)) - ss->reduction += ONE_PLY; - - // Decrease reduction for moves with a good history - if ( thisThread->history[pos.piece_on(to_sq(move))][to_sq(move)] > VALUE_ZERO - && cmh[pos.piece_on(to_sq(move))][to_sq(move)] > VALUE_ZERO) - ss->reduction = std::max(DEPTH_ZERO, ss->reduction - ONE_PLY); - - // Decrease reduction for moves that escape a capture - if ( ss->reduction + r += ONE_PLY; + + // Decrease/increase reduction for moves with a good/bad history + int rHist = ( thisThread->history[pos.piece_on(to_sq(move))][to_sq(move)] + + cmh[pos.piece_on(to_sq(move))][to_sq(move)]) / 14980; + r = std::max(DEPTH_ZERO, r - rHist * ONE_PLY); + + // Decrease reduction for moves that escape a capture. Filter out + // castling moves, because they are coded as "king captures rook" and + // hence break make_move(). Also use see() instead of see_sign(), + // because the destination square is empty. + if ( r && type_of(move) == NORMAL && type_of(pos.piece_on(to_sq(move))) != PAWN && pos.see(make_move(to_sq(move), from_sq(move))) < VALUE_ZERO) - ss->reduction = std::max(DEPTH_ZERO, ss->reduction - ONE_PLY); + r = std::max(DEPTH_ZERO, r - ONE_PLY); - Depth d = std::max(newDepth - ss->reduction, ONE_PLY); + Depth d = std::max(newDepth - r, ONE_PLY); value = -search(pos, ss+1, -(alpha+1), -alpha, d, true); - doFullDepthSearch = (value > alpha && ss->reduction != DEPTH_ZERO); - ss->reduction = DEPTH_ZERO; + doFullDepthSearch = (value > alpha && r != DEPTH_ZERO); } else doFullDepthSearch = !PvNode || moveCount > 1; - // Step 16. Full depth search, when LMR is skipped or fails high + // Step 16. Full depth search when LMR is skipped or fails high if (doFullDepthSearch) value = newDepth < ONE_PLY ? givesCheck ? -qsearch(pos, ss+1, -(alpha+1), -alpha, DEPTH_ZERO) @@ -987,7 +1037,7 @@ moves_loop: // When in check search starts from here // 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. + // parent node fail low with value <= alpha and try another move. if (PvNode && (moveCount == 1 || (value > alpha && (RootNode || value < beta)))) { (ss+1)->pv = pv; @@ -1004,11 +1054,11 @@ moves_loop: // When in check search starts from here assert(value > -VALUE_INFINITE && value < VALUE_INFINITE); - // Step 18. Check for new best move + // Step 18. Check for a new best move // Finished searching the move. If a stop occurred, the return value of // the search cannot be trusted, and we return immediately without // updating best move, PV and TT. - if (Signals.stop) + if (Signals.stop.load(std::memory_order_relaxed)) return VALUE_ZERO; if (RootNode) @@ -1031,7 +1081,7 @@ moves_loop: // When in check search starts from here // iteration. This information is used for time management: When // the best move changes frequently, we allocate some more time. if (moveCount > 1 && thisThread == Threads.main()) - ++BestMoveChanges; + ++static_cast(thisThread)->bestMoveChanges; } else // All other moves but the PV are set to the lowest value: this is @@ -1072,7 +1122,7 @@ moves_loop: // When in check search starts from here quietsSearched[quietCount++] = move; } - // Following condition would detect a stop only after move loop has been + // The following condition would detect a stop 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. /* @@ -1082,7 +1132,7 @@ moves_loop: // When in check search starts from here // 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. If we are in a singular extension search then + // must be a mate or a stalemate. If we are in a singular extension search then // return a fail low score. if (!moveCount) bestValue = excludedMove ? alpha @@ -1100,9 +1150,9 @@ moves_loop: // When in check search starts from here && is_ok((ss - 1)->currentMove) && is_ok((ss - 2)->currentMove)) { - Value bonus = Value((depth / ONE_PLY) * (depth / ONE_PLY)); + Value bonus = Value((depth / ONE_PLY) * (depth / ONE_PLY) + depth / ONE_PLY - 1); Square prevPrevSq = to_sq((ss - 2)->currentMove); - CounterMovesStats& prevCmh = CounterMovesHistory[pos.piece_on(prevPrevSq)][prevPrevSq]; + CounterMoveStats& prevCmh = CounterMoveHistory[pos.piece_on(prevPrevSq)][prevPrevSq]; prevCmh.update(pos.piece_on(prevSq), prevSq, bonus); } @@ -1288,7 +1338,7 @@ moves_loop: // When in check search starts from here assert(value > -VALUE_INFINITE && value < VALUE_INFINITE); - // Check for new best move + // Check for a new best move if (value > bestValue) { bestValue = value; @@ -1364,8 +1414,8 @@ moves_loop: // When in check search starts from here } - // update_stats() updates killers, history, countermove history and - // countermoves stats for a quiet best move. + // update_stats() updates killers, history, countermove and countermove + // history when a new quiet best move is found. void update_stats(const Position& pos, Stack* ss, Move move, Depth depth, Move* quiets, int quietsCnt) { @@ -1376,10 +1426,10 @@ moves_loop: // When in check search starts from here ss->killers[0] = move; } - Value bonus = Value((depth / ONE_PLY) * (depth / ONE_PLY)); + Value bonus = Value((depth / ONE_PLY) * (depth / ONE_PLY) + depth / ONE_PLY - 1); Square prevSq = to_sq((ss-1)->currentMove); - CounterMovesStats& cmh = CounterMovesHistory[pos.piece_on(prevSq)][prevSq]; + CounterMoveStats& cmh = CounterMoveHistory[pos.piece_on(prevSq)][prevSq]; Thread* thisThread = pos.this_thread(); thisThread->history.update(pos.moved_piece(move), to_sq(move), bonus); @@ -1399,14 +1449,14 @@ moves_loop: // When in check search starts from here cmh.update(pos.moved_piece(quiets[i]), to_sq(quiets[i]), -bonus); } - // Extra penalty for TT move in previous ply when it gets refuted + // Extra penalty for a quiet TT move in previous ply when it gets refuted if ( (ss-1)->moveCount == 1 && !pos.captured_piece_type() && is_ok((ss-2)->currentMove)) { Square prevPrevSq = to_sq((ss-2)->currentMove); - CounterMovesStats& prevCmh = CounterMovesHistory[pos.piece_on(prevPrevSq)][prevPrevSq]; - prevCmh.update(pos.piece_on(prevSq), prevSq, -bonus - 2 * depth / ONE_PLY - 1); + CounterMoveStats& prevCmh = CounterMoveHistory[pos.piece_on(prevPrevSq)][prevPrevSq]; + prevCmh.update(pos.piece_on(prevSq), prevSq, -bonus - 2 * (depth + 1) / ONE_PLY); } } @@ -1416,23 +1466,23 @@ moves_loop: // When in check search starts from here Move Skill::pick_best(size_t multiPV) { - // PRNG sequence should be non-deterministic, so we seed it with the time at init const Search::RootMoveVector& rootMoves = Threads.main()->rootMoves; - static PRNG rng(now()); + static PRNG rng(now()); // PRNG sequence should be non-deterministic // RootMoves are already sorted by score in descending order - int variance = std::min(rootMoves[0].score - rootMoves[multiPV - 1].score, PawnValueMg); + Value topScore = rootMoves[0].score; + int delta = std::min(topScore - rootMoves[multiPV - 1].score, PawnValueMg); int weakness = 120 - 2 * level; int maxScore = -VALUE_INFINITE; - // Choose best move. For each move score we add two terms both dependent on - // weakness. One deterministic and bigger for weaker levels, and one random, - // then we choose the move with the resulting highest score. + // 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 + // random. Then we choose the move with the resulting highest score. for (size_t i = 0; i < multiPV; ++i) { // This is our magic formula - int push = ( weakness * int(rootMoves[0].score - rootMoves[i].score) - + variance * (rng.rand() % weakness)) / 128; + int push = ( weakness * int(topScore - rootMoves[i].score) + + delta * (rng.rand() % weakness)) / 128; if (rootMoves[i].score + push > maxScore) { @@ -1440,9 +1490,37 @@ moves_loop: // When in check search starts from here best = rootMoves[i].pv[0]; } } + return best; } + + // check_time() is used to print debug info and, more importantly, to detect + // when we are out of available time and thus stop the search. + + void check_time() { + + static TimePoint lastInfoTime = now(); + + int elapsed = Time.elapsed(); + TimePoint tick = Limits.startTime + elapsed; + + if (tick - lastInfoTime >= 1000) + { + lastInfoTime = tick; + dbg_print(); + } + + // An engine may not stop pondering until told so by the GUI + if (Limits.ponder) + return; + + if ( (Limits.use_time_management() && elapsed > Time.maximum() - 10) + || (Limits.movetime && elapsed >= Limits.movetime) + || (Limits.nodes && Threads.nodes_searched() >= Limits.nodes)) + Signals.stop = true; + } + } // namespace @@ -1517,7 +1595,8 @@ void RootMove::insert_pv_in_tt(Position& pos) { TTEntry* tte = TT.probe(pos.key(), ttHit); if (!ttHit || tte->move() != m) // Don't overwrite correct entries - tte->save(pos.key(), VALUE_NONE, BOUND_NONE, DEPTH_NONE, m, VALUE_NONE, TT.generation()); + tte->save(pos.key(), VALUE_NONE, BOUND_NONE, DEPTH_NONE, + m, VALUE_NONE, TT.generation()); pos.do_move(m, *st++, pos.gives_check(m, CheckInfo(pos))); } @@ -1527,10 +1606,10 @@ void RootMove::insert_pv_in_tt(Position& pos) { } -/// RootMove::extract_ponder_from_tt() is called in case we have no ponder move before -/// exiting the search, for instance in case we stop the search during a fail high at -/// root. We try hard to have a ponder move to return to the GUI, otherwise in case of -/// 'ponder on' we have nothing to think on. +/// RootMove::extract_ponder_from_tt() is called in case we have no ponder move +/// before exiting the search, for instance, in case we stop the search during a +/// fail high at root. We try hard to have a ponder move to return to the GUI, +/// otherwise in case of 'ponder on' we have nothing to think on. bool RootMove::extract_ponder_from_tt(Position& pos) { @@ -1552,40 +1631,3 @@ bool RootMove::extract_ponder_from_tt(Position& pos) return false; } - - -/// check_time() is called by the timer thread when the timer triggers. It is -/// used to print debug info and, more importantly, to detect when we are out of -/// available time and thus stop the search. - -void check_time() { - - static TimePoint lastInfoTime = now(); - int elapsed = Time.elapsed(); - - if (now() - lastInfoTime >= 1000) - { - lastInfoTime = now(); - dbg_print(); - } - - // An engine may not stop pondering until told so by the GUI - if (Limits.ponder) - return; - - if (Limits.use_time_management()) - { - bool stillAtFirstMove = Signals.firstRootMove - && !Signals.failedLowAtRoot - && elapsed > Time.available() * 75 / 100; - - if ( stillAtFirstMove - || elapsed > Time.maximum() - 2 * TimerThread::Resolution) - Signals.stop = true; - } - else if (Limits.movetime && elapsed >= Limits.movetime) - Signals.stop = true; - - else if (Limits.nodes && Threads.nodes_searched() >= Limits.nodes) - Signals.stop = true; -}