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