README: Mention large-scale board patterns
[pachi/nmclean.git] / timeinfo.c
blob81b86dfdf0e6ee9dcad5c27aa9b117a4240f9289
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>
9 #define DEBUG
11 #include "debug.h"
12 #include "tactics/util.h"
13 #include "timeinfo.h"
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
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
32 bool
33 time_parse(struct time_info *ti, char *s)
35 switch (s[0]) {
36 case '_': ti->period = TT_TOTAL; s++; break;
37 default: ti->period = TT_MOVE; break;
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;
64 break;
66 return true;
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)
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);
98 ti->len.t.byoyomi_time_max = ti->len.t.byoyomi_time;
99 ti->len.t.byoyomi_stones_max = ti->len.t.byoyomi_stones;
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)
109 assert(ti->period != TT_NULL);
110 ti->dim = TD_WALLTIME;
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;
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;
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;
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)
145 if (ti->period != TT_NULL && ti->dim == TD_WALLTIME)
146 ti->len.t.timer_start = time_now();
149 void
150 time_sub(struct time_info *ti, double interval, bool new_move)
152 assert(ti->dim == TD_WALLTIME && ti->period != TT_NULL);
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;
166 /* Fall-through to byoyomi. */
167 ti->period = TT_MOVE;
168 interval = -ti->len.t.main_time;
169 ti->len.t.main_time = 0;
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;
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;
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;
192 /* Returns the current time. */
193 double
194 time_now(void)
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
207 /* Sleep for a given interval (in seconds). Return immediately if interval < 0. */
208 void
209 time_sleep(double interval)
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
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;
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)
247 int moves_left = board_estimated_moves_left(b);
248 stop->worst.time = ti->len.t.main_time;
250 if (!ti->len.t.byoyomi_time)
251 return moves_left;
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;
257 /* (i) Plan to extend our thinking time to make use of byoyom. */
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
267 /* In case of Canadian byoyomi, include time that can be spent
268 * on its first move. */
269 stop->worst.time += move_time;
271 /* (ii) Do not play faster in main time than we would in byoyomi. */
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;
285 if (moves_left <= 0) // possible if too much lag
286 moves_left = 1;
289 return moves_left;
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)
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);
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;
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;
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);
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;
332 void
333 lag_adjust(double *time, double net_lag)
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;
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)
346 /* We must have _some_ limits by now, be it random default values! */
347 assert(ti->period != TT_NULL);
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);
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;
363 assert(ti->dim == TD_WALLTIME);
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
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;
380 if (ti->period == TT_MOVE) {
381 /* We are in byoyomi, or almost! */
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;
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;
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;
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);
406 } else { assert(ti->period == TT_TOTAL);
407 /* We are in main time. */
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);
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);
419 /* Furthermore, tweak the slice based on the game phase. */
420 time_stop_phase_adjust(b, fuseki_end, yose_start, stop);
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;
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;
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);
443 /* Account for lag. */
444 lag_adjust(&stop->desired.time, net_lag);
445 lag_adjust(&stop->worst.time, net_lag);