From: mstembera Date: Thu, 12 Mar 2015 19:49:30 +0000 (+0000) Subject: New easy move implementation X-Git-Url: https://git.sesse.net/?p=stockfish;a=commitdiff_plain;h=062ca91db5d9f4b86f0218666b50d3f9456b0ba2 New easy move implementation Spend much less time in positions where one move is much better than all other alternatives. We carry forward pv stability information from the previous search to identify such positions. It's based on my old InstaMove idea but with two significant improvements. 1) Much better instability detection inside the search itself. 2) When it's time to make a FastMove we no longer make it instantly but still spend at least 10% of normal time verifying it. Credit to Gull for the inspiration. BIG thanks to Gary because this would not work without accurate PV! 20K ELO: 8.22 +-3.0 (95%) LOS: 100.0% Total: 20000 W: 4203 L: 3730 D: 12067 STC LLR: 2.96 (-2.94,2.94) [-1.50,4.50] Total: 23266 W: 4662 L: 4492 D: 14112 LTC LLR: 2.95 (-2.94,2.94) [0.00,6.00] Total: 12470 W: 2091 L: 1931 D: 8448 Resolves #283 --- diff --git a/src/search.cpp b/src/search.cpp index f374b462..ca1fe49c 100644 --- a/src/search.cpp +++ b/src/search.cpp @@ -90,6 +90,45 @@ 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; @@ -281,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; @@ -405,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(), @@ -1012,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 diff --git a/src/timeman.h b/src/timeman.h index b904e1c1..551d7385 100644 --- a/src/timeman.h +++ b/src/timeman.h @@ -27,7 +27,7 @@ class TimeManager { public: void init(const Search::LimitsType& limits, Color us, int ply); void pv_instability(double bestMoveChanges) { unstablePvFactor = 1 + bestMoveChanges; } - int available_time() const { return int(optimumSearchTime * unstablePvFactor * 0.71); } + int available_time() const { return int(optimumSearchTime * unstablePvFactor * 0.76); } int maximum_time() const { return maximumSearchTime; } private: