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