From c6ce612f0ada9b5f0d9530128545d1ee7d58b3e5 Mon Sep 17 00:00:00 2001 From: protonspring Date: Wed, 13 May 2020 11:52:41 -0600 Subject: [PATCH 1/1] Simplify Time Management This is a functional simplification of the time management system. With this patch, there is a simple equation for each of two distinct time controls: basetime + increment, and x moves in y seconds (+increment). These equations are easy to plot and understand making future modifications or adding additional time controls much easier. SlowMover is reset to 100 so that is has no effect unless a user changes it. There are two scaling variables: * Opt_scale is a scale factor (or percentage) of time to use for this current move. * Max_scale is a scale factor to apply to the resulting optimumTime. There seems to be some elo gain in most scenarios. Better performance is attributable to one of two things: * minThinkingTime was not allowing reasonable time calculations for very short games like 10+0 or 10+0.01. This is because adding almost no increment and substracting move overhead for 50 moves quickly results in almost 0 time very early in the game. Master depended on minThinkingTime to handle these short games instead of good time management. This patch addresses this issue by lowering minThinkingTime to 0 and adjusting moverOverhead if there are very low increments. * Notice that the time distribution curves tail downward for the first 10 moves or so. This causes less time to attribute for very early moves leaving more time available for middle moves where more important decisions happen. Here is a summary of tests for this version at different time controls: SMP 5+0.05 LLR: 2.97 (-2.94,2.94) {-1.50,0.50} Total: 46544 W: 7175 L: 7089 D: 32280 Ptnml(0-2): 508, 4826, 12517, 4914, 507 https://tests.stockfishchess.org/tests/user/protonspring STC LLR: 2.94 (-2.94,2.94) {-1.50,0.50} Total: 20480 W: 3872 L: 3718 D: 12890 Ptnml(0-2): 295, 2364, 4824, 2406, 351 https://tests.stockfishchess.org/tests/view/5ebc343e7dd5693aad4e6873 STC, sudden death LLR: 2.93 (-2.94,2.94) {-1.50,0.50} Total: 7024 W: 1706 L: 1489 D: 3829 Ptnml(0-2): 149, 813, 1417, 938, 195 https://tests.stockfishchess.org/tests/view/5ebc346f7dd5693aad4e6875 STC, TCEC style LLR: 2.95 (-2.94,2.94) {-1.50,0.50} Total: 4192 W: 1014 L: 811 D: 2367 Ptnml(0-2): 66, 446, 912, 563, 109 https://tests.stockfishchess.org/tests/view/5ebc34857dd5693aad4e6877 40/10 LLR: 2.93 (-2.94,2.94) {-1.50,0.50} Total: 54032 W: 10592 L: 10480 D: 32960 Ptnml(0-2): 967, 6148, 12677, 6254, 970 https://tests.stockfishchess.org/tests/view/5ebc50597dd5693aad4e688d LTC, sudden death LLR: 2.95 (-2.94,2.94) {-1.50,0.50} Total: 9152 W: 1391 L: 1263 D: 6498 Ptnml(0-2): 75, 888, 2526, 1008, 79 https://tests.stockfishchess.org/tests/view/5ebc6f5c7dd5693aad4e689b LTC LLR: 2.98 (-2.94,2.94) {-1.50,0.50} Total: 12344 W: 1563 L: 1459 D: 9322 Ptnml(0-2): 70, 1103, 3740, 1171, 88 https://tests.stockfishchess.org/tests/view/5ebc6f4c7dd5693aad4e6899 closes https://github.com/official-stockfish/Stockfish/pull/2678 Bench: 4395562 --- src/timeman.cpp | 107 ++++++++++++++++------------------------------ src/ucioption.cpp | 4 +- 2 files changed, 40 insertions(+), 71 deletions(-) diff --git a/src/timeman.cpp b/src/timeman.cpp index 0848be42..f794ab13 100644 --- a/src/timeman.cpp +++ b/src/timeman.cpp @@ -28,58 +28,10 @@ TimeManagement Time; // Our global time management object -namespace { - - enum TimeType { OptimumTime, MaxTime }; - - constexpr int MoveHorizon = 50; // Plan time management at most this many moves ahead - constexpr double MaxRatio = 7.3; // When in trouble, we can step over reserved time with this ratio - constexpr double StealRatio = 0.34; // However we must not steal time from remaining moves over this ratio - - - // move_importance() is a skew-logistic function based on naive statistical - // analysis of "how many games are still undecided after n half-moves". Game - // is considered "undecided" as long as neither side has >275cp advantage. - // Data was extracted from the CCRL game database with some simple filtering criteria. - - double move_importance(int ply) { - - constexpr double XScale = 6.85; - constexpr double XShift = 64.5; - constexpr double Skew = 0.171; - - return pow((1 + exp((ply - XShift) / XScale)), -Skew) + DBL_MIN; // Ensure non-zero - } - - template - TimePoint remaining(TimePoint myTime, int movesToGo, int ply, TimePoint slowMover) { - - constexpr double TMaxRatio = (T == OptimumTime ? 1.0 : MaxRatio); - constexpr double TStealRatio = (T == OptimumTime ? 0.0 : StealRatio); - - double moveImportance = (move_importance(ply) * slowMover) / 100.0; - double otherMovesImportance = 0.0; - - for (int i = 1; i < movesToGo; ++i) - otherMovesImportance += move_importance(ply + 2 * i); - - double ratio1 = (TMaxRatio * moveImportance) / (TMaxRatio * moveImportance + otherMovesImportance); - double ratio2 = (moveImportance + TStealRatio * otherMovesImportance) / (moveImportance + otherMovesImportance); - - return TimePoint(myTime * std::min(ratio1, ratio2)); // Intel C++ asks for an explicit cast - } - -} // namespace - - -/// init() is called at the beginning of the search and calculates the allowed -/// thinking time out of the time control and current game ply. We support four -/// different kinds of time controls, passed in 'limits': -/// -/// inc == 0 && movestogo == 0 means: x basetime [sudden death!] -/// inc == 0 && movestogo != 0 means: x moves in y minutes -/// inc > 0 && movestogo == 0 means: x basetime + z increment -/// inc > 0 && movestogo != 0 means: x moves in y minutes + z increment +/// init() is called at the beginning of the search and calculates the bounds +/// of time allowed for the current game ply. We currently support: +// 1) x basetime (+z increment) +// 2) x moves in y seconds (+z increment) void TimeManagement::init(Search::LimitsType& limits, Color us, int ply) { @@ -87,7 +39,10 @@ void TimeManagement::init(Search::LimitsType& limits, Color us, int ply) { TimePoint moveOverhead = Options["Move Overhead"]; TimePoint slowMover = Options["Slow Mover"]; TimePoint npmsec = Options["nodestime"]; - TimePoint hypMyTime; + + // opt_scale is a percentage of available time to use for the current move. + // max_scale is a multiplier applied to optimumTime. + double opt_scale, max_scale; // If we have to play in 'nodes as time' mode, then convert from time // to nodes, and use resulting values in time management formulas. @@ -105,29 +60,43 @@ void TimeManagement::init(Search::LimitsType& limits, Color us, int ply) { } startTime = limits.startTime; - optimumTime = maximumTime = std::max(limits.time[us], minThinkingTime); - const int maxMTG = limits.movestogo ? std::min(limits.movestogo, MoveHorizon) : MoveHorizon; + //Maximum move horizon of 50 moves + int mtg = limits.movestogo ? std::min(limits.movestogo, 50) : 50; - // We calculate optimum time usage for different hypothetical "moves to go" values - // and choose the minimum of calculated search time values. Usually the greatest - // hypMTG gives the minimum values. - for (int hypMTG = 1; hypMTG <= maxMTG; ++hypMTG) - { - // Calculate thinking time for hypothetical "moves to go"-value - hypMyTime = limits.time[us] - + limits.inc[us] * (hypMTG - 1) - - moveOverhead * (2 + std::min(hypMTG, 40)); + // Adjust moveOverhead if there are tiny increments + moveOverhead = std::max(10, std::min(limits.inc[us] / 2, moveOverhead)); + + // Make sure timeLeft is > 0 since we may use it as a divisor + TimePoint timeLeft = std::max(TimePoint(1), + limits.time[us] + limits.inc[us] * (mtg - 1) - moveOverhead * (2 + mtg)); - hypMyTime = std::max(hypMyTime, TimePoint(0)); + // A user may scale time usage by setting UCI option "Slow Mover" + // Default is 100 and changing this value will probably lose elo. + timeLeft = slowMover * timeLeft / 100; - TimePoint t1 = minThinkingTime + remaining(hypMyTime, hypMTG, ply, slowMover); - TimePoint t2 = minThinkingTime + remaining(hypMyTime, hypMTG, ply, slowMover); + // x basetime (+ z increment) + // If there is a healthy increment, timeLeft can exceed actual available + // game time for the current move, so also cap to 20% of available game time. + if (limits.movestogo == 0) + { + opt_scale = std::min(0.007 + std::pow(ply + 3.0, 0.5) / 250.0, + 0.2 * limits.time[us] / double(timeLeft)); + max_scale = 4 + std::pow(ply + 3, 0.3); + } - optimumTime = std::min(t1, optimumTime); - maximumTime = std::min(t2, maximumTime); + // x moves in y seconds (+ z increment) + else + { + opt_scale = std::min((0.8 + ply / 128.0) / mtg, + 0.8 * limits.time[us] / double(timeLeft)); + max_scale = std::min(6.3, 1.5 + 0.11 * mtg); } + // Never use more than 80% of the available time for this move + optimumTime = std::max(minThinkingTime, opt_scale * timeLeft); + maximumTime = std::min(0.8 * limits.time[us] - moveOverhead, max_scale * optimumTime); + if (Options["Ponder"]) optimumTime += optimumTime / 4; } diff --git a/src/ucioption.cpp b/src/ucioption.cpp index 26fcf302..ad576fda 100644 --- a/src/ucioption.cpp +++ b/src/ucioption.cpp @@ -69,8 +69,8 @@ void init(OptionsMap& o) { o["MultiPV"] << Option(1, 1, 500); o["Skill Level"] << Option(20, 0, 20); o["Move Overhead"] << Option(30, 0, 5000); - o["Minimum Thinking Time"] << Option(20, 0, 5000); - o["Slow Mover"] << Option(84, 10, 1000); + o["Minimum Thinking Time"] << Option( 0, 0, 5000); + o["Slow Mover"] << Option(100, 10, 1000); o["nodestime"] << Option(0, 0, 10000); o["UCI_Chess960"] << Option(false); o["UCI_AnalyseMode"] << Option(false); -- 2.39.2