Add option -c chat_file to support fancy replies to kgs-chat
[pachi.git] / uct / search.c
blob222851683caf98d9cbf0b69d5cc7b2b0a8a753c3
1 #include <assert.h>
2 #include <math.h>
3 #include <pthread.h>
4 #include <signal.h>
5 #include <stdio.h>
6 #include <stdlib.h>
7 #include <string.h>
8 #include <time.h>
10 #define DEBUG
12 #include "debug.h"
13 #include "distributed/distributed.h"
14 #include "move.h"
15 #include "random.h"
16 #include "timeinfo.h"
17 #include "uct/dynkomi.h"
18 #include "uct/internal.h"
19 #include "uct/search.h"
20 #include "uct/tree.h"
21 #include "uct/uct.h"
22 #include "uct/walk.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 = {
29 .period = TT_MOVE,
30 .dim = TD_GAMES,
31 .len = { .games = MC_GAMES },
34 /* When terminating UCT search early, the safety margin to add to the
35 * remaining playout number estimate when deciding whether the result can
36 * still change. */
37 #define PLAYOUT_DELTA_SAFEMARGIN 1000
39 /* Minimal number of simulations to consider early break. */
40 #define PLAYOUT_EARLY_BREAK_MIN 5000
42 /* Minimal time to consider early break (in seconds). */
43 #define TIME_EARLY_BREAK_MIN 1.0
46 /* Pachi threading structure:
48 * main thread
49 * | main(), GTP communication, ...
50 * | starts and stops the search managed by thread_manager
51 * |
52 * thread_manager
53 * | spawns and collects worker threads
54 * |
55 * worker0
56 * worker1
57 * ...
58 * workerK
59 * uct_playouts() loop, doing descend-playout until uct_halt
61 * Another way to look at it is by functions (lines denote thread boundaries):
63 * | uct_genmove()
64 * | uct_search() (uct_search_start() .. uct_search_stop())
65 * | -----------------------
66 * | spawn_thread_manager()
67 * | -----------------------
68 * | spawn_worker()
69 * V uct_playouts() */
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;
82 static void *
83 spawn_worker(void *ctx_)
85 struct uct_thread_ctx *ctx = ctx_;
86 /* Setup */
87 fast_srandom(ctx->seed);
88 /* Run */
89 ctx->games = uct_playouts(ctx->u, ctx->b, ctx->color, ctx->t, ctx->ti);
90 /* Finish */
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);
96 return ctx;
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. */
107 static void *
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];
118 int joined = 0;
120 uct_halt = 0;
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;
133 ctx->ti = mctx->ti;
134 pthread_create(&threads[ti], NULL, spawn_worker, ctx);
135 if (UDEBUGL(3))
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
145 * and unblock them from terminating. */
146 uct_halt = 1;
147 /* We need to make sure the workers do not complete
148 * the termination sequence before we get officially
149 * stopped - their wake and the stop wake could get
150 * coalesced. */
151 pthread_mutex_unlock(&finish_serializer);
152 continue;
154 /* ...and gather its remnants. */
155 struct uct_thread_ctx *ctx;
156 pthread_join(threads[finish_thread], (void **) &ctx);
157 played_games += ctx->games;
158 joined++;
159 free(ctx);
160 if (UDEBUGL(3))
161 fprintf(stderr, "Joined worker %d\n", finish_thread);
162 pthread_mutex_unlock(&finish_serializer);
165 pthread_mutex_unlock(&finish_mutex);
167 mctx->games = played_games;
168 return mctx;
172 /*** THREAD MANAGER end */
174 /*** Search infrastructure: */
178 uct_search_games(struct uct_search_state *s)
180 return s->ctx->t->root->u.playouts;
183 void
184 uct_search_start(struct uct *u, struct board *b, enum stone color,
185 struct tree *t, struct time_info *ti,
186 struct uct_search_state *s)
188 /* Set up search state. */
189 s->base_playouts = s->last_dynkomi = s->last_print = t->root->u.playouts;
190 s->print_interval = u->reportfreq * u->threads;
191 s->fullmem = false;
193 if (ti) {
194 if (ti->period == TT_NULL) *ti = default_ti;
195 time_stop_conditions(ti, b, u->fuseki_end, u->yose_start, u->max_maintime_ratio, &s->stop);
198 /* Fire up the tree search thread manager, which will in turn
199 * spawn the searching threads. */
200 assert(u->threads > 0);
201 assert(!thread_manager_running);
202 static struct uct_thread_ctx mctx;
203 mctx = (struct uct_thread_ctx) { .u = u, .b = b, .color = color, .t = t, .seed = fast_random(65536), .ti = ti };
204 s->ctx = &mctx;
205 pthread_mutex_lock(&finish_serializer);
206 pthread_mutex_lock(&finish_mutex);
207 pthread_create(&thread_manager, NULL, spawn_thread_manager, s->ctx);
208 thread_manager_running = true;
211 struct uct_thread_ctx *
212 uct_search_stop(void)
214 assert(thread_manager_running);
216 /* Signal thread manager to stop the workers. */
217 pthread_mutex_lock(&finish_mutex);
218 finish_thread = -1;
219 pthread_cond_signal(&finish_cond);
220 pthread_mutex_unlock(&finish_mutex);
222 /* Collect the thread manager. */
223 struct uct_thread_ctx *pctx;
224 thread_manager_running = false;
225 pthread_join(thread_manager, (void **) &pctx);
226 return pctx;
230 void
231 uct_search_progress(struct uct *u, struct board *b, enum stone color,
232 struct tree *t, struct time_info *ti,
233 struct uct_search_state *s, int i)
235 struct uct_thread_ctx *ctx = s->ctx;
237 /* Adjust dynkomi? */
238 int di = u->dynkomi_interval * u->threads;
239 if (ctx->t->use_extra_komi && u->dynkomi->permove
240 && !u->pondering && di
241 && i > s->last_dynkomi + di) {
242 s->last_dynkomi += di;
243 floating_t old_dynkomi = ctx->t->extra_komi;
244 ctx->t->extra_komi = u->dynkomi->permove(u->dynkomi, b, ctx->t);
245 if (UDEBUGL(3) && old_dynkomi != ctx->t->extra_komi)
246 fprintf(stderr, "dynkomi adjusted (%f -> %f)\n",
247 old_dynkomi, ctx->t->extra_komi);
250 /* Print progress? */
251 if (i - s->last_print > s->print_interval) {
252 s->last_print += s->print_interval; // keep the numbers tidy
253 uct_progress_status(u, ctx->t, color, s->last_print, false);
256 if (!s->fullmem && ctx->t->nodes_size > u->max_tree_size) {
257 if (UDEBUGL(2))
258 fprintf(stderr, "memory limit hit (%lu > %lu)\n",
259 ctx->t->nodes_size, u->max_tree_size);
260 s->fullmem = true;
265 /* Determine whether we should terminate the search early. */
266 static bool
267 uct_search_stop_early(struct uct *u, struct tree *t, struct board *b,
268 struct time_info *ti, struct time_stop *stop,
269 struct tree_node *best, struct tree_node *best2,
270 int played, bool fullmem)
272 /* If the memory is full, stop immediately. Since the tree
273 * cannot grow anymore, some non-well-expanded nodes will
274 * quickly take over with extremely high ratio since the
275 * counters are not properly simulated (just as if we use
276 * non-UCT MonteCarlo). */
277 /* (XXX: A proper solution would be to prune the tree
278 * on the spot.) */
279 if (fullmem)
280 return true;
282 /* Think at least 100ms to avoid a random move. This is particularly
283 * important in distributed mode, where this function is called frequently. */
284 double elapsed = 0.0;
285 if (ti->dim == TD_WALLTIME) {
286 elapsed = time_now() - ti->len.t.timer_start;
287 if (elapsed < TREE_BUSYWAIT_INTERVAL) return false;
290 /* Break early if we estimate the second-best move cannot
291 * catch up in assigned time anymore. We use all our time
292 * if we are in byoyomi with single stone remaining in our
293 * period, however - it's better to pre-ponder. */
294 bool time_indulgent = (!ti->len.t.main_time && ti->len.t.byoyomi_stones == 1);
295 if (best2 && ti->dim == TD_WALLTIME
296 && played >= PLAYOUT_EARLY_BREAK_MIN && !time_indulgent) {
297 double remaining = stop->worst.time - elapsed;
298 double pps = ((double)played) / elapsed;
299 double estplayouts = remaining * pps + PLAYOUT_DELTA_SAFEMARGIN;
300 if (best->u.playouts > best2->u.playouts + estplayouts) {
301 if (UDEBUGL(2))
302 fprintf(stderr, "Early stop, result cannot change: "
303 "best %d, best2 %d, estimated %f simulations to go (%d/%f=%f pps)\n",
304 best->u.playouts, best2->u.playouts, estplayouts, played, elapsed, pps);
305 return true;
309 /* Early break in won situation. */
310 if (best->u.playouts >= PLAYOUT_EARLY_BREAK_MIN
311 && (ti->dim != TD_WALLTIME || elapsed > TIME_EARLY_BREAK_MIN)
312 && tree_node_get_value(t, 1, best->u.value) >= u->sure_win_threshold) {
313 return true;
316 return false;
319 /* Determine whether we should terminate the search later than expected. */
320 static bool
321 uct_search_keep_looking(struct uct *u, struct tree *t, struct board *b,
322 struct time_info *ti, struct time_stop *stop,
323 struct tree_node *best, struct tree_node *best2,
324 struct tree_node *bestr, struct tree_node *winner, int i)
326 if (!best) {
327 if (UDEBUGL(2))
328 fprintf(stderr, "Did not find best move, still trying...\n");
329 return true;
332 /* Do not waste time if we are winning. Spend up to worst time if
333 * we are unsure, but only desired time if we are sure of winning. */
334 floating_t beta = 2 * (tree_node_get_value(t, 1, best->u.value) - 0.5);
335 if (ti->dim == TD_WALLTIME && beta > 0) {
336 double good_enough = stop->desired.time * beta + stop->worst.time * (1 - beta);
337 double elapsed = time_now() - ti->len.t.timer_start;
338 if (elapsed > good_enough) return false;
341 if (u->best2_ratio > 0) {
342 /* Check best/best2 simulations ratio. If the
343 * two best moves give very similar results,
344 * keep simulating. */
345 if (best2 && best2->u.playouts
346 && (double)best->u.playouts / best2->u.playouts < u->best2_ratio) {
347 if (UDEBUGL(2))
348 fprintf(stderr, "Best2 ratio %f < threshold %f\n",
349 (double)best->u.playouts / best2->u.playouts,
350 u->best2_ratio);
351 return true;
355 if (u->bestr_ratio > 0) {
356 /* Check best, best_best value difference. If the best move
357 * and its best child do not give similar enough results,
358 * keep simulating. */
359 if (bestr && bestr->u.playouts
360 && fabs((double)best->u.value - bestr->u.value) > u->bestr_ratio) {
361 if (UDEBUGL(2))
362 fprintf(stderr, "Bestr delta %f > threshold %f\n",
363 fabs((double)best->u.value - bestr->u.value),
364 u->bestr_ratio);
365 return true;
369 if (winner && winner != best) {
370 /* Keep simulating if best explored
371 * does not have also highest value. */
372 if (UDEBUGL(2))
373 fprintf(stderr, "[%d] best %3s [%d] %f != winner %3s [%d] %f\n", i,
374 coord2sstr(node_coord(best), t->board),
375 best->u.playouts, tree_node_get_value(t, 1, best->u.value),
376 coord2sstr(node_coord(winner), t->board),
377 winner->u.playouts, tree_node_get_value(t, 1, winner->u.value));
378 return true;
381 /* No reason to keep simulating, bye. */
382 return false;
385 bool
386 uct_search_check_stop(struct uct *u, struct board *b, enum stone color,
387 struct tree *t, struct time_info *ti,
388 struct uct_search_state *s, int i)
390 struct uct_thread_ctx *ctx = s->ctx;
392 /* Never consider stopping if we played too few simulations.
393 * Maybe we risk losing on time when playing in super-extreme
394 * time pressure but the tree is going to be just too messed
395 * up otherwise - we might even play invalid suicides or pass
396 * when we mustn't. */
397 assert(!(ti->dim == TD_GAMES && ti->len.games < GJ_MINGAMES));
398 if (i < GJ_MINGAMES)
399 return false;
401 struct tree_node *best = NULL;
402 struct tree_node *best2 = NULL; // Second-best move.
403 struct tree_node *bestr = NULL; // best's best child.
404 struct tree_node *winner = NULL;
406 best = u->policy->choose(u->policy, ctx->t->root, b, color, resign);
407 if (best) best2 = u->policy->choose(u->policy, ctx->t->root, b, color, node_coord(best));
409 /* Possibly stop search early if it's no use to try on. */
410 int played = u->played_all + i - s->base_playouts;
411 if (best && uct_search_stop_early(u, ctx->t, b, ti, &s->stop, best, best2, played, s->fullmem))
412 return true;
414 /* Check against time settings. */
415 bool desired_done;
416 if (ti->dim == TD_WALLTIME) {
417 double elapsed = time_now() - ti->len.t.timer_start;
418 if (elapsed > s->stop.worst.time) return true;
419 desired_done = elapsed > s->stop.desired.time;
421 } else { assert(ti->dim == TD_GAMES);
422 if (i > s->stop.worst.playouts) return true;
423 desired_done = i > s->stop.desired.playouts;
426 /* We want to stop simulating, but are willing to keep trying
427 * if we aren't completely sure about the winner yet. */
428 if (desired_done) {
429 if (u->policy->winner && u->policy->evaluate) {
430 struct uct_descent descent = { .node = ctx->t->root };
431 u->policy->winner(u->policy, ctx->t, &descent);
432 winner = descent.node;
434 if (best)
435 bestr = u->policy->choose(u->policy, best, b, stone_other(color), resign);
436 if (!uct_search_keep_looking(u, ctx->t, b, ti, &s->stop, best, best2, bestr, winner, i))
437 return true;
440 /* TODO: Early break if best->variance goes under threshold
441 * and we already have enough playouts (possibly thanks to tbook
442 * or to pondering)? */
443 return false;
447 struct tree_node *
448 uct_search_result(struct uct *u, struct board *b, enum stone color,
449 bool pass_all_alive, int played_games, int base_playouts,
450 coord_t *best_coord)
452 /* Choose the best move from the tree. */
453 struct tree_node *best = u->policy->choose(u->policy, u->t->root, b, color, resign);
454 if (!best) {
455 *best_coord = pass;
456 return NULL;
458 *best_coord = node_coord(best);
459 if (UDEBUGL(1))
460 fprintf(stderr, "*** WINNER is %s (%d,%d) with score %1.4f (%d/%d:%d/%d games), extra komi %f\n",
461 coord2sstr(node_coord(best), b), coord_x(node_coord(best), b), coord_y(node_coord(best), b),
462 tree_node_get_value(u->t, 1, best->u.value), best->u.playouts,
463 u->t->root->u.playouts, u->t->root->u.playouts - base_playouts, played_games,
464 u->t->extra_komi);
466 /* Do not resign if we're so short of time that evaluation of best
467 * move is completely unreliable, we might be winning actually.
468 * In this case best is almost random but still better than resign.
469 * Also do not resign if we are getting bad results while actually
470 * giving away extra komi points (dynkomi). */
471 if (tree_node_get_value(u->t, 1, best->u.value) < u->resign_threshold
472 && !is_pass(node_coord(best)) && best->u.playouts > GJ_MINGAMES
473 && (!u->t->use_extra_komi || komi_by_color(u->t->extra_komi, color) < 0.5)) {
474 *best_coord = resign;
475 return NULL;
478 /* If the opponent just passed and we win counting, always
479 * pass as well. For option stones_only, we pass only when there
480 * there is nothing else to do, to show how to maximize score. */
481 if (b->moves > 1 && is_pass(b->last_move.coord) && b->rules != RULES_STONES_ONLY) {
482 if (uct_pass_is_safe(u, b, color, pass_all_alive)) {
483 if (UDEBUGL(0))
484 fprintf(stderr, "<Will rather pass, looks safe enough; score %f>\n",
485 board_official_score(b, NULL) / 2);
486 *best_coord = pass;
487 best = u->t->root->children; // pass is the first child
488 assert(is_pass(node_coord(best)));
489 return best;
490 } else {
491 if (UDEBUGL(3))
492 fprintf(stderr, "Refusing to pass, unsafe; pass_all_alive %d, ownermap #playouts %d, raw score %f\n",
493 pass_all_alive, u->ownermap.playouts,
494 board_official_score(b, NULL) / 2);
498 return best;