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/plugins.h"
  14 #include "uct/prior.h"
  15 #include "uct/tree.h"
  16
  17 /* Applying heuristic values to the tree nodes, skewing the reading in
  18  * most interesting directions. */
  19
  20 /* TODO: Introduce foreach_fpoint() to iterate only over non-occupied
  21  * positions. */
  22
  23 struct uct_prior {
  24         /* Equivalent experience for prior knowledge. MoGo paper recommends
  25          * 50 playouts per source; in practice, esp. with RAVE, about 6
  26          * playouts per source seems best. */
  27         int eqex;
  28         int even_eqex, policy_eqex, b19_eqex, eye_eqex, ko_eqex, plugin_eqex;
  29         int cfgdn; int *cfgd_eqex;
  30 };
  31
  32 void
  33 uct_prior_even(struct uct *u, struct tree_node *node, struct prior_map *map)
  34 {
  35         /* Q_{even} */
  36         /* This may be dubious for normal UCB1 but is essential for
  37          * reading stability of RAVE, it appears. */
  38         foreach_point_and_pass(map->b) {
  39                 if (!map->consider[c])
  40                         continue;
  41                 add_prior_value(map, c, 0.5, u->prior->even_eqex);
  42         } foreach_point_end;
  43 }
  44
  45 void
  46 uct_prior_eye(struct uct *u, struct tree_node *node, struct prior_map *map)
  47 {
  48         /* Discourage playing into our own eyes. However, we cannot
  49          * completely prohibit it:
  50          * #######
  51          * ...XX.#
  52          * XOOOXX#
  53          * X.OOOO#
  54          * .XXXX.# */
  55         foreach_point(map->b) {
  56                 if (!map->consider[c])
  57                         continue;
  58                 if (!board_is_one_point_eye(map->b, c, map->to_play))
  59                         continue;
  60                 add_prior_value(map, c, 0, u->prior->eye_eqex);
  61         } foreach_point_end;
  62 }
  63
  64 void
  65 uct_prior_ko(struct uct *u, struct tree_node *node, struct prior_map *map)
  66 {
  67         /* Favor fighting ko, if we took it le 10 moves ago. */
  68         coord_t ko = map->b->last_ko.coord;
  69         if (is_pass(ko) || map->b->moves - map->b->last_ko_age > 10 || !map->consider[ko])
  70                 return;
  71         // fprintf(stderr, "prior ko-fight @ %s %s\n", stone2str(map->to_play), coord2sstr(ko, map->b));
  72         add_prior_value(map, ko, 1, u->prior->ko_eqex);
  73 }
  74
  75 void
  76 uct_prior_b19(struct uct *u, struct tree_node *node, struct prior_map *map)
  77 {
  78         /* Q_{b19} */
  79         /* Specific hints for 19x19 board - priors for certain edge distances. */
  80         foreach_point(map->b) {
  81                 if (!map->consider[c])
  82                         continue;
  83                 int d = coord_edge_distance(c, map->b);
  84                 if (d != 0 && d != 2)
  85                         continue;
  86                 /* The bonus applies only with no stones in immediate
  87                  * vincinity. */
  88                 if (board_stone_radar(map->b, c, 2))
  89                         continue;
  90                 /* First line: 0 */
  91                 /* Third line: 1 */
  92                 add_prior_value(map, c, d == 2, u->prior->b19_eqex);
  93         } foreach_point_end;
  94 }
  95
  96 void
  97 uct_prior_playout(struct uct *u, struct tree_node *node, struct prior_map *map)
  98 {
  99         /* Q_{playout-policy} */
 100         if (u->playout->assess)
 101                 u->playout->assess(u->playout, map, u->prior->policy_eqex);
 102 }
 103
 104 void
 105 uct_prior_cfgd(struct uct *u, struct tree_node *node, struct prior_map *map)
 106 {
 107         /* Q_{common_fate_graph_distance} */
 108         /* Give bonus to moves local to the last move, where "local" means
 109          * local in terms of groups, not just manhattan distance. */
 110         if (is_pass(map->b->last_move.coord) || is_resign(map->b->last_move.coord))
 111                 return;
 112
 113         foreach_point(map->b) {
 114                 if (!map->consider[c])
 115                         continue;
 116                 if (map->distances[c] > u->prior->cfgdn)
 117                         continue;
 118                 assert(map->distances[c] != 0);
 119                 int bonus = u->prior->cfgd_eqex[map->distances[c]];
 120                 add_prior_value(map, c, 1, bonus);
 121         } foreach_point_end;
 122 }
 123
 124 void
 125 uct_prior(struct uct *u, struct tree_node *node, struct prior_map *map)
 126 {
 127         if (u->prior->even_eqex)
 128                 uct_prior_even(u, node, map);
 129         if (u->prior->eye_eqex)
 130                 uct_prior_eye(u, node, map);
 131         if (u->prior->ko_eqex)
 132                 uct_prior_ko(u, node, map);
 133         if (u->prior->b19_eqex)
 134                 uct_prior_b19(u, node, map);
 135         if (u->prior->policy_eqex)
 136                 uct_prior_playout(u, node, map);
 137         if (u->prior->cfgd_eqex)
 138                 uct_prior_cfgd(u, node, map);
 139         if (u->prior->plugin_eqex)
 140                 plugin_prior(u->plugins, node, map, u->prior->plugin_eqex);
 141 }
 142
 143 struct uct_prior *
 144 uct_prior_init(char *arg, struct board *b)
 145 {
 146         struct uct_prior *p = calloc2(1, sizeof(struct uct_prior));
 147
 148         p->even_eqex = p->policy_eqex = p->b19_eqex = p->eye_eqex = p->ko_eqex = p->plugin_eqex = -1;
 149         p->cfgdn = -1;
 150
 151         /* Even number! */
 152         p->eqex = board_size(b)-2 >= 19 ? 20 : 14;
 153
 154         if (arg) {
 155                 char *optspec, *next = arg;
 156                 while (*next) {
 157                         optspec = next;
 158                         next += strcspn(next, ":");
 159                         if (*next) { *next++ = 0; } else { *next = 0; }
 160
 161                         char *optname = optspec;
 162                         char *optval = strchr(optspec, '=');
 163                         if (optval) *optval++ = 0;
 164
 165                         if (!strcasecmp(optname, "eqex") && optval) {
 166                                 p->eqex = atoi(optval);
 167
 168                         /* In the following settings, you can use -1 to
 169                          * set the prior to default eqex, or -2 to set
 170                          * it to the half of the default eqex. */
 171                         } else if (!strcasecmp(optname, "even") && optval) {
 172                                 p->even_eqex = atoi(optval);
 173                         } else if (!strcasecmp(optname, "policy") && optval) {
 174                                 p->policy_eqex = atoi(optval);
 175                         } else if (!strcasecmp(optname, "b19") && optval) {
 176                                 p->b19_eqex = atoi(optval);
 177                         } else if (!strcasecmp(optname, "cfgd") && optval) {
 178                                 /* cfgd=3%40%20%20 - 3 levels; immediate libs
 179                                  * of last move => 40 wins, their neighbors
 180                                  * 20 wins, 2nd-level neighbors 20 wins;
 181                                  * neighbors are group-transitive. */
 182                                 p->cfgdn = atoi(optval); optval += strcspn(optval, ":");
 183                                 p->cfgd_eqex = calloc2(p->cfgdn + 1, sizeof(*p->cfgd_eqex));
 184                                 p->cfgd_eqex[0] = 0;
 185                                 for (int i = 1; *optval; i++, optval += strcspn(optval, ":")) {
 186                                         optval++;
 187                                         p->cfgd_eqex[i] = atoi(optval);
 188                                 }
 189                         } else if (!strcasecmp(optname, "eye") && optval) {
 190                                 p->eye_eqex = atoi(optval);
 191                         } else if (!strcasecmp(optname, "ko") && optval) {
 192                                 p->ko_eqex = atoi(optval);
 193                         } else if (!strcasecmp(optname, "plugin") && optval) {
 194                                 /* Unlike others, this is just a *recommendation*. */
 195                                 p->plugin_eqex = atoi(optval);
 196                         } else {
 197                                 fprintf(stderr, "uct: Invalid prior argument %s or missing value\n", optname);
 198                                 exit(1);
 199                         }
 200                 }
 201         }
 202
 203         if (p->even_eqex < 0) p->even_eqex = p->eqex / -p->even_eqex;
 204         if (p->policy_eqex < 0) p->policy_eqex = p->eqex / -p->policy_eqex;
 205         if (p->b19_eqex < 0) p->b19_eqex = p->eqex / -p->b19_eqex;
 206         if (p->eye_eqex < 0) p->eye_eqex = p->eqex / -p->eye_eqex;
 207         if (p->ko_eqex < 0) p->ko_eqex = p->eqex / -p->ko_eqex;
 208         if (p->plugin_eqex < 0) p->plugin_eqex = p->eqex / -p->plugin_eqex;
 209
 210         if (p->cfgdn < 0) {
 211                 int bonuses[] = { 0, p->eqex, p->eqex / 2, p->eqex / 2 };
 212                 p->cfgdn = 3;
 213                 p->cfgd_eqex = calloc2(p->cfgdn + 1, sizeof(*p->cfgd_eqex));
 214                 memcpy(p->cfgd_eqex, bonuses, sizeof(bonuses));
 215         }
 216         if (p->cfgdn > TREE_NODE_D_MAX) {
 217                 fprintf(stderr, "uct: CFG distances only up to %d available\n", TREE_NODE_D_MAX);
 218                 exit(1);
 219         }
 220
 221         return p;
 222 }
 223
 224 void
 225 uct_prior_done(struct uct_prior *p)
 226 {
 227         assert(p->cfgd_eqex);
 228         free(p->cfgd_eqex);
 229         free(p);
 230 }