uct/tree.c

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