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 */
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
22 time_parse(struct time_info
*ti
, char *s
)
25 case '_': ti
->period
= TT_TOTAL
; s
++; break;
26 default: ti
->period
= TT_MOVE
; break;
31 ti
->len
.games
= atoi(++s
);
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;
58 /* Update time settings according to gtp time_settings or kgs-time_settings command. */
60 time_settings(struct time_info
*ti
, int main_time
, int byoyomi_time
, int byoyomi_stones
, int byoyomi_periods
)
63 ti
->period
= TT_NULL
; // no time limit, rely on engine default
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;
85 assert(!ti
->len
.t
.byoyomi_periods
&& !ti
->len
.t
.byoyomi_stones
);
87 ti
->len
.t
.byoyomi_time_max
= ti
->len
.t
.byoyomi_time
;
88 ti
->len
.t
.byoyomi_stones_max
= ti
->len
.t
.byoyomi_stones
;
92 /* Update time information according to gtp time_left command.
93 * kgs doesn't give time_left for the first move, so make sure
94 * that just time_settings + time_stop_conditions still work. */
96 time_left(struct time_info
*ti
, int time_left
, int stones_left
)
98 assert(ti
->period
!= TT_NULL
);
99 ti
->dim
= TD_WALLTIME
;
101 if (!time_left
&& !stones_left
) {
102 /* Some GTP peers send time_left 0 0 at the end of main time. */
103 ti
->period
= TT_MOVE
;
104 ti
->len
.t
.main_time
= 0;
105 /* byoyomi_time kept fully charged. */
107 } else if (!stones_left
) {
109 ti
->period
= TT_TOTAL
;
110 ti
->len
.t
.main_time
= time_left
;
111 /* byoyomi_time kept fully charged. */
115 ti
->period
= TT_MOVE
;
116 ti
->len
.t
.main_time
= 0;
117 ti
->len
.t
.byoyomi_time
= time_left
;
118 if (ti
->len
.t
.canadian
) {
119 ti
->len
.t
.byoyomi_stones
= stones_left
;
121 // field misused by kgs
122 ti
->len
.t
.byoyomi_periods
= stones_left
;
127 /* Start our timer. kgs does this (correctly) on "play" not "genmove"
128 * unless we are making the first move of the game. */
130 time_start_timer(struct time_info
*ti
)
132 if (ti
->period
!= TT_NULL
&& ti
->dim
== TD_WALLTIME
)
133 ti
->len
.t
.timer_start
= time_now();
137 time_sub(struct time_info
*ti
, double interval
)
139 assert(ti
->dim
== TD_WALLTIME
&& ti
->period
!= TT_NULL
);
141 if (ti
->period
== TT_TOTAL
) {
142 ti
->len
.t
.main_time
-= interval
;
143 if (ti
->len
.t
.main_time
>= 0)
145 /* Fall-through to byoyomi. */
146 ti
->period
= TT_MOVE
;
147 interval
= -ti
->len
.t
.main_time
;
148 ti
->len
.t
.main_time
= 0;
151 ti
->len
.t
.byoyomi_time
-= interval
;
152 if (ti
->len
.t
.byoyomi_time
< 0) {
154 if (--ti
->len
.t
.byoyomi_periods
< 1) {
155 fprintf(stderr
, "*** LOST ON TIME internally! (%0.2f, spent %0.2fs on last move)\n",
156 ti
->len
.t
.byoyomi_time
, interval
);
157 /* Well, what can we do? Pretend this didn't happen. */
158 ti
->len
.t
.byoyomi_periods
= 1;
160 ti
->len
.t
.byoyomi_time
= ti
->len
.t
.byoyomi_time_max
;
161 ti
->len
.t
.byoyomi_stones
= ti
->len
.t
.byoyomi_stones_max
;
164 if (--ti
->len
.t
.byoyomi_stones
< 1) {
165 /* Finished a period. */
166 ti
->len
.t
.byoyomi_time
= ti
->len
.t
.byoyomi_time_max
;
167 ti
->len
.t
.byoyomi_stones
= ti
->len
.t
.byoyomi_stones_max
;
171 /* Returns the current time. */
176 clock_gettime(CLOCK_REALTIME
, &now
);
177 return now
.tv_sec
+ now
.tv_nsec
/1000000000.0;
180 /* Sleep for a given interval (in seconds). Return immediately if interval < 0. */
182 time_sleep(double interval
)
186 ts
.tv_nsec
= (int)(modf(interval
, &sec
)*1000000000.0);
187 ts
.tv_sec
= (int)sec
;
188 nanosleep(&ts
, NULL
); /* ignore error if interval was < 0 */
192 /* Returns true if we are in byoyomi (or should play as if in byo yomi
193 * because remaining time per move in main time is less than byoyomi time
196 time_in_byoyomi(struct time_info
*ti
) {
197 assert(ti
->dim
== TD_WALLTIME
);
198 if (!ti
->len
.t
.byoyomi_time
)
199 return false; // there is no byoyomi!
200 assert(ti
->len
.t
.byoyomi_stones
> 0);
201 if (!ti
->len
.t
.main_time
)
202 return true; // we _are_ in byoyomi
203 if (ti
->len
.t
.main_time
<= ti
->len
.t
.byoyomi_time
/ ti
->len
.t
.byoyomi_stones
+ 0.001)
204 return true; // our basic time left is less than byoyomi time per move
208 /* Set worst.time to all available remaining time (main time plus usable
209 * byoyomi), to be spread over returned number of moves (expected game
210 * length minus moves to be played in final byoyomi - if we would not be
211 * able to spend more time on them in main time anyway). */
213 time_stop_set_remaining(struct time_info
*ti
, struct board
*b
, double net_lag
, struct time_stop
*stop
)
215 int moves_left
= board_estimated_moves_left(b
);
216 stop
->worst
.time
= ti
->len
.t
.main_time
;
218 if (!ti
->len
.t
.byoyomi_time
)
221 /* Time for one move in byoyomi. */
222 assert(ti
->len
.t
.byoyomi_stones
> 0);
223 double move_time
= ti
->len
.t
.byoyomi_time
/ ti
->len
.t
.byoyomi_stones
;
225 /* (i) Plan to extend our thinking time to make use of byoyom. */
227 /* For Japanese byoyomi with N>1 periods, we use N-1 periods
228 * as main time, keeping the last one as insurance against
229 * unexpected net lag. */
230 if (ti
->len
.t
.byoyomi_periods
> 2) {
231 stop
->worst
.time
+= (ti
->len
.t
.byoyomi_periods
- 2) * move_time
;
232 // Will add 1 more byoyomi_time just below
235 /* In case of Canadian byoyomi, include time that can be spent
236 * on its first move. */
237 stop
->worst
.time
+= move_time
;
239 /* (ii) Do not play faster in main time than we would in byoyomi. */
241 /* Maximize the number of moves played uniformly in main time,
242 * while not playing faster in main time than in byoyomi.
243 * At this point, the main time remaining is stop->worst.time and
244 * already includes the first (canadian) or N-1 byoyomi periods. */
245 double real_move_time
= move_time
- net_lag
;
246 if (real_move_time
> 0) {
247 int main_moves
= stop
->worst
.time
/ real_move_time
;
248 if (moves_left
> main_moves
) {
249 /* We plan to do too many moves in main time,
250 * do the rest in byoyomi. */
251 moves_left
= main_moves
;
253 if (moves_left
<= 0) // possible if too much lag
260 /* Adjust the recommended per-move time based on the current game phase.
261 * We expect stop->worst to be total time available, stop->desired the current
262 * per-move time allocation, and set stop->desired to adjusted per-move time. */
264 time_stop_phase_adjust(struct board
*b
, int fuseki_end
, int yose_start
, struct time_stop
*stop
)
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
);
271 /* No adjustments in yose. */
272 if (b
->moves
>= yose_start
)
274 int moves_to_yose
= (yose_start
- b
->moves
) / 2;
275 // ^- /2 because we only consider the moves we have to play ourselves
276 int left_at_yose_start
= board_estimated_moves_left(b
) - moves_to_yose
;
277 if (left_at_yose_start
< MIN_MOVES_LEFT
)
278 left_at_yose_start
= MIN_MOVES_LEFT
;
280 /* This particular value of middlegame_time will continuously converge
281 * to effective "yose_time" value as we approach yose_start. */
282 double middlegame_time
= stop
->worst
.time
/ left_at_yose_start
;
283 if (middlegame_time
< stop
->desired
.time
)
286 if (b
->moves
< fuseki_end
) {
287 assert(fuseki_end
> 0);
288 /* At the game start, use stop->desired.time (rather
289 * conservative estimate), then gradually prolong it. */
290 double beta
= b
->moves
/ fuseki_end
;
291 stop
->desired
.time
= middlegame_time
* beta
+ stop
->desired
.time
* (1 - beta
);
293 } else { assert(b
->moves
< yose_start
);
294 /* Middlegame, start with relatively large value, then
295 * converge to the uniform-timeslice yose value. */
296 stop
->desired
.time
= middlegame_time
;
300 /* Pre-process time_info for search control and sets the desired stopping conditions. */
302 time_stop_conditions(struct time_info
*ti
, struct board
*b
, int fuseki_end
, int yose_start
, struct time_stop
*stop
)
304 /* We must have _some_ limits by now, be it random default values! */
305 assert(ti
->period
!= TT_NULL
);
307 /* Special-case limit by number of simulations. */
308 if (ti
->dim
== TD_GAMES
) {
309 if (ti
->period
== TT_TOTAL
) {
310 ti
->period
= TT_MOVE
;
311 ti
->len
.games
/= board_estimated_moves_left(b
);
314 stop
->desired
.playouts
= ti
->len
.games
;
315 /* We force worst == desired, so note that we will NOT loop
316 * until best == winner. */
317 stop
->worst
.playouts
= ti
->len
.games
;
321 assert(ti
->dim
== TD_WALLTIME
);
324 /* Minimum net lag (seconds) to be reserved in the time for move. */
325 double net_lag
= MAX_NET_LAG
;
326 if (!ti
->len
.t
.timer_start
) {
327 ti
->len
.t
.timer_start
= time_now(); // we're playing the first game move
329 net_lag
+= time_now() - ti
->len
.t
.timer_start
;
330 // TODO: keep statistics to get good estimate of lag not just current move
334 if (ti
->period
== TT_TOTAL
&& time_in_byoyomi(ti
)) {
335 /* Technically, we are still in main time, but we can
336 * effectively switch to byoyomi scheduling since we
337 * have less time available than one byoyomi move takes. */
338 ti
->period
= TT_MOVE
;
342 if (ti
->period
== TT_MOVE
) {
343 /* We are in byoyomi, or almost! */
345 /* The period can still include some tiny remnant of main
346 * time if we are just switching to byoyomi. */
347 double period_len
= ti
->len
.t
.byoyomi_time
+ ti
->len
.t
.main_time
;
349 stop
->worst
.time
= period_len
;
350 assert(ti
->len
.t
.byoyomi_stones
> 0);
351 stop
->desired
.time
= period_len
/ ti
->len
.t
.byoyomi_stones
;
353 /* Use a larger safety margin if we risk losing on time on
354 * this move; it makes no sense to have 30s byoyomi and wait
355 * until 28s to play our move). */
356 if (stop
->desired
.time
>= period_len
- net_lag
) {
357 double safe_margin
= RESERVED_BYOYOMI_PERCENT
* stop
->desired
.time
/ 100;
358 if (safe_margin
> net_lag
)
359 net_lag
= safe_margin
;
362 /* Make recommended_old == average(recommended_new, max) */
363 double worst_time
= stop
->desired
.time
* MAX_BYOYOMI_TIME_EXTENSION
;
364 if (worst_time
< stop
->worst
.time
)
365 stop
->worst
.time
= worst_time
;
366 stop
->desired
.time
*= (2 - MAX_BYOYOMI_TIME_EXTENSION
);
368 } else { assert(ti
->period
== TT_TOTAL
);
369 /* We are in main time. */
371 assert(ti
->len
.t
.main_time
> 0);
372 /* Set worst.time to all available remaining time, to be spread
373 * over returned number of moves. */
374 int moves_left
= time_stop_set_remaining(ti
, b
, net_lag
, stop
);
376 /* Allocate even slice of the remaining time for next move. */
377 stop
->desired
.time
= stop
->worst
.time
/ moves_left
;
378 assert(stop
->desired
.time
> 0 && stop
->worst
.time
> 0);
379 assert(stop
->desired
.time
<= stop
->worst
.time
+ 0.001);
381 /* Furthermore, tweak the slice based on the game phase. */
382 time_stop_phase_adjust(b
, fuseki_end
, yose_start
, stop
);
384 /* Put final upper bound on maximal time spent on the move. */
385 double worst_time
= stop
->desired
.time
* MAX_MAIN_TIME_EXTENSION
;
386 if (worst_time
< stop
->worst
.time
)
387 stop
->worst
.time
= worst_time
;
388 if (stop
->desired
.time
> stop
->worst
.time
)
389 stop
->desired
.time
= stop
->worst
.time
;
393 fprintf(stderr
, "desired %0.2f, worst %0.2f, clock [%d] %0.2f + %0.2f/%d*%d, lag %0.2f\n",
394 stop
->desired
.time
, stop
->worst
.time
,
395 ti
->dim
, ti
->len
.t
.main_time
,
396 ti
->len
.t
.byoyomi_time
, ti
->len
.t
.byoyomi_stones
,
397 ti
->len
.t
.byoyomi_periods
, net_lag
);
399 /* Account for lag. */
400 stop
->desired
.time
-= net_lag
;
401 stop
->worst
.time
-= net_lag
;