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