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