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