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.recommended_time = atof(s);
  38                         ti->len.t.max_time = ti->len.t.recommended_time;
  39                         ti->len.t.net_lag = MAX_NET_LAG;
  40                         ti->len.t.timer_start = 0;
  41                         ti->len.t.byoyomi_time = 0.0;
  42                         ti->len.t.byoyomi_periods = 0;
  43                         break;
  44         }
  45         return true;
  46 }
  47
  48 /* Update time settings according to gtp time_settings or kgs-time_settings command. */
  49 void
  50 time_settings(struct time_info *ti, int main_time, int byoyomi_time, int byoyomi_stones, int byoyomi_periods)
  51 {
  52         if (byoyomi_time > 0 && byoyomi_stones == 0) {
  53                 ti->period = TT_NULL; // no time limit, rely on engine default
  54         } else {
  55                 ti->period = TT_TOTAL;
  56                 ti->dim = TD_WALLTIME;
  57                 ti->len.t.max_time = (double) main_time; // byoyomi will be added at next genmove
  58                 ti->len.t.recommended_time = ti->len.t.max_time;
  59                 ti->len.t.timer_start = 0;
  60                 ti->len.t.net_lag = MAX_NET_LAG;
  61                 ti->len.t.byoyomi_time = (double) byoyomi_time;
  62                 if (byoyomi_stones > 0)
  63                         ti->len.t.byoyomi_time /= byoyomi_stones;
  64                 ti->len.t.byoyomi_periods = byoyomi_periods;
  65         }
  66 }
  67
  68 /* Update time information according to gtp time_left command.
  69  * kgs doesn't give time_left for the first move, so make sure
  70  * that just time_settings + time_select_best still work. */
  71 void
  72 time_left(struct time_info *ti, int time_left, int stones_left)
  73 {
  74         assert(ti->period != TT_NULL);
  75         ti->dim = TD_WALLTIME;
  76         ti->len.t.max_time = (double)time_left;
  77
  78         if (ti->len.t.byoyomi_periods > 0 && stones_left > 0) {
  79                 ti->len.t.byoyomi_periods = stones_left; // field misused by kgs
  80                 stones_left = 1;
  81         }
  82         if (stones_left == 0) {
  83                 /* Main time */
  84                 ti->period = TT_TOTAL;
  85                 ti->len.t.recommended_time = ti->len.t.max_time;
  86                 /* byoyomi_time, net_lag & timer_start unchanged. */
  87         } else {
  88                 ti->period = TT_MOVE;
  89                 ti->len.t.byoyomi_time = ((double)time_left)/stones_left;
  90                 ti->len.t.recommended_time = ti->len.t.byoyomi_time;
  91                 /* net_lag & timer_start unchanged. */
  92         }
  93 }
  94
  95 /* Set correct time information before making a move, and
  96  * always make it time per move for the engine. */
  97 void
  98 time_prepare_move(struct time_info *ti, struct board *board)
  99 {
 100         int moves_left;
 101
 102         if (ti->period == TT_TOTAL) {
 103                 moves_left = board_estimated_moves_left(board);
 104                 assert(moves_left > 0);
 105                 if (ti->dim == TD_GAMES) {
 106                         ti->period = TT_MOVE;
 107                         ti->len.games /= moves_left;
 108                 }
 109         }
 110         if (ti->period == TT_NULL || ti->dim != TD_WALLTIME)
 111                 return;
 112
 113         double now = time_now();
 114         double lag;
 115         if (!ti->len.t.timer_start) {
 116                 ti->len.t.timer_start = now; // we're playing the first game move
 117                 lag = 0;
 118         } else {
 119                 lag = now - ti->len.t.timer_start;
 120                 // TODO: keep statistics to get good estimate of lag not just current move
 121                 ti->len.t.max_time -= lag; // can become < 0, taken into account below
 122                 ti->len.t.recommended_time -= lag;
 123                 if (DEBUGL(1) && lag > MAX_NET_LAG)
 124                         fprintf(stderr, "lag %0.2f > max_net_lag %0.2f\n", lag, MAX_NET_LAG);
 125         }
 126         if (ti->period == TT_TOTAL) {
 127                 if (ti->len.t.byoyomi_time > 0) {
 128                         /* For non-canadian byoyomi with N>1 periods, we use N-1 periods as main time,
 129                          * keeping the last one as insurance against unexpected net lag. */
 130                         if (ti->len.t.byoyomi_periods > 2) {
 131                                 ti->len.t.max_time += (ti->len.t.byoyomi_periods - 2) * ti->len.t.byoyomi_time;
 132                                 // Will add 1 more byoyomi_time just below
 133                         }
 134                         ti->len.t.max_time += ti->len.t.byoyomi_time;
 135                         ti->len.t.recommended_time = ti->len.t.max_time;
 136
 137                         /* Maximize the number of moves played uniformly in main time, while
 138                          * not playing faster in main time than in byoyomi. At this point,
 139                          * the main time remaining is ti->len.t.max_time and already includes
 140                          * the first (canadian) or N-1 byoyomi periods.
 141                          *    main_speed = max_time / main_moves >= byoyomi_time
 142                          * => main_moves <= max_time / byoyomi_time */
 143                         double actual_byoyomi = ti->len.t.byoyomi_time - MAX_NET_LAG;
 144                         if (actual_byoyomi > 0) {
 145                                 int main_moves = (int)(ti->len.t.max_time / actual_byoyomi);
 146                                 if (moves_left > main_moves)
 147                                         moves_left = main_moves; // will do the rest in byoyomi
 148                                 if (moves_left <= 0) // possible if too much lag
 149                                         moves_left = 1;
 150                         }
 151                 }
 152                 ti->period = TT_MOVE;
 153                 ti->len.t.recommended_time /= moves_left;
 154         }
 155         // To simplify the engine code, do not leave negative times:
 156         if (ti->len.t.recommended_time < 0)
 157                 ti->len.t.recommended_time = 0;
 158         if (ti->len.t.max_time < 0)
 159                 ti->len.t.max_time = 0;
 160         assert(ti->len.t.recommended_time <= ti->len.t.max_time + 0.001);
 161
 162         /* Use a larger safety margin if we risk losing on time on this move: */
 163         double safe_margin = RESERVED_BYOYOMI_PERCENT * ti->len.t.byoyomi_time/100;
 164         if (safe_margin > MAX_NET_LAG && ti->len.t.recommended_time >= ti->len.t.max_time - MAX_NET_LAG) {
 165                 ti->len.t.net_lag = safe_margin;
 166         } else {
 167                 ti->len.t.net_lag = MAX_NET_LAG;
 168         }
 169
 170         if (DEBUGL(1))
 171                 fprintf(stderr, "recommended_time %0.2f, max_time %0.2f, byoyomi %0.2f, lag %0.2f max %0.2f\n",
 172                         ti->len.t.recommended_time, ti->len.t.max_time, ti->len.t.byoyomi_time, lag,
 173                         ti->len.t.net_lag);
 174 }
 175
 176 /* Start our timer. kgs does this (correctly) on "play" not "genmove"
 177  * unless we are making the first move of the game. */
 178 void
 179 time_start_timer(struct time_info *ti)
 180 {
 181         if (ti->period != TT_NULL && ti->dim == TD_WALLTIME)
 182                 ti->len.t.timer_start = time_now();
 183 }
 184
 185 /* Returns true if we are in byoyomi (or should play as if in byo yomi
 186  * because remaining time per move in main time is less than byoyomi time
 187  * per move). */
 188 bool
 189 time_in_byoyomi(struct time_info *ti) {
 190         return ti->period == TT_MOVE && ti->dim == TD_WALLTIME && ti->len.t.byoyomi_time > 0
 191                && ti->len.t.recommended_time <= ti->len.t.byoyomi_time + 0.001;
 192 }
 193
 194 /* Returns the current time. */
 195 double
 196 time_now(void)
 197 {
 198         struct timespec now;
 199         clock_gettime(CLOCK_REALTIME, &now);
 200         return now.tv_sec + now.tv_nsec/1000000000.0;
 201 }
 202
 203 /* Sleep for a given interval (in seconds). Return immediately if interval < 0. */
 204 void
 205 time_sleep(double interval)
 206 {
 207         struct timespec ts;
 208         double sec;
 209         ts.tv_nsec = (int)(modf(interval, &sec)*1000000000.0);
 210         ts.tv_sec = (int)sec;
 211         nanosleep(&ts, NULL); /* ignore error if interval was < 0 */
 212 }
 213
 214
 215 /* Pre-process time_info for search control and sets the desired stopping conditions. */
 216 void
 217 time_stop_conditions(struct time_info *ti, struct board *b, int fuseki_end, int yose_start, struct time_stop *stop)
 218 {
 219         assert(ti->period == TT_MOVE);
 220
 221         if (ti->dim == TD_GAMES) {
 222                 stop->desired.playouts = ti->len.games;
 223                 /* We force worst == desired, so note that we will not loop
 224                  * until best == winner. */
 225                 stop->worst.playouts = ti->len.games;
 226
 227         } else {
 228                 double desired_time = ti->len.t.recommended_time;
 229                 double worst_time;
 230                 if (time_in_byoyomi(ti)) {
 231                         // make recommended == average(desired, worst)
 232                         worst_time = desired_time * MAX_BYOYOMI_TIME_EXTENSION;
 233                         desired_time *= (2 - MAX_BYOYOMI_TIME_EXTENSION);
 234
 235                 } else {
 236                         int bsize = (board_size(b)-2)*(board_size(b)-2);
 237                         fuseki_end = fuseki_end * bsize / 100; // move nb at fuseki end
 238                         yose_start = yose_start * bsize / 100; // move nb at yose start
 239                         assert(fuseki_end < yose_start);
 240
 241                         /* Before yose, spend some extra. */
 242                         if (b->moves < yose_start) {
 243                                 int moves_to_yose = (yose_start - b->moves) / 2;
 244                                 // ^- /2 because we only consider the moves we have to play ourselves
 245                                 int left_at_yose_start = board_estimated_moves_left(b) - moves_to_yose;
 246                                 if (left_at_yose_start < MIN_MOVES_LEFT)
 247                                         left_at_yose_start = MIN_MOVES_LEFT;
 248                                 double longest_time = ti->len.t.max_time / left_at_yose_start;
 249                                 if (longest_time < desired_time) {
 250                                         // Should rarely happen, but keep desired_time anyway
 251                                 } else if (b->moves < fuseki_end) {
 252                                         assert(fuseki_end > 0);
 253                                         desired_time += ((longest_time - desired_time) * b->moves) / fuseki_end;
 254                                 } else { assert(b->moves < yose_start);
 255                                         desired_time = longest_time;
 256                                 }
 257                         }
 258                         worst_time = desired_time * MAX_MAIN_TIME_EXTENSION;
 259                 }
 260                 if (worst_time > ti->len.t.max_time)
 261                         worst_time = ti->len.t.max_time;
 262                 if (desired_time > worst_time)
 263                         desired_time = worst_time;
 264
 265                 stop->desired.time = ti->len.t.timer_start + desired_time - ti->len.t.net_lag;
 266                 stop->worst.time = ti->len.t.timer_start + worst_time - ti->len.t.net_lag;
 267                 // Both stop points may be in the past if too much lag.
 268
 269                 if (DEBUGL(2))
 270                         fprintf(stderr, "desired time %.02f, worst %.02f\n", desired_time, worst_time);
 271         }
 272 }