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

diff --git a/src/timeman.cpp b/src/timeman.cpp
index 0848be420c056beef1356bb85cca99c43ff1c244..f794ab133326e8a31ed8a50044a7d62c92726cdc 100644 (file)
--- a/src/timeman.cpp
+++ b/src/timeman.cpp
@@ -28,58 +28,10 @@
 
 TimeManagement Time; // Our global time management object
 
 
 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<TimeType T>
-  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) {
 
 
 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 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.
 
   // 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;
   }
 
   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<int>(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<OptimumTime>(hypMyTime, hypMTG, ply, slowMover);
-      TimePoint t2 = minThinkingTime + remaining<MaxTime    >(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<int>(minThinkingTime, opt_scale * timeLeft);
+  maximumTime = std::min(0.8 * limits.time[us] - moveOverhead, max_scale * optimumTime);
+

   if (Options["Ponder"])
       optimumTime += optimumTime / 4;
 }
   if (Options["Ponder"])
       optimumTime += optimumTime / 4;
 }

diff --git a/src/ucioption.cpp b/src/ucioption.cpp
index 26fcf30227a0cf209bffe006230a49ea336ce569..ad576fda2d10fe55c8f49a4f61a283953396eba1 100644 (file)
--- 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["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);
   o["nodestime"]             << Option(0, 0, 10000);
   o["UCI_Chess960"]          << Option(false);
   o["UCI_AnalyseMode"]       << Option(false);