13 #include "distributed/distributed.h"
17 #include "uct/dynkomi.h"
18 #include "uct/internal.h"
19 #include "uct/search.h"
25 /* Default number of simulations to perform per move.
26 * Note that this is now in total over all threads!. */
27 #define MC_GAMES 80000
28 static const struct time_info default_ti
= {
31 .len
= { .games
= MC_GAMES
},
34 /* Once per how many simulations (per thread) to show a progress report line. */
35 #define TREE_SIMPROGRESS_INTERVAL 10000
37 /* When terminating UCT search early, the safety margin to add to the
38 * remaining playout number estimate when deciding whether the result can
40 #define PLAYOUT_DELTA_SAFEMARGIN 1000
42 /* Minimal number of simulations to consider early break. */
43 #define PLAYOUT_EARLY_BREAK_MIN 5000
46 /* Pachi threading structure:
49 * | main(), GTP communication, ...
50 * | starts and stops the search managed by thread_manager
53 * | spawns and collects worker threads
59 * uct_playouts() loop, doing descend-playout until uct_halt
61 * Another way to look at it is by functions (lines denote thread boundaries):
64 * | uct_search() (uct_search_start() .. uct_search_stop())
65 * | -----------------------
66 * | spawn_thread_manager()
67 * | -----------------------
71 /* Set in thread manager in case the workers should stop. */
72 volatile sig_atomic_t uct_halt
= 0;
73 /* ID of the thread manager. */
74 static pthread_t thread_manager
;
75 bool thread_manager_running
;
77 static pthread_mutex_t finish_mutex
= PTHREAD_MUTEX_INITIALIZER
;
78 static pthread_cond_t finish_cond
= PTHREAD_COND_INITIALIZER
;
79 static volatile int finish_thread
;
80 static pthread_mutex_t finish_serializer
= PTHREAD_MUTEX_INITIALIZER
;
83 spawn_worker(void *ctx_
)
85 struct uct_thread_ctx
*ctx
= ctx_
;
87 fast_srandom(ctx
->seed
);
89 ctx
->games
= uct_playouts(ctx
->u
, ctx
->b
, ctx
->color
, ctx
->t
, ctx
->ti
);
91 pthread_mutex_lock(&finish_serializer
);
92 pthread_mutex_lock(&finish_mutex
);
93 finish_thread
= ctx
->tid
;
94 pthread_cond_signal(&finish_cond
);
95 pthread_mutex_unlock(&finish_mutex
);
99 /* Thread manager, controlling worker threads. It must be called with
100 * finish_mutex lock held, but it will unlock it itself before exiting;
101 * this is necessary to be completely deadlock-free. */
102 /* The finish_cond can be signalled for it to stop; in that case,
103 * the caller should set finish_thread = -1. */
104 /* After it is started, it will update mctx->t to point at some tree
105 * used for the actual search, on return
106 * it will set mctx->games to the number of performed simulations. */
108 spawn_thread_manager(void *ctx_
)
110 /* In thread_manager, we use only some of the ctx fields. */
111 struct uct_thread_ctx
*mctx
= ctx_
;
112 struct uct
*u
= mctx
->u
;
113 struct tree
*t
= mctx
->t
;
114 fast_srandom(mctx
->seed
);
116 int played_games
= 0;
117 pthread_t threads
[u
->threads
];
122 /* Garbage collect the tree by preference when pondering. */
123 if (u
->pondering
&& t
->nodes
&& t
->nodes_size
>= t
->pruning_threshold
) {
124 t
->root
= tree_garbage_collect(t
, t
->root
);
127 /* Spawn threads... */
128 for (int ti
= 0; ti
< u
->threads
; ti
++) {
129 struct uct_thread_ctx
*ctx
= malloc2(sizeof(*ctx
));
130 ctx
->u
= u
; ctx
->b
= mctx
->b
; ctx
->color
= mctx
->color
;
131 mctx
->t
= ctx
->t
= t
;
132 ctx
->tid
= ti
; ctx
->seed
= fast_random(65536) + ti
;
134 pthread_create(&threads
[ti
], NULL
, spawn_worker
, ctx
);
136 fprintf(stderr
, "Spawned worker %d\n", ti
);
139 /* ...and collect them back: */
140 while (joined
< u
->threads
) {
141 /* Wait for some thread to finish... */
142 pthread_cond_wait(&finish_cond
, &finish_mutex
);
143 if (finish_thread
< 0) {
144 /* Stop-by-caller. Tell the workers to wrap up. */
148 /* ...and gather its remnants. */
149 struct uct_thread_ctx
*ctx
;
150 pthread_join(threads
[finish_thread
], (void **) &ctx
);
151 played_games
+= ctx
->games
;
155 fprintf(stderr
, "Joined worker %d\n", finish_thread
);
156 pthread_mutex_unlock(&finish_serializer
);
159 pthread_mutex_unlock(&finish_mutex
);
161 mctx
->games
= played_games
;
166 /*** THREAD MANAGER end */
168 /*** Search infrastructure: */
172 uct_search_games(struct uct_search_state
*s
)
174 return s
->ctx
->t
->root
->u
.playouts
;
178 uct_search_start(struct uct
*u
, struct board
*b
, enum stone color
,
179 struct tree
*t
, struct time_info
*ti
,
180 struct uct_search_state
*s
)
182 /* Set up search state. */
183 s
->base_playouts
= s
->last_dynkomi
= s
->last_print
= t
->root
->u
.playouts
;
184 s
->print_interval
= TREE_SIMPROGRESS_INTERVAL
* u
->threads
;
188 if (ti
->period
== TT_NULL
) *ti
= default_ti
;
189 time_stop_conditions(ti
, b
, u
->fuseki_end
, u
->yose_start
, &s
->stop
);
192 /* Fire up the tree search thread manager, which will in turn
193 * spawn the searching threads. */
194 assert(u
->threads
> 0);
195 assert(!thread_manager_running
);
196 static struct uct_thread_ctx mctx
;
197 mctx
= (struct uct_thread_ctx
) { .u
= u
, .b
= b
, .color
= color
, .t
= t
, .seed
= fast_random(65536), .ti
= ti
};
199 pthread_mutex_lock(&finish_mutex
);
200 pthread_create(&thread_manager
, NULL
, spawn_thread_manager
, s
->ctx
);
201 thread_manager_running
= true;
204 struct uct_thread_ctx
*
205 uct_search_stop(void)
207 assert(thread_manager_running
);
209 /* Signal thread manager to stop the workers. */
210 pthread_mutex_lock(&finish_mutex
);
212 pthread_cond_signal(&finish_cond
);
213 pthread_mutex_unlock(&finish_mutex
);
215 /* Collect the thread manager. */
216 struct uct_thread_ctx
*pctx
;
217 thread_manager_running
= false;
218 pthread_join(thread_manager
, (void **) &pctx
);
224 uct_search_progress(struct uct
*u
, struct board
*b
, enum stone color
,
225 struct tree
*t
, struct time_info
*ti
,
226 struct uct_search_state
*s
, int i
)
228 struct uct_thread_ctx
*ctx
= s
->ctx
;
230 /* Adjust dynkomi? */
231 int di
= u
->dynkomi_interval
* u
->threads
;
232 if (ctx
->t
->use_extra_komi
&& u
->dynkomi
->permove
233 && !u
->pondering
&& di
234 && i
> s
->last_dynkomi
+ di
) {
235 s
->last_dynkomi
+= di
;
236 float old_dynkomi
= ctx
->t
->extra_komi
;
237 ctx
->t
->extra_komi
= u
->dynkomi
->permove(u
->dynkomi
, b
, ctx
->t
);
238 if (UDEBUGL(3) && old_dynkomi
!= ctx
->t
->extra_komi
)
239 fprintf(stderr
, "dynkomi adjusted (%f -> %f)\n",
240 old_dynkomi
, ctx
->t
->extra_komi
);
243 /* Print progress? */
244 if (i
- s
->last_print
> s
->print_interval
) {
245 s
->last_print
+= s
->print_interval
; // keep the numbers tidy
246 uct_progress_status(u
, ctx
->t
, color
, s
->last_print
);
249 if (!s
->fullmem
&& ctx
->t
->nodes_size
> u
->max_tree_size
) {
251 fprintf(stderr
, "memory limit hit (%lu > %lu)\n",
252 ctx
->t
->nodes_size
, u
->max_tree_size
);
258 /* Determine whether we should terminate the search early. */
260 uct_search_stop_early(struct uct
*u
, struct tree
*t
, struct board
*b
,
261 struct time_info
*ti
, struct time_stop
*stop
,
262 struct tree_node
*best
, struct tree_node
*best2
,
263 int played
, bool fullmem
)
265 /* If the memory is full, stop immediately. Since the tree
266 * cannot grow anymore, some non-well-expanded nodes will
267 * quickly take over with extremely high ratio since the
268 * counters are not properly simulated (just as if we use
269 * non-UCT MonteCarlo). */
270 /* (XXX: A proper solution would be to prune the tree
275 /* Think at least 100ms to avoid a random move. This is particularly
276 * important in distributed mode, where this function is called frequently. */
277 double elapsed
= 0.0;
278 if (ti
->dim
== TD_WALLTIME
) {
279 elapsed
= time_now() - ti
->len
.t
.timer_start
;
280 if (elapsed
< TREE_BUSYWAIT_INTERVAL
) return false;
283 /* Break early if we estimate the second-best move cannot
284 * catch up in assigned time anymore. We use all our time
285 * if we are in byoyomi with single stone remaining in our
286 * period, however - it's better to pre-ponder. */
287 bool time_indulgent
= (!ti
->len
.t
.main_time
&& ti
->len
.t
.byoyomi_stones
== 1);
288 if (best2
&& ti
->dim
== TD_WALLTIME
&& !time_indulgent
) {
289 double remaining
= stop
->worst
.time
- elapsed
;
290 double pps
= ((double)played
) / elapsed
;
291 double estplayouts
= remaining
* pps
+ PLAYOUT_DELTA_SAFEMARGIN
;
292 if (best
->u
.playouts
> best2
->u
.playouts
+ estplayouts
) {
294 fprintf(stderr
, "Early stop, result cannot change: "
295 "best %d, best2 %d, estimated %f simulations to go\n",
296 best
->u
.playouts
, best2
->u
.playouts
, estplayouts
);
301 /* Early break in won situation. */
302 if (best
->u
.playouts
>= PLAYOUT_EARLY_BREAK_MIN
303 && tree_node_get_value(t
, 1, best
->u
.value
) >= u
->sure_win_threshold
) {
310 /* Determine whether we should terminate the search later than expected. */
312 uct_search_keep_looking(struct uct
*u
, struct tree
*t
, struct board
*b
,
313 struct time_info
*ti
, struct time_stop
*stop
,
314 struct tree_node
*best
, struct tree_node
*best2
,
315 struct tree_node
*bestr
, struct tree_node
*winner
, int i
)
319 fprintf(stderr
, "Did not find best move, still trying...\n");
323 /* Do not waste time if we are winning. Spend up to worst time if
324 * we are unsure, but only desired time if we are sure of winning. */
325 float beta
= 2 * (tree_node_get_value(t
, 1, best
->u
.value
) - 0.5);
326 if (ti
->dim
== TD_WALLTIME
&& beta
> 0) {
327 double good_enough
= stop
->desired
.time
* beta
+ stop
->worst
.time
* (1 - beta
);
328 double elapsed
= time_now() - ti
->len
.t
.timer_start
;
329 if (elapsed
> good_enough
) return false;
332 if (u
->best2_ratio
> 0) {
333 /* Check best/best2 simulations ratio. If the
334 * two best moves give very similar results,
335 * keep simulating. */
336 if (best2
&& best2
->u
.playouts
337 && (double)best
->u
.playouts
/ best2
->u
.playouts
< u
->best2_ratio
) {
339 fprintf(stderr
, "Best2 ratio %f < threshold %f\n",
340 (double)best
->u
.playouts
/ best2
->u
.playouts
,
346 if (u
->bestr_ratio
> 0) {
347 /* Check best, best_best value difference. If the best move
348 * and its best child do not give similar enough results,
349 * keep simulating. */
350 if (bestr
&& bestr
->u
.playouts
351 && fabs((double)best
->u
.value
- bestr
->u
.value
) > u
->bestr_ratio
) {
353 fprintf(stderr
, "Bestr delta %f > threshold %f\n",
354 fabs((double)best
->u
.value
- bestr
->u
.value
),
360 if (winner
&& winner
!= best
) {
361 /* Keep simulating if best explored
362 * does not have also highest value. */
364 fprintf(stderr
, "[%d] best %3s [%d] %f != winner %3s [%d] %f\n", i
,
365 coord2sstr(best
->coord
, t
->board
),
366 best
->u
.playouts
, tree_node_get_value(t
, 1, best
->u
.value
),
367 coord2sstr(winner
->coord
, t
->board
),
368 winner
->u
.playouts
, tree_node_get_value(t
, 1, winner
->u
.value
));
372 /* No reason to keep simulating, bye. */
377 uct_search_check_stop(struct uct
*u
, struct board
*b
, enum stone color
,
378 struct tree
*t
, struct time_info
*ti
,
379 struct uct_search_state
*s
, int i
)
381 struct uct_thread_ctx
*ctx
= s
->ctx
;
383 /* Never consider stopping if we played too few simulations.
384 * Maybe we risk losing on time when playing in super-extreme
385 * time pressure but the tree is going to be just too messed
386 * up otherwise - we might even play invalid suicides or pass
387 * when we mustn't. */
388 assert(!(ti
->dim
== TD_GAMES
&& ti
->len
.games
< GJ_MINGAMES
));
392 struct tree_node
*best
= NULL
;
393 struct tree_node
*best2
= NULL
; // Second-best move.
394 struct tree_node
*bestr
= NULL
; // best's best child.
395 struct tree_node
*winner
= NULL
;
397 best
= u
->policy
->choose(u
->policy
, ctx
->t
->root
, b
, color
, resign
);
398 if (best
) best2
= u
->policy
->choose(u
->policy
, ctx
->t
->root
, b
, color
, best
->coord
);
400 /* Possibly stop search early if it's no use to try on. */
401 int played
= u
->played_all
+ i
- s
->base_playouts
;
402 if (best
&& uct_search_stop_early(u
, ctx
->t
, b
, ti
, &s
->stop
, best
, best2
, played
, s
->fullmem
))
405 /* Check against time settings. */
407 if (ti
->dim
== TD_WALLTIME
) {
408 double elapsed
= time_now() - ti
->len
.t
.timer_start
;
409 if (elapsed
> s
->stop
.worst
.time
) return true;
410 desired_done
= elapsed
> s
->stop
.desired
.time
;
412 } else { assert(ti
->dim
== TD_GAMES
);
413 if (i
> s
->stop
.worst
.playouts
) return true;
414 desired_done
= i
> s
->stop
.desired
.playouts
;
417 /* We want to stop simulating, but are willing to keep trying
418 * if we aren't completely sure about the winner yet. */
420 if (u
->policy
->winner
&& u
->policy
->evaluate
) {
421 struct uct_descent descent
= { .node
= ctx
->t
->root
};
422 u
->policy
->winner(u
->policy
, ctx
->t
, &descent
);
423 winner
= descent
.node
;
426 bestr
= u
->policy
->choose(u
->policy
, best
, b
, stone_other(color
), resign
);
427 if (!uct_search_keep_looking(u
, ctx
->t
, b
, ti
, &s
->stop
, best
, best2
, bestr
, winner
, i
))
431 /* TODO: Early break if best->variance goes under threshold
432 * and we already have enough playouts (possibly thanks to tbook
433 * or to pondering)? */
439 uct_search_result(struct uct
*u
, struct board
*b
, enum stone color
,
440 bool pass_all_alive
, int played_games
, int base_playouts
,
443 /* Choose the best move from the tree. */
444 struct tree_node
*best
= u
->policy
->choose(u
->policy
, u
->t
->root
, b
, color
, resign
);
449 *best_coord
= best
->coord
;
451 fprintf(stderr
, "*** WINNER is %s (%d,%d) with score %1.4f (%d/%d:%d/%d games), extra komi %f\n",
452 coord2sstr(best
->coord
, b
), coord_x(best
->coord
, b
), coord_y(best
->coord
, b
),
453 tree_node_get_value(u
->t
, 1, best
->u
.value
), best
->u
.playouts
,
454 u
->t
->root
->u
.playouts
, u
->t
->root
->u
.playouts
- base_playouts
, played_games
,
457 /* Do not resign if we're so short of time that evaluation of best
458 * move is completely unreliable, we might be winning actually.
459 * In this case best is almost random but still better than resign.
460 * Also do not resign if we are getting bad results while actually
461 * giving away extra komi points (dynkomi). */
462 if (tree_node_get_value(u
->t
, 1, best
->u
.value
) < u
->resign_threshold
463 && !is_pass(best
->coord
) && best
->u
.playouts
> GJ_MINGAMES
464 && (!u
->t
->use_extra_komi
|| komi_by_color(u
->t
->extra_komi
, color
) < 0.5)) {
465 *best_coord
= resign
;
469 /* If the opponent just passed and we win counting, always
471 if (b
->moves
> 1 && is_pass(b
->last_move
.coord
)) {
472 /* Make sure enough playouts are simulated. */
473 while (u
->ownermap
.playouts
< GJ_MINGAMES
)
474 uct_playout(u
, b
, color
, u
->t
);
475 if (uct_pass_is_safe(u
, b
, color
, u
->pass_all_alive
|| pass_all_alive
)) {
477 fprintf(stderr
, "<Will rather pass, looks safe enough; score %f>\n",
478 board_official_score(b
, NULL
) / 2);
480 best
= u
->t
->root
->children
; // pass is the first child
481 assert(is_pass(best
->coord
));