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
)
62 if (byoyomi_time
> 0 && byoyomi_stones
== 0) {
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 ti
->len
.t
.byoyomi_time_max
= ti
->len
.t
.byoyomi_time
;
86 ti
->len
.t
.byoyomi_stones_max
= ti
->len
.t
.byoyomi_stones
;
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. */
94 time_left(struct time_info
*ti
, int time_left
, int stones_left
)
96 assert(ti
->period
!= TT_NULL
);
97 ti
->dim
= TD_WALLTIME
;
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. */
105 } else if (!stones_left
) {
107 ti
->period
= TT_TOTAL
;
108 ti
->len
.t
.main_time
= time_left
;
109 /* byoyomi_time kept fully charged. */
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
;
119 // field misused by kgs
120 ti
->len
.t
.byoyomi_periods
= stones_left
;
125 /* Start our timer. kgs does this (correctly) on "play" not "genmove"
126 * unless we are making the first move of the game. */
128 time_start_timer(struct time_info
*ti
)
130 if (ti
->period
!= TT_NULL
&& ti
->dim
== TD_WALLTIME
)
131 ti
->len
.t
.timer_start
= time_now();
135 time_sub(struct time_info
*ti
, double interval
)
137 assert(ti
->dim
== TD_WALLTIME
&& ti
->period
!= TT_NULL
);
139 if (ti
->period
== TT_TOTAL
) {
140 ti
->len
.t
.main_time
-= interval
;
141 if (ti
->len
.t
.main_time
>= 0)
143 /* Fall-through to byoyomi. */
144 ti
->period
= TT_MOVE
;
145 interval
= -ti
->len
.t
.main_time
;
146 ti
->len
.t
.main_time
= 0;
149 ti
->len
.t
.byoyomi_time
-= interval
;
150 if (ti
->len
.t
.byoyomi_time
< 0) {
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;
158 ti
->len
.t
.byoyomi_time
= ti
->len
.t
.byoyomi_time_max
;
159 ti
->len
.t
.byoyomi_stones
= ti
->len
.t
.byoyomi_stones_max
;
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
;
169 /* Returns the current time. */
174 clock_gettime(CLOCK_REALTIME
, &now
);
175 return now
.tv_sec
+ now
.tv_nsec
/1000000000.0;
178 /* Sleep for a given interval (in seconds). Return immediately if interval < 0. */
180 time_sleep(double interval
)
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 */
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
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
206 /* Pre-process time_info for search control and sets the desired stopping conditions. */
208 time_stop_conditions(struct time_info
*ti
, struct board
*b
, int fuseki_end
, int yose_start
, struct time_stop
*stop
)
210 /* We must have _some_ limits by now, be it random default values! */
211 assert(ti
->period
!= TT_NULL
);
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
);
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
;
227 assert(ti
->dim
== TD_WALLTIME
);
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
236 net_lag
+= time_now() - ti
->len
.t
.timer_start
;
237 // TODO: keep statistics to get good estimate of lag not just current move
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
;
249 /* Absolute maximum time possible to spend on the move. */
251 /* Ideal/reasonable time to spend on the move. */
252 double recommended_time
;
254 if (ti
->period
== TT_MOVE
) {
255 /* We are in byoyomi, or almost! */
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
;
261 max_time
= period_len
;
262 assert(ti
->len
.t
.byoyomi_stones
> 0);
263 recommended_time
= period_len
/ ti
->len
.t
.byoyomi_stones
;
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
;
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
);
280 } else { assert(ti
->period
== TT_TOTAL
);
281 /* We are in main time. */
283 assert(ti
->len
.t
.main_time
> 0);
284 max_time
= ti
->len
.t
.main_time
;
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
;
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
302 /* In case of Canadian byoyomi, include time that can
303 * be spent on its first move. */
304 max_time
+= move_time
;
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
;
319 if (moves_left
<= 0) // possible if too much lag
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);
329 /* Furthermore, tweak the slice based on the game phase. */
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
);
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
;
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
;
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
;
375 fprintf(stderr
, "recommended_time %0.2f, max_time %0.2f, byoyomi %0.2f/%d, lag %0.2f\n",
376 recommended_time
, max_time
,
377 ti
->len
.t
.byoyomi_time
, ti
->len
.t
.byoyomi_stones
,
380 stop
->desired
.time
= ti
->len
.t
.timer_start
+ recommended_time
- net_lag
;
381 stop
->worst
.time
= ti
->len
.t
.timer_start
+ max_time
- net_lag
;
382 // Both stop points may be in the past if too much lag.