X-Git-Url: https://git.sesse.net/?p=stockfish;a=blobdiff_plain;f=src%2Fsearch.cpp;h=e0ba79380c3ecbce68f2431ceeb4952e2383f970;hp=681acb8141a0e1b5d7c8def9569ce28e8bb15ffc;hb=e5da0e4b79b405da5bdc42f6fb4c2ba49afba00a;hpb=be509525336b65419e708678abe4e16efb5f6f4d diff --git a/src/search.cpp b/src/search.cpp index 681acb81..e0ba7938 100644 --- a/src/search.cpp +++ b/src/search.cpp @@ -90,11 +90,51 @@ namespace { Move best = MOVE_NONE; }; + struct FastMove { + FastMove() { clear(); } + + inline void clear() { + expectedPosKey = 0; + pv3[0] = pv3[1] = pv3[2] = MOVE_NONE; + stableCnt = 0; + } + + void update(Position& pos) { + // Keep track how many times in a row the PV stays stable 3 ply deep. + const std::vector& RMpv = RootMoves[0].pv; + if (RMpv.size() >= 3) + { + if (pv3[2] == RMpv[2]) + stableCnt++; + else + stableCnt = 0, pv3[2] = RMpv[2]; + + if (!expectedPosKey || pv3[0] != RMpv[0] || pv3[1] != RMpv[1]) + { + pv3[0] = RMpv[0], pv3[1] = RMpv[1]; + StateInfo st[2]; + pos.do_move(RMpv[0], st[0], pos.gives_check(RMpv[0], CheckInfo(pos))); + pos.do_move(RMpv[1], st[1], pos.gives_check(RMpv[1], CheckInfo(pos))); + expectedPosKey = pos.key(); + pos.undo_move(RMpv[1]); + pos.undo_move(RMpv[0]); + } + } + else + clear(); + } + + Key expectedPosKey; + Move pv3[3]; + int stableCnt; + } FM; + size_t PVIdx; TimeManager TimeMgr; double BestMoveChanges; Value DrawValue[COLOR_NB]; HistoryStats History; + CounterMovesHistoryStats CounterMovesHistory; GainsStats Gains; MovesStats Countermoves, Followupmoves; @@ -280,6 +320,10 @@ namespace { Depth depth; Value bestValue, alpha, beta, delta; + // Init fastMove if the previous search generated a candidate and we now got the predicted position. + const Move fastMove = (FM.expectedPosKey == pos.key()) ? FM.pv3[2] : MOVE_NONE; + FM.clear(); + std::memset(ss-2, 0, 5 * sizeof(Stack)); depth = DEPTH_ZERO; @@ -289,6 +333,7 @@ namespace { TT.new_search(); History.clear(); + CounterMovesHistory.clear(); Gains.clear(); Countermoves.clear(); Followupmoves.clear(); @@ -403,27 +448,43 @@ namespace { Signals.stop = true; // Do we have time for the next iteration? Can we stop searching now? - if (Limits.use_time_management() && !Signals.stop && !Signals.stopOnPonderhit) + if (Limits.use_time_management()) { - // Take some extra time if the best move has changed - if (depth > 4 * ONE_PLY && multiPV == 1) - TimeMgr.pv_instability(BestMoveChanges); - - // Stop the search if only one legal move is available or all - // of the available time has been used. - if ( RootMoves.size() == 1 - || now() - SearchTime > TimeMgr.available_time()) + if (!Signals.stop && !Signals.stopOnPonderhit) { - // If we are allowed to ponder do not stop the search now but - // keep pondering until the GUI sends "ponderhit" or "stop". - if (Limits.ponder) - Signals.stopOnPonderhit = true; - else - Signals.stop = true; + // Take some extra time if the best move has changed + if (depth > 4 * ONE_PLY && multiPV == 1) + TimeMgr.pv_instability(BestMoveChanges); + + // Stop the search if only one legal move is available or all + // of the available time has been used or we matched a fastMove + // from the previous search and just did a fast verification. + if ( RootMoves.size() == 1 + || now() - SearchTime > TimeMgr.available_time() + || ( fastMove == RootMoves[0].pv[0] + && BestMoveChanges < 0.03 + && 10 * (now() - SearchTime) > TimeMgr.available_time())) + { + // If we are allowed to ponder do not stop the search now but + // keep pondering until the GUI sends "ponderhit" or "stop". + if (Limits.ponder) + Signals.stopOnPonderhit = true; + else + Signals.stop = true; + } } + + // Update fast move stats. + FM.update(pos); } } + // Clear any candidate fast move that wasn't completely stable for at least + // the 6 final search iterations. (Independent of actual depth and thus TC.) + // Time condition prevents consecutive fast moves. + if (FM.stableCnt < 6 || now() - SearchTime < TimeMgr.available_time()) + FM.clear(); + // If skill level is enabled, swap best PV line with the sub-optimal one if (skill.enabled()) std::swap(RootMoves[0], *std::find(RootMoves.begin(), @@ -687,7 +748,7 @@ namespace { assert((ss-1)->currentMove != MOVE_NONE); assert((ss-1)->currentMove != MOVE_NULL); - MovePicker mp(pos, ttMove, History, pos.captured_piece_type()); + MovePicker mp(pos, ttMove, History, CounterMovesHistory, pos.captured_piece_type()); CheckInfo ci(pos); while ((move = mp.next_move()) != MOVE_NONE) @@ -726,7 +787,7 @@ moves_loop: // When in check and at SpNode search starts from here Move followupmoves[] = { Followupmoves[pos.piece_on(prevOwnMoveSq)][prevOwnMoveSq].first, Followupmoves[pos.piece_on(prevOwnMoveSq)][prevOwnMoveSq].second }; - MovePicker mp(pos, ttMove, depth, History, countermoves, followupmoves, ss); + MovePicker mp(pos, ttMove, depth, History, CounterMovesHistory, countermoves, followupmoves, ss); CheckInfo ci(pos); value = bestValue; // Workaround a bogus 'uninitialized' warning under gcc improving = ss->staticEval >= (ss-2)->staticEval @@ -765,7 +826,7 @@ moves_loop: // When in check and at SpNode search starts from here continue; moveCount = ++splitPoint->moveCount; - splitPoint->spinlock.release(); + splitPoint->mutex.unlock(); } else ++moveCount; @@ -834,7 +895,7 @@ moves_loop: // When in check and at SpNode search starts from here && moveCount >= FutilityMoveCounts[improving][depth]) { if (SpNode) - splitPoint->spinlock.acquire(); + splitPoint->mutex.lock(); continue; } @@ -853,7 +914,7 @@ moves_loop: // When in check and at SpNode search starts from here if (SpNode) { - splitPoint->spinlock.acquire(); + splitPoint->mutex.lock(); if (bestValue > splitPoint->bestValue) splitPoint->bestValue = bestValue; } @@ -865,7 +926,7 @@ moves_loop: // When in check and at SpNode search starts from here if (predictedDepth < 4 * ONE_PLY && pos.see_sign(move) < VALUE_ZERO) { if (SpNode) - splitPoint->spinlock.acquire(); + splitPoint->mutex.lock(); continue; } @@ -965,7 +1026,7 @@ moves_loop: // When in check and at SpNode search starts from here // Step 18. Check for new best move if (SpNode) { - splitPoint->spinlock.acquire(); + splitPoint->mutex.lock(); bestValue = splitPoint->bestValue; alpha = splitPoint->alpha; } @@ -1010,6 +1071,10 @@ moves_loop: // When in check and at SpNode search starts from here if (value > alpha) { + // Clear fast move if unstable. + if (PvNode && pos.key() == FM.expectedPosKey && (move != FM.pv3[2] || moveCount > 1)) + FM.clear(); + bestMove = SpNode ? splitPoint->bestMove = move : move; if (PvNode && !RootNode) // Update pv even in fail-high case @@ -1192,7 +1257,7 @@ moves_loop: // When in check and at SpNode search starts from here // to search the moves. Because the depth is <= 0 here, only captures, // queen promotions and checks (only if depth >= DEPTH_QS_CHECKS) will // be generated. - MovePicker mp(pos, ttMove, depth, History, to_sq((ss-1)->currentMove)); + MovePicker mp(pos, ttMove, depth, History, CounterMovesHistory, to_sq((ss-1)->currentMove)); CheckInfo ci(pos); // Loop through the moves until no moves remain or a beta cutoff occurs @@ -1356,7 +1421,16 @@ moves_loop: // When in check and at SpNode search starts from here if (is_ok((ss-1)->currentMove)) { Square prevMoveSq = to_sq((ss-1)->currentMove); - Countermoves.update(pos.piece_on(prevMoveSq), prevMoveSq, move); + Piece prevMovePiece = pos.piece_on(prevMoveSq); + Countermoves.update(prevMovePiece, prevMoveSq, move); + + HistoryStats& cmh = CounterMovesHistory[prevMovePiece][prevMoveSq]; + cmh.update(pos.moved_piece(move), to_sq(move), bonus); + for (int i = 0; i < quietsCnt; ++i) + { + Move m = quiets[i]; + cmh.update(pos.moved_piece(m), to_sq(m), -bonus); + } } if (is_ok((ss-2)->currentMove) && (ss-1)->currentMove == (ss-1)->ttMove) @@ -1526,13 +1600,12 @@ void Thread::idle_loop() { // If this thread has been assigned work, launch a search while (searching) { - Threads.spinlock.acquire(); + mutex.lock(); assert(activeSplitPoint); - SplitPoint* sp = activeSplitPoint; - Threads.spinlock.release(); + mutex.unlock(); Stack stack[MAX_PLY+4], *ss = stack+2; // To allow referencing (ss-2) and (ss+2) Position pos(*sp->pos, this); @@ -1540,7 +1613,7 @@ void Thread::idle_loop() { std::memcpy(ss-2, sp->ss-2, 5 * sizeof(Stack)); ss->splitPoint = sp; - sp->spinlock.acquire(); + sp->mutex.lock(); assert(activePosition == nullptr); @@ -1578,7 +1651,7 @@ 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. - sp->spinlock.release(); + sp->mutex.unlock(); // Try to late join to another split point if none of its slaves has // already finished. @@ -1618,25 +1691,29 @@ void Thread::idle_loop() { sp = bestSp; // Recheck the conditions under lock protection - Threads.spinlock.acquire(); - sp->spinlock.acquire(); + sp->mutex.lock(); if ( sp->allSlavesSearching - && sp->slavesMask.count() < MAX_SLAVES_PER_SPLITPOINT - && can_join(sp)) + && sp->slavesMask.count() < MAX_SLAVES_PER_SPLITPOINT) { - sp->slavesMask.set(idx); - activeSplitPoint = sp; - searching = true; + allocMutex.lock(); + + if (can_join(sp)) + { + sp->slavesMask.set(idx); + activeSplitPoint = sp; + searching = true; + } + + allocMutex.unlock(); } - sp->spinlock.release(); - Threads.spinlock.release(); + sp->mutex.unlock(); } } // Avoid races with notify_one() fired from last slave of the split point - std::unique_lock lk(mutex); + std::unique_lock lk(mutex); // If we are master and all slaves have finished then exit idle_loop if (this_sp && this_sp->slavesMask.none()) @@ -1687,18 +1764,17 @@ void check_time() { else if (Limits.nodes) { - Threads.spinlock.acquire(); - int64_t nodes = RootPos.nodes_searched(); // Loop across all split points and sum accumulated SplitPoint nodes plus // all the currently active positions nodes. + // FIXME: Racy... for (Thread* th : Threads) for (size_t i = 0; i < th->splitPointsSize; ++i) { SplitPoint& sp = th->splitPoints[i]; - sp.spinlock.acquire(); + sp.mutex.lock(); nodes += sp.nodes; @@ -1706,11 +1782,9 @@ void check_time() { if (sp.slavesMask.test(idx) && Threads[idx]->activePosition) nodes += Threads[idx]->activePosition->nodes_searched(); - sp.spinlock.release(); + sp.mutex.unlock(); } - Threads.spinlock.release(); - if (nodes >= Limits.nodes) Signals.stop = true; }