uct/tree.h

   1 #ifndef ZZGO_UCT_TREE_H
   2 #define ZZGO_UCT_TREE_H
   3
   4 #include <stdbool.h>
   5 #include <pthread.h>
   6 #include "move.h"
   7 #include "stats.h"
   8 #include "probdist.h"
   9
  10 struct board;
  11 struct uct;
  12
  13 /*
  14  *            +------+
  15  *            | node |
  16  *            +------+
  17  *          / <- parent
  18  * +------+   v- sibling +------+
  19  * | node | ------------ | node |
  20  * +------+              +------+
  21  *    | <- children          |
  22  * +------+   +------+   +------+   +------+
  23  * | node | - | node |   | node | - | node |
  24  * +------+   +------+   +------+   +------+
  25  */
  26
  27 struct tree_node {
  28         hash_t hash;
  29         struct tree_node *parent, *sibling, *children;
  30
  31         /*** From here on, struct is saved/loaded from opening book */
  32
  33         int depth; // just for statistics
  34
  35         coord_t coord;
  36         /* Common Fate Graph distance from parent, but at most TREE_NODE_D_MAX+1 */
  37         int d;
  38 #define TREE_NODE_D_MAX 3
  39
  40         struct move_stats u;
  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;
  46
  47 #define TREE_HINT_INVALID 1 // don't go to this node, invalid move
  48         int hints;
  49
  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 */
  56         bool is_expanded;
  57 };
  58
  59 struct tree {
  60         struct board *board;
  61         struct tree_node *root;
  62         struct board_symmetry root_symmetry;
  63         enum stone root_color;
  64         float extra_komi;
  65
  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
  69
  70         // Statistics
  71         int max_depth;
  72         volatile unsigned long nodes_size; // byte size of all allocated nodes
  73 };
  74
  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);
  83
  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_promote_node(struct tree *tree, struct tree_node *node);
  88 bool tree_promote_at(struct tree *tree, struct board *b, coord_t c);
  89
  90 static bool tree_leaf_node(struct tree_node *node);
  91
  92 /* Get black parity from parity within the tree. */
  93 #define tree_parity(tree, parity) \
  94         (tree->root_color == S_WHITE ? (parity) : -1 * (parity))
  95
  96 /* Get a 0..1 value to maximize; @parity is parity within the tree. */
  97 #define tree_node_get_value(tree, parity, value) \
  98         (tree_parity(tree, parity) > 0 ? value : 1 - value)
  99
 100 static inline bool
 101 tree_leaf_node(struct tree_node *node)
 102 {
 103         return !(node->children);
 104 }
 105
 106 #endif