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                         if (ti->period == TT_TOTAL) {
  38                                 ti->len.t.main_time = atof(s);
  39                                 ti->len.t.byoyomi_time = 0.0;
  40                                 ti->len.t.byoyomi_periods = 0;
  41                                 ti->len.t.byoyomi_stones = 0;
  42                         } else { assert(ti->period == TT_MOVE);
  43                                 ti->len.t.main_time = 0.0;
  44                                 ti->len.t.byoyomi_time = atof(s);
  45                                 ti->len.t.byoyomi_periods = 1;
  46                                 ti->len.t.byoyomi_stones = 1;
  47                         }
  48                         ti->len.t.timer_start = 0;
  49                         break;
  50         }
  51         return true;
  52 }
  53
  54 /* Update time settings according to gtp time_settings or kgs-time_settings command. */
  55 void
  56 time_settings(struct time_info *ti, int main_time, int byoyomi_time, int byoyomi_stones, int byoyomi_periods)
  57 {
  58         if (byoyomi_time > 0 && byoyomi_stones == 0) {
  59                 ti->period = TT_NULL; // no time limit, rely on engine default
  60         } else {
  61                 ti->period = TT_TOTAL;
  62                 ti->dim = TD_WALLTIME;
  63                 ti->len.t.main_time = (double) main_time;
  64                 ti->len.t.byoyomi_time = (double) byoyomi_time;
  65                 ti->len.t.byoyomi_periods = byoyomi_periods > 1 ? byoyomi_periods : 1;
  66                 ti->len.t.byoyomi_stones = byoyomi_stones > 1 ? byoyomi_stones : 1;
  67                 ti->len.t.canadian = byoyomi_stones > 0;
  68                 ti->len.t.timer_start = 0;
  69         }
  70 }
  71
  72 /* Update time information according to gtp time_left command.
  73  * kgs doesn't give time_left for the first move, so make sure
  74  * that just time_settings + time_stop_conditions still work. */
  75 void
  76 time_left(struct time_info *ti, int time_left, int stones_left)
  77 {
  78         assert(ti->period != TT_NULL);
  79         ti->dim = TD_WALLTIME;
  80
  81         if (stones_left == 0) {
  82                 /* Main time */
  83                 ti->period = TT_TOTAL;
  84                 ti->len.t.main_time = time_left;
  85                 /* byoyomi_time kept fully charged. */
  86         } else {
  87                 /* Byoyomi */
  88                 ti->period = TT_MOVE;
  89                 ti->len.t.main_time = 0;
  90                 ti->len.t.byoyomi_time = time_left;
  91                 if (ti->len.t.canadian) {
  92                         ti->len.t.byoyomi_stones = stones_left;
  93                 } else {
  94                         // field misused by kgs
  95                         ti->len.t.byoyomi_periods = stones_left;
  96                 }
  97         }
  98 }
  99
 100 /* Returns true if we are in byoyomi (or should play as if in byo yomi
 101  * because remaining time per move in main time is less than byoyomi time
 102  * per move). */
 103 bool
 104 time_in_byoyomi(struct time_info *ti) {
 105         assert(ti->dim == TD_WALLTIME);
 106         if (!ti->len.t.byoyomi_time)
 107                 return false; // there is no byoyomi!
 108         assert(ti->len.t.byoyomi_stones > 0);
 109         if (!ti->len.t.main_time)
 110                 return true; // we _are_ in byoyomi
 111         if (ti->len.t.main_time <= ti->len.t.byoyomi_time / ti->len.t.byoyomi_stones + 0.001)
 112                 return true; // our basic time left is less than byoyomi time per move
 113         return false;
 114 }
 115
 116 /* Start our timer. kgs does this (correctly) on "play" not "genmove"
 117  * unless we are making the first move of the game. */
 118 void
 119 time_start_timer(struct time_info *ti)
 120 {
 121         if (ti->period != TT_NULL && ti->dim == TD_WALLTIME)
 122                 ti->len.t.timer_start = time_now();
 123 }
 124
 125 /* Returns the current time. */
 126 double
 127 time_now(void)
 128 {
 129         struct timespec now;
 130         clock_gettime(CLOCK_REALTIME, &now);
 131         return now.tv_sec + now.tv_nsec/1000000000.0;
 132 }
 133
 134 /* Sleep for a given interval (in seconds). Return immediately if interval < 0. */
 135 void
 136 time_sleep(double interval)
 137 {
 138         struct timespec ts;
 139         double sec;
 140         ts.tv_nsec = (int)(modf(interval, &sec)*1000000000.0);
 141         ts.tv_sec = (int)sec;
 142         nanosleep(&ts, NULL); /* ignore error if interval was < 0 */
 143 }
 144
 145
 146 /* Pre-process time_info for search control and sets the desired stopping conditions. */
 147 void
 148 time_stop_conditions(struct time_info *ti, struct board *b, int fuseki_end, int yose_start, struct time_stop *stop)
 149 {
 150         /* We must have _some_ limits by now, be it random default values! */
 151         assert(ti->period != TT_NULL);
 152
 153         /* Special-case limit by number of simulations. */
 154         if (ti->dim == TD_GAMES) {
 155                 if (ti->period == TT_TOTAL) {
 156                         ti->period = TT_MOVE;
 157                         ti->len.games /= board_estimated_moves_left(b);
 158                 }
 159
 160                 stop->desired.playouts = ti->len.games;
 161                 /* We force worst == desired, so note that we will NOT loop
 162                  * until best == winner. */
 163                 stop->worst.playouts = ti->len.games;
 164                 return;
 165         }
 166
 167         assert(ti->dim == TD_WALLTIME);
 168
 169
 170         /* Minimum net lag (seconds) to be reserved in the time for move. */
 171         double net_lag = MAX_NET_LAG;
 172         /* Make sure timer_start is set up, adjust net_lag. */
 173         if (!ti->len.t.timer_start) {
 174                 ti->len.t.timer_start = time_now(); // we're playing the first game move
 175         } else {
 176                 net_lag += time_now() - ti->len.t.timer_start;
 177                 // TODO: keep statistics to get good estimate of lag not just current move
 178         }
 179
 180
 181         if (ti->period == TT_TOTAL && time_in_byoyomi(ti)) {
 182                 /* Technically, we are still in main time, but we can
 183                  * effectively switch to byoyomi scheduling since we
 184                  * have less time available than one byoyomi move takes. */
 185                 ti->period = TT_MOVE;
 186         }
 187
 188
 189         /* Absolute maximum time possible to spend on the move. */
 190         double max_time;
 191         /* Ideal/reasonable time to spend on the move. */
 192         double recommended_time;
 193
 194         if (ti->period == TT_MOVE) {
 195                 /* We are in byoyomi, or almost! */
 196
 197                 /* The period can still include some tiny remnant of main
 198                  * time if we are just switching to byoyomi. */
 199                 double period_len = ti->len.t.byoyomi_time + ti->len.t.main_time;
 200
 201                 max_time = period_len;
 202                 assert(ti->len.t.byoyomi_stones > 0);
 203                 recommended_time = period_len / ti->len.t.byoyomi_stones;
 204
 205                 /* Use a larger safety margin if we risk losing on time on
 206                  * this move; it makes no sense to have 30s byoyomi and wait
 207                  * until 28s to play our move). */
 208                 if (recommended_time >= period_len - net_lag) {
 209                         double safe_margin = RESERVED_BYOYOMI_PERCENT * recommended_time / 100;
 210                         if (safe_margin > net_lag)
 211                                 net_lag = safe_margin;
 212                 }
 213
 214                 /* Make recommended_old == average(recommended_new, max) */
 215                 double max_time2 = recommended_time * MAX_BYOYOMI_TIME_EXTENSION;
 216                 if (max_time2 < max_time)
 217                         max_time = max_time2;
 218                 recommended_time *= (2 - MAX_BYOYOMI_TIME_EXTENSION);
 219
 220         } else { assert(ti->period == TT_TOTAL);
 221                 /* We are in main time. */
 222
 223                 assert(ti->len.t.main_time > 0);
 224                 max_time = recommended_time = ti->len.t.main_time;
 225
 226                 int moves_left = board_estimated_moves_left(b);
 227                 /* If we have byoyomi available, plan to extend our thinking
 228                  * time to make use of it. */
 229                 if (ti->len.t.byoyomi_time > 0) {
 230                         assert(ti->len.t.byoyomi_stones > 0);
 231                         /* Time for one move in byoyomi. */
 232                         double move_time = ti->len.t.byoyomi_time / ti->len.t.byoyomi_stones;
 233
 234                         /* For Japanese byoyomi with N>1 periods, we use N-1 periods as main time,
 235                          * keeping the last one as insurance against unexpected net lag. */
 236                         if (ti->len.t.byoyomi_periods > 2) {
 237                                 max_time += (ti->len.t.byoyomi_periods - 2) * move_time;
 238                                 // Will add 1 more byoyomi_time just below
 239                         }
 240                         max_time += move_time;
 241                         recommended_time = max_time;
 242
 243                         /* Maximize the number of moves played uniformly in main time, while
 244                          * not playing faster in main time than in byoyomi. At this point,
 245                          * the main time remaining is ti->len.t.max_time and already includes
 246                          * the first (canadian) or N-1 byoyomi periods.
 247                          *    main_speed = max_time / main_moves >= move_time
 248                          * => main_moves <= max_time / move_time */
 249                         double actual_byoyomi = move_time - net_lag;
 250                         if (actual_byoyomi > 0) {
 251                                 int main_moves = (int)(max_time / actual_byoyomi);
 252                                 if (moves_left > main_moves)
 253                                         moves_left = main_moves; // will do the rest in byoyomi
 254                                 if (moves_left <= 0) // possible if too much lag
 255                                         moves_left = 1;
 256                         }
 257                 }
 258
 259                 /* Allocate even slice of the remaining time for next move. */
 260                 recommended_time /= moves_left;
 261                 assert(recommended_time > 0 && max_time > 0);
 262                 assert(recommended_time <= max_time + 0.001);
 263
 264                 /* Furthermore, tweak the slice based on the game phase. */
 265
 266                 int bsize = (board_size(b)-2)*(board_size(b)-2);
 267                 fuseki_end = fuseki_end * bsize / 100; // move nb at fuseki end
 268                 yose_start = yose_start * bsize / 100; // move nb at yose start
 269                 assert(fuseki_end < yose_start);
 270
 271                 /* Before yose, spend some extra. */
 272                 if (b->moves < yose_start) {
 273                         int moves_to_yose = (yose_start - b->moves) / 2;
 274                         // ^- /2 because we only consider the moves we have to play ourselves
 275                         int left_at_yose_start = board_estimated_moves_left(b) - moves_to_yose;
 276                         if (left_at_yose_start < MIN_MOVES_LEFT)
 277                                 left_at_yose_start = MIN_MOVES_LEFT;
 278                         double longest_time = max_time / left_at_yose_start;
 279                         if (longest_time < recommended_time) {
 280                                 // Should rarely happen, but keep recommended_time anyway
 281                         } else if (b->moves < fuseki_end) {
 282                                 assert(fuseki_end > 0);
 283                                 recommended_time += ((longest_time - recommended_time) * b->moves) / fuseki_end;
 284                         } else { assert(b->moves < yose_start);
 285                                 recommended_time = longest_time;
 286                         }
 287                 }
 288
 289                 /* Put final upper bound on maximal time spent on the move. */
 290                 double max_time2 = recommended_time * MAX_MAIN_TIME_EXTENSION;
 291                 if (max_time2 < max_time)
 292                         max_time = max_time2;
 293                 if (recommended_time > max_time)
 294                         recommended_time = max_time;
 295         }
 296
 297         if (DEBUGL(1))
 298                 fprintf(stderr, "recommended_time %0.2f, max_time %0.2f, byoyomi %0.2f/%d, lag %0.2f\n",
 299                         recommended_time, max_time,
 300                         ti->len.t.byoyomi_time, ti->len.t.byoyomi_stones,
 301                         net_lag);
 302
 303         stop->desired.time = ti->len.t.timer_start + recommended_time - net_lag;
 304         stop->worst.time = ti->len.t.timer_start + max_time - net_lag;
 305         // Both stop points may be in the past if too much lag.
 306 }