uct/tree.c

   1 #include <assert.h>
   2 #include <math.h>
   3 #include <stddef.h>
   4 #include <stdint.h>
   5 #include <stdio.h>
   6 #include <stdlib.h>
   7 #include <string.h>
   8
   9 #define DEBUG
  10 #include "board.h"
  11 #include "debug.h"
  12 #include "engine.h"
  13 #include "move.h"
  14 #include "playout.h"
  15 #include "tactics.h"
  16 #include "uct/internal.h"
  17 #include "uct/prior.h"
  18 #include "uct/tree.h"
  19
  20
  21 /* This function may be called by multiple threads in parallel */
  22 static struct tree_node *
  23 tree_init_node(struct tree *t, coord_t coord, int depth)
  24 {
  25         struct tree_node *n = calloc(1, sizeof(*n));
  26         if (!n) {
  27                 fprintf(stderr, "tree_init_node(): OUT OF MEMORY\n");
  28                 exit(1);
  29         }
  30         __sync_fetch_and_add(&t->nodes_size, sizeof(*n));
  31         n->coord = coord;
  32         n->depth = depth;
  33         volatile static long c = 1000000;
  34         n->hash = __sync_fetch_and_add(&c, 1);
  35         if (depth > t->max_depth)
  36                 t->max_depth = depth;
  37         return n;
  38 }
  39
  40 struct tree *
  41 tree_init(struct board *board, enum stone color)
  42 {
  43         struct tree *t = calloc(1, sizeof(*t));
  44         t->board = board;
  45         /* The root PASS move is only virtual, we never play it. */
  46         t->root = tree_init_node(t, pass, 0);
  47         t->root_symmetry = board->symmetry;
  48         t->root_color = stone_other(color); // to research black moves, root will be white
  49         return t;
  50 }
  51
  52
  53 /* This function may be called by multiple threads in parallel on the
  54  * same tree, but not on node n. n may be detached from the tree but
  55  * must have been created in this tree originally.
  56  * It returns the remaining size of the tree after n has been freed. */
  57 static unsigned long
  58 tree_done_node(struct tree *t, struct tree_node *n)
  59 {
  60         struct tree_node *ni = n->children;
  61         while (ni) {
  62                 struct tree_node *nj = ni->sibling;
  63                 tree_done_node(t, ni);
  64                 ni = nj;
  65         }
  66         free(n);
  67         unsigned long old_size = __sync_fetch_and_sub(&t->nodes_size, sizeof(*n));
  68         return old_size - sizeof(*n);
  69 }
  70
  71 struct subtree_ctx {
  72         struct tree *t;
  73         struct tree_node *n;
  74 };
  75
  76 /* Worker thread for tree_done_node_detached() */
  77 static void *
  78 tree_done_node_worker(void *ctx_)
  79 {
  80         struct subtree_ctx *ctx = ctx_;
  81         char *str = coord2str(ctx->n->coord, ctx->t->board);
  82
  83         unsigned long tree_size = tree_done_node(ctx->t, ctx->n);
  84         if (!tree_size)
  85                 free(ctx->t);
  86         if (DEBUGL(0)) // jlg: 0->3
  87                 fprintf(stderr, "done freeing node at %s, tree size %lu\n", str, tree_size);
  88         free(str);
  89         free(ctx);
  90         return NULL;
  91 }
  92
  93 /* Asynchronously free the subtree of nodes rooted at n. If the tree becomes
  94  * empty free the tree also. */
  95 static void
  96 tree_done_node_detached(struct tree *t, struct tree_node *n)
  97 {
  98         if (n->u.playouts < 1000) { // no thread for small tree
  99                 if (!tree_done_node(t, n))
 100                         free(t);
 101                 return;
 102         }
 103         pthread_attr_t attr;
 104         pthread_attr_init(&attr);
 105         pthread_attr_setdetachstate(&attr, PTHREAD_CREATE_DETACHED);
 106
 107         pthread_t thread;
 108         struct subtree_ctx *ctx = malloc(sizeof(struct subtree_ctx));
 109         if (!ctx) {
 110                 fprintf(stderr, "tree_done_node_detached(): OUT OF MEMORY\n");
 111                 exit(1);
 112         }
 113         ctx->t = t;
 114         ctx->n = n;
 115         pthread_create(&thread, &attr, tree_done_node_worker, ctx);
 116         pthread_attr_destroy(&attr);
 117 }
 118
 119 void
 120 tree_done(struct tree *t)
 121 {
 122         if (t->chchvals) free(t->chchvals);
 123         if (t->chvals) free(t->chvals);
 124         if (!tree_done_node(t, t->root))
 125             free(t);
 126         /* A tree_done_node_worker might still be running on this tree but
 127          * it will free the tree later. It is also freeing nodes faster than
 128          * we will create new ones. */
 129 }
 130
 131
 132 static void
 133 tree_node_dump(struct tree *tree, struct tree_node *node, int l, int thres)
 134 {
 135         for (int i = 0; i < l; i++) fputc(' ', stderr);
 136         int children = 0;
 137         for (struct tree_node *ni = node->children; ni; ni = ni->sibling)
 138                 children++;
 139         /* We use 1 as parity, since for all nodes we want to know the
 140          * win probability of _us_, not the node color. */
 141         fprintf(stderr, "[%s] %f %% %d [prior %f %% %d amaf %f %% %d]; hints %x; %d children <%"PRIhash">\n",
 142                 coord2sstr(node->coord, tree->board),
 143                 tree_node_get_value(tree, 1, node->u.value), node->u.playouts,
 144                 tree_node_get_value(tree, 1, node->prior.value), node->prior.playouts,
 145                 tree_node_get_value(tree, 1, node->amaf.value), node->amaf.playouts,
 146                 node->hints, children, node->hash);
 147
 148         /* Print nodes sorted by #playouts. */
 149
 150         struct tree_node *nbox[1000]; int nboxl = 0;
 151         for (struct tree_node *ni = node->children; ni; ni = ni->sibling)
 152                 if (ni->u.playouts > thres)
 153                         nbox[nboxl++] = ni;
 154
 155         while (true) {
 156                 int best = -1;
 157                 for (int i = 0; i < nboxl; i++)
 158                         if (nbox[i] && (best < 0 || nbox[i]->u.playouts > nbox[best]->u.playouts))
 159                                 best = i;
 160                 if (best < 0)
 161                         break;
 162                 tree_node_dump(tree, nbox[best], l + 1, /* node->u.value < 0.1 ? 0 : */ thres);
 163                 nbox[best] = NULL;
 164         }
 165 }
 166
 167 void
 168 tree_dump_chval(struct tree *tree, struct move_stats *v)
 169 {
 170         for (int y = board_size(tree->board) - 2; y > 1; y--) {
 171                 for (int x = 1; x < board_size(tree->board) - 1; x++) {
 172                         coord_t c = coord_xy(tree->board, x, y);
 173                         fprintf(stderr, "%.2f%%%05d  ", v[c].value, v[c].playouts);
 174                 }
 175                 fprintf(stderr, "\n");
 176         }
 177 }
 178
 179 void
 180 tree_dump(struct tree *tree, int thres)
 181 {
 182         if (thres && tree->root->u.playouts / thres > 100) {
 183                 /* Be a bit sensible about this; the opening book can create
 184                  * huge dumps at first. */
 185                 thres = tree->root->u.playouts / 100 * (thres < 1000 ? 1 : thres / 1000);
 186         }
 187         fprintf(stderr, "(UCT tree; root %s; extra komi %f)\n",
 188                 stone2str(tree->root_color), tree->extra_komi);
 189         tree_node_dump(tree, tree->root, 0, thres);
 190
 191         if (DEBUGL(3) && tree->chvals) {
 192                 fprintf(stderr, "children stats:\n");
 193                 tree_dump_chval(tree, tree->chvals);
 194                 fprintf(stderr, "grandchildren stats:\n");
 195                 tree_dump_chval(tree, tree->chchvals);
 196         }
 197 }
 198
 199
 200 static char *
 201 tree_book_name(struct board *b)
 202 {
 203         static char buf[256];
 204         if (b->handicap > 0) {
 205                 sprintf(buf, "uctbook-%d-%02.01f-h%d.pachitree", b->size - 2, b->komi, b->handicap);
 206         } else {
 207                 sprintf(buf, "uctbook-%d-%02.01f.pachitree", b->size - 2, b->komi);
 208         }
 209         return buf;
 210 }
 211
 212 static void
 213 tree_node_save(FILE *f, struct tree_node *node, int thres)
 214 {
 215         bool save_children = node->u.playouts >= thres;
 216
 217         if (!save_children)
 218                 node->is_expanded = 0;
 219
 220         fputc(1, f);
 221         fwrite(((void *) node) + offsetof(struct tree_node, depth),
 222                sizeof(struct tree_node) - offsetof(struct tree_node, depth),
 223                1, f);
 224
 225         if (save_children) {
 226                 for (struct tree_node *ni = node->children; ni; ni = ni->sibling)
 227                         tree_node_save(f, ni, thres);
 228         } else {
 229                 if (node->children)
 230                         node->is_expanded = 1;
 231         }
 232
 233         fputc(0, f);
 234 }
 235
 236 void
 237 tree_save(struct tree *tree, struct board *b, int thres)
 238 {
 239         char *filename = tree_book_name(b);
 240         FILE *f = fopen(filename, "wb");
 241         if (!f) {
 242                 perror("fopen");
 243                 return;
 244         }
 245         tree_node_save(f, tree->root, thres);
 246         fputc(0, f);
 247         fclose(f);
 248 }
 249
 250
 251 void
 252 tree_node_load(FILE *f, struct tree_node *node, int *num)
 253 {
 254         (*num)++;
 255
 256         fread(((void *) node) + offsetof(struct tree_node, depth),
 257                sizeof(struct tree_node) - offsetof(struct tree_node, depth),
 258                1, f);
 259
 260         /* Keep values in sane scale, otherwise we start overflowing. */
 261 #define MAX_PLAYOUTS    10000000
 262         if (node->u.playouts > MAX_PLAYOUTS) {
 263                 node->u.playouts = MAX_PLAYOUTS;
 264         }
 265         if (node->amaf.playouts > MAX_PLAYOUTS) {
 266                 node->amaf.playouts = MAX_PLAYOUTS;
 267         }
 268         memcpy(&node->pamaf, &node->amaf, sizeof(node->amaf));
 269         memcpy(&node->pu, &node->u, sizeof(node->u));
 270
 271         struct tree_node *ni = NULL, *ni_prev = NULL;
 272         while (fgetc(f)) {
 273                 ni_prev = ni; ni = calloc(1, sizeof(*ni));
 274                 if (!node->children)
 275                         node->children = ni;
 276                 else
 277                         ni_prev->sibling = ni;
 278                 ni->parent = node;
 279                 tree_node_load(f, ni, num);
 280         }
 281 }
 282
 283 void
 284 tree_load(struct tree *tree, struct board *b)
 285 {
 286         char *filename = tree_book_name(b);
 287         FILE *f = fopen(filename, "rb");
 288         if (!f)
 289                 return;
 290
 291         fprintf(stderr, "Loading opening book %s...\n", filename);
 292
 293         int num = 0;
 294         if (fgetc(f))
 295                 tree_node_load(f, tree->root, &num);
 296         fprintf(stderr, "Loaded %d nodes.\n", num);
 297
 298         fclose(f);
 299 }
 300
 301
 302 static struct tree_node *
 303 tree_node_copy(struct tree_node *node)
 304 {
 305         struct tree_node *n2 = malloc(sizeof(*n2));
 306         *n2 = *node;
 307         if (!node->children)
 308                 return n2;
 309         struct tree_node *ni = node->children;
 310         struct tree_node *ni2 = tree_node_copy(ni);
 311         n2->children = ni2; ni2->parent = n2;
 312         while ((ni = ni->sibling)) {
 313                 ni2->sibling = tree_node_copy(ni);
 314                 ni2 = ni2->sibling; ni2->parent = n2;
 315         }
 316         return n2;
 317 }
 318
 319 struct tree *
 320 tree_copy(struct tree *tree)
 321 {
 322         struct tree *t2 = malloc(sizeof(*t2));
 323         *t2 = *tree;
 324         t2->root = tree_node_copy(tree->root);
 325         return t2;
 326 }
 327
 328 static void
 329 tree_node_merge(struct tree_node *dest, struct tree_node *src)
 330 {
 331         /* Do not merge nodes that weren't touched at all. */
 332         assert(dest->pamaf.playouts == src->pamaf.playouts);
 333         assert(dest->pu.playouts == src->pu.playouts);
 334         if (src->amaf.playouts - src->pamaf.playouts == 0
 335             && src->u.playouts - src->pu.playouts == 0) {
 336                 return;
 337         }
 338
 339         dest->hints |= src->hints;
 340
 341         /* Merge the children, both are coord-sorted lists. */
 342         struct tree_node *di = dest->children, **dref = &dest->children;
 343         struct tree_node *si = src->children, **sref = &src->children;
 344         while (di && si) {
 345                 if (di->coord != si->coord) {
 346                         /* src has some extra items or misses di */
 347                         struct tree_node *si2 = si->sibling;
 348                         while (si2 && di->coord != si2->coord) {
 349                                 si2 = si2->sibling;
 350                         }
 351                         if (!si2)
 352                                 goto next_di; /* src misses di, move on */
 353                         /* chain the extra [si,si2) items before di */
 354                         (*dref) = si;
 355                         while (si->sibling != si2) {
 356                                 si->parent = dest;
 357                                 si = si->sibling;
 358                         }
 359                         si->parent = dest;
 360                         si->sibling = di;
 361                         si = si2;
 362                         (*sref) = si;
 363                 }
 364                 /* Matching nodes - recurse... */
 365                 tree_node_merge(di, si);
 366                 /* ...and move on. */
 367                 sref = &si->sibling; si = si->sibling;
 368 next_di:
 369                 dref = &di->sibling; di = di->sibling;
 370         }
 371         if (si) {
 372                 /* Some outstanding nodes are left on src side, rechain
 373                  * them to dst. */
 374                 (*dref) = si;
 375                 while (si) {
 376                         si->parent = dest;
 377                         si = si->sibling;
 378                 }
 379                 (*sref) = NULL;
 380         }
 381
 382         /* Priors should be constant. */
 383         assert(dest->prior.playouts == src->prior.playouts && dest->prior.value == src->prior.value);
 384
 385         stats_merge(&dest->amaf, &src->amaf);
 386         stats_merge(&dest->u, &src->u);
 387 }
 388
 389 /* Merge two trees built upon the same board. Note that the operation is
 390  * destructive on src. */
 391 void
 392 tree_merge(struct tree *dest, struct tree *src)
 393 {
 394         if (src->max_depth > dest->max_depth)
 395                 dest->max_depth = src->max_depth;
 396         tree_node_merge(dest->root, src->root);
 397 }
 398
 399
 400 static void
 401 tree_node_normalize(struct tree_node *node, int factor)
 402 {
 403         for (struct tree_node *ni = node->children; ni; ni = ni->sibling)
 404                 tree_node_normalize(ni, factor);
 405
 406 #define normalize(s1, s2, t) node->s2.t = node->s1.t + (node->s2.t - node->s1.t) / factor;
 407         normalize(pamaf, amaf, playouts);
 408         memcpy(&node->pamaf, &node->amaf, sizeof(node->amaf));
 409
 410         normalize(pu, u, playouts);
 411         memcpy(&node->pu, &node->u, sizeof(node->u));
 412 #undef normalize
 413 }
 414
 415 /* Normalize a tree, dividing the amaf and u values by given
 416  * factor; otherwise, simulations run in independent threads
 417  * two trees built upon the same board. To correctly handle
 418  * results taken from previous simulation run, they are backed
 419  * up in tree. */
 420 void
 421 tree_normalize(struct tree *tree, int factor)
 422 {
 423         tree_node_normalize(tree->root, factor);
 424 }
 425
 426
 427 /* Tree symmetry: When possible, we will localize the tree to a single part
 428  * of the board in tree_expand_node() and possibly flip along symmetry axes
 429  * to another part of the board in tree_promote_at(). We follow b->symmetry
 430  * guidelines here. */
 431
 432
 433 void
 434 tree_expand_node(struct tree *t, struct tree_node *node, struct board *b, enum stone color, struct uct *u, int parity)
 435 {
 436         /* Get a Common Fate Graph distance map from parent node. */
 437         int distances[board_size2(b)];
 438         if (!is_pass(b->last_move.coord) && !is_resign(b->last_move.coord)) {
 439                 cfg_distances(b, node->coord, distances, TREE_NODE_D_MAX);
 440         } else {
 441                 // Pass or resign - everything is too far.
 442                 foreach_point(b) { distances[c] = TREE_NODE_D_MAX + 1; } foreach_point_end;
 443         }
 444
 445         /* Get a map of prior values to initialize the new nodes with. */
 446         struct prior_map map = {
 447                 .b = b,
 448                 .to_play = color,
 449                 .parity = tree_parity(t, parity),
 450                 .distances = distances,
 451         };
 452         // Include pass in the prior map.
 453         struct move_stats map_prior[board_size2(b) + 1]; map.prior = &map_prior[1];
 454         bool map_consider[board_size2(b) + 1]; map.consider = &map_consider[1];
 455         memset(map_prior, 0, sizeof(map_prior));
 456         memset(map_consider, 0, sizeof(map_consider));
 457         struct move pm = { .color = color };
 458         map.consider[pass] = true;
 459         foreach_point(b) {
 460                 if (board_at(b, c) != S_NONE)
 461                         continue;
 462                 pm.coord = c;
 463                 if (!board_is_valid_move(b, &pm))
 464                         continue;
 465                 map.consider[c] = true;
 466         } foreach_point_end;
 467         uct_prior(u, node, &map);
 468
 469         /* Now, create the nodes. */
 470         struct tree_node *ni = tree_init_node(t, pass, node->depth + 1);
 471         struct tree_node *first_child = ni;
 472         ni->parent = node;
 473         ni->prior = map.prior[pass]; ni->d = TREE_NODE_D_MAX + 1;
 474
 475         /* The loop considers only the symmetry playground. */
 476         if (UDEBUGL(6)) {
 477                 fprintf(stderr, "expanding %s within [%d,%d],[%d,%d] %d-%d\n",
 478                                 coord2sstr(node->coord, b),
 479                                 b->symmetry.x1, b->symmetry.y1,
 480                                 b->symmetry.x2, b->symmetry.y2,
 481                                 b->symmetry.type, b->symmetry.d);
 482         }
 483         for (int i = b->symmetry.x1; i <= b->symmetry.x2; i++) {
 484                 for (int j = b->symmetry.y1; j <= b->symmetry.y2; j++) {
 485                         if (b->symmetry.d) {
 486                                 int x = b->symmetry.type == SYM_DIAG_DOWN ? board_size(b) - 1 - i : i;
 487                                 if (x > j) {
 488                                         if (UDEBUGL(7))
 489                                                 fprintf(stderr, "drop %d,%d\n", i, j);
 490                                         continue;
 491                                 }
 492                         }
 493
 494                         coord_t c = coord_xy_otf(i, j, t->board);
 495                         if (!map.consider[c]) // Filter out invalid moves
 496                                 continue;
 497                         assert(c != node->coord); // I have spotted "C3 C3" in some sequence...
 498
 499                         struct tree_node *nj = tree_init_node(t, c, node->depth + 1);
 500                         nj->parent = node; ni->sibling = nj; ni = nj;
 501
 502                         ni->prior = map.prior[c];
 503                         ni->d = distances[c];
 504                 }
 505         }
 506         node->children = first_child; // must be done at the end to avoid race
 507 }
 508
 509
 510 static coord_t
 511 flip_coord(struct board *b, coord_t c,
 512            bool flip_horiz, bool flip_vert, int flip_diag)
 513 {
 514         int x = coord_x(c, b), y = coord_y(c, b);
 515         if (flip_diag) {
 516                 int z = x; x = y; y = z;
 517         }
 518         if (flip_horiz) {
 519                 x = board_size(b) - 1 - x;
 520         }
 521         if (flip_vert) {
 522                 y = board_size(b) - 1 - y;
 523         }
 524         return coord_xy_otf(x, y, b);
 525 }
 526
 527 static void
 528 tree_fix_node_symmetry(struct board *b, struct tree_node *node,
 529                        bool flip_horiz, bool flip_vert, int flip_diag)
 530 {
 531         if (!is_pass(node->coord))
 532                 node->coord = flip_coord(b, node->coord, flip_horiz, flip_vert, flip_diag);
 533
 534         for (struct tree_node *ni = node->children; ni; ni = ni->sibling)
 535                 tree_fix_node_symmetry(b, ni, flip_horiz, flip_vert, flip_diag);
 536 }
 537
 538 static void
 539 tree_fix_symmetry(struct tree *tree, struct board *b, coord_t c)
 540 {
 541         if (is_pass(c))
 542                 return;
 543
 544         struct board_symmetry *s = &tree->root_symmetry;
 545         int cx = coord_x(c, b), cy = coord_y(c, b);
 546
 547         /* playground   X->h->v->d normalization
 548          * :::..        .d...
 549          * .::..        v....
 550          * ..:..        .....
 551          * .....        h...X
 552          * .....        .....  */
 553         bool flip_horiz = cx < s->x1 || cx > s->x2;
 554         bool flip_vert = cy < s->y1 || cy > s->y2;
 555
 556         bool flip_diag = 0;
 557         if (s->d) {
 558                 bool dir = (s->type == SYM_DIAG_DOWN);
 559                 int x = dir ^ flip_horiz ^ flip_vert ? board_size(b) - 1 - cx : cx;
 560                 if (flip_vert ? x < cy : x > cy) {
 561                         flip_diag = 1;
 562                 }
 563         }
 564
 565         if (DEBUGL(4)) {
 566                 fprintf(stderr, "%s [%d,%d -> %d,%d;%d,%d] will flip %d %d %d -> %s, sym %d (%d) -> %d (%d)\n",
 567                         coord2sstr(c, b),
 568                         cx, cy, s->x1, s->y1, s->x2, s->y2,
 569                         flip_horiz, flip_vert, flip_diag,
 570                         coord2sstr(flip_coord(b, c, flip_horiz, flip_vert, flip_diag), b),
 571                         s->type, s->d, b->symmetry.type, b->symmetry.d);
 572         }
 573         if (flip_horiz || flip_vert || flip_diag)
 574                 tree_fix_node_symmetry(b, tree->root, flip_horiz, flip_vert, flip_diag);
 575 }
 576
 577
 578 static void
 579 tree_unlink_node(struct tree_node *node)
 580 {
 581         struct tree_node *ni = node->parent;
 582         if (ni->children == node) {
 583                 ni->children = node->sibling;
 584         } else {
 585                 ni = ni->children;
 586                 while (ni->sibling != node)
 587                         ni = ni->sibling;
 588                 ni->sibling = node->sibling;
 589         }
 590         node->sibling = NULL;
 591         node->parent = NULL;
 592 }
 593
 594 void
 595 tree_promote_node(struct tree *tree, struct tree_node *node)
 596 {
 597         assert(node->parent == tree->root);
 598         tree_unlink_node(node);
 599         /* Freeing the rest of the tree can take several seconds on large
 600          * trees, so we must do it asynchronously: */
 601         tree_done_node_detached(tree, tree->root);
 602         tree->root = node;
 603         tree->root_color = stone_other(tree->root_color);
 604         board_symmetry_update(tree->board, &tree->root_symmetry, node->coord);
 605         tree->max_depth--;
 606         if (tree->chchvals) { free(tree->chchvals); tree->chchvals = NULL; }
 607         if (tree->chvals) { free(tree->chvals); tree->chvals = NULL; }
 608 }
 609
 610 bool
 611 tree_promote_at(struct tree *tree, struct board *b, coord_t c)
 612 {
 613         tree_fix_symmetry(tree, b, c);
 614
 615         for (struct tree_node *ni = tree->root->children; ni; ni = ni->sibling) {
 616                 if (ni->coord == c) {
 617                         tree_promote_node(tree, ni);
 618                         return true;
 619                 }
 620         }
 621         return false;
 622 }