13 #include "distributed/distributed.h"
17 #include "uct/dynkomi.h"
18 #include "uct/internal.h"
19 #include "uct/search.h"
25 /* Default time settings for the UCT engine. */
26 static struct time_info default_ti
;
27 static __attribute__((constructor
)) void
30 time_parse(&default_ti
, "15");
33 /* When terminating UCT search early, the safety margin to add to the
34 * remaining playout number estimate when deciding whether the result can
36 #define PLAYOUT_DELTA_SAFEMARGIN 1000
38 /* Minimal number of simulations to consider early break. */
39 #define PLAYOUT_EARLY_BREAK_MIN 5000
41 /* Minimal time to consider early break (in seconds). */
42 #define TIME_EARLY_BREAK_MIN 1.0
45 /* Pachi threading structure:
48 * | main(), GTP communication, ...
49 * | starts and stops the search managed by thread_manager
52 * | spawns and collects worker threads
58 * uct_playouts() loop, doing descend-playout until uct_halt
60 * Another way to look at it is by functions (lines denote thread boundaries):
63 * | uct_search() (uct_search_start() .. uct_search_stop())
64 * | -----------------------
65 * | spawn_thread_manager()
66 * | -----------------------
70 /* Set in thread manager in case the workers should stop. */
71 volatile sig_atomic_t uct_halt
= 0;
72 /* ID of the thread manager. */
73 static pthread_t thread_manager
;
74 bool thread_manager_running
;
76 static pthread_mutex_t finish_mutex
= PTHREAD_MUTEX_INITIALIZER
;
77 static pthread_cond_t finish_cond
= PTHREAD_COND_INITIALIZER
;
78 static volatile int finish_thread
;
79 static pthread_mutex_t finish_serializer
= PTHREAD_MUTEX_INITIALIZER
;
82 spawn_worker(void *ctx_
)
84 struct uct_thread_ctx
*ctx
= ctx_
;
86 fast_srandom(ctx
->seed
);
88 ctx
->games
= uct_playouts(ctx
->u
, ctx
->b
, ctx
->color
, ctx
->t
, ctx
->ti
);
90 pthread_mutex_lock(&finish_serializer
);
91 pthread_mutex_lock(&finish_mutex
);
92 finish_thread
= ctx
->tid
;
93 pthread_cond_signal(&finish_cond
);
94 pthread_mutex_unlock(&finish_mutex
);
98 /* Thread manager, controlling worker threads. It must be called with
99 * finish_mutex lock held, but it will unlock it itself before exiting;
100 * this is necessary to be completely deadlock-free. */
101 /* The finish_cond can be signalled for it to stop; in that case,
102 * the caller should set finish_thread = -1. */
103 /* After it is started, it will update mctx->t to point at some tree
104 * used for the actual search, on return
105 * it will set mctx->games to the number of performed simulations. */
107 spawn_thread_manager(void *ctx_
)
109 /* In thread_manager, we use only some of the ctx fields. */
110 struct uct_thread_ctx
*mctx
= ctx_
;
111 struct uct
*u
= mctx
->u
;
112 struct tree
*t
= mctx
->t
;
113 fast_srandom(mctx
->seed
);
115 int played_games
= 0;
116 pthread_t threads
[u
->threads
];
121 /* Garbage collect the tree by preference when pondering. */
122 if (u
->pondering
&& t
->nodes
&& t
->nodes_size
>= t
->pruning_threshold
) {
123 t
->root
= tree_garbage_collect(t
, t
->root
);
126 /* Spawn threads... */
127 for (int ti
= 0; ti
< u
->threads
; ti
++) {
128 struct uct_thread_ctx
*ctx
= malloc2(sizeof(*ctx
));
129 ctx
->u
= u
; ctx
->b
= mctx
->b
; ctx
->color
= mctx
->color
;
130 mctx
->t
= ctx
->t
= t
;
131 ctx
->tid
= ti
; ctx
->seed
= fast_random(65536) + ti
;
134 pthread_attr_init(&a
);
135 pthread_attr_setstacksize(&a
, 1048576);
136 pthread_create(&threads
[ti
], &a
, spawn_worker
, ctx
);
138 fprintf(stderr
, "Spawned worker %d\n", ti
);
141 /* ...and collect them back: */
142 while (joined
< u
->threads
) {
143 /* Wait for some thread to finish... */
144 pthread_cond_wait(&finish_cond
, &finish_mutex
);
145 if (finish_thread
< 0) {
146 /* Stop-by-caller. Tell the workers to wrap up
147 * and unblock them from terminating. */
149 /* We need to make sure the workers do not complete
150 * the termination sequence before we get officially
151 * stopped - their wake and the stop wake could get
153 pthread_mutex_unlock(&finish_serializer
);
156 /* ...and gather its remnants. */
157 struct uct_thread_ctx
*ctx
;
158 pthread_join(threads
[finish_thread
], (void **) &ctx
);
159 played_games
+= ctx
->games
;
163 fprintf(stderr
, "Joined worker %d\n", finish_thread
);
164 pthread_mutex_unlock(&finish_serializer
);
167 pthread_mutex_unlock(&finish_mutex
);
169 mctx
->games
= played_games
;
174 /*** THREAD MANAGER end */
176 /*** Search infrastructure: */
180 uct_search_games(struct uct_search_state
*s
)
182 return s
->ctx
->t
->root
->u
.playouts
;
186 uct_search_start(struct uct
*u
, struct board
*b
, enum stone color
,
187 struct tree
*t
, struct time_info
*ti
,
188 struct uct_search_state
*s
)
190 /* Set up search state. */
191 s
->base_playouts
= s
->last_dynkomi
= s
->last_print
= t
->root
->u
.playouts
;
192 s
->print_interval
= u
->reportfreq
* u
->threads
;
196 if (ti
->period
== TT_NULL
) {
198 time_start_timer(ti
);
200 time_stop_conditions(ti
, b
, u
->fuseki_end
, u
->yose_start
, u
->max_maintime_ratio
, &s
->stop
);
203 /* Fire up the tree search thread manager, which will in turn
204 * spawn the searching threads. */
205 assert(u
->threads
> 0);
206 assert(!thread_manager_running
);
207 static struct uct_thread_ctx mctx
;
208 mctx
= (struct uct_thread_ctx
) { .u
= u
, .b
= b
, .color
= color
, .t
= t
, .seed
= fast_random(65536), .ti
= ti
};
210 pthread_mutex_lock(&finish_serializer
);
211 pthread_mutex_lock(&finish_mutex
);
212 pthread_create(&thread_manager
, NULL
, spawn_thread_manager
, s
->ctx
);
213 thread_manager_running
= true;
216 struct uct_thread_ctx
*
217 uct_search_stop(void)
219 assert(thread_manager_running
);
221 /* Signal thread manager to stop the workers. */
222 pthread_mutex_lock(&finish_mutex
);
224 pthread_cond_signal(&finish_cond
);
225 pthread_mutex_unlock(&finish_mutex
);
227 /* Collect the thread manager. */
228 struct uct_thread_ctx
*pctx
;
229 thread_manager_running
= false;
230 pthread_join(thread_manager
, (void **) &pctx
);
236 uct_search_progress(struct uct
*u
, struct board
*b
, enum stone color
,
237 struct tree
*t
, struct time_info
*ti
,
238 struct uct_search_state
*s
, int i
)
240 struct uct_thread_ctx
*ctx
= s
->ctx
;
242 /* Adjust dynkomi? */
243 int di
= u
->dynkomi_interval
* u
->threads
;
244 if (ctx
->t
->use_extra_komi
&& u
->dynkomi
->permove
245 && !u
->pondering
&& di
246 && i
> s
->last_dynkomi
+ di
) {
247 s
->last_dynkomi
+= di
;
248 floating_t old_dynkomi
= ctx
->t
->extra_komi
;
249 ctx
->t
->extra_komi
= u
->dynkomi
->permove(u
->dynkomi
, b
, ctx
->t
);
250 if (UDEBUGL(3) && old_dynkomi
!= ctx
->t
->extra_komi
)
251 fprintf(stderr
, "dynkomi adjusted (%f -> %f)\n",
252 old_dynkomi
, ctx
->t
->extra_komi
);
255 /* Print progress? */
256 if (i
- s
->last_print
> s
->print_interval
) {
257 s
->last_print
+= s
->print_interval
; // keep the numbers tidy
258 uct_progress_status(u
, ctx
->t
, color
, s
->last_print
, NULL
);
261 if (!s
->fullmem
&& ctx
->t
->nodes_size
> u
->max_tree_size
) {
263 fprintf(stderr
, "memory limit hit (%lu > %lu)\n",
264 ctx
->t
->nodes_size
, u
->max_tree_size
);
270 /* Determine whether we should terminate the search early. */
272 uct_search_stop_early(struct uct
*u
, struct tree
*t
, struct board
*b
,
273 struct time_info
*ti
, struct time_stop
*stop
,
274 struct tree_node
*best
, struct tree_node
*best2
,
275 int played
, bool fullmem
)
277 /* If the memory is full, stop immediately. Since the tree
278 * cannot grow anymore, some non-well-expanded nodes will
279 * quickly take over with extremely high ratio since the
280 * counters are not properly simulated (just as if we use
281 * non-UCT MonteCarlo). */
282 /* (XXX: A proper solution would be to prune the tree
287 /* Think at least 100ms to avoid a random move. This is particularly
288 * important in distributed mode, where this function is called frequently. */
289 double elapsed
= 0.0;
290 if (ti
->dim
== TD_WALLTIME
) {
291 elapsed
= time_now() - ti
->len
.t
.timer_start
;
292 if (elapsed
< TREE_BUSYWAIT_INTERVAL
) return false;
295 /* Break early if we estimate the second-best move cannot
296 * catch up in assigned time anymore. We use all our time
297 * if we are in byoyomi with single stone remaining in our
298 * period, however - it's better to pre-ponder. */
299 bool time_indulgent
= (!ti
->len
.t
.main_time
&& ti
->len
.t
.byoyomi_stones
== 1);
300 if (best2
&& ti
->dim
== TD_WALLTIME
301 && played
>= PLAYOUT_EARLY_BREAK_MIN
&& !time_indulgent
) {
302 double remaining
= stop
->worst
.time
- elapsed
;
303 double pps
= ((double)played
) / elapsed
;
304 double estplayouts
= remaining
* pps
+ PLAYOUT_DELTA_SAFEMARGIN
;
305 if (best
->u
.playouts
> best2
->u
.playouts
+ estplayouts
) {
307 fprintf(stderr
, "Early stop, result cannot change: "
308 "best %d, best2 %d, estimated %f simulations to go (%d/%f=%f pps)\n",
309 best
->u
.playouts
, best2
->u
.playouts
, estplayouts
, played
, elapsed
, pps
);
314 /* Early break in won situation. */
315 if (best
->u
.playouts
>= PLAYOUT_EARLY_BREAK_MIN
316 && (ti
->dim
!= TD_WALLTIME
|| elapsed
> TIME_EARLY_BREAK_MIN
)
317 && tree_node_get_value(t
, 1, best
->u
.value
) >= u
->sure_win_threshold
) {
324 /* Determine whether we should terminate the search later than expected. */
326 uct_search_keep_looking(struct uct
*u
, struct tree
*t
, struct board
*b
,
327 struct time_info
*ti
, struct time_stop
*stop
,
328 struct tree_node
*best
, struct tree_node
*best2
,
329 struct tree_node
*bestr
, struct tree_node
*winner
, int i
)
333 fprintf(stderr
, "Did not find best move, still trying...\n");
337 /* Do not waste time if we are winning. Spend up to worst time if
338 * we are unsure, but only desired time if we are sure of winning. */
339 floating_t beta
= 2 * (tree_node_get_value(t
, 1, best
->u
.value
) - 0.5);
340 if (ti
->dim
== TD_WALLTIME
&& beta
> 0) {
341 double good_enough
= stop
->desired
.time
* beta
+ stop
->worst
.time
* (1 - beta
);
342 double elapsed
= time_now() - ti
->len
.t
.timer_start
;
343 if (elapsed
> good_enough
) return false;
346 if (u
->best2_ratio
> 0) {
347 /* Check best/best2 simulations ratio. If the
348 * two best moves give very similar results,
349 * keep simulating. */
350 if (best2
&& best2
->u
.playouts
351 && (double)best
->u
.playouts
/ best2
->u
.playouts
< u
->best2_ratio
) {
353 fprintf(stderr
, "Best2 ratio %f < threshold %f\n",
354 (double)best
->u
.playouts
/ best2
->u
.playouts
,
360 if (u
->bestr_ratio
> 0) {
361 /* Check best, best_best value difference. If the best move
362 * and its best child do not give similar enough results,
363 * keep simulating. */
364 if (bestr
&& bestr
->u
.playouts
365 && fabs((double)best
->u
.value
- bestr
->u
.value
) > u
->bestr_ratio
) {
367 fprintf(stderr
, "Bestr delta %f > threshold %f\n",
368 fabs((double)best
->u
.value
- bestr
->u
.value
),
374 if (winner
&& winner
!= best
) {
375 /* Keep simulating if best explored
376 * does not have also highest value. */
378 fprintf(stderr
, "[%d] best %3s [%d] %f != winner %3s [%d] %f\n", i
,
379 coord2sstr(node_coord(best
), t
->board
),
380 best
->u
.playouts
, tree_node_get_value(t
, 1, best
->u
.value
),
381 coord2sstr(node_coord(winner
), t
->board
),
382 winner
->u
.playouts
, tree_node_get_value(t
, 1, winner
->u
.value
));
386 /* No reason to keep simulating, bye. */
391 uct_search_check_stop(struct uct
*u
, struct board
*b
, enum stone color
,
392 struct tree
*t
, struct time_info
*ti
,
393 struct uct_search_state
*s
, int i
)
395 struct uct_thread_ctx
*ctx
= s
->ctx
;
397 /* Never consider stopping if we played too few simulations.
398 * Maybe we risk losing on time when playing in super-extreme
399 * time pressure but the tree is going to be just too messed
400 * up otherwise - we might even play invalid suicides or pass
401 * when we mustn't. */
402 assert(!(ti
->dim
== TD_GAMES
&& ti
->len
.games
< GJ_MINGAMES
));
406 struct tree_node
*best
= NULL
;
407 struct tree_node
*best2
= NULL
; // Second-best move.
408 struct tree_node
*bestr
= NULL
; // best's best child.
409 struct tree_node
*winner
= NULL
;
411 best
= u
->policy
->choose(u
->policy
, ctx
->t
->root
, b
, color
, resign
);
412 if (best
) best2
= u
->policy
->choose(u
->policy
, ctx
->t
->root
, b
, color
, node_coord(best
));
414 /* Possibly stop search early if it's no use to try on. */
415 int played
= u
->played_all
+ i
- s
->base_playouts
;
416 if (best
&& uct_search_stop_early(u
, ctx
->t
, b
, ti
, &s
->stop
, best
, best2
, played
, s
->fullmem
))
419 /* Check against time settings. */
421 if (ti
->dim
== TD_WALLTIME
) {
422 double elapsed
= time_now() - ti
->len
.t
.timer_start
;
423 if (elapsed
> s
->stop
.worst
.time
) return true;
424 desired_done
= elapsed
> s
->stop
.desired
.time
;
426 } else { assert(ti
->dim
== TD_GAMES
);
427 if (i
> s
->stop
.worst
.playouts
) return true;
428 desired_done
= i
> s
->stop
.desired
.playouts
;
431 /* We want to stop simulating, but are willing to keep trying
432 * if we aren't completely sure about the winner yet. */
434 if (u
->policy
->winner
&& u
->policy
->evaluate
) {
435 struct uct_descent descent
= { .node
= ctx
->t
->root
};
436 u
->policy
->winner(u
->policy
, ctx
->t
, &descent
);
437 winner
= descent
.node
;
440 bestr
= u
->policy
->choose(u
->policy
, best
, b
, stone_other(color
), resign
);
441 if (!uct_search_keep_looking(u
, ctx
->t
, b
, ti
, &s
->stop
, best
, best2
, bestr
, winner
, i
))
445 /* TODO: Early break if best->variance goes under threshold
446 * and we already have enough playouts (possibly thanks to tbook
447 * or to pondering)? */
453 uct_search_result(struct uct
*u
, struct board
*b
, enum stone color
,
454 bool pass_all_alive
, int played_games
, int base_playouts
,
457 /* Choose the best move from the tree. */
458 struct tree_node
*best
= u
->policy
->choose(u
->policy
, u
->t
->root
, b
, color
, resign
);
463 *best_coord
= node_coord(best
);
465 fprintf(stderr
, "*** WINNER is %s (%d,%d) with score %1.4f (%d/%d:%d/%d games), extra komi %f\n",
466 coord2sstr(node_coord(best
), b
), coord_x(node_coord(best
), b
), coord_y(node_coord(best
), b
),
467 tree_node_get_value(u
->t
, 1, best
->u
.value
), best
->u
.playouts
,
468 u
->t
->root
->u
.playouts
, u
->t
->root
->u
.playouts
- base_playouts
, played_games
,
471 /* Do not resign if we're so short of time that evaluation of best
472 * move is completely unreliable, we might be winning actually.
473 * In this case best is almost random but still better than resign.
474 * Also do not resign if we are getting bad results while actually
475 * giving away extra komi points (dynkomi). */
476 if (tree_node_get_value(u
->t
, 1, best
->u
.value
) < u
->resign_threshold
477 && !is_pass(node_coord(best
)) && best
->u
.playouts
> GJ_MINGAMES
478 && (!u
->t
->use_extra_komi
|| komi_by_color(u
->t
->extra_komi
, color
) < 0.5)) {
479 *best_coord
= resign
;
483 /* If the opponent just passed and we win counting, always
484 * pass as well. For option stones_only, we pass only when there
485 * there is nothing else to do, to show how to maximize score. */
486 if (b
->moves
> 1 && is_pass(b
->last_move
.coord
) && b
->rules
!= RULES_STONES_ONLY
) {
487 if (uct_pass_is_safe(u
, b
, color
, pass_all_alive
)) {
489 fprintf(stderr
, "<Will rather pass, looks safe enough; score %f>\n",
490 board_official_score(b
, NULL
) / 2);
492 best
= u
->t
->root
->children
; // pass is the first child
493 assert(is_pass(node_coord(best
)));
497 fprintf(stderr
, "Refusing to pass, unsafe; pass_all_alive %d, ownermap #playouts %d, raw score %f\n",
498 pass_all_alive
, u
->ownermap
.playouts
,
499 board_official_score(b
, NULL
) / 2);