uct/tree.h

   1 #ifndef ZZGO_UCT_TREE_H
   2 #define ZZGO_UCT_TREE_H
   3
   4 /* Management of UCT trees. See diagram below for the node structure.
   5  *
   6  * Two allocation methods are supported for the tree nodes:
   7  *
   8  * - calloc/free: each node is allocated with one calloc.
   9  *   After a move, all nodes except the subtree rooted at
  10  *   the played move are freed one by one with free().
  11  *   Since this can be very slow (seen 9s and loss on time because
  12  *   of this) the nodes are freed in a background thread.
  13  *   We still reserve enough memory for the next move in case
  14  *   the background thread doesn't free nodes fast enough.
  15  *
  16  * - fast_alloc: a large buffer is allocated once, and each
  17  *   node allocation takes some of this buffer. After a move
  18  *   is played, no memory if freed if the buffer still has
  19  *   enough free space. Otherwise the subtree rooted at the
  20  *   played move is copied to a temporary buffer, pruning it
  21  *   if necessary to fit in this small buffer. We copy by
  22  *   preference nodes with largest number of playouts.
  23  *   Then the temporary buffer is copied back to the original
  24  *   buffer, which has now plenty of space.
  25  *   Once the fast_alloc mode is proven reliable, the
  26  *   calloc/free method will be removed. */
  27
  28 #include <stdbool.h>
  29 #include <pthread.h>
  30 #include "move.h"
  31 #include "stats.h"
  32 #include "probdist.h"
  33
  34 struct board;
  35 struct uct;
  36
  37 /*
  38  *            +------+
  39  *            | node |
  40  *            +------+
  41  *          / <- parent
  42  * +------+   v- sibling +------+
  43  * | node | ------------ | node |
  44  * +------+              +------+
  45  *    | <- children          |
  46  * +------+   +------+   +------+   +------+
  47  * | node | - | node |   | node | - | node |
  48  * +------+   +------+   +------+   +------+
  49  */
  50
  51 struct tree_node {
  52         hash_t hash;
  53         struct tree_node *parent, *sibling, *children;
  54
  55         /*** From here on, struct is saved/loaded from opening book */
  56
  57         int depth; // just for statistics
  58
  59         coord_t coord;
  60         /* Common Fate Graph distance from parent, but at most TREE_NODE_D_MAX+1 */
  61         int d;
  62 #define TREE_NODE_D_MAX 3
  63
  64         struct move_stats u;
  65         struct move_stats prior;
  66         /* XXX: Should be way for policies to add their own stats */
  67         struct move_stats amaf;
  68         /* Stats before starting playout; used for multi-thread normalization. */
  69         struct move_stats pu, pamaf;
  70
  71 #define TREE_HINT_INVALID 1 // don't go to this node, invalid move
  72         int hints;
  73
  74         /* In case multiple threads walk the tree, is_expanded is set
  75          * atomically. Only the first thread setting it expands the node.
  76          * The node goes through 3 states:
  77          *   1) children == null, is_expanded == false: leaf node
  78          *   2) children == null, is_expanded == true: one thread currently expanding
  79          *   2) children != null, is_expanded == true: fully expanded node */
  80         bool is_expanded;
  81 };
  82
  83 struct tree {
  84         struct board *board;
  85         struct tree_node *root;
  86         struct board_symmetry root_symmetry;
  87         enum stone root_color;
  88         float extra_komi;
  89
  90         // Summary statistics of good black, white moves in the tree
  91         struct move_stats *chvals; // [bsize2] root children
  92         struct move_stats *chchvals; // [bsize2] root children's children
  93
  94         // Statistics
  95         int max_depth;
  96         volatile unsigned long nodes_size; // byte size of all allocated nodes
  97         unsigned long max_tree_size; // maximum byte size for entire tree, > 0 only for fast_alloc
  98         void *nodes; // nodes buffer, only for fast_alloc
  99 };
 100
 101 /* Warning: all functions below except tree_expand_node & tree_leaf_node are THREAD-UNSAFE! */
 102 struct tree *tree_init(struct board *board, enum stone color, unsigned long max_tree_size);
 103 void tree_done(struct tree *tree);
 104 void tree_dump(struct tree *tree, int thres);
 105 void tree_save(struct tree *tree, struct board *b, int thres);
 106 void tree_load(struct tree *tree, struct board *b);
 107 struct tree *tree_copy(struct tree *tree);
 108 void tree_merge(struct tree *dest, struct tree *src);
 109 void tree_normalize(struct tree *tree, int factor);
 110
 111 void tree_expand_node(struct tree *tree, struct tree_node *node, struct board *b, enum stone color, struct uct *u, int parity);
 112 void tree_promote_node(struct tree *tree, struct tree_node **node);
 113 bool tree_promote_at(struct tree *tree, struct board *b, coord_t c);
 114
 115 static bool tree_leaf_node(struct tree_node *node);
 116
 117 /* Get black parity from parity within the tree. */
 118 #define tree_parity(tree, parity) \
 119         (tree->root_color == S_WHITE ? (parity) : -1 * (parity))
 120
 121 /* Get a 0..1 value to maximize; @parity is parity within the tree. */
 122 #define tree_node_get_value(tree, parity, value) \
 123         (tree_parity(tree, parity) > 0 ? value : 1 - value)
 124
 125 static inline bool
 126 tree_leaf_node(struct tree_node *node)
 127 {
 128         return !(node->children);
 129 }
 130
 131 /* Leave always at least 10% memory free for the next move: */
 132 #define MIN_FREE_MEM_PERCENT 10
 133
 134 #endif