uct/prior.c

   1 #include <assert.h>
   2 #include <math.h>
   3 #include <stdio.h>
   4 #include <stdlib.h>
   5 #include <string.h>
   6
   7 #include "board.h"
   8 #include "debug.h"
   9 #include "move.h"
  10 #include "random.h"
  11 #include "tactics.h"
  12 #include "uct/internal.h"
  13 #include "uct/prior.h"
  14 #include "uct/tree.h"
  15
  16 /* Applying heuristic values to the tree nodes, skewing the reading in
  17  * most interesting directions. */
  18
  19
  20 void
  21 uct_prior_even(struct uct *u, struct tree_node *node, struct prior_map *map)
  22 {
  23         /* Q_{even} */
  24         /* This may be dubious for normal UCB1 but is essential for
  25          * reading stability of RAVE, it appears. */
  26         foreach_point_and_pass(map->b) {
  27                 if (!map->consider[c])
  28                         continue;
  29                 add_prior_value(map, c, 0.5, u->even_eqex);
  30         } foreach_point_end;
  31 }
  32
  33 void
  34 uct_prior_eye(struct uct *u, struct tree_node *node, struct prior_map *map)
  35 {
  36         /* Discourage playing into our own eyes. However, we cannot
  37          * completely prohibit it:
  38          * #######
  39          * ...XX.#
  40          * XOOOXX#
  41          * X.OOOO#
  42          * .XXXX.# */
  43         foreach_point(map->b) {
  44                 if (!map->consider[c])
  45                         continue;
  46                 if (!board_is_one_point_eye(map->b, &c, map->to_play))
  47                         continue;
  48                 add_prior_value(map, c, 0, u->eqex);
  49         } foreach_point_end;
  50 }
  51
  52 void
  53 uct_prior_ko(struct uct *u, struct tree_node *node, struct prior_map *map)
  54 {
  55         /* Favor fighting ko, if we took it le 10 moves ago. */
  56         coord_t ko = map->b->last_ko.coord;
  57         if (is_pass(ko) || map->b->moves - map->b->last_ko_age > 10 || !map->consider[ko])
  58                 return;
  59         // fprintf(stderr, "prior ko-fight @ %s %s\n", stone2str(map->to_play), coord2sstr(ko, map->b));
  60         add_prior_value(map, ko, 1, u->eqex);
  61 }
  62
  63 void
  64 uct_prior_b19(struct uct *u, struct tree_node *node, struct prior_map *map)
  65 {
  66         /* Q_{b19} */
  67         /* Specific hints for 19x19 board - priors for certain edge distances. */
  68         foreach_point(map->b) {
  69                 if (!map->consider[c])
  70                         continue;
  71                 int d = coord_edge_distance(c, map->b);
  72                 if (d != 1 && d != 3)
  73                         continue;
  74                 /* The bonus applies only with no stones in immediate
  75                  * vincinity. */
  76                 if (board_stone_radar(map->b, c, 2))
  77                         continue;
  78                 /* First line: 0 */
  79                 /* Third line: 1 */
  80                 add_prior_value(map, c, d == 3, u->b19_eqex);
  81         } foreach_point_end;
  82 }
  83
  84 void
  85 uct_prior_grandparent(struct uct *u, struct tree_node *node, struct prior_map *map)
  86 {
  87         /* Q_{grandparent} */
  88         foreach_point_and_pass(map->b) {
  89                 if (!map->consider[c])
  90                         continue;
  91                 if (!node->parent || !node->parent->parent)
  92                         continue;
  93                 struct tree_node *gpp = node->parent->parent;
  94                 for (struct tree_node *ni = gpp->children; ni; ni = ni->sibling) {
  95                         /* Be careful not to emphasize too random results. */
  96                         if (ni->coord == node->coord && ni->u.playouts > u->gp_eqex) {
  97                                 /* We purposefuly ignore the parity. */
  98                                 stats_add_result(&map->prior[c], ni->u.value, u->gp_eqex);
  99                         }
 100                 }
 101         } foreach_point_end;
 102 }
 103
 104 void
 105 uct_prior_playout(struct uct *u, struct tree_node *node, struct prior_map *map)
 106 {
 107         /* Q_{playout-policy} */
 108         if (u->playout->assess)
 109                 u->playout->assess(u->playout, map, u->policy_eqex);
 110 }
 111
 112 void
 113 uct_prior_cfgd(struct uct *u, struct tree_node *node, struct prior_map *map)
 114 {
 115         /* Q_{common_fate_graph_distance} */
 116         /* Give bonus to moves local to the last move, where "local" means
 117          * local in terms of groups, not just manhattan distance. */
 118         if (is_pass(map->b->last_move.coord))
 119                 return;
 120
 121         int distances[board_size2(map->b)];
 122         cfg_distances(map->b, map->b->last_move.coord, distances, 3);
 123         foreach_point(map->b) {
 124                 if (!map->consider[c])
 125                         continue;
 126                 // fprintf(stderr, "distance %s-%s: %d\n", coord2sstr(map->b->last_move.coord, map->b), coord2sstr(c, map->b), distances[c]);
 127                 if (distances[c] > 3)
 128                         continue;
 129                 assert(distances[c] != 0);
 130                 int bonuses[] = { 0, u->cfgd_eqex, u->cfgd_eqex / 2, u->cfgd_eqex / 2 };
 131                 int bonus = bonuses[distances[c]];
 132                 add_prior_value(map, c, 1, bonus);
 133         } foreach_point_end;
 134 }
 135
 136 void
 137 uct_prior(struct uct *u, struct tree_node *node, struct prior_map *map)
 138 {
 139         if (u->even_eqex)
 140                 uct_prior_even(u, node, map);
 141         if (u->eye_eqex)
 142                 uct_prior_eye(u, node, map);
 143         if (u->ko_eqex)
 144                 uct_prior_ko(u, node, map);
 145         if (u->b19_eqex)
 146                 uct_prior_b19(u, node, map);
 147         if (u->gp_eqex)
 148                 uct_prior_grandparent(u, node, map);
 149         if (u->policy_eqex)
 150                 uct_prior_playout(u, node, map);
 151         if (u->cfgd_eqex)
 152                 uct_prior_cfgd(u, node, map);
 153 }