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