1 #ifndef ZZGO_UCT_TREE_H
2 #define ZZGO_UCT_TREE_H
18 * +------+ v- sibling +------+
19 * | node | ------------ | node |
22 * +------+ +------+ +------+ +------+
23 * | node | - | node | | node | - | node |
24 * +------+ +------+ +------+ +------+
29 struct tree_node
*parent
, *sibling
, *children
;
31 /*** From here on, struct is saved/loaded from opening book */
33 int depth
; // just for statistics
36 /* Common Fate Graph distance from parent, but at most TREE_NODE_D_MAX+1 */
38 #define TREE_NODE_D_MAX 3
41 struct move_stats prior
;
42 /* XXX: Should be way for policies to add their own stats */
43 struct move_stats amaf
;
44 /* Stats before starting playout; used for multi-thread normalization. */
45 struct move_stats pu
, pamaf
;
47 #define TREE_HINT_INVALID 1 // don't go to this node, invalid move
50 /* In case multiple threads walk the tree, is_expanded is set
51 * atomically. Only the first thread setting it expands the node.
52 * The node goes through 3 states:
53 * 1) children == null, is_expanded == false: leaf node
54 * 2) children == null, is_expanded == true: one thread currently expanding
55 * 2) children != null, is_expanded == true: fully expanded node */
61 struct tree_node
*root
;
62 struct board_symmetry root_symmetry
;
63 enum stone root_color
;
66 // Summary statistics of good black, white moves in the tree
67 struct move_stats
*chvals
; // [bsize2] root children
68 struct move_stats
*chchvals
; // [bsize2] root children's children
72 volatile unsigned long nodes_size
; // byte size of all allocated nodes
75 struct tree
*tree_init(struct board
*board
, enum stone color
);
76 void tree_done(struct tree
*tree
);
77 void tree_dump(struct tree
*tree
, int thres
);
78 void tree_save(struct tree
*tree
, struct board
*b
, int thres
);
79 void tree_load(struct tree
*tree
, struct board
*b
);
80 struct tree
*tree_copy(struct tree
*tree
);
81 void tree_merge(struct tree
*dest
, struct tree
*src
);
82 void tree_normalize(struct tree
*tree
, int factor
);
84 /* Warning: All these functions are THREAD-UNSAFE! */
85 struct tree_node
*tree_get_node(struct tree
*tree
, struct tree_node
*node
, coord_t c
, bool create
);
86 void tree_expand_node(struct tree
*tree
, struct tree_node
*node
, struct board
*b
, enum stone color
, struct uct
*u
, int parity
);
87 void tree_delete_node(struct tree
*tree
, struct tree_node
*node
);
88 void tree_promote_node(struct tree
*tree
, struct tree_node
*node
);
89 bool tree_promote_at(struct tree
*tree
, struct board
*b
, coord_t c
);
91 static bool tree_leaf_node(struct tree_node
*node
);
93 /* Get black parity from parity within the tree. */
94 #define tree_parity(tree, parity) \
95 (tree->root_color == S_WHITE ? (parity) : -1 * (parity))
97 /* Get a 0..1 value to maximize; @parity is parity within the tree. */
98 #define tree_node_get_value(tree, parity, value) \
99 (tree_parity(tree, parity) > 0 ? value : 1 - value)
102 tree_leaf_node(struct tree_node
*node
)
104 return !(node
->children
);