uct/tree.h

   1 #ifndef ZZGO_UCT_TREE_H
   2 #define ZZGO_UCT_TREE_H
   3
   4 #include <stdbool.h>
   5 #include "move.h"
   6 #include "stats.h"
   7
   8 struct board;
   9 struct uct;
  10
  11 /*
  12  *            +------+
  13  *            | node |
  14  *            +------+
  15  *          / <- parent
  16  * +------+   v- sibling +------+
  17  * | node | ------------ | node |
  18  * +------+              +------+
  19  *    | <- children          |
  20  * +------+   +------+   +------+   +------+
  21  * | node | - | node |   | node | - | node |
  22  * +------+   +------+   +------+   +------+
  23  */
  24
  25 struct tree_node {
  26         hash_t hash;
  27         struct tree_node *parent, *sibling, *children;
  28
  29         /*** From here on, struct is saved/loaded from opening book */
  30
  31         int depth; // just for statistics
  32
  33         coord_t coord;
  34
  35         struct move_stats u;
  36         struct move_stats prior;
  37         /* XXX: Should be way for policies to add their own stats */
  38         struct move_stats amaf;
  39         /* Stats before starting playout; used for multi-thread normalization. */
  40         struct move_stats pu, pamaf;
  41         int hints;
  42 };
  43
  44 struct tree {
  45         struct board *board;
  46         struct tree_node *root;
  47         struct board_symmetry root_symmetry;
  48         enum stone root_color;
  49         float extra_komi;
  50
  51         // Statistics
  52         int max_depth;
  53 };
  54
  55 struct tree *tree_init(struct board *board, enum stone color);
  56 void tree_done(struct tree *tree);
  57 void tree_dump(struct tree *tree, int thres);
  58 void tree_save(struct tree *tree, struct board *b, int thres);
  59 void tree_load(struct tree *tree, struct board *b);
  60 struct tree *tree_copy(struct tree *tree);
  61 void tree_merge(struct tree *dest, struct tree *src);
  62 void tree_normalize(struct tree *tree, int factor);
  63
  64 void tree_expand_node(struct tree *tree, struct tree_node *node, struct board *b, enum stone color, int radar, struct uct *u, int parity);
  65 void tree_delete_node(struct tree *tree, struct tree_node *node);
  66 void tree_promote_node(struct tree *tree, struct tree_node *node);
  67 bool tree_promote_at(struct tree *tree, struct board *b, coord_t c);
  68
  69 static bool tree_leaf_node(struct tree_node *node);
  70
  71 /* Get black parity from parity within the tree. */
  72 #define tree_parity(tree, parity) \
  73         (tree->root_color == S_WHITE ? (parity) : -1 * (parity))
  74
  75 /* Get a value to maximize; @parity is parity within the tree. */
  76 #define tree_node_get_value(tree, node, type, parity) \
  77         (tree_parity(tree, parity) > 0 ? node->type.value : 1 - node->type.value)
  78
  79 static inline bool
  80 tree_leaf_node(struct tree_node *node)
  81 {
  82         return !(node->children);
  83 }
  84
  85 #endif