uct/policy/ucb1.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 "uct/internal.h"
  12 #include "uct/tree.h"
  13
  14 /* This implements the basic UCB1 policy. */
  15
  16 struct ucb1_policy {
  17         /* This is what the Modification of UCT with Patterns in Monte Carlo Go
  18          * paper calls 'p'. Original UCB has this on 2, but this seems to
  19          * produce way too wide searches; reduce this to get deeper and
  20          * narrower readouts - try 0.2. */
  21         float explore_p;
  22         /* First Play Urgency - if set to less than infinity (the MoGo paper
  23          * above reports 1.0 as the best), new branches are explored only
  24          * if none of the existing ones has higher urgency than fpu. */
  25         float fpu;
  26         /* Equivalent experience for prior knowledge. MoGo paper recommends
  27          * 50 playouts per source. */
  28         int eqex, even_eqex, gp_eqex, policy_eqex;
  29         int urg_randoma, urg_randomm;
  30 };
  31
  32
  33 struct tree_node *
  34 ucb1_choose(struct uct_policy *p, struct tree_node *node, struct board *b, enum stone color)
  35 {
  36         struct tree_node *nbest = NULL;
  37         for (struct tree_node *ni = node->children; ni; ni = ni->sibling)
  38                 // we compare playouts and choose the best-explored
  39                 // child; comparing values is more brittle
  40                 if (!nbest || ni->u.playouts > nbest->u.playouts) {
  41                         /* Play pass only if we can afford scoring */
  42                         if (is_pass(ni->coord)) {
  43                                 float score = board_official_score(b);
  44                                 if (color == S_BLACK)
  45                                         score = -score;
  46                                 //fprintf(stderr, "%d score %f\n", color, score);
  47                                 if (score <= 0)
  48                                         continue;
  49                         }
  50                         nbest = ni;
  51                 }
  52         return nbest;
  53 }
  54
  55
  56 struct tree_node *
  57 ucb1_descend(struct uct_policy *p, struct tree *tree, struct tree_node *node, int parity, bool allow_pass)
  58 {
  59         /* We want to count in the prior stats here after all. Otherwise,
  60          * nodes with positive prior will get explored _LESS_ since the
  61          * urgency will be always higher; even with normal FPU because
  62          * of the explore coefficient. */
  63
  64         struct ucb1_policy *b = p->data;
  65         float xpl = log(node->u.playouts + node->prior.playouts) * b->explore_p;
  66
  67         struct tree_node *nbest = node->children;
  68         float best_urgency = -9999;
  69         for (struct tree_node *ni = node->children; ni; ni = ni->sibling) {
  70                 /* Do not consider passing early. */
  71                 if (likely(!allow_pass) && unlikely(is_pass(ni->coord)))
  72                         continue;
  73                 int uct_playouts = ni->u.playouts + ni->prior.playouts;
  74                 ni->prior.value = (float)ni->prior.wins / ni->prior.playouts;
  75                 float urgency = uct_playouts ? (parity > 0 ? ni->u.value : 1 - ni->u.value) + sqrt(xpl / uct_playouts) : b->fpu;
  76
  77 #if 0
  78                 {
  79                         struct board b2; b2.size = 9+2;
  80                         fprintf(stderr, "[%s -> %s] UCB1 urgency %f (%f + %f : %f)\n", coord2sstr(node->coord, &b2), coord2sstr(ni->coord, &b2), urgency, ni->u.value, sqrt(xpl / ni->u.playouts), b->fpu);
  81                 }
  82 #endif
  83                 if (b->urg_randoma)
  84                         urgency += (float)(fast_random(b->urg_randoma) - b->urg_randoma / 2) / 1000;
  85                 if (b->urg_randomm)
  86                         urgency *= (float)(fast_random(b->urg_randomm) + 5) / b->urg_randomm;
  87                 if (urgency > best_urgency) {
  88                         best_urgency = urgency;
  89                         nbest = ni;
  90                 }
  91         }
  92         return nbest;
  93 }
  94
  95 void
  96 ucb1_prior(struct uct_policy *p, struct tree *tree, struct tree_node *node, struct board *b, enum stone color, int parity)
  97 {
  98         /* Initialization of UCT values based on prior knowledge */
  99         struct ucb1_policy *pp = p->data;
 100
 101         /* Q_{even} */
 102         /* This may be dubious for normal UCB1 but is essential for
 103          * reading stability of RAVE, it appears. */
 104         if (pp->even_eqex) {
 105                 node->prior.playouts += pp->even_eqex;
 106                 node->prior.wins += pp->even_eqex / 2;
 107         }
 108
 109         /* Q_{grandparent} */
 110         if (pp->gp_eqex && node->parent && node->parent->parent && node->parent->parent->parent) {
 111                 struct tree_node *gpp = node->parent->parent->parent;
 112                 for (struct tree_node *ni = gpp->children; ni; ni = ni->sibling) {
 113                         /* Be careful not to emphasize too random results. */
 114                         if (ni->coord == node->coord && ni->u.playouts > pp->gp_eqex) {
 115                                 node->prior.playouts += pp->gp_eqex;
 116                                 node->prior.wins += pp->gp_eqex * ni->u.wins / ni->u.playouts;
 117                                 node->hints |= 1;
 118                         }
 119                 }
 120         }
 121
 122         /* Q_{playout-policy} */
 123         if (pp->policy_eqex) {
 124                 float assess = NAN;
 125                 struct playout_policy *playout = p->uct->playout;
 126                 if (playout->assess) {
 127                         struct move m = { node->coord, color };
 128                         assess = playout->assess(playout, b, &m);
 129                 }
 130                 if (!isnan(assess)) {
 131                         if (parity < 0) {
 132                                 /* Good moves for enemy are losses for us.
 133                                  * We will properly maximize this in the UCB1
 134                                  * decision. */
 135                                 assess = 1 - assess;
 136                         }
 137                         node->prior.playouts += pp->policy_eqex;
 138                         node->prior.wins += pp->policy_eqex * assess;
 139                         node->hints |= 2;
 140                 }
 141         }
 142
 143         if (node->prior.playouts) {
 144                 node->prior.value = (float) node->prior.wins / node->prior.playouts;
 145                 tree_update_node_value(node);
 146         }
 147
 148         //fprintf(stderr, "%s,%s prior: %d/%d = %f (%f)\n", coord2sstr(node->parent->coord, b), coord2sstr(node->coord, b), node->prior.wins, node->prior.playouts, node->prior.value, assess);
 149 }
 150
 151 void
 152 ucb1_update(struct uct_policy *p, struct tree *tree, struct tree_node *node, enum stone color, struct playout_amafmap *map, int result)
 153 {
 154         /* It is enough to iterate by a single chain; we will
 155          * update all the preceding positions properly since
 156          * they had to all occur in all branches, only in
 157          * different order. */
 158         for (; node; node = node->parent) {
 159                 node->u.playouts++;
 160                 node->u.wins += result;
 161                 tree_update_node_value(node);
 162         }
 163 }
 164
 165
 166 struct uct_policy *
 167 policy_ucb1_init(struct uct *u, char *arg)
 168 {
 169         struct uct_policy *p = calloc(1, sizeof(*p));
 170         struct ucb1_policy *b = calloc(1, sizeof(*b));
 171         p->uct = u;
 172         p->data = b;
 173         p->descend = ucb1_descend;
 174         p->choose = ucb1_choose;
 175         p->update = ucb1_update;
 176
 177         b->explore_p = 0.2;
 178         b->fpu = INFINITY;
 179         b->even_eqex = 0;
 180         b->gp_eqex = b->policy_eqex = -1;
 181         b->eqex = 50;
 182
 183         if (arg) {
 184                 char *optspec, *next = arg;
 185                 while (*next) {
 186                         optspec = next;
 187                         next += strcspn(next, ":");
 188                         if (*next) { *next++ = 0; } else { *next = 0; }
 189
 190                         char *optname = optspec;
 191                         char *optval = strchr(optspec, '=');
 192                         if (optval) *optval++ = 0;
 193
 194                         if (!strcasecmp(optname, "explore_p") && optval) {
 195                                 b->explore_p = atof(optval);
 196                         } else if (!strcasecmp(optname, "prior")) {
 197                                 if (optval)
 198                                         b->eqex = atoi(optval);
 199                         } else if (!strcasecmp(optname, "prior_even") && optval) {
 200                                 b->even_eqex = atoi(optval);
 201                         } else if (!strcasecmp(optname, "prior_gp") && optval) {
 202                                 b->gp_eqex = atoi(optval);
 203                         } else if (!strcasecmp(optname, "prior_policy") && optval) {
 204                                 b->policy_eqex = atoi(optval);
 205                         } else if (!strcasecmp(optname, "fpu") && optval) {
 206                                 b->fpu = atof(optval);
 207                         } else if (!strcasecmp(optname, "urg_randoma") && optval) {
 208                                 b->urg_randoma = atoi(optval);
 209                         } else if (!strcasecmp(optname, "urg_randomm") && optval) {
 210                                 b->urg_randomm = atoi(optval);
 211                         } else {
 212                                 fprintf(stderr, "ucb1: Invalid policy argument %s or missing value\n", optname);
 213                         }
 214                 }
 215         }
 216
 217         if (b->eqex) p->prior = ucb1_prior;
 218         if (b->even_eqex < 0) b->even_eqex = b->eqex;
 219         if (b->gp_eqex < 0) b->gp_eqex = b->eqex;
 220         if (b->policy_eqex < 0) b->policy_eqex = b->eqex;
 221
 222         return p;
 223 }