timeinfo.c

   1 #include <assert.h>
   2 #include <ctype.h>
   3 #include <stdio.h>
   4 #include <stdlib.h>
   5 #include <math.h>
   6 #include <time.h>
   7 #include <sys/time.h>
   8
   9 #define DEBUG
  10
  11 #include "debug.h"
  12 #include "tactics/util.h"
  13 #include "timeinfo.h"
  14
  15 /* Max net lag in seconds. TODO: estimate dynamically. */
  16 #define MAX_NET_LAG 2.0
  17 /* Minimal thinking time; in case reserved time gets smaller than MAX_NET_LAG,
  18  * this makes sure we play minimally sensible moves even in massive time
  19  * pressure; we still keep MAX_NET_LAG-MIN_THINK_WITH_LAG safety margin.
  20  * Note that this affects only lag adjustmnet - if reserved time *before*
  21  * lag adjustment gets too small, we still respect it and don't apply
  22  * MIN_THINK_WITH_LAG. */
  23 #define MIN_THINK_WITH_LAG (MAX_NET_LAG / 2)
  24 /* Reserve 15% of byoyomi time as safety margin if risk of losing on time */
  25 #define RESERVED_BYOYOMI_PERCENT 15
  26
  27 /* For safety, use at most 2 times the desired time on a single move
  28  * in sudden death and 1.1 times in byoyomi. */
  29 #define MAX_SUDDEN_DEATH_RATIO 2.0
  30 #define MAX_BYOYOMI_TIME_RATIO 1.1
  31
  32 bool
  33 time_parse(struct time_info *ti, char *s)
  34 {
  35         switch (s[0]) {
  36                 case '_': ti->period = TT_TOTAL; s++; break;
  37                 default: ti->period = TT_MOVE; break;
  38         }
  39         switch (s[0]) {
  40                 case '=':
  41                         ti->dim = TD_GAMES;
  42                         ti->len.games = atoi(++s);
  43                         break;
  44                 default:
  45                         if (!isdigit(s[0]))
  46                                 return false;
  47                         ti->dim = TD_WALLTIME;
  48                         ti->len.t.timer_start = 0;
  49                         if (ti->period == TT_TOTAL) {
  50                                 ti->len.t.main_time = atof(s);
  51                                 ti->len.t.byoyomi_time = 0.0;
  52                                 ti->len.t.byoyomi_time_max = 0.0;
  53                                 ti->len.t.byoyomi_periods = 0;
  54                                 ti->len.t.byoyomi_stones = 0;
  55                                 ti->len.t.byoyomi_stones_max = 0;
  56                         } else { assert(ti->period == TT_MOVE);
  57                                 ti->len.t.main_time = 0.0;
  58                                 ti->len.t.byoyomi_time = atof(s);
  59                                 ti->len.t.byoyomi_time_max = ti->len.t.byoyomi_time;
  60                                 ti->len.t.byoyomi_periods = 1;
  61                                 ti->len.t.byoyomi_stones = 1;
  62                                 ti->len.t.byoyomi_stones_max = 1;
  63                         }
  64                         break;
  65         }
  66         return true;
  67 }
  68
  69 /* Update time settings according to gtp time_settings or kgs-time_settings command. */
  70 void
  71 time_settings(struct time_info *ti, int main_time, int byoyomi_time, int byoyomi_stones, int byoyomi_periods)
  72 {
  73         if (main_time < 0) {
  74                 ti->period = TT_NULL; // no time limit, rely on engine default
  75         } else {
  76                 ti->period = main_time > 0 ? TT_TOTAL : TT_MOVE;
  77                 ti->dim = TD_WALLTIME;
  78                 ti->len.t.timer_start = 0;
  79                 ti->len.t.main_time = (double) main_time;
  80                 ti->len.t.byoyomi_time = (double) byoyomi_time;
  81                 ti->len.t.byoyomi_periods = byoyomi_periods;
  82                 ti->len.t.byoyomi_stones = byoyomi_stones;
  83                 ti->len.t.canadian = byoyomi_stones > 0;
  84                 if (byoyomi_time > 0) {
  85                         /* Normally, only one of byoyomi_periods and
  86                          * byoyomi_stones arguments will be > 0. However,
  87                          * our data structure uses generalized byoyomi
  88                          * specification that will assume "1 byoyomi period
  89                          * of N stones" for Canadian byoyomi and "N byoyomi
  90                          * periods of 1 stone" for Japanese byoyomi. */
  91                         if (ti->len.t.byoyomi_periods < 1)
  92                                 ti->len.t.byoyomi_periods = 1;
  93                         if (ti->len.t.byoyomi_stones < 1)
  94                                 ti->len.t.byoyomi_stones = 1;
  95                 } else {
  96                         assert(!ti->len.t.byoyomi_periods && !ti->len.t.byoyomi_stones);
  97                 }
  98                 ti->len.t.byoyomi_time_max = ti->len.t.byoyomi_time;
  99                 ti->len.t.byoyomi_stones_max = ti->len.t.byoyomi_stones;
 100         }
 101 }
 102
 103 /* Update time information according to gtp time_left command.
 104  * kgs doesn't give time_left for the first move, so make sure
 105  * that just time_settings + time_stop_conditions still work. */
 106 void
 107 time_left(struct time_info *ti, int time_left, int stones_left)
 108 {
 109         assert(ti->period != TT_NULL);
 110         ti->dim = TD_WALLTIME;
 111
 112         if (!time_left && !stones_left) {
 113                 /* Some GTP peers send time_left 0 0 at the end of main time. */
 114                 ti->period = TT_MOVE;
 115                 ti->len.t.main_time = 0;
 116                 ti->len.t.byoyomi_time = ti->len.t.byoyomi_time_max;
 117                 ti->len.t.byoyomi_stones = ti->len.t.byoyomi_stones_max;
 118
 119         } else if (!stones_left) {
 120                 /* Main time */
 121                 ti->period = TT_TOTAL;
 122                 ti->len.t.main_time = time_left;
 123                 ti->len.t.byoyomi_time = ti->len.t.byoyomi_time_max;
 124                 ti->len.t.byoyomi_stones = ti->len.t.byoyomi_stones_max;
 125
 126         } else {
 127                 /* Byoyomi */
 128                 ti->period = TT_MOVE;
 129                 ti->len.t.main_time = 0;
 130                 ti->len.t.byoyomi_time = time_left;
 131                 if (ti->len.t.canadian) {
 132                         ti->len.t.byoyomi_stones = stones_left;
 133                 } else {
 134                         // field misused by kgs
 135                         ti->len.t.byoyomi_periods = stones_left;
 136                 }
 137         }
 138 }
 139
 140 /* Start our timer. kgs does this (correctly) on "play" not "genmove"
 141  * unless we are making the first move of the game. */
 142 void
 143 time_start_timer(struct time_info *ti)
 144 {
 145         if (ti->period != TT_NULL && ti->dim == TD_WALLTIME)
 146                 ti->len.t.timer_start = time_now();
 147 }
 148
 149 void
 150 time_sub(struct time_info *ti, double interval, bool new_move)
 151 {
 152         assert(ti->dim == TD_WALLTIME && ti->period != TT_NULL);
 153
 154         if (ti->period == TT_TOTAL) {
 155                 ti->len.t.main_time -= interval;
 156                 if (ti->len.t.main_time >= 0)
 157                         return;
 158                 if (ti->len.t.byoyomi_time <= 0) {
 159                         /* No byoyomi to save us. */
 160                         fprintf(stderr, "*** LOST ON TIME internally! (%0.2f, spent %0.2fs on last move)\n",
 161                                 ti->len.t.main_time, interval);
 162                         /* What can we do? Pretend this didn't happen. */
 163                         ti->len.t.main_time = 1.0f;
 164                         return;
 165                 }
 166                 /* Fall-through to byoyomi. */
 167                 ti->period = TT_MOVE;
 168                 interval = -ti->len.t.main_time;
 169                 ti->len.t.main_time = 0;
 170         }
 171
 172         ti->len.t.byoyomi_time -= interval;
 173         if (ti->len.t.byoyomi_time < 0) {
 174                 /* Lost a period. */
 175                 if (--ti->len.t.byoyomi_periods < 1) {
 176                         fprintf(stderr, "*** LOST ON TIME internally! (%0.2f, spent %0.2fs on last move)\n",
 177                                 ti->len.t.byoyomi_time, interval);
 178                         /* Well, what can we do? Pretend this didn't happen. */
 179                         ti->len.t.byoyomi_periods = 1;
 180                 }
 181                 ti->len.t.byoyomi_time = ti->len.t.byoyomi_time_max;
 182                 ti->len.t.byoyomi_stones = ti->len.t.byoyomi_stones_max;
 183                 return;
 184         }
 185         if (new_move && --ti->len.t.byoyomi_stones < 1) {
 186                 /* Finished a period. */
 187                 ti->len.t.byoyomi_time = ti->len.t.byoyomi_time_max;
 188                 ti->len.t.byoyomi_stones = ti->len.t.byoyomi_stones_max;
 189         }
 190 }
 191
 192 /* Returns the current time. */
 193 double
 194 time_now(void)
 195 {
 196 #if _POSIX_TIMERS > 0
 197         struct timespec now;
 198         clock_gettime(CLOCK_REALTIME, &now);
 199         return now.tv_sec + now.tv_nsec/1000000000.0;
 200 #else
 201         struct timeval now;
 202         gettimeofday(&now, NULL);
 203         return now.tv_sec + now.tv_usec/1000000.0;
 204 #endif
 205 }
 206
 207 /* Sleep for a given interval (in seconds). Return immediately if interval < 0. */
 208 void
 209 time_sleep(double interval)
 210 {
 211 #ifdef _WIN32
 212         unsigned int t = interval * 1000.0;
 213         Sleep(t);
 214 #else
 215         struct timespec ts;
 216         double sec;
 217         ts.tv_nsec = (int)(modf(interval, &sec)*1000000000.0);
 218         ts.tv_sec = (int)sec;
 219         nanosleep(&ts, NULL); /* ignore error if interval was < 0 */
 220 #endif
 221 }
 222
 223
 224 /* Returns true if we are in byoyomi (or should play as if in byo yomi
 225  * because remaining time per move in main time is less than byoyomi time
 226  * per move). */
 227 static bool
 228 time_in_byoyomi(struct time_info *ti) {
 229         assert(ti->dim == TD_WALLTIME);
 230         if (!ti->len.t.byoyomi_time)
 231                 return false; // there is no byoyomi!
 232         assert(ti->len.t.byoyomi_stones > 0);
 233         if (!ti->len.t.main_time)
 234                 return true; // we _are_ in byoyomi
 235         if (ti->len.t.main_time <= ti->len.t.byoyomi_time / ti->len.t.byoyomi_stones + 0.001)
 236                 return true; // our basic time left is less than byoyomi time per move
 237         return false;
 238 }
 239
 240 /* Set worst.time to all available remaining time (main time plus usable
 241  * byoyomi), to be spread over returned number of moves (expected game
 242  * length minus moves to be played in final byoyomi - if we would not be
 243  * able to spend more time on them in main time anyway). */
 244 static int
 245 time_stop_set_remaining(struct time_info *ti, struct board *b, double net_lag, struct time_stop *stop)
 246 {
 247         int moves_left = board_estimated_moves_left(b);
 248         stop->worst.time = ti->len.t.main_time;
 249
 250         if (!ti->len.t.byoyomi_time)
 251                 return moves_left;
 252
 253         /* Time for one move in byoyomi. */
 254         assert(ti->len.t.byoyomi_stones > 0);
 255         double move_time = ti->len.t.byoyomi_time / ti->len.t.byoyomi_stones;
 256
 257         /* (i) Plan to extend our thinking time to make use of byoyom. */
 258
 259         /* For Japanese byoyomi with N>1 periods, we use N-1 periods
 260          * as main time, keeping the last one as insurance against
 261          * unexpected net lag. */
 262         if (ti->len.t.byoyomi_periods > 2) {
 263                 stop->worst.time += (ti->len.t.byoyomi_periods - 2) * move_time;
 264                 // Will add 1 more byoyomi_time just below
 265         }
 266
 267         /* In case of Canadian byoyomi, include time that can be spent
 268          * on its first move. */
 269         stop->worst.time += move_time;
 270
 271         /* (ii) Do not play faster in main time than we would in byoyomi. */
 272
 273         /* Maximize the number of moves played uniformly in main time,
 274          * while not playing faster in main time than in byoyomi.
 275          * At this point, the main time remaining is stop->worst.time and
 276          * already includes the first (canadian) or N-1 byoyomi periods. */
 277         double real_move_time = move_time - net_lag;
 278         if (real_move_time > 0) {
 279                 int main_moves = stop->worst.time / real_move_time;
 280                 if (moves_left > main_moves) {
 281                         /* We plan to do too many moves in main time,
 282                          * do the rest in byoyomi. */
 283                         moves_left = main_moves;
 284                 }
 285                 if (moves_left <= 0) // possible if too much lag
 286                         moves_left = 1;
 287         }
 288
 289         return moves_left;
 290 }
 291
 292 /* Adjust the recommended per-move time based on the current game phase.
 293  * We expect stop->worst to be total time available, stop->desired the current
 294  * per-move time allocation, and set stop->desired to adjusted per-move time. */
 295 static void
 296 time_stop_phase_adjust(struct board *b, int fuseki_end, int yose_start, struct time_stop *stop)
 297 {
 298         int bsize = (board_size(b)-2)*(board_size(b)-2);
 299         fuseki_end = fuseki_end * bsize / 100; // move nb at fuseki end
 300         yose_start = yose_start * bsize / 100; // move nb at yose start
 301         assert(fuseki_end < yose_start);
 302
 303         /* No adjustments in yose. */
 304         if (b->moves >= yose_start)
 305                 return;
 306         int moves_to_yose = (yose_start - b->moves) / 2;
 307         // ^- /2 because we only consider the moves we have to play ourselves
 308         int left_at_yose_start = board_estimated_moves_left(b) - moves_to_yose;
 309         if (left_at_yose_start < MIN_MOVES_LEFT)
 310                 left_at_yose_start = MIN_MOVES_LEFT;
 311
 312         /* This particular value of middlegame_time will continuously converge
 313          * to effective "yose_time" value as we approach yose_start. */
 314         double middlegame_time = stop->worst.time / left_at_yose_start;
 315         if (middlegame_time < stop->desired.time)
 316                 return;
 317
 318         if (b->moves < fuseki_end) {
 319                 assert(fuseki_end > 0);
 320                 /* At the game start, use stop->desired.time (rather
 321                  * conservative estimate), then gradually prolong it. */
 322                 double beta = b->moves / fuseki_end;
 323                 stop->desired.time = middlegame_time * beta + stop->desired.time * (1 - beta);
 324
 325         } else { assert(b->moves < yose_start);
 326                 /* Middlegame, start with relatively large value, then
 327                  * converge to the uniform-timeslice yose value. */
 328                 stop->desired.time = middlegame_time;
 329         }
 330 }
 331
 332 void
 333 lag_adjust(double *time, double net_lag)
 334 {
 335         double nolag_time = *time;
 336         *time -= net_lag;
 337         if (*time < MIN_THINK_WITH_LAG && nolag_time > MIN_THINK_WITH_LAG)
 338                 *time = MIN_THINK_WITH_LAG;
 339 }
 340
 341 /* Pre-process time_info for search control and sets the desired stopping conditions. */
 342 void
 343 time_stop_conditions(struct time_info *ti, struct board *b, int fuseki_end, int yose_start,
 344                      floating_t max_maintime_ratio, struct time_stop *stop)
 345 {
 346         /* We must have _some_ limits by now, be it random default values! */
 347         assert(ti->period != TT_NULL);
 348
 349         /* Special-case limit by number of simulations. */
 350         if (ti->dim == TD_GAMES) {
 351                 if (ti->period == TT_TOTAL) {
 352                         ti->period = TT_MOVE;
 353                         ti->len.games /= board_estimated_moves_left(b);
 354                 }
 355
 356                 stop->desired.playouts = ti->len.games;
 357                 /* We force worst == desired, so note that we will NOT loop
 358                  * until best == winner. */
 359                 stop->worst.playouts = ti->len.games;
 360                 return;
 361         }
 362
 363         assert(ti->dim == TD_WALLTIME);
 364
 365
 366         /* Minimum net lag (seconds) to be reserved in the time for move. */
 367         double net_lag = MAX_NET_LAG;
 368         net_lag += time_now() - ti->len.t.timer_start;
 369         // TODO: keep statistics to get good estimate of lag not just current move
 370
 371
 372         if (ti->period == TT_TOTAL && time_in_byoyomi(ti)) {
 373                 /* Technically, we are still in main time, but we can
 374                  * effectively switch to byoyomi scheduling since we
 375                  * have less time available than one byoyomi move takes. */
 376                 ti->period = TT_MOVE;
 377         }
 378
 379
 380         if (ti->period == TT_MOVE) {
 381                 /* We are in byoyomi, or almost! */
 382
 383                 /* The period can still include some tiny remnant of main
 384                  * time if we are just switching to byoyomi. */
 385                 double period_len = ti->len.t.byoyomi_time + ti->len.t.main_time;
 386
 387                 stop->worst.time = period_len;
 388                 assert(ti->len.t.byoyomi_stones > 0);
 389                 stop->desired.time = period_len / ti->len.t.byoyomi_stones;
 390
 391                 /* Use a larger safety margin if we risk losing on time on
 392                  * this move; it makes no sense to have 30s byoyomi and wait
 393                  * until 28s to play our move). */
 394                 if (stop->desired.time >= period_len - net_lag) {
 395                         double safe_margin = RESERVED_BYOYOMI_PERCENT * stop->desired.time / 100;
 396                         if (safe_margin > net_lag)
 397                                 net_lag = safe_margin;
 398                 }
 399
 400                 /* Make recommended_old == average(recommended_new, max) */
 401                 double worst_time = stop->desired.time * MAX_BYOYOMI_TIME_RATIO;
 402                 if (worst_time < stop->worst.time)
 403                         stop->worst.time = worst_time;
 404                 stop->desired.time *= (2 - MAX_BYOYOMI_TIME_RATIO);
 405
 406         } else { assert(ti->period == TT_TOTAL);
 407                 /* We are in main time. */
 408
 409                 assert(ti->len.t.main_time > 0);
 410                 /* Set worst.time to all available remaining time, to be spread
 411                  * over returned number of moves. */
 412                 int moves_left = time_stop_set_remaining(ti, b, net_lag, stop);
 413
 414                 /* Allocate even slice of the remaining time for next move. */
 415                 stop->desired.time = stop->worst.time / moves_left;
 416                 assert(stop->desired.time > 0 && stop->worst.time > 0);
 417                 assert(stop->desired.time <= stop->worst.time + 0.001);
 418
 419                 /* Furthermore, tweak the slice based on the game phase. */
 420                 time_stop_phase_adjust(b, fuseki_end, yose_start, stop);
 421
 422                 /* Put final upper bound on maximal time spent on the move.
 423                  * Keep enough time for sudden death (or near SD) games. */
 424                 double worst_time = stop->desired.time;
 425                 if (ti->len.t.byoyomi_time_max > ti->len.t.byoyomi_stones_max) {
 426                         worst_time *= max_maintime_ratio;
 427                 } else {
 428                         worst_time *= MAX_SUDDEN_DEATH_RATIO;
 429                 }
 430                 if (worst_time < stop->worst.time)
 431                         stop->worst.time = worst_time;
 432                 if (stop->desired.time > stop->worst.time)
 433                         stop->desired.time = stop->worst.time;
 434         }
 435
 436         if (DEBUGL(1))
 437                 fprintf(stderr, "desired %0.2f, worst %0.2f, clock [%d] %0.2f + %0.2f/%d*%d, lag %0.2f\n",
 438                         stop->desired.time, stop->worst.time,
 439                         ti->dim, ti->len.t.main_time,
 440                         ti->len.t.byoyomi_time, ti->len.t.byoyomi_stones,
 441                         ti->len.t.byoyomi_periods, net_lag);
 442
 443         /* Account for lag. */
 444         lag_adjust(&stop->desired.time, net_lag);
 445         lag_adjust(&stop->worst.time, net_lag);
 446 }