Do not waste time if we are winning. Spend up to worst time if
[pachi/derm.git] / uct / uct.c
blobb6a9114ccf85378a4a5de435d33e69db95c1a95a
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 "board.h"
14 #include "gtp.h"
15 #include "move.h"
16 #include "mq.h"
17 #include "playout.h"
18 #include "playout/elo.h"
19 #include "playout/moggy.h"
20 #include "playout/light.h"
21 #include "random.h"
22 #include "tactics.h"
23 #include "timeinfo.h"
24 #include "uct/dynkomi.h"
25 #include "uct/internal.h"
26 #include "uct/prior.h"
27 #include "uct/tree.h"
28 #include "uct/uct.h"
29 #include "uct/walk.h"
31 struct uct_policy *policy_ucb1_init(struct uct *u, char *arg);
32 struct uct_policy *policy_ucb1amaf_init(struct uct *u, char *arg);
33 static void uct_pondering_stop(struct uct *u);
36 /* Default number of simulations to perform per move.
37 * Note that this is now in total over all threads! (Unless TM_ROOT.) */
38 #define MC_GAMES 80000
39 #define MC_GAMELEN MAX_GAMELEN
40 static const struct time_info default_ti = {
41 .period = TT_MOVE,
42 .dim = TD_GAMES,
43 .len = { .games = MC_GAMES },
46 /* How big proportion of ownermap counts must be of one color to consider
47 * the point sure. */
48 #define GJ_THRES 0.8
49 /* How many games to consider at minimum before judging groups. */
50 #define GJ_MINGAMES 500
52 /* How often to inspect the tree from the main thread to check for playout
53 * stop, progress reports, etc. (in seconds) */
54 #define TREE_BUSYWAIT_INTERVAL 0.1 /* 100ms */
56 /* Once per how many simulations (per thread) to show a progress report line. */
57 #define TREE_SIMPROGRESS_INTERVAL 10000
59 /* When terminating uct_search() early, the safety margin to add to the
60 * remaining playout number estimate when deciding whether the result can
61 * still change. */
62 #define PLAYOUT_DELTA_SAFEMARGIN 1000
65 static void
66 setup_state(struct uct *u, struct board *b, enum stone color)
68 u->t = tree_init(b, color, u->fast_alloc ? u->max_tree_size : 0, u->local_tree_aging);
69 if (u->force_seed)
70 fast_srandom(u->force_seed);
71 if (UDEBUGL(0))
72 fprintf(stderr, "Fresh board with random seed %lu\n", fast_getseed());
73 //board_print(b, stderr);
74 if (!u->no_book && b->moves == 0) {
75 assert(color == S_BLACK);
76 tree_load(u->t, b);
80 static void
81 reset_state(struct uct *u)
83 assert(u->t);
84 tree_done(u->t); u->t = NULL;
87 static void
88 setup_dynkomi(struct uct *u, struct board *b, enum stone to_play)
90 if (u->t->use_extra_komi && u->dynkomi->permove)
91 u->t->extra_komi = u->dynkomi->permove(u->dynkomi, b, u->t);
94 static void
95 prepare_move(struct engine *e, struct board *b, enum stone color)
97 struct uct *u = e->data;
99 if (u->t) {
100 /* Verify that we have sane state. */
101 assert(b->es == u);
102 assert(u->t && b->moves);
103 if (color != stone_other(u->t->root_color)) {
104 fprintf(stderr, "Fatal: Non-alternating play detected %d %d\n",
105 color, u->t->root_color);
106 exit(1);
109 } else {
110 /* We need fresh state. */
111 b->es = u;
112 setup_state(u, b, color);
115 u->ownermap.playouts = 0;
116 memset(u->ownermap.map, 0, board_size2(b) * sizeof(u->ownermap.map[0]));
119 static void
120 dead_group_list(struct uct *u, struct board *b, struct move_queue *mq)
122 struct group_judgement gj;
123 gj.thres = GJ_THRES;
124 gj.gs = alloca(board_size2(b) * sizeof(gj.gs[0]));
125 board_ownermap_judge_group(b, &u->ownermap, &gj);
126 groups_of_status(b, &gj, GS_DEAD, mq);
129 bool
130 uct_pass_is_safe(struct uct *u, struct board *b, enum stone color, bool pass_all_alive)
132 if (u->ownermap.playouts < GJ_MINGAMES)
133 return false;
135 struct move_queue mq = { .moves = 0 };
136 if (!pass_all_alive)
137 dead_group_list(u, b, &mq);
138 return pass_is_safe(b, color, &mq);
142 static void
143 uct_printhook_ownermap(struct board *board, coord_t c, FILE *f)
145 struct uct *u = board->es;
146 assert(u);
147 const char chr[] = ":XO,"; // dame, black, white, unclear
148 const char chm[] = ":xo,";
149 char ch = chr[board_ownermap_judge_point(&u->ownermap, c, GJ_THRES)];
150 if (ch == ',') { // less precise estimate then?
151 ch = chm[board_ownermap_judge_point(&u->ownermap, c, 0.67)];
153 fprintf(f, "%c ", ch);
156 static char *
157 uct_notify_play(struct engine *e, struct board *b, struct move *m)
159 struct uct *u = e->data;
160 if (!u->t) {
161 /* No state, create one - this is probably game beginning
162 * and we need to load the opening book right now. */
163 prepare_move(e, b, m->color);
164 assert(u->t);
167 /* Stop pondering. */
168 /* XXX: If we are about to receive multiple 'play' commands,
169 * e.g. in a rengo, we will not ponder during the rest of them. */
170 uct_pondering_stop(u);
172 if (is_resign(m->coord)) {
173 /* Reset state. */
174 reset_state(u);
175 return NULL;
178 /* Promote node of the appropriate move to the tree root. */
179 assert(u->t->root);
180 if (!tree_promote_at(u->t, b, m->coord)) {
181 if (UDEBUGL(0))
182 fprintf(stderr, "Warning: Cannot promote move node! Several play commands in row?\n");
183 reset_state(u);
184 return NULL;
186 return NULL;
189 static char *
190 uct_chat(struct engine *e, struct board *b, char *cmd)
192 struct uct *u = e->data;
193 static char reply[1024];
195 cmd += strspn(cmd, " \n\t");
196 if (!strncasecmp(cmd, "winrate", 7)) {
197 if (!u->t)
198 return "no game context (yet?)";
199 enum stone color = u->t->root_color;
200 struct tree_node *n = u->t->root;
201 snprintf(reply, 1024, "In %d playouts at %d threads, %s %s can win with %.2f%% probability",
202 n->u.playouts, u->threads, stone2str(color), coord2sstr(n->coord, b),
203 tree_node_get_value(u->t, -1, n->u.value) * 100);
204 if (u->t->use_extra_komi && abs(u->t->extra_komi) >= 0.5) {
205 sprintf(reply + strlen(reply), ", while self-imposing extra komi %.1f",
206 u->t->extra_komi);
208 strcat(reply, ".");
209 return reply;
211 return NULL;
214 static void
215 uct_dead_group_list(struct engine *e, struct board *b, struct move_queue *mq)
217 struct uct *u = e->data;
219 /* This means the game is probably over, no use pondering on. */
220 uct_pondering_stop(u);
222 if (u->pass_all_alive)
223 return; // no dead groups
225 bool mock_state = false;
227 if (!u->t) {
228 /* No state, but we cannot just back out - we might
229 * have passed earlier, only assuming some stones are
230 * dead, and then re-connected, only to lose counting
231 * when all stones are assumed alive. */
232 /* Mock up some state and seed the ownermap by few
233 * simulations. */
234 prepare_move(e, b, S_BLACK); assert(u->t);
235 for (int i = 0; i < GJ_MINGAMES; i++)
236 uct_playout(u, b, S_BLACK, u->t);
237 mock_state = true;
240 dead_group_list(u, b, mq);
242 if (mock_state) {
243 /* Clean up the mock state in case we will receive
244 * a genmove; we could get a non-alternating-move
245 * error from prepare_move() in that case otherwise. */
246 reset_state(u);
250 static void
251 playout_policy_done(struct playout_policy *p)
253 if (p->done) p->done(p);
254 if (p->data) free(p->data);
255 free(p);
258 static void
259 uct_done(struct engine *e)
261 /* This is called on engine reset, especially when clear_board
262 * is received and new game should begin. */
263 struct uct *u = e->data;
264 uct_pondering_stop(u);
265 if (u->t) reset_state(u);
266 free(u->ownermap.map);
268 free(u->policy);
269 free(u->random_policy);
270 playout_policy_done(u->playout);
271 uct_prior_done(u->prior);
275 /* Pachi threading structure (if uct_playouts_parallel() is used):
277 * main thread
278 * | main(), GTP communication, ...
279 * | starts and stops the search managed by thread_manager
281 * thread_manager
282 * | spawns and collects worker threads
284 * worker0
285 * worker1
286 * ...
287 * workerK
288 * uct_playouts() loop, doing descend-playout until uct_halt
290 * Another way to look at it is by functions (lines denote thread boundaries):
292 * | uct_genmove()
293 * | uct_search() (uct_search_start() .. uct_search_stop())
294 * | -----------------------
295 * | spawn_thread_manager()
296 * | -----------------------
297 * | spawn_worker()
298 * V uct_playouts() */
300 /* Set in thread manager in case the workers should stop. */
301 volatile sig_atomic_t uct_halt = 0;
302 /* ID of the running worker thread. */
303 __thread int thread_id = -1;
304 /* ID of the thread manager. */
305 static pthread_t thread_manager;
306 static bool thread_manager_running;
308 static pthread_mutex_t finish_mutex = PTHREAD_MUTEX_INITIALIZER;
309 static pthread_cond_t finish_cond = PTHREAD_COND_INITIALIZER;
310 static volatile int finish_thread;
311 static pthread_mutex_t finish_serializer = PTHREAD_MUTEX_INITIALIZER;
313 struct spawn_ctx {
314 int tid;
315 struct uct *u;
316 struct board *b;
317 enum stone color;
318 struct tree *t;
319 unsigned long seed;
320 int games;
323 static void *
324 spawn_worker(void *ctx_)
326 struct spawn_ctx *ctx = ctx_;
327 /* Setup */
328 fast_srandom(ctx->seed);
329 thread_id = ctx->tid;
330 /* Run */
331 ctx->games = uct_playouts(ctx->u, ctx->b, ctx->color, ctx->t);
332 /* Finish */
333 pthread_mutex_lock(&finish_serializer);
334 pthread_mutex_lock(&finish_mutex);
335 finish_thread = ctx->tid;
336 pthread_cond_signal(&finish_cond);
337 pthread_mutex_unlock(&finish_mutex);
338 return ctx;
341 /* Thread manager, controlling worker threads. It must be called with
342 * finish_mutex lock held, but it will unlock it itself before exiting;
343 * this is necessary to be completely deadlock-free. */
344 /* The finish_cond can be signalled for it to stop; in that case,
345 * the caller should set finish_thread = -1. */
346 /* After it is started, it will update mctx->t to point at some tree
347 * used for the actual search (matters only for TM_ROOT), on return
348 * it will set mctx->games to the number of performed simulations. */
349 static void *
350 spawn_thread_manager(void *ctx_)
352 /* In thread_manager, we use only some of the ctx fields. */
353 struct spawn_ctx *mctx = ctx_;
354 struct uct *u = mctx->u;
355 struct tree *t = mctx->t;
356 bool shared_tree = u->parallel_tree;
357 fast_srandom(mctx->seed);
359 int played_games = 0;
360 pthread_t threads[u->threads];
361 int joined = 0;
363 uct_halt = 0;
365 /* Garbage collect the tree by preference when pondering. */
366 if (u->pondering && t->nodes && t->nodes_size > t->max_tree_size/2) {
367 unsigned long temp_size = (MIN_FREE_MEM_PERCENT * t->max_tree_size) / 100;
368 t->root = tree_garbage_collect(t, temp_size, t->root);
371 /* Spawn threads... */
372 for (int ti = 0; ti < u->threads; ti++) {
373 struct spawn_ctx *ctx = malloc(sizeof(*ctx));
374 ctx->u = u; ctx->b = mctx->b; ctx->color = mctx->color;
375 mctx->t = ctx->t = shared_tree ? t : tree_copy(t);
376 ctx->tid = ti; ctx->seed = fast_random(65536) + ti;
377 pthread_create(&threads[ti], NULL, spawn_worker, ctx);
378 if (UDEBUGL(3))
379 fprintf(stderr, "Spawned worker %d\n", ti);
382 /* ...and collect them back: */
383 while (joined < u->threads) {
384 /* Wait for some thread to finish... */
385 pthread_cond_wait(&finish_cond, &finish_mutex);
386 if (finish_thread < 0) {
387 /* Stop-by-caller. Tell the workers to wrap up. */
388 uct_halt = 1;
389 continue;
391 /* ...and gather its remnants. */
392 struct spawn_ctx *ctx;
393 pthread_join(threads[finish_thread], (void **) &ctx);
394 played_games += ctx->games;
395 joined++;
396 if (!shared_tree) {
397 if (ctx->t == mctx->t) mctx->t = t;
398 tree_merge(t, ctx->t);
399 tree_done(ctx->t);
401 free(ctx);
402 if (UDEBUGL(3))
403 fprintf(stderr, "Joined worker %d\n", finish_thread);
404 pthread_mutex_unlock(&finish_serializer);
407 pthread_mutex_unlock(&finish_mutex);
409 if (!shared_tree)
410 tree_normalize(mctx->t, u->threads);
412 mctx->games = played_games;
413 return mctx;
416 static struct spawn_ctx *
417 uct_search_start(struct uct *u, struct board *b, enum stone color, struct tree *t)
419 assert(u->threads > 0);
420 assert(!thread_manager_running);
422 struct spawn_ctx ctx = { .u = u, .b = b, .color = color, .t = t, .seed = fast_random(65536) };
423 static struct spawn_ctx mctx; mctx = ctx;
424 pthread_mutex_lock(&finish_mutex);
425 pthread_create(&thread_manager, NULL, spawn_thread_manager, &mctx);
426 thread_manager_running = true;
427 return &mctx;
430 static struct spawn_ctx *
431 uct_search_stop(void)
433 assert(thread_manager_running);
435 /* Signal thread manager to stop the workers. */
436 pthread_mutex_lock(&finish_mutex);
437 finish_thread = -1;
438 pthread_cond_signal(&finish_cond);
439 pthread_mutex_unlock(&finish_mutex);
441 /* Collect the thread manager. */
442 struct spawn_ctx *pctx;
443 thread_manager_running = false;
444 pthread_join(thread_manager, (void **) &pctx);
445 return pctx;
449 /* Determine whether we should terminate the search early. */
450 static bool
451 uct_search_stop_early(struct uct *u, struct tree *t, struct board *b,
452 struct time_info *ti, struct time_stop *stop,
453 struct tree_node *best, struct tree_node *best2,
454 int base_playouts, int i)
456 /* Always use at least half the desired time. It is silly
457 * to lose a won game because we played a bad move in 0.1s. */
458 double elapsed = 0;
459 if (ti->dim == TD_WALLTIME) {
460 elapsed = time_now() - ti->len.t.timer_start;
461 if (elapsed < 0.5 * stop->desired.time) return false;
464 /* Early break in won situation. */
465 if (best->u.playouts >= 2000 && tree_node_get_value(t, 1, best->u.value) >= u->loss_threshold)
466 return true;
467 /* Earlier break in super-won situation. */
468 if (best->u.playouts >= 500 && tree_node_get_value(t, 1, best->u.value) >= 0.95)
469 return true;
471 /* Break early if we estimate the second-best move cannot
472 * catch up in assigned time anymore. We use all our time
473 * if we are in byoyomi with single stone remaining in our
474 * period, however - it's better to pre-ponder. */
475 bool time_indulgent = (!ti->len.t.main_time && ti->len.t.byoyomi_stones == 1);
476 if (best2 && ti->dim == TD_WALLTIME && !time_indulgent) {
477 double remaining = stop->worst.time - elapsed;
478 double pps = ((double)i - base_playouts) / elapsed;
479 double estplayouts = remaining * pps + PLAYOUT_DELTA_SAFEMARGIN;
480 if (best->u.playouts > best2->u.playouts + estplayouts) {
481 if (UDEBUGL(2))
482 fprintf(stderr, "Early stop, result cannot change: "
483 "best %d, best2 %d, estimated %f simulations to go\n",
484 best->u.playouts, best2->u.playouts, estplayouts);
485 return true;
489 return false;
492 /* Determine whether we should terminate the search later. */
493 static bool
494 uct_search_keep_looking(struct uct *u, struct tree *t, struct board *b,
495 struct time_info *ti, struct time_stop *stop,
496 struct tree_node *best, struct tree_node *best2,
497 struct tree_node *bestr, struct tree_node *winner, int i)
499 if (!best) {
500 if (UDEBUGL(2))
501 fprintf(stderr, "Did not find best move, still trying...\n");
502 return true;
505 /* Do not waste time if we are winning. Spend up to worst time if
506 * we are unsure, but only desired time if we are sure of winning. */
507 float beta = 2 * (tree_node_get_value(t, 1, best->u.value) - 0.5);
508 if (ti->dim == TD_WALLTIME && beta > 0) {
509 double good_enough = stop->desired.time * beta + stop->worst.time * (1 - beta);
510 double elapsed = time_now() - ti->len.t.timer_start;
511 if (elapsed > good_enough) return false;
514 if (u->best2_ratio > 0) {
515 /* Check best/best2 simulations ratio. If the
516 * two best moves give very similar results,
517 * keep simulating. */
518 if (best2 && best2->u.playouts
519 && (double)best->u.playouts / best2->u.playouts < u->best2_ratio) {
520 if (UDEBUGL(2))
521 fprintf(stderr, "Best2 ratio %f < threshold %f\n",
522 (double)best->u.playouts / best2->u.playouts,
523 u->best2_ratio);
524 return true;
528 if (u->bestr_ratio > 0) {
529 /* Check best, best_best value difference. If the best move
530 * and its best child do not give similar enough results,
531 * keep simulating. */
532 if (bestr && bestr->u.playouts
533 && fabs((double)best->u.value - bestr->u.value) > u->bestr_ratio) {
534 if (UDEBUGL(2))
535 fprintf(stderr, "Bestr delta %f > threshold %f\n",
536 fabs((double)best->u.value - bestr->u.value),
537 u->bestr_ratio);
538 return true;
542 if (winner && winner != best) {
543 /* Keep simulating if best explored
544 * does not have also highest value. */
545 if (UDEBUGL(2))
546 fprintf(stderr, "[%d] best %3s [%d] %f != winner %3s [%d] %f\n", i,
547 coord2sstr(best->coord, t->board),
548 best->u.playouts, tree_node_get_value(t, 1, best->u.value),
549 coord2sstr(winner->coord, t->board),
550 winner->u.playouts, tree_node_get_value(t, 1, winner->u.value));
551 return true;
554 /* No reason to keep simulating, bye. */
555 return false;
558 /* Run time-limited MCTS search on foreground. */
559 static int
560 uct_search(struct uct *u, struct board *b, struct time_info *ti, enum stone color, struct tree *t)
562 int base_playouts = u->t->root->u.playouts;
563 if (UDEBUGL(2) && base_playouts > 0)
564 fprintf(stderr, "<pre-simulated %d games skipped>\n", base_playouts);
566 /* Set up time conditions. */
567 if (ti->period == TT_NULL) *ti = default_ti;
568 struct time_stop stop;
569 time_stop_conditions(ti, b, u->fuseki_end, u->yose_start, &stop);
571 /* Number of last dynkomi adjustment. */
572 int last_dynkomi = t->root->u.playouts;
573 /* Number of last game with progress print. */
574 int last_print = t->root->u.playouts;
575 /* Number of simulations to wait before next print. */
576 int print_interval = TREE_SIMPROGRESS_INTERVAL * (u->thread_model == TM_ROOT ? 1 : u->threads);
577 /* Printed notification about full memory? */
578 bool print_fullmem = false;
580 struct spawn_ctx *ctx = uct_search_start(u, b, color, t);
582 /* The search tree is ctx->t. This is normally == t, but in case of
583 * TM_ROOT, it is one of the trees belonging to the independent
584 * workers. It is important to reference ctx->t directly since the
585 * thread manager will swap the tree pointer asynchronously. */
586 /* XXX: This means TM_ROOT support is suboptimal since single stalled
587 * thread can stall the others in case of limiting the search by game
588 * count. However, TM_ROOT just does not deserve any more extra code
589 * right now. */
591 struct tree_node *best = NULL;
592 struct tree_node *best2 = NULL; // Second-best move.
593 struct tree_node *bestr = NULL; // best's best child.
594 struct tree_node *winner = NULL;
596 double busywait_interval = TREE_BUSYWAIT_INTERVAL;
598 /* Now, just periodically poll the search tree. */
599 while (1) {
600 time_sleep(busywait_interval);
601 /* busywait_interval should never be less than desired time, or the
602 * time control is broken. But if it happens to be less, we still search
603 * at least 100ms otherwise the move is completely random. */
605 int i = ctx->t->root->u.playouts;
607 /* Adjust dynkomi? */
608 if (ctx->t->use_extra_komi && u->dynkomi->permove
609 && u->dynkomi_interval
610 && i > last_dynkomi + u->dynkomi_interval) {
611 float old_dynkomi = ctx->t->extra_komi;
612 ctx->t->extra_komi = u->dynkomi->permove(u->dynkomi, b, ctx->t);
613 if (UDEBUGL(3) && old_dynkomi != ctx->t->extra_komi)
614 fprintf(stderr, "dynkomi adjusted (%f -> %f)\n", old_dynkomi, ctx->t->extra_komi);
617 /* Print progress? */
618 if (i - last_print > print_interval) {
619 last_print += print_interval; // keep the numbers tidy
620 uct_progress_status(u, ctx->t, color, last_print);
622 if (!print_fullmem && ctx->t->nodes_size > u->max_tree_size) {
623 if (UDEBUGL(2))
624 fprintf(stderr, "memory limit hit (%lu > %lu)\n", ctx->t->nodes_size, u->max_tree_size);
625 print_fullmem = true;
628 /* Never consider stopping if we played too few simulations.
629 * Maybe we risk losing on time when playing in super-extreme
630 * time pressure but the tree is going to be just too messed
631 * up otherwise - we might even play invalid suicides or pass
632 * when we mustn't. */
633 if (i < GJ_MINGAMES)
634 continue;
636 best = u->policy->choose(u->policy, ctx->t->root, b, color, resign);
637 if (best) best2 = u->policy->choose(u->policy, ctx->t->root, b, color, best->coord);
639 /* Possibly stop search early if it's no use to try on. */
640 if (best && uct_search_stop_early(u, ctx->t, b, ti, &stop, best, best2, base_playouts, i))
641 break;
643 /* Check against time settings. */
644 bool desired_done = false;
645 if (ti->dim == TD_WALLTIME) {
646 double elapsed = time_now() - ti->len.t.timer_start;
647 if (elapsed > stop.worst.time) break;
648 desired_done = elapsed > stop.desired.time;
650 } else { assert(ti->dim == TD_GAMES);
651 if (i > stop.worst.playouts) break;
652 desired_done = i > stop.desired.playouts;
655 /* We want to stop simulating, but are willing to keep trying
656 * if we aren't completely sure about the winner yet. */
657 if (desired_done) {
658 if (u->policy->winner && u->policy->evaluate) {
659 struct uct_descent descent = { .node = ctx->t->root };
660 u->policy->winner(u->policy, ctx->t, &descent);
661 winner = descent.node;
663 if (best)
664 bestr = u->policy->choose(u->policy, best, b, stone_other(color), resign);
665 if (!uct_search_keep_looking(u, ctx->t, b, ti, &stop, best, best2, bestr, winner, i))
666 break;
669 /* TODO: Early break if best->variance goes under threshold and we already
670 * have enough playouts (possibly thanks to book or to pondering)? */
673 ctx = uct_search_stop();
675 if (UDEBUGL(2))
676 tree_dump(t, u->dumpthres);
677 if (UDEBUGL(0))
678 uct_progress_status(u, t, color, ctx->games);
680 return ctx->games;
684 /* Start pondering background with @color to play. */
685 static void
686 uct_pondering_start(struct uct *u, struct board *b0, struct tree *t, enum stone color)
688 if (UDEBUGL(1))
689 fprintf(stderr, "Starting to ponder with color %s\n", stone2str(stone_other(color)));
690 u->pondering = true;
692 /* We need a local board copy to ponder upon. */
693 struct board *b = malloc(sizeof(*b)); board_copy(b, b0);
695 /* *b0 did not have the genmove'd move played yet. */
696 struct move m = { t->root->coord, t->root_color };
697 int res = board_play(b, &m);
698 assert(res >= 0);
699 setup_dynkomi(u, b, stone_other(m.color));
701 /* Start MCTS manager thread "headless". */
702 uct_search_start(u, b, color, t);
705 /* uct_search_stop() frontend for the pondering (non-genmove) mode. */
706 static void
707 uct_pondering_stop(struct uct *u)
709 u->pondering = false;
710 if (!thread_manager_running)
711 return;
713 /* Stop the thread manager. */
714 struct spawn_ctx *ctx = uct_search_stop();
715 if (UDEBUGL(1)) {
716 fprintf(stderr, "(pondering) ");
717 uct_progress_status(u, ctx->t, ctx->color, ctx->games);
719 free(ctx->b);
723 static coord_t *
724 uct_genmove(struct engine *e, struct board *b, struct time_info *ti, enum stone color, bool pass_all_alive)
726 double start_time = time_now();
727 struct uct *u = e->data;
729 if (b->superko_violation) {
730 fprintf(stderr, "!!! WARNING: SUPERKO VIOLATION OCCURED BEFORE THIS MOVE\n");
731 fprintf(stderr, "Maybe you play with situational instead of positional superko?\n");
732 fprintf(stderr, "I'm going to ignore the violation, but note that I may miss\n");
733 fprintf(stderr, "some moves valid under this ruleset because of this.\n");
734 b->superko_violation = false;
737 /* Seed the tree. */
738 uct_pondering_stop(u);
739 prepare_move(e, b, color);
740 assert(u->t);
742 /* How to decide whether to use dynkomi in this game? Since we use
743 * pondering, it's not simple "who-to-play" matter. Decide based on
744 * the last genmove issued. */
745 u->t->use_extra_komi = !!(u->dynkomi_mask & color);
746 setup_dynkomi(u, b, color);
748 /* Make pessimistic assumption about komi for Japanese rules to
749 * avoid losing by 0.5 when winning by 0.5 with Chinese rules.
750 * The rules usually give the same winner if the integer part of komi
751 * is odd so we adjust the komi only if it is even (for a board of
752 * odd size). We are not trying to get an exact evaluation for rare
753 * cases of seki. For details see http://home.snafu.de/jasiek/parity.html
754 * TODO: Support the kgs-rules command once available. */
755 if (u->territory_scoring && (((int)floor(b->komi) + board_size(b)) & 1)) {
756 b->komi += (color == S_BLACK ? 1.0 : -1.0);
757 if (UDEBUGL(0))
758 fprintf(stderr, "Setting komi to %.1f assuming Japanese rules\n",
759 b->komi);
762 int base_playouts = u->t->root->u.playouts;
763 /* Perform the Monte Carlo Tree Search! */
764 int played_games = uct_search(u, b, ti, color, u->t);
766 /* Choose the best move from the tree. */
767 struct tree_node *best = u->policy->choose(u->policy, u->t->root, b, color, resign);
768 if (!best) {
769 reset_state(u);
770 return coord_copy(pass);
772 if (UDEBUGL(1))
773 fprintf(stderr, "*** WINNER is %s (%d,%d) with score %1.4f (%d/%d:%d/%d games), extra komi %f\n",
774 coord2sstr(best->coord, b), coord_x(best->coord, b), coord_y(best->coord, b),
775 tree_node_get_value(u->t, 1, best->u.value), best->u.playouts,
776 u->t->root->u.playouts, u->t->root->u.playouts - base_playouts, played_games,
777 u->t->extra_komi);
779 /* Do not resign if we're so short of time that evaluation of best
780 * move is completely unreliable, we might be winning actually.
781 * In this case best is almost random but still better than resign.
782 * Also do not resign if we are getting bad results while actually
783 * giving away extra komi points (dynkomi). */
784 if (tree_node_get_value(u->t, 1, best->u.value) < u->resign_ratio
785 && !is_pass(best->coord) && best->u.playouts > GJ_MINGAMES
786 && u->t->extra_komi <= 1 /* XXX we assume dynamic komi == we are black */) {
787 reset_state(u);
788 return coord_copy(resign);
791 /* If the opponent just passed and we win counting, always
792 * pass as well. */
793 if (b->moves > 1 && is_pass(b->last_move.coord)) {
794 /* Make sure enough playouts are simulated. */
795 while (u->ownermap.playouts < GJ_MINGAMES)
796 uct_playout(u, b, color, u->t);
797 if (uct_pass_is_safe(u, b, color, u->pass_all_alive || pass_all_alive)) {
798 if (UDEBUGL(0))
799 fprintf(stderr, "<Will rather pass, looks safe enough.>\n");
800 best->coord = pass;
804 tree_promote_node(u->t, &best);
805 /* After a pass, pondering is harmful for two reasons:
806 * (i) We might keep pondering even when the game is over.
807 * Of course this is the case for opponent resign as well.
808 * (ii) More importantly, the ownermap will get skewed since
809 * the UCT will start cutting off any playouts. */
810 if (u->pondering_opt && !is_pass(best->coord)) {
811 uct_pondering_start(u, b, u->t, stone_other(color));
813 if (UDEBUGL(2)) {
814 double time = time_now() - start_time + 0.000001; /* avoid divide by zero */
815 fprintf(stderr, "genmove in %0.2fs (%d games/s, %d games/s/thread)\n",
816 time, (int)(played_games/time), (int)(played_games/time/u->threads));
818 return coord_copy(best->coord);
822 bool
823 uct_genbook(struct engine *e, struct board *b, struct time_info *ti, enum stone color)
825 struct uct *u = e->data;
826 if (!u->t) prepare_move(e, b, color);
827 assert(u->t);
829 if (ti->dim == TD_GAMES) {
830 /* Don't count in games that already went into the book. */
831 ti->len.games += u->t->root->u.playouts;
833 uct_search(u, b, ti, color, u->t);
835 assert(ti->dim == TD_GAMES);
836 tree_save(u->t, b, ti->len.games / 100);
838 return true;
841 void
842 uct_dumpbook(struct engine *e, struct board *b, enum stone color)
844 struct uct *u = e->data;
845 struct tree *t = tree_init(b, color, u->fast_alloc ? u->max_tree_size : 0, u->local_tree_aging);
846 tree_load(t, b);
847 tree_dump(t, 0);
848 tree_done(t);
852 struct uct *
853 uct_state_init(char *arg, struct board *b)
855 struct uct *u = calloc(1, sizeof(struct uct));
856 bool using_elo = false;
858 u->debug_level = debug_level;
859 u->gamelen = MC_GAMELEN;
860 u->mercymin = 0;
861 u->expand_p = 2;
862 u->dumpthres = 1000;
863 u->playout_amaf = true;
864 u->playout_amaf_nakade = false;
865 u->amaf_prior = false;
866 u->max_tree_size = 3072ULL * 1048576;
868 u->dynkomi_mask = S_BLACK;
870 u->threads = 1;
871 u->thread_model = TM_TREEVL;
872 u->parallel_tree = true;
873 u->virtual_loss = true;
875 u->fuseki_end = 20; // max time at 361*20% = 72 moves (our 36th move, still 99 to play)
876 u->yose_start = 40; // (100-40-25)*361/100/2 = 63 moves still to play by us then
877 u->bestr_ratio = 0.02;
878 // 2.5 is clearly too much, but seems to compensate well for overly stern time allocations.
879 // TODO: Further tuning and experiments with better time allocation schemes.
880 u->best2_ratio = 2.5;
882 u->val_scale = 0.04; u->val_points = 40;
884 u->tenuki_d = 4;
885 u->local_tree_aging = 2;
887 if (arg) {
888 char *optspec, *next = arg;
889 while (*next) {
890 optspec = next;
891 next += strcspn(next, ",");
892 if (*next) { *next++ = 0; } else { *next = 0; }
894 char *optname = optspec;
895 char *optval = strchr(optspec, '=');
896 if (optval) *optval++ = 0;
898 if (!strcasecmp(optname, "debug")) {
899 if (optval)
900 u->debug_level = atoi(optval);
901 else
902 u->debug_level++;
903 } else if (!strcasecmp(optname, "mercy") && optval) {
904 /* Minimal difference of black/white captures
905 * to stop playout - "Mercy Rule". Speeds up
906 * hopeless playouts at the expense of some
907 * accuracy. */
908 u->mercymin = atoi(optval);
909 } else if (!strcasecmp(optname, "gamelen") && optval) {
910 u->gamelen = atoi(optval);
911 } else if (!strcasecmp(optname, "expand_p") && optval) {
912 u->expand_p = atoi(optval);
913 } else if (!strcasecmp(optname, "dumpthres") && optval) {
914 u->dumpthres = atoi(optval);
915 } else if (!strcasecmp(optname, "best2_ratio") && optval) {
916 /* If set, prolong simulating while
917 * first_best/second_best playouts ratio
918 * is less than best2_ratio. */
919 u->best2_ratio = atof(optval);
920 } else if (!strcasecmp(optname, "bestr_ratio") && optval) {
921 /* If set, prolong simulating while
922 * best,best_best_child values delta
923 * is more than bestr_ratio. */
924 u->bestr_ratio = atof(optval);
925 } else if (!strcasecmp(optname, "playout_amaf")) {
926 /* Whether to include random playout moves in
927 * AMAF as well. (Otherwise, only tree moves
928 * are included in AMAF. Of course makes sense
929 * only in connection with an AMAF policy.) */
930 /* with-without: 55.5% (+-4.1) */
931 if (optval && *optval == '0')
932 u->playout_amaf = false;
933 else
934 u->playout_amaf = true;
935 } else if (!strcasecmp(optname, "playout_amaf_nakade")) {
936 /* Whether to include nakade moves from playouts
937 * in the AMAF statistics; this tends to nullify
938 * the playout_amaf effect by adding too much
939 * noise. */
940 if (optval && *optval == '0')
941 u->playout_amaf_nakade = false;
942 else
943 u->playout_amaf_nakade = true;
944 } else if (!strcasecmp(optname, "playout_amaf_cutoff") && optval) {
945 /* Keep only first N% of playout stage AMAF
946 * information. */
947 u->playout_amaf_cutoff = atoi(optval);
948 } else if ((!strcasecmp(optname, "policy") || !strcasecmp(optname, "random_policy")) && optval) {
949 char *policyarg = strchr(optval, ':');
950 struct uct_policy **p = !strcasecmp(optname, "policy") ? &u->policy : &u->random_policy;
951 if (policyarg)
952 *policyarg++ = 0;
953 if (!strcasecmp(optval, "ucb1")) {
954 *p = policy_ucb1_init(u, policyarg);
955 } else if (!strcasecmp(optval, "ucb1amaf")) {
956 *p = policy_ucb1amaf_init(u, policyarg);
957 } else {
958 fprintf(stderr, "UCT: Invalid tree policy %s\n", optval);
959 exit(1);
961 } else if (!strcasecmp(optname, "playout") && optval) {
962 char *playoutarg = strchr(optval, ':');
963 if (playoutarg)
964 *playoutarg++ = 0;
965 if (!strcasecmp(optval, "moggy")) {
966 u->playout = playout_moggy_init(playoutarg, b);
967 } else if (!strcasecmp(optval, "light")) {
968 u->playout = playout_light_init(playoutarg, b);
969 } else if (!strcasecmp(optval, "elo")) {
970 u->playout = playout_elo_init(playoutarg, b);
971 using_elo = true;
972 } else {
973 fprintf(stderr, "UCT: Invalid playout policy %s\n", optval);
974 exit(1);
976 } else if (!strcasecmp(optname, "prior") && optval) {
977 u->prior = uct_prior_init(optval, b);
978 } else if (!strcasecmp(optname, "amaf_prior") && optval) {
979 u->amaf_prior = atoi(optval);
980 } else if (!strcasecmp(optname, "threads") && optval) {
981 /* By default, Pachi will run with only single
982 * tree search thread! */
983 u->threads = atoi(optval);
984 } else if (!strcasecmp(optname, "thread_model") && optval) {
985 if (!strcasecmp(optval, "root")) {
986 /* Root parallelization - each thread
987 * does independent search, trees are
988 * merged at the end. */
989 u->thread_model = TM_ROOT;
990 u->parallel_tree = false;
991 u->virtual_loss = false;
992 } else if (!strcasecmp(optval, "tree")) {
993 /* Tree parallelization - all threads
994 * grind on the same tree. */
995 u->thread_model = TM_TREE;
996 u->parallel_tree = true;
997 u->virtual_loss = false;
998 } else if (!strcasecmp(optval, "treevl")) {
999 /* Tree parallelization, but also
1000 * with virtual losses - this discou-
1001 * rages most threads choosing the
1002 * same tree branches to read. */
1003 u->thread_model = TM_TREEVL;
1004 u->parallel_tree = true;
1005 u->virtual_loss = true;
1006 } else {
1007 fprintf(stderr, "UCT: Invalid thread model %s\n", optval);
1008 exit(1);
1010 } else if (!strcasecmp(optname, "pondering")) {
1011 /* Keep searching even during opponent's turn. */
1012 u->pondering_opt = !optval || atoi(optval);
1013 } else if (!strcasecmp(optname, "fuseki_end") && optval) {
1014 /* At the very beginning it's not worth thinking
1015 * too long because the playout evaluations are
1016 * very noisy. So gradually increase the thinking
1017 * time up to maximum when fuseki_end percent
1018 * of the board has been played.
1019 * This only applies if we are not in byoyomi. */
1020 u->fuseki_end = atoi(optval);
1021 } else if (!strcasecmp(optname, "yose_start") && optval) {
1022 /* When yose_start percent of the board has been
1023 * played, or if we are in byoyomi, stop spending
1024 * more time and spread the remaining time
1025 * uniformly.
1026 * Between fuseki_end and yose_start, we spend
1027 * a constant proportion of the remaining time
1028 * on each move. (yose_start should actually
1029 * be much earlier than when real yose start,
1030 * but "yose" is a good short name to convey
1031 * the idea.) */
1032 u->yose_start = atoi(optval);
1033 } else if (!strcasecmp(optname, "force_seed") && optval) {
1034 u->force_seed = atoi(optval);
1035 } else if (!strcasecmp(optname, "no_book")) {
1036 u->no_book = true;
1037 } else if (!strcasecmp(optname, "dynkomi") && optval) {
1038 /* Dynamic komi approach; there are multiple
1039 * ways to adjust komi dynamically throughout
1040 * play. We currently support two: */
1041 char *dynkomiarg = strchr(optval, ':');
1042 if (dynkomiarg)
1043 *dynkomiarg++ = 0;
1044 if (!strcasecmp(optval, "none")) {
1045 u->dynkomi = uct_dynkomi_init_none(u, dynkomiarg, b);
1046 } else if (!strcasecmp(optval, "linear")) {
1047 u->dynkomi = uct_dynkomi_init_linear(u, dynkomiarg, b);
1048 } else if (!strcasecmp(optval, "adaptive")) {
1049 u->dynkomi = uct_dynkomi_init_adaptive(u, dynkomiarg, b);
1050 } else {
1051 fprintf(stderr, "UCT: Invalid dynkomi mode %s\n", optval);
1052 exit(1);
1054 } else if (!strcasecmp(optname, "dynkomi_mask") && optval) {
1055 /* Bitmask of colors the player must be
1056 * for dynkomi be applied; you may want
1057 * to use dynkomi_mask=3 to allow dynkomi
1058 * even in games where Pachi is white. */
1059 u->dynkomi_mask = atoi(optval);
1060 } else if (!strcasecmp(optname, "dynkomi_interval") && optval) {
1061 /* If non-zero, re-adjust dynamic komi
1062 * throughout a single genmove reading,
1063 * roughly every N simulations. */
1064 u->dynkomi_interval = atoi(optval);
1065 } else if (!strcasecmp(optname, "val_scale") && optval) {
1066 /* How much of the game result value should be
1067 * influenced by win size. Zero means it isn't. */
1068 u->val_scale = atof(optval);
1069 } else if (!strcasecmp(optname, "val_points") && optval) {
1070 /* Maximum size of win to be scaled into game
1071 * result value. Zero means boardsize^2. */
1072 u->val_points = atoi(optval) * 2; // result values are doubled
1073 } else if (!strcasecmp(optname, "val_extra")) {
1074 /* If false, the score coefficient will be simply
1075 * added to the value, instead of scaling the result
1076 * coefficient because of it. */
1077 u->val_extra = !optval || atoi(optval);
1078 } else if (!strcasecmp(optname, "local_tree") && optval) {
1079 /* Whether to bias exploration by local tree values
1080 * (must be supported by the used policy).
1081 * 0: Don't.
1082 * 1: Do, value = result.
1083 * Try to temper the result:
1084 * 2: Do, value = 0.5+(result-expected)/2.
1085 * 3: Do, value = 0.5+bzz((result-expected)^2).
1086 * 4: Do, value = 0.5+sqrt(result-expected)/2. */
1087 u->local_tree = atoi(optval);
1088 } else if (!strcasecmp(optname, "tenuki_d") && optval) {
1089 /* Tenuki distance at which to break the local tree. */
1090 u->tenuki_d = atoi(optval);
1091 if (u->tenuki_d > TREE_NODE_D_MAX + 1) {
1092 fprintf(stderr, "uct: tenuki_d must not be larger than TREE_NODE_D_MAX+1 %d\n", TREE_NODE_D_MAX + 1);
1093 exit(1);
1095 } else if (!strcasecmp(optname, "local_tree_aging") && optval) {
1096 /* How much to reduce local tree values between moves. */
1097 u->local_tree_aging = atof(optval);
1098 } else if (!strcasecmp(optname, "local_tree_allseq")) {
1099 /* By default, only complete sequences are stored
1100 * in the local tree. If this is on, also
1101 * subsequences starting at each move are stored. */
1102 u->local_tree_allseq = !optval || atoi(optval);
1103 } else if (!strcasecmp(optname, "local_tree_playout")) {
1104 /* Whether to adjust ELO playout probability
1105 * distributions according to matched localtree
1106 * information. */
1107 u->local_tree_playout = !optval || atoi(optval);
1108 } else if (!strcasecmp(optname, "local_tree_pseqroot")) {
1109 /* By default, when we have no sequence move
1110 * to suggest in-playout, we give up. If this
1111 * is on, we make probability distribution from
1112 * sequences first moves instead. */
1113 u->local_tree_pseqroot = !optval || atoi(optval);
1114 } else if (!strcasecmp(optname, "pass_all_alive")) {
1115 /* Whether to consider all stones alive at the game
1116 * end instead of marking dead groupd. */
1117 u->pass_all_alive = !optval || atoi(optval);
1118 } else if (!strcasecmp(optname, "territory_scoring")) {
1119 /* Use territory scoring (default is area scoring).
1120 * An explicit kgs-rules command overrides this. */
1121 u->territory_scoring = !optval || atoi(optval);
1122 } else if (!strcasecmp(optname, "random_policy_chance") && optval) {
1123 /* If specified (N), with probability 1/N, random_policy policy
1124 * descend is used instead of main policy descend; useful
1125 * if specified policy (e.g. UCB1AMAF) can make unduly biased
1126 * choices sometimes, you can fall back to e.g.
1127 * random_policy=UCB1. */
1128 u->random_policy_chance = atoi(optval);
1129 } else if (!strcasecmp(optname, "max_tree_size") && optval) {
1130 /* Maximum amount of memory [MiB] consumed by the move tree.
1131 * For fast_alloc it includes the temp tree used for pruning.
1132 * Default is 3072 (3 GiB). Note that if you use TM_ROOT,
1133 * this limits size of only one of the trees, not all of them
1134 * together. */
1135 u->max_tree_size = atol(optval) * 1048576;
1136 } else if (!strcasecmp(optname, "fast_alloc")) {
1137 u->fast_alloc = !optval || atoi(optval);
1138 } else if (!strcasecmp(optname, "banner") && optval) {
1139 /* Additional banner string. This must come as the
1140 * last engine parameter. */
1141 if (*next) *--next = ',';
1142 u->banner = strdup(optval);
1143 break;
1144 } else {
1145 fprintf(stderr, "uct: Invalid engine argument %s or missing value\n", optname);
1146 exit(1);
1151 u->resign_ratio = 0.2; /* Resign when most games are lost. */
1152 u->loss_threshold = 0.85; /* Stop reading if after at least 2000 playouts this is best value. */
1153 if (!u->policy)
1154 u->policy = policy_ucb1amaf_init(u, NULL);
1156 if (!!u->random_policy_chance ^ !!u->random_policy) {
1157 fprintf(stderr, "uct: Only one of random_policy and random_policy_chance is set\n");
1158 exit(1);
1161 if (!u->local_tree) {
1162 /* No ltree aging. */
1163 u->local_tree_aging = 1.0f;
1165 if (!using_elo)
1166 u->local_tree_playout = false;
1168 if (u->fast_alloc && !u->parallel_tree) {
1169 fprintf(stderr, "fast_alloc not supported with root parallelization.\n");
1170 exit(1);
1172 if (u->fast_alloc)
1173 u->max_tree_size = (100ULL * u->max_tree_size) / (100 + MIN_FREE_MEM_PERCENT);
1175 if (!u->prior)
1176 u->prior = uct_prior_init(NULL, b);
1178 if (!u->playout)
1179 u->playout = playout_moggy_init(NULL, b);
1180 u->playout->debug_level = u->debug_level;
1182 u->ownermap.map = malloc(board_size2(b) * sizeof(u->ownermap.map[0]));
1184 if (!u->dynkomi)
1185 u->dynkomi = uct_dynkomi_init_linear(u, NULL, b);
1187 /* Some things remain uninitialized for now - the opening book
1188 * is not loaded and the tree not set up. */
1189 /* This will be initialized in setup_state() at the first move
1190 * received/requested. This is because right now we are not aware
1191 * about any komi or handicap setup and such. */
1193 return u;
1196 struct engine *
1197 engine_uct_init(char *arg, struct board *b)
1199 struct uct *u = uct_state_init(arg, b);
1200 struct engine *e = calloc(1, sizeof(struct engine));
1201 e->name = "UCT Engine";
1202 e->printhook = uct_printhook_ownermap;
1203 e->notify_play = uct_notify_play;
1204 e->chat = uct_chat;
1205 e->genmove = uct_genmove;
1206 e->dead_group_list = uct_dead_group_list;
1207 e->done = uct_done;
1208 e->data = u;
1210 const char banner[] = "I'm playing UCT. When I'm losing, I will resign, "
1211 "if I think I win, I play until you pass. "
1212 "Anyone can send me 'winrate' in private chat to get my assessment of the position.";
1213 if (!u->banner) u->banner = "";
1214 e->comment = malloc(sizeof(banner) + strlen(u->banner) + 1);
1215 sprintf(e->comment, "%s %s", banner, u->banner);
1217 return e;