uct/search.c

   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>
   9
  10 #define DEBUG
  11
  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"
  23
  24
  25 /* Default time settings for the UCT engine. */
  26 static struct time_info default_ti;
  27 static __attribute__((constructor)) void
  28 default_ti_init(void)
  29 {
  30         time_parse(&default_ti, "15");
  31 }
  32
  33 /* When terminating UCT search early, the safety margin to add to the
  34  * remaining playout number estimate when deciding whether the result can
  35  * still change. */
  36 #define PLAYOUT_DELTA_SAFEMARGIN 1000
  37
  38 /* Minimal number of simulations to consider early break. */
  39 #define PLAYOUT_EARLY_BREAK_MIN 5000
  40
  41 /* Minimal time to consider early break (in seconds). */
  42 #define TIME_EARLY_BREAK_MIN 1.0
  43
  44
  45 /* Pachi threading structure:
  46  *
  47  * main thread
  48  *   |         main(), GTP communication, ...
  49  *   |         starts and stops the search managed by thread_manager
  50  *   |
  51  * thread_manager
  52  *   |         spawns and collects worker threads
  53  *   |
  54  * worker0
  55  * worker1
  56  * ...
  57  * workerK
  58  *             uct_playouts() loop, doing descend-playout until uct_halt
  59  *
  60  * Another way to look at it is by functions (lines denote thread boundaries):
  61  *
  62  * | uct_genmove()
  63  * | uct_search()            (uct_search_start() .. uct_search_stop())
  64  * | -----------------------
  65  * | spawn_thread_manager()
  66  * | -----------------------
  67  * | spawn_worker()
  68  * V uct_playouts() */
  69
  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;
  75
  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;
  80
  81 static void *
  82 spawn_worker(void *ctx_)
  83 {
  84         struct uct_thread_ctx *ctx = ctx_;
  85         /* Setup */
  86         fast_srandom(ctx->seed);
  87         /* Run */
  88         ctx->games = uct_playouts(ctx->u, ctx->b, ctx->color, ctx->t, ctx->ti);
  89         /* Finish */
  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);
  95         return ctx;
  96 }
  97
  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. */
 106 static void *
 107 spawn_thread_manager(void *ctx_)
 108 {
 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);
 114
 115         int played_games = 0;
 116         pthread_t threads[u->threads];
 117         int joined = 0;
 118
 119         uct_halt = 0;
 120
 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);
 124         }
 125
 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;
 132                 ctx->ti = mctx->ti;
 133                 pthread_attr_t a;
 134                 pthread_attr_init(&a);
 135                 pthread_attr_setstacksize(&a, 1048576);
 136                 pthread_create(&threads[ti], &a, spawn_worker, ctx);
 137                 if (UDEBUGL(3))
 138                         fprintf(stderr, "Spawned worker %d\n", ti);
 139         }
 140
 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. */
 148                         uct_halt = 1;
 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
 152                          * coalesced. */
 153                         pthread_mutex_unlock(&finish_serializer);
 154                         continue;
 155                 }
 156                 /* ...and gather its remnants. */
 157                 struct uct_thread_ctx *ctx;
 158                 pthread_join(threads[finish_thread], (void **) &ctx);
 159                 played_games += ctx->games;
 160                 joined++;
 161                 free(ctx);
 162                 if (UDEBUGL(3))
 163                         fprintf(stderr, "Joined worker %d\n", finish_thread);
 164                 pthread_mutex_unlock(&finish_serializer);
 165         }
 166
 167         pthread_mutex_unlock(&finish_mutex);
 168
 169         mctx->games = played_games;
 170         return mctx;
 171 }
 172
 173
 174 /*** THREAD MANAGER end */
 175
 176 /*** Search infrastructure: */
 177
 178
 179 int
 180 uct_search_games(struct uct_search_state *s)
 181 {
 182         return s->ctx->t->root->u.playouts;
 183 }
 184
 185 void
 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)
 189 {
 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;
 193         s->fullmem = false;
 194
 195         if (ti) {
 196                 if (ti->period == TT_NULL) {
 197                         *ti = default_ti;
 198                         time_start_timer(ti);
 199                 }
 200                 time_stop_conditions(ti, b, u->fuseki_end, u->yose_start, u->max_maintime_ratio, &s->stop);
 201         }
 202
 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 };
 209         s->ctx = &mctx;
 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;
 214 }
 215
 216 struct uct_thread_ctx *
 217 uct_search_stop(void)
 218 {
 219         assert(thread_manager_running);
 220
 221         /* Signal thread manager to stop the workers. */
 222         pthread_mutex_lock(&finish_mutex);
 223         finish_thread = -1;
 224         pthread_cond_signal(&finish_cond);
 225         pthread_mutex_unlock(&finish_mutex);
 226
 227         /* Collect the thread manager. */
 228         struct uct_thread_ctx *pctx;
 229         thread_manager_running = false;
 230         pthread_join(thread_manager, (void **) &pctx);
 231         return pctx;
 232 }
 233
 234
 235 void
 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)
 239 {
 240         struct uct_thread_ctx *ctx = s->ctx;
 241
 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);
 253         }
 254
 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);
 259         }
 260
 261         if (!s->fullmem && ctx->t->nodes_size > u->max_tree_size) {
 262                 if (UDEBUGL(2))
 263                         fprintf(stderr, "memory limit hit (%lu > %lu)\n",
 264                                 ctx->t->nodes_size, u->max_tree_size);
 265                 s->fullmem = true;
 266         }
 267 }
 268
 269
 270 /* Determine whether we should terminate the search early. */
 271 static bool
 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)
 276 {
 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
 283          * on the spot.) */
 284         if (fullmem)
 285                 return true;
 286
 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;
 293         }
 294
 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) {
 306                         if (UDEBUGL(2))
 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);
 310                         return true;
 311                 }
 312         }
 313
 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) {
 318                 return true;
 319         }
 320
 321         return false;
 322 }
 323
 324 /* Determine whether we should terminate the search later than expected. */
 325 static bool
 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)
 330 {
 331         if (!best) {
 332                 if (UDEBUGL(2))
 333                         fprintf(stderr, "Did not find best move, still trying...\n");
 334                 return true;
 335         }
 336
 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;
 344         }
 345
 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) {
 352                         if (UDEBUGL(2))
 353                                 fprintf(stderr, "Best2 ratio %f < threshold %f\n",
 354                                         (double)best->u.playouts / best2->u.playouts,
 355                                         u->best2_ratio);
 356                         return true;
 357                 }
 358         }
 359
 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) {
 366                         if (UDEBUGL(2))
 367                                 fprintf(stderr, "Bestr delta %f > threshold %f\n",
 368                                         fabs((double)best->u.value - bestr->u.value),
 369                                         u->bestr_ratio);
 370                         return true;
 371                 }
 372         }
 373
 374         if (winner && winner != best) {
 375                 /* Keep simulating if best explored
 376                  * does not have also highest value. */
 377                 if (UDEBUGL(2))
 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));
 383                 return true;
 384         }
 385
 386         /* No reason to keep simulating, bye. */
 387         return false;
 388 }
 389
 390 bool
 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)
 394 {
 395         struct uct_thread_ctx *ctx = s->ctx;
 396
 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));
 403         if (i < GJ_MINGAMES)
 404                 return false;
 405
 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;
 410
 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));
 413
 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))
 417                 return true;
 418
 419         /* Check against time settings. */
 420         bool desired_done;
 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;
 425
 426         } else { assert(ti->dim == TD_GAMES);
 427                 if (i > s->stop.worst.playouts) return true;
 428                 desired_done = i > s->stop.desired.playouts;
 429         }
 430
 431         /* We want to stop simulating, but are willing to keep trying
 432          * if we aren't completely sure about the winner yet. */
 433         if (desired_done) {
 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;
 438                 }
 439                 if (best)
 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))
 442                         return true;
 443         }
 444
 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)? */
 448         return false;
 449 }
 450
 451
 452 struct tree_node *
 453 uct_search_result(struct uct *u, struct board *b, enum stone color,
 454                   bool pass_all_alive, int played_games, int base_playouts,
 455                   coord_t *best_coord)
 456 {
 457         /* Choose the best move from the tree. */
 458         struct tree_node *best = u->policy->choose(u->policy, u->t->root, b, color, resign);
 459         if (!best) {
 460                 *best_coord = pass;
 461                 return NULL;
 462         }
 463         *best_coord = node_coord(best);
 464         if (UDEBUGL(1))
 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,
 469                         u->t->extra_komi);
 470
 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;
 480                 return NULL;
 481         }
 482
 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)) {
 488                         if (UDEBUGL(0))
 489                                 fprintf(stderr, "<Will rather pass, looks safe enough; score %f>\n",
 490                                         board_official_score(b, NULL) / 2);
 491                         *best_coord = pass;
 492                         best = u->t->root->children; // pass is the first child
 493                         assert(is_pass(node_coord(best)));
 494                         return best;
 495                 } else {
 496                         if (UDEBUGL(3))
 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);
 500                 }
 501         }
 502
 503         return best;
 504 }