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