uct/uct.c

   1 #include <assert.h>
   2 #include <pthread.h>
   3 #include <signal.h>
   4 #include <stdio.h>
   5 #include <stdlib.h>
   6 #include <string.h>
   7
   8 #define DEBUG
   9
  10 #include "debug.h"
  11 #include "board.h"
  12 #include "move.h"
  13 #include "playout.h"
  14 #include "playout/moggy.h"
  15 #include "playout/old.h"
  16 #include "playout/light.h"
  17 #include "random.h"
  18 #include "uct/internal.h"
  19 #include "uct/tree.h"
  20 #include "uct/uct.h"
  21
  22 struct uct_policy *policy_ucb1_init(struct uct *u, char *arg);
  23 struct uct_policy *policy_ucb1tuned_init(struct uct *u, char *arg);
  24 struct uct_policy *policy_ucb1amaf_init(struct uct *u, char *arg);
  25
  26
  27 #define MC_GAMES        80000
  28 #define MC_GAMELEN      400
  29
  30
  31 static void
  32 progress_status(struct uct *u, struct tree *t, enum stone color, int playouts)
  33 {
  34         if (!UDEBUGL(0))
  35                 return;
  36
  37         /* Best move */
  38         struct tree_node *best = u->policy->choose(u->policy, t->root, t->board, color);
  39         if (!best) {
  40                 fprintf(stderr, "... No moves left\n");
  41                 return;
  42         }
  43         fprintf(stderr, "[%d] ", playouts);
  44         fprintf(stderr, "best %f ", best->u.value);
  45
  46         /* Max depth */
  47         fprintf(stderr, "deepest % 2d ", t->max_depth - t->root->depth);
  48
  49         /* Best sequence */
  50         fprintf(stderr, "| seq ");
  51         for (int depth = 0; depth < 6; depth++) {
  52                 if (best && best->u.playouts >= 25) {
  53                         fprintf(stderr, "%3s ", coord2sstr(best->coord, t->board));
  54                         best = u->policy->choose(u->policy, best, t->board, color);
  55                 } else {
  56                         fprintf(stderr, "    ");
  57                 }
  58         }
  59
  60         /* Best candidates */
  61         fprintf(stderr, "| can ");
  62         int cans = 4;
  63         struct tree_node *can[cans];
  64         memset(can, 0, sizeof(can));
  65         best = t->root->children;
  66         while (best) {
  67                 int c = 0;
  68                 while ((!can[c] || best->u.playouts > can[c]->u.playouts) && ++c < cans);
  69                 for (int d = 0; d < c; d++) can[d] = can[d + 1];
  70                 if (c > 0) can[c - 1] = best;
  71                 best = best->sibling;
  72         }
  73         while (--cans >= 0) {
  74                 if (can[cans]) {
  75                         fprintf(stderr, "%3s(%.3f) ", coord2sstr(can[cans]->coord, t->board), can[cans]->u.value);
  76                 } else {
  77                         fprintf(stderr, "           ");
  78                 }
  79         }
  80
  81         fprintf(stderr, "\n");
  82 }
  83
  84
  85 static int
  86 uct_playout(struct uct *u, struct board *b, enum stone color, struct tree *t)
  87 {
  88         struct board b2;
  89         board_copy(&b2, b);
  90
  91         struct playout_amafmap *amaf = NULL;
  92         if (u->policy->wants_amaf) {
  93                 amaf = calloc(1, sizeof(*amaf));
  94                 amaf->map = calloc(board_size2(&b2) + 1, sizeof(*amaf->map));
  95                 amaf->map++; // -1 is pass
  96         }
  97
  98         /* Walk the tree until we find a leaf, then expand it and do
  99          * a random playout. */
 100         struct tree_node *n = t->root;
 101         enum stone orig_color = color;
 102         int result;
 103         int pass_limit = (board_size(&b2) - 2) * (board_size(&b2) - 2) / 2;
 104         int passes = is_pass(b->last_move.coord);
 105         /* debug */
 106         int depth = 0;
 107         static char spaces[] = "\0                                                      ";
 108         /* /debug */
 109         if (UDEBUGL(8))
 110                 fprintf(stderr, "--- UCT walk with color %d\n", color);
 111         for (; pass; color = stone_other(color)) {
 112                 if (tree_leaf_node(n)) {
 113                         if (n->u.playouts >= u->expand_p)
 114                                 tree_expand_node(t, n, &b2, color, u->radar_d, u->policy, (color == orig_color ? 1 : -1));
 115                         if (UDEBUGL(7))
 116                                 fprintf(stderr, "%s*-- UCT playout #%d start [%s] %f\n", spaces, n->u.playouts, coord2sstr(n->coord, t->board), n->u.value);
 117
 118                         result = play_random_game(&b2, color, u->gamelen, u->playout_amaf ? amaf : NULL, u->playout);
 119                         if (orig_color != color && result >= 0)
 120                                 result = !result;
 121                         if (UDEBUGL(7))
 122                                 fprintf(stderr, "%s -- [%d..%d] %s random playout result %d\n", spaces, orig_color, color, coord2sstr(n->coord, t->board), result);
 123
 124                         /* Reset color to the @n color. */
 125                         color = stone_other(color);
 126                         break;
 127                 }
 128                 spaces[depth++] = ' '; spaces[depth] = 0;
 129
 130                 n = u->policy->descend(u->policy, t, n, (color == orig_color ? 1 : -1), pass_limit);
 131                 assert(n == t->root || n->parent);
 132                 if (UDEBUGL(7))
 133                         fprintf(stderr, "%s+-- UCT sent us to [%s:%d] %f\n", spaces, coord2sstr(n->coord, t->board), n->coord, n->u.value);
 134                 if (amaf && n->coord >= -1 && !is_pass(n->coord)) {
 135                         if (amaf->map[n->coord] == S_NONE) {
 136                                 amaf->map[n->coord] = color;
 137                         } else {
 138                                 amaf_op(amaf->map[n->coord], +);
 139                         }
 140                 }
 141                 struct move m = { n->coord, color };
 142                 int res = board_play(&b2, &m);
 143
 144                 if (res < 0 || (!is_pass(m.coord) && !group_at(&b2, m.coord)) /* suicide */
 145                     || b2.superko_violation) {
 146                         if (UDEBUGL(3)) {
 147                                 for (struct tree_node *ni = n; ni; ni = ni->parent)
 148                                         fprintf(stderr, "%s ", coord2sstr(ni->coord, t->board));
 149                                 fprintf(stderr, "deleting invalid %s node %d,%d res %d group %d spk %d\n",
 150                                         stone2str(color), coord_x(n->coord,b), coord_y(n->coord,b),
 151                                         res, group_at(&b2, m.coord), b2.superko_violation);
 152                         }
 153                         tree_delete_node(t, n);
 154                         result = -1;
 155                         goto end;
 156                 }
 157
 158                 if (is_pass(n->coord)) {
 159                         passes++;
 160                         if (passes >= 2) {
 161                                 float score = board_official_score(&b2);
 162                                 result = (orig_color == S_BLACK) ? score < 0 : score > 0;
 163                                 if (UDEBUGL(5))
 164                                         fprintf(stderr, "[%d..%d] %s p-p scoring playout result %d (W %f)\n", orig_color, color, coord2sstr(n->coord, t->board), result, score);
 165                                 if (UDEBUGL(6))
 166                                         board_print(&b2, stderr);
 167                                 break;
 168                         }
 169                 } else {
 170                         passes = 0;
 171                 }
 172         }
 173
 174         assert(n == t->root || n->parent);
 175         if (result >= 0)
 176                 u->policy->update(u->policy, t, n, color, orig_color, amaf, result);
 177
 178 end:
 179         if (amaf) {
 180                 free(amaf->map - 1);
 181                 free(amaf);
 182         }
 183         board_done_noalloc(&b2);
 184         return result;
 185 }
 186
 187 static void
 188 prepare_move(struct engine *e, struct board *b, enum stone color, coord_t promote)
 189 {
 190         struct uct *u = e->data;
 191
 192         if (!b->moves && u->t) {
 193                 /* Stale state from last game */
 194                 tree_done(u->t);
 195                 u->t = NULL;
 196         }
 197
 198         if (!u->t) {
 199                 u->t = tree_init(b, color);
 200                 if (UDEBUGL(0))
 201                         fprintf(stderr, "Fresh board with random seed %lu\n", fast_getseed());
 202                 //board_print(b, stderr);
 203                 tree_load(u->t, b, color);
 204         }
 205
 206         /* XXX: We hope that the opponent didn't suddenly play
 207          * several moves in the row. */
 208         if (!is_resign(promote) && !tree_promote_at(u->t, b, promote)) {
 209                 if (UDEBUGL(2))
 210                         fprintf(stderr, "<cannot find node to promote>\n");
 211                 /* Reset tree */
 212                 tree_done(u->t);
 213                 u->t = tree_init(b, color);
 214         }
 215 }
 216
 217 /* Set in main thread in case the playouts should stop. */
 218 static volatile sig_atomic_t halt = 0;
 219
 220 static int
 221 uct_playouts(struct uct *u, struct board *b, enum stone color, struct tree *t)
 222 {
 223         int i, games = u->games;
 224         if (t->root->children)
 225                 games -= t->root->u.playouts / 1.5;
 226         /* else this is highly read-out but dead-end branch of opening book;
 227          * we need to start from scratch; XXX: Maybe actually base the readout
 228          * count based on number of playouts of best node? */
 229         for (i = 0; i < games; i++) {
 230                 int result = uct_playout(u, b, color, t);
 231                 if (result < 0) {
 232                         /* Tree descent has hit invalid move. */
 233                         continue;
 234                 }
 235
 236                 if (i > 0 && !(i % 10000)) {
 237                         progress_status(u, t, color, i);
 238                 }
 239
 240                 if (i > 0 && !(i % 500)) {
 241                         struct tree_node *best = u->policy->choose(u->policy, t->root, b, color);
 242                         if (best && best->u.playouts >= 1500 && best->u.value >= u->loss_threshold)
 243                                 break;
 244                 }
 245
 246                 if (halt) {
 247                         if (UDEBUGL(2))
 248                                 fprintf(stderr, "<halting early, %d games skipped>\n", games - i);
 249                         break;
 250                 }
 251         }
 252
 253         progress_status(u, t, color, i);
 254         if (UDEBUGL(3))
 255                 tree_dump(t, u->dumpthres);
 256         return i;
 257 }
 258
 259 static pthread_mutex_t finish_mutex = PTHREAD_MUTEX_INITIALIZER;
 260 static pthread_cond_t finish_cond = PTHREAD_COND_INITIALIZER;
 261 static volatile int finish_thread;
 262 static pthread_mutex_t finish_serializer = PTHREAD_MUTEX_INITIALIZER;
 263
 264 struct spawn_ctx {
 265         int tid;
 266         struct uct *u;
 267         struct board *b;
 268         enum stone color;
 269         struct tree *t;
 270         unsigned long seed;
 271         int games;
 272 };
 273
 274 static void *
 275 spawn_helper(void *ctx_)
 276 {
 277         struct spawn_ctx *ctx = ctx_;
 278         /* Setup */
 279         fast_srandom(ctx->seed);
 280         /* Run */
 281         ctx->games = uct_playouts(ctx->u, ctx->b, ctx->color, ctx->t);
 282         /* Finish */
 283         pthread_mutex_lock(&finish_serializer);
 284         pthread_mutex_lock(&finish_mutex);
 285         finish_thread = ctx->tid;
 286         pthread_cond_signal(&finish_cond);
 287         pthread_mutex_unlock(&finish_mutex);
 288         return ctx;
 289 }
 290
 291 static void
 292 uct_notify_play(struct engine *e, struct board *b, struct move *m)
 293 {
 294         prepare_move(e, b, stone_other(m->color), m->coord);
 295 }
 296
 297 static coord_t *
 298 uct_genmove(struct engine *e, struct board *b, enum stone color)
 299 {
 300         struct uct *u = e->data;
 301
 302         /* Seed the tree. */
 303         prepare_move(e, b, color, resign);
 304
 305         int played_games = 0;
 306         if (!u->threads) {
 307                 played_games = uct_playouts(u, b, color, u->t);
 308         } else {
 309                 pthread_t threads[u->threads];
 310                 int joined = 0;
 311                 halt = 0;
 312                 pthread_mutex_lock(&finish_mutex);
 313                 /* Spawn threads... */
 314                 for (int ti = 0; ti < u->threads; ti++) {
 315                         struct spawn_ctx *ctx = malloc(sizeof(*ctx));
 316                         ctx->u = u; ctx->b = b; ctx->color = color;
 317                         ctx->t = tree_copy(u->t); ctx->tid = ti;
 318                         ctx->seed = fast_random(65536) + ti;
 319                         pthread_create(&threads[ti], NULL, spawn_helper, ctx);
 320                         if (UDEBUGL(2))
 321                                 fprintf(stderr, "Spawned thread %d\n", ti);
 322                 }
 323                 /* ...and collect them back: */
 324                 while (joined < u->threads) {
 325                         /* Wait for some thread to finish... */
 326                         pthread_cond_wait(&finish_cond, &finish_mutex);
 327                         /* ...and gather its remnants. */
 328                         struct spawn_ctx *ctx;
 329                         pthread_join(threads[finish_thread], (void **) &ctx);
 330                         played_games += ctx->games;
 331                         joined++;
 332                         tree_merge(u->t, ctx->t);
 333                         tree_done(ctx->t);
 334                         free(ctx);
 335                         if (UDEBUGL(2))
 336                                 fprintf(stderr, "Joined thread %d\n", finish_thread);
 337                         /* Do not get stalled by slow threads. */
 338                         if (joined >= u->threads / 2)
 339                                 halt = 1;
 340                         pthread_mutex_unlock(&finish_serializer);
 341                 }
 342                 pthread_mutex_unlock(&finish_mutex);
 343         }
 344
 345         if (UDEBUGL(2))
 346                 tree_dump(u->t, u->dumpthres);
 347
 348         struct tree_node *best = u->policy->choose(u->policy, u->t->root, b, color);
 349         if (!best) {
 350                 tree_done(u->t); u->t = NULL;
 351                 return coord_copy(pass);
 352         }
 353         if (UDEBUGL(0))
 354                 fprintf(stderr, "*** WINNER is %s (%d,%d) with score %1.4f (%d/%d:%d games)\n", coord2sstr(best->coord, b), coord_x(best->coord, b), coord_y(best->coord, b), best->u.value, best->u.playouts, u->t->root->u.playouts, played_games);
 355         if (best->u.value < u->resign_ratio && !is_pass(best->coord)) {
 356                 tree_done(u->t); u->t = NULL;
 357                 return coord_copy(resign);
 358         }
 359         tree_promote_node(u->t, best);
 360         return coord_copy(best->coord);
 361 }
 362
 363 bool
 364 uct_genbook(struct engine *e, struct board *b, enum stone color)
 365 {
 366         struct uct *u = e->data;
 367         u->t = tree_init(b, color);
 368         tree_load(u->t, b, color);
 369
 370         int i;
 371         for (i = 0; i < u->games; i++) {
 372                 int result = uct_playout(u, b, color, u->t);
 373                 if (result < 0) {
 374                         /* Tree descent has hit invalid move. */
 375                         continue;
 376                 }
 377
 378                 if (i > 0 && !(i % 10000)) {
 379                         progress_status(u, u->t, color, i);
 380                 }
 381         }
 382         progress_status(u, u->t, color, i);
 383
 384         tree_save(u->t, b, u->games / 100);
 385
 386         tree_done(u->t);
 387
 388         return true;
 389 }
 390
 391 void
 392 uct_dumpbook(struct engine *e, struct board *b, enum stone color)
 393 {
 394         struct uct *u = e->data;
 395         u->t = tree_init(b, color);
 396         tree_load(u->t, b, color);
 397         tree_dump(u->t, 0);
 398         tree_done(u->t);
 399 }
 400
 401
 402 struct uct *
 403 uct_state_init(char *arg)
 404 {
 405         struct uct *u = calloc(1, sizeof(struct uct));
 406
 407         u->debug_level = 1;
 408         u->games = MC_GAMES;
 409         u->gamelen = MC_GAMELEN;
 410         u->expand_p = 2;
 411         u->dumpthres = 1000;
 412         u->playout_amaf = false;
 413
 414         if (arg) {
 415                 char *optspec, *next = arg;
 416                 while (*next) {
 417                         optspec = next;
 418                         next += strcspn(next, ",");
 419                         if (*next) { *next++ = 0; } else { *next = 0; }
 420
 421                         char *optname = optspec;
 422                         char *optval = strchr(optspec, '=');
 423                         if (optval) *optval++ = 0;
 424
 425                         if (!strcasecmp(optname, "debug")) {
 426                                 if (optval)
 427                                         u->debug_level = atoi(optval);
 428                                 else
 429                                         u->debug_level++;
 430                         } else if (!strcasecmp(optname, "games") && optval) {
 431                                 u->games = atoi(optval);
 432                         } else if (!strcasecmp(optname, "gamelen") && optval) {
 433                                 u->gamelen = atoi(optval);
 434                         } else if (!strcasecmp(optname, "expand_p") && optval) {
 435                                 u->expand_p = atoi(optval);
 436                         } else if (!strcasecmp(optname, "radar_d") && optval) {
 437                                 /* For 19x19, it is good idea to set this to 3. */
 438                                 u->radar_d = atoi(optval);
 439                         } else if (!strcasecmp(optname, "dumpthres") && optval) {
 440                                 u->dumpthres = atoi(optval);
 441                         } else if (!strcasecmp(optname, "playout_amaf")) {
 442                                 /* Whether to include random playout moves in
 443                                  * AMAF as well. (Otherwise, only tree moves
 444                                  * are included in AMAF. Of course makes sense
 445                                  * only in connection with an AMAF policy.) */
 446                                 /* with-without: 55.5% (+-4.1) */
 447                                 if (optval && *optval == '0')
 448                                         u->playout_amaf = false;
 449                                 else
 450                                         u->playout_amaf = true;
 451                         } else if (!strcasecmp(optname, "policy") && optval) {
 452                                 char *policyarg = strchr(optval, ':');
 453                                 if (policyarg)
 454                                         *policyarg++ = 0;
 455                                 if (!strcasecmp(optval, "ucb1")) {
 456                                         u->policy = policy_ucb1_init(u, policyarg);
 457                                 } else if (!strcasecmp(optval, "ucb1tuned")) {
 458                                         u->policy = policy_ucb1tuned_init(u, policyarg);
 459                                 } else if (!strcasecmp(optval, "ucb1amaf")) {
 460                                         u->policy = policy_ucb1amaf_init(u, policyarg);
 461                                 } else {
 462                                         fprintf(stderr, "UCT: Invalid tree policy %s\n", optval);
 463                                 }
 464                         } else if (!strcasecmp(optname, "playout") && optval) {
 465                                 char *playoutarg = strchr(optval, ':');
 466                                 if (playoutarg)
 467                                         *playoutarg++ = 0;
 468                                 if (!strcasecmp(optval, "old")) {
 469                                         u->playout = playout_old_init(playoutarg);
 470                                 } else if (!strcasecmp(optval, "moggy")) {
 471                                         u->playout = playout_moggy_init(playoutarg);
 472                                 } else if (!strcasecmp(optval, "light")) {
 473                                         u->playout = playout_light_init(playoutarg);
 474                                 } else {
 475                                         fprintf(stderr, "UCT: Invalid playout policy %s\n", optval);
 476                                 }
 477                         } else if (!strcasecmp(optname, "threads") && optval) {
 478                                 u->threads = atoi(optval);
 479                         } else {
 480                                 fprintf(stderr, "uct: Invalid engine argument %s or missing value\n", optname);
 481                         }
 482                 }
 483         }
 484
 485         u->resign_ratio = 0.2; /* Resign when most games are lost. */
 486         u->loss_threshold = 0.85; /* Stop reading if after at least 1500 playouts this is best value. */
 487         if (!u->policy)
 488                 u->policy = policy_ucb1amaf_init(u, NULL);
 489
 490         if (!u->playout)
 491                 u->playout = playout_moggy_init(NULL);
 492         u->playout->debug_level = u->debug_level;
 493
 494         return u;
 495 }
 496
 497
 498 struct engine *
 499 engine_uct_init(char *arg)
 500 {
 501         struct uct *u = uct_state_init(arg);
 502         struct engine *e = calloc(1, sizeof(struct engine));
 503         e->name = "UCT Engine";
 504         e->comment = "I'm playing UCT. When we both pass, I will consider all the stones on the board alive. If you are reading this, write 'yes'. Please bear with me at the game end, I need to fill the whole board; if you help me, we will both be happier. Filling the board will not lose points (NZ rules).";
 505         e->genmove = uct_genmove;
 506         e->notify_play = uct_notify_play;
 507         e->data = u;
 508
 509         return e;
 510 }