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         if (is_pass(node->coord)) {
 102                 node->prior.playouts += 0;
 103                 node->prior.wins += 10;
 104         }
 105
 106         /* Q_{even} */
 107         /* This may be dubious for normal UCB1 but is essential for
 108          * reading stability of RAVE, it appears. */
 109         if (pp->even_eqex) {
 110                 node->prior.playouts += pp->even_eqex;
 111                 node->prior.wins += pp->even_eqex / 2;
 112         }
 113
 114         /* Q_{grandparent} */
 115         if (pp->gp_eqex && node->parent && node->parent->parent && node->parent->parent->parent) {
 116                 struct tree_node *gpp = node->parent->parent->parent;
 117                 for (struct tree_node *ni = gpp->children; ni; ni = ni->sibling) {
 118                         /* Be careful not to emphasize too random results. */
 119                         if (ni->coord == node->coord && ni->u.playouts > pp->gp_eqex) {
 120                                 node->prior.playouts += pp->gp_eqex;
 121                                 node->prior.wins += pp->gp_eqex * ni->u.wins / ni->u.playouts;
 122                                 node->hints |= 1;
 123                         }
 124                 }
 125         }
 126
 127         /* Q_{playout-policy} */
 128         if (pp->policy_eqex) {
 129                 float assess = NAN;
 130                 struct playout_policy *playout = p->uct->playout;
 131                 if (playout->assess) {
 132                         struct move m = { node->coord, color };
 133                         assess = playout->assess(playout, b, &m);
 134                 }
 135                 if (!isnan(assess)) {
 136                         if (parity < 0) {
 137                                 /* Good moves for enemy are losses for us.
 138                                  * We will properly maximize this in the UCB1
 139                                  * decision. */
 140                                 assess = 1 - assess;
 141                         }
 142                         node->prior.playouts += pp->policy_eqex;
 143                         node->prior.wins += pp->policy_eqex * assess;
 144                         node->hints |= 2;
 145                 }
 146         }
 147
 148         if (node->prior.playouts) {
 149                 node->prior.value = (float) node->prior.wins / node->prior.playouts;
 150                 tree_update_node_value(node);
 151         }
 152
 153         //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);
 154 }
 155
 156 void
 157 ucb1_update(struct uct_policy *p, struct tree *tree, struct tree_node *node, enum stone node_color, enum stone player_color, struct playout_amafmap *map, int result)
 158 {
 159         /* It is enough to iterate by a single chain; we will
 160          * update all the preceding positions properly since
 161          * they had to all occur in all branches, only in
 162          * different order. */
 163         for (; node; node = node->parent) {
 164                 node->u.playouts++;
 165                 node->u.wins += result;
 166                 tree_update_node_value(node);
 167         }
 168 }
 169
 170
 171 struct uct_policy *
 172 policy_ucb1_init(struct uct *u, char *arg)
 173 {
 174         struct uct_policy *p = calloc(1, sizeof(*p));
 175         struct ucb1_policy *b = calloc(1, sizeof(*b));
 176         p->uct = u;
 177         p->data = b;
 178         p->descend = ucb1_descend;
 179         p->choose = ucb1_choose;
 180         p->update = ucb1_update;
 181
 182         b->explore_p = 0.2;
 183         b->fpu = INFINITY;
 184         b->even_eqex = 0;
 185         b->gp_eqex = b->policy_eqex = -1;
 186         b->eqex = 50;
 187
 188         if (arg) {
 189                 char *optspec, *next = arg;
 190                 while (*next) {
 191                         optspec = next;
 192                         next += strcspn(next, ":");
 193                         if (*next) { *next++ = 0; } else { *next = 0; }
 194
 195                         char *optname = optspec;
 196                         char *optval = strchr(optspec, '=');
 197                         if (optval) *optval++ = 0;
 198
 199                         if (!strcasecmp(optname, "explore_p") && optval) {
 200                                 b->explore_p = atof(optval);
 201                         } else if (!strcasecmp(optname, "prior")) {
 202                                 if (optval)
 203                                         b->eqex = atoi(optval);
 204                         } else if (!strcasecmp(optname, "prior_even") && optval) {
 205                                 b->even_eqex = atoi(optval);
 206                         } else if (!strcasecmp(optname, "prior_gp") && optval) {
 207                                 b->gp_eqex = atoi(optval);
 208                         } else if (!strcasecmp(optname, "prior_policy") && optval) {
 209                                 b->policy_eqex = atoi(optval);
 210                         } else if (!strcasecmp(optname, "fpu") && optval) {
 211                                 b->fpu = atof(optval);
 212                         } else if (!strcasecmp(optname, "urg_randoma") && optval) {
 213                                 b->urg_randoma = atoi(optval);
 214                         } else if (!strcasecmp(optname, "urg_randomm") && optval) {
 215                                 b->urg_randomm = atoi(optval);
 216                         } else {
 217                                 fprintf(stderr, "ucb1: Invalid policy argument %s or missing value\n", optname);
 218                         }
 219                 }
 220         }
 221
 222         if (b->eqex) p->prior = ucb1_prior;
 223         if (b->even_eqex < 0) b->even_eqex = b->eqex;
 224         if (b->gp_eqex < 0) b->gp_eqex = b->eqex;
 225         if (b->policy_eqex < 0) b->policy_eqex = b->eqex;
 226
 227         return p;
 228 }