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