uct/tree.c

   1 #include <assert.h>
   2 #include <math.h>
   3 #include <stdio.h>
   4 #include <stdlib.h>
   5 #include <string.h>
   6
   7 #include "board.h"
   8 #include "debug.h"
   9 #include "engine.h"
  10 #include "move.h"
  11 #include "playout.h"
  12 #include "uct/internal.h"
  13 #include "uct/tree.h"
  14
  15
  16 static struct tree_node *
  17 tree_init_node(struct tree *t, coord_t coord, int depth)
  18 {
  19         struct tree_node *n = calloc(1, sizeof(*n));
  20         n->coord = coord;
  21         n->depth = depth;
  22         if (depth > t->max_depth)
  23                 t->max_depth = depth;
  24         return n;
  25 }
  26
  27 struct tree *
  28 tree_init(struct board *board, enum stone color)
  29 {
  30         struct tree *t = calloc(1, sizeof(*t));
  31         t->board = board;
  32         /* The root PASS move is only virtual, we never play it. */
  33         t->root = tree_init_node(t, pass, 0);
  34         return t;
  35 }
  36
  37
  38 static void
  39 tree_done_node(struct tree *t, struct tree_node *n)
  40 {
  41         struct tree_node *ni = n->children;
  42         while (ni) {
  43                 struct tree_node *nj = ni->sibling;
  44                 tree_done_node(t, ni);
  45                 ni = nj;
  46         }
  47         free(n);
  48 }
  49
  50 void
  51 tree_done(struct tree *t)
  52 {
  53         tree_done_node(t, t->root);
  54         free(t);
  55 }
  56
  57
  58 static void
  59 tree_node_dump(struct tree *tree, struct tree_node *node, int l)
  60 {
  61         for (int i = 0; i < l; i++) fputc(' ', stderr);
  62         fprintf(stderr, "[%s] %f (%d/%d playouts)\n", coord2sstr(node->coord, tree->board), node->value, node->wins, node->playouts);
  63
  64         /* Print nodes sorted by #playouts. */
  65
  66         struct tree_node *nbox[1000]; int nboxl = 0;
  67         for (struct tree_node *ni = node->children; ni; ni = ni->sibling)
  68                 if (ni->playouts > 500)
  69                         nbox[nboxl++] = ni;
  70
  71         while (true) {
  72                 int best = -1;
  73                 for (int i = 0; i < nboxl; i++)
  74                         if (nbox[i] && (best < 0 || nbox[i]->playouts > nbox[best]->playouts))
  75                                 best = i;
  76                 if (best < 0)
  77                         break;
  78                 tree_node_dump(tree, nbox[best], l + 1);
  79                 nbox[best] = NULL;
  80         }
  81 }
  82
  83 void
  84 tree_dump(struct tree *tree)
  85 {
  86         tree_node_dump(tree, tree->root, 0);
  87 }
  88
  89
  90 void
  91 tree_expand_node(struct tree *t, struct tree_node *node, struct board *b, enum stone color, int radar, struct uct_policy *policy)
  92 {
  93         struct tree_node *ni = tree_init_node(t, pass, node->depth + 1);
  94         ni->parent = node; node->children = ni;
  95
  96         /* The loop excludes the offboard margin. */
  97         for (int i = 1; i < t->board->size; i++) {
  98                 for (int j = 1; j < t->board->size; j++) {
  99                         coord_t c = coord_xy_otf(i, j, t->board);
 100                         if (board_at(b, c) != S_NONE)
 101                                 continue;
 102                         /* This looks very useful on large boards - weeds out huge amount of crufty moves. */
 103                         if (b->hash /* not empty board */ && radar && !board_stone_radar(b, c, radar))
 104                                 continue;
 105
 106                         struct tree_node *nj = tree_init_node(t, c, node->depth + 1);
 107                         nj->parent = node; ni->sibling = nj; ni = nj;
 108
 109                         if (policy->prior)
 110                                 policy->prior(policy, t, ni, b, color);
 111                 }
 112         }
 113 }
 114
 115 static void
 116 tree_unlink_node(struct tree_node *node)
 117 {
 118         struct tree_node *ni = node->parent;
 119         if (ni->children == node) {
 120                 ni->children = node->sibling;
 121         } else {
 122                 ni = ni->children;
 123                 while (ni->sibling != node)
 124                         ni = ni->sibling;
 125                 ni->sibling = node->sibling;
 126         }
 127 }
 128
 129 void
 130 tree_delete_node(struct tree *tree, struct tree_node *node)
 131 {
 132         tree_unlink_node(node);
 133         tree_done_node(tree, node);
 134 }
 135
 136 void
 137 tree_promote_node(struct tree *tree, struct tree_node *node)
 138 {
 139         assert(node->parent == tree->root);
 140         tree_unlink_node(node);
 141         tree_done_node(tree, tree->root);
 142         tree->root = node;
 143         node->parent = NULL;
 144 }
 145
 146 bool
 147 tree_leaf_node(struct tree_node *node)
 148 {
 149         return !(node->children);
 150 }