1 #ifndef ZZGO_UCT_TREE_H
2 #define ZZGO_UCT_TREE_H
4 /* Management of UCT trees. See diagram below for the node structure.
6 * Two allocation methods are supported for the tree nodes:
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.
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. */
42 * +------+ v- sibling +------+
43 * | node | ------------ | node |
46 * +------+ +------+ +------+ +------+
47 * | node | - | node | | node | - | node |
48 * +------+ +------+ +------+ +------+
53 struct tree_node
*parent
, *sibling
, *children
;
55 /*** From here on, struct is saved/loaded from opening book */
57 unsigned short depth
; // just for statistics
59 /* Common Fate Graph distance from parent, but at most TREE_NODE_D_MAX+1 */
60 #define TREE_NODE_D_MAX 3
63 #define TREE_HINT_INVALID 1 // don't go to this node, invalid move
66 /* In case multiple threads walk the tree, is_expanded is set
67 * atomically. Only the first thread setting it expands the node.
68 * The node goes through 3 states:
69 * 1) children == null, is_expanded == false: leaf node
70 * 2) children == null, is_expanded == true: one thread currently expanding
71 * 2) children != null, is_expanded == true: fully expanded node */
77 struct move_stats prior
;
78 /* XXX: Should be way for policies to add their own stats */
79 struct move_stats amaf
;
80 /* Stats before starting playout; used for distributed engine. */
81 struct move_stats pu
, pamaf
;
88 struct tree_node
*root
;
89 struct board_symmetry root_symmetry
;
90 enum stone root_color
;
92 /* Whether to use any extra komi during score counting. This is
93 * tree-specific variable since this can arbitrarily change between
96 /* The value of applied extra komi. For DYNKOMI_LINEAR, this value
97 * is only informative, the actual value is computed per simulation
98 * based on leaf node depth. */
101 /* We merge local (non-tenuki) sequences for both colors, occuring
102 * anywhere in the tree; nodes are created on-demand, special 'pass'
103 * nodes represent tenuki. Only u move_stats are used, prior and amaf
104 * is ignored. Values in root node are ignored. */
105 /* The values in the tree can be either "raw" or "tempered"
106 * (representing difference against parent node in the main tree),
107 * controlled by local_tree setting. */
108 struct tree_node
*ltree_black
;
109 // Of course even in white tree, winrates are from b's perspective
110 // as anywhere else. ltree_white has white-first sequences as children.
111 struct tree_node
*ltree_white
;
112 // Aging factor; 2 means halve all playout values after each turn.
113 // 1 means don't age at all.
116 /* Hash table used when working as slave for the distributed engine.
117 * Maps coordinate path to tree node. */
118 struct tree_hash
*htable
;
123 volatile unsigned long nodes_size
; // byte size of all allocated nodes
124 unsigned long max_tree_size
; // maximum byte size for entire tree, > 0 only for fast_alloc
125 void *nodes
; // nodes buffer, only for fast_alloc
128 /* Warning: all functions below except tree_expand_node & tree_leaf_node are THREAD-UNSAFE! */
129 struct tree
*tree_init(struct board
*board
, enum stone color
, unsigned long max_tree_size
, float ltree_aging
, int hbits
);
130 void tree_done(struct tree
*tree
);
131 void tree_dump(struct tree
*tree
, int thres
);
132 void tree_save(struct tree
*tree
, struct board
*b
, int thres
);
133 void tree_load(struct tree
*tree
, struct board
*b
);
135 struct tree_node
*tree_get_node(struct tree
*tree
, struct tree_node
*node
, coord_t c
, bool create
);
136 struct tree_node
*tree_garbage_collect(struct tree
*tree
, unsigned long max_size
, struct tree_node
*node
);
137 void tree_promote_node(struct tree
*tree
, struct tree_node
**node
);
138 bool tree_promote_at(struct tree
*tree
, struct board
*b
, coord_t c
);
140 void tree_expand_node(struct tree
*tree
, struct tree_node
*node
, struct board
*b
, enum stone color
, struct uct
*u
, int parity
);
141 struct tree_node
*tree_lnode_for_node(struct tree
*tree
, struct tree_node
*ni
, struct tree_node
*lni
, int tenuki_d
);
143 static bool tree_leaf_node(struct tree_node
*node
);
145 /* Get black parity from parity within the tree. */
146 #define tree_parity(tree, parity) \
147 (tree->root_color == S_WHITE ? (parity) : -1 * (parity))
149 /* Get a 0..1 value to maximize; @parity is parity within the tree. */
150 #define tree_node_get_value(tree, parity, value) \
151 (tree_parity(tree, parity) > 0 ? value : 1 - value)
154 tree_leaf_node(struct tree_node
*node
)
156 return !(node
->children
);
159 /* Leave always at least 10% memory free for the next move: */
160 #define MIN_FREE_MEM_PERCENT 10ULL