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
  50         // Statistics
  51         int max_depth;
  52 };
  53
  54 struct tree *tree_init(struct board *board, enum stone color);
  55 void tree_done(struct tree *tree);
  56 void tree_dump(struct tree *tree, int thres);
  57 void tree_save(struct tree *tree, struct board *b, int thres);
  58 void tree_load(struct tree *tree, struct board *b);
  59 struct tree *tree_copy(struct tree *tree);
  60 void tree_merge(struct tree *dest, struct tree *src);
  61 void tree_normalize(struct tree *tree, int factor);
  62
  63 void tree_expand_node(struct tree *tree, struct tree_node *node, struct board *b, enum stone color, int radar, struct uct *u, int parity);
  64 void tree_delete_node(struct tree *tree, struct tree_node *node);
  65 void tree_promote_node(struct tree *tree, struct tree_node *node);
  66 bool tree_promote_at(struct tree *tree, struct board *b, coord_t c);
  67
  68 static bool tree_leaf_node(struct tree_node *node);
  69
  70 /* Get black parity from parity within the tree. */
  71 #define tree_parity(tree, parity) \
  72         (tree->root_color == S_WHITE ? (parity) : -1 * (parity))
  73
  74 /* Get a value to maximize; @parity is parity within the tree. */
  75 #define tree_node_get_value(tree, node, type, parity) \
  76         (tree_parity(tree, parity) > 0 ? node->type.value : 1 - node->type.value)
  77 #define tree_node_get_wins(tree, node, type, parity) \
  78         (tree_parity(tree, parity) > 0 ? node->type.wins : node->type.playouts - node->type.wins)
  79
  80 /* Recompute the value. */
  81 #define tree_node_update_value(node, type) stats_update_value(&(node)->type)
  82
  83 static inline bool
  84 tree_leaf_node(struct tree_node *node)
  85 {
  86         return !(node->children);
  87 }
  88
  89 #endif