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