uct/policy/ucb1amaf.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 UCB1 policy with an extra AMAF heuristics. */
  15
  16 struct ucb1_policy_amaf {
  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         float explore_p_rave;
  31         int equiv_rave;
  32         bool rave_prior, both_colors;
  33 };
  34
  35
  36 struct tree_node *ucb1_choose(struct uct_policy *p, struct tree_node *node, struct board *b, enum stone color);
  37
  38 struct tree_node *ucb1_descend(struct uct_policy *p, struct tree *tree, struct tree_node *node, int parity, bool allow_pass);
  39
  40 void ucb1_prior(struct uct_policy *p, struct tree *tree, struct tree_node *node, struct board *b, enum stone color, int parity);
  41
  42
  43 /* Original RAVE function */
  44 struct tree_node *
  45 ucb1orave_descend(struct uct_policy *p, struct tree *tree, struct tree_node *node, int parity, bool allow_pass)
  46 {
  47         /* We want to count in the prior stats here after all. Otherwise,
  48          * nodes with positive prior will get explored _LESS_ since the
  49          * urgency will be always higher; even with normal FPU because
  50          * of the explore coefficient. */
  51
  52         struct ucb1_policy_amaf *b = p->data;
  53         float xpl = log(node->u.playouts + node->prior.playouts) * b->explore_p;
  54         float xpl_rave = log(node->amaf.playouts + (b->rave_prior ? node->prior.playouts : 0)) * b->explore_p_rave;
  55         float beta = sqrt((float)b->equiv_rave / (3 * (node->u.playouts + node->prior.playouts) + b->equiv_rave));
  56
  57         struct tree_node *nbest = node->children;
  58         float best_urgency = -9999;
  59         for (struct tree_node *ni = node->children; ni; ni = ni->sibling) {
  60                 /* Do not consider passing early. */
  61                 if (likely(!allow_pass) && unlikely(is_pass(ni->coord)))
  62                         continue;
  63                 int amaf_wins = ni->amaf.wins + (b->rave_prior ? ni->prior.wins : 0);
  64                 int amaf_playouts = ni->amaf.playouts + (b->rave_prior ? ni->prior.playouts : 0);
  65                 int uct_playouts = ni->u.playouts + ni->prior.playouts;
  66                 ni->amaf.value = (float)amaf_wins / amaf_playouts;
  67                 ni->prior.value = (float)ni->prior.wins / ni->prior.playouts;
  68                 float uctp = (parity > 0 ? ni->u.value : 1 - ni->u.value) + sqrt(xpl / uct_playouts);
  69                 float ravep = (parity > 0 ? ni->amaf.value : 1 - ni->amaf.value) + sqrt(xpl_rave / amaf_playouts);
  70                 float urgency = ni->u.playouts ? beta * ravep + (1 - beta) * uctp : b->fpu;
  71                 // fprintf(stderr, "uctp %f (uct %d/%d) ravep %f (xpl %f amaf %d/%d) beta %f => %f\n", uctp, ni->u.wins, ni->u.playouts, ravep, xpl_rave, amaf_wins, amaf_playouts, beta, urgency);
  72                 if (b->urg_randoma)
  73                         urgency += (float)(fast_random(b->urg_randoma) - b->urg_randoma / 2) / 1000;
  74                 if (b->urg_randomm)
  75                         urgency *= (float)(fast_random(b->urg_randomm) + 5) / b->urg_randomm;
  76                 if (urgency > best_urgency) {
  77                         best_urgency = urgency;
  78                         nbest = ni;
  79                 }
  80         }
  81         return nbest;
  82 }
  83
  84 float fast_sqrt(int x)
  85 {
  86         static const float table[] = {
  87                 0,
  88                 1,
  89                 1.41421356237309504880,
  90                 1.73205080756887729352,
  91                 2.00000000000000000000,
  92 #if 0
  93                 2.23606797749978969640,
  94                 2.44948974278317809819,
  95                 2.64575131106459059050,
  96                 2.82842712474619009760,
  97                 3.00000000000000000000,
  98                 3.16227766016837933199,
  99                 3.31662479035539984911,
 100                 3.46410161513775458705,
 101                 3.60555127546398929311,
 102                 3.74165738677394138558,
 103                 3.87298334620741688517,
 104                 4.00000000000000000000,
 105                 4.12310562561766054982,
 106                 4.24264068711928514640,
 107                 4.35889894354067355223,
 108                 4.47213595499957939281,
 109                 4.58257569495584000658,
 110                 4.69041575982342955456,
 111                 4.79583152331271954159,
 112                 4.89897948556635619639,
 113                 5.00000000000000000000,
 114                 5.09901951359278483002,
 115                 5.19615242270663188058,
 116                 5.29150262212918118100,
 117                 5.38516480713450403125,
 118                 5.47722557505166113456,
 119                 5.56776436283002192211,
 120                 5.65685424949238019520,
 121                 5.74456264653802865985,
 122                 5.83095189484530047087,
 123                 5.91607978309961604256,
 124                 6.00000000000000000000,
 125                 6.08276253029821968899,
 126                 6.16441400296897645025,
 127                 6.24499799839839820584,
 128                 6.32455532033675866399,
 129                 6.40312423743284868648,
 130                 6.48074069840786023096,
 131                 6.55743852430200065234,
 132                 6.63324958071079969822,
 133                 6.70820393249936908922,
 134                 6.78232998312526813906,
 135                 6.85565460040104412493,
 136                 6.92820323027550917410,
 137                 7.00000000000000000000,
 138                 7.07106781186547524400,
 139                 7.14142842854284999799,
 140                 7.21110255092797858623,
 141                 7.28010988928051827109,
 142                 7.34846922834953429459,
 143                 7.41619848709566294871,
 144                 7.48331477354788277116,
 145                 7.54983443527074969723,
 146                 7.61577310586390828566,
 147                 7.68114574786860817576,
 148                 7.74596669241483377035,
 149                 7.81024967590665439412,
 150                 7.87400787401181101968,
 151                 7.93725393319377177150,
 152 #endif
 153         };
 154         //printf("sqrt %d\n", x);
 155         if (x < sizeof(table) / sizeof(*table)) {
 156                 return table[x];
 157         } else {
 158                 return sqrt(x);
 159 #if 0
 160                 int y = 0;
 161                 int base = 1 << (sizeof(int) * 8 - 2);
 162                 if ((x & 0xFFFF0000) == 0) base >>= 16;
 163                 if ((x & 0xFF00FF00) == 0) base >>= 8;
 164                 if ((x & 0xF0F0F0F0) == 0) base >>= 4;
 165                 if ((x & 0xCCCCCCCC) == 0) base >>= 2;
 166                 // "base" starts at the highest power of four <= the argument.
 167
 168                 while (base > 0) {
 169                         if (x >= y + base) {
 170                                 x -= y + base;
 171                                 y += base << 1;
 172                         }
 173                         y >>= 1;
 174                         base >>= 2;
 175                 }
 176                 printf("sqrt %d = %d\n", x, y);
 177                 return y;
 178 #endif
 179         }
 180 }
 181
 182 /* Sylvain RAVE function */
 183 struct tree_node *
 184 ucb1srave_descend(struct uct_policy *p, struct tree *tree, struct tree_node *node, int parity, bool allow_pass)
 185 {
 186         struct ucb1_policy_amaf *b = p->data;
 187         float rave_coef = 1.0f / b->equiv_rave;
 188         float conf = 1.f;
 189         if (b->explore_p > 0 || b->explore_p_rave > 0)
 190                 conf = sqrt(log(node->u.playouts + node->prior.playouts));
 191
 192         struct tree_node *nbest = node->children;
 193         float best_urgency = -9999;
 194         for (struct tree_node *ni = node->children; ni; ni = ni->sibling) {
 195                 /* Do not consider passing early. */
 196                 if (likely(!allow_pass) && unlikely(is_pass(ni->coord)))
 197                         continue;
 198
 199                 /* TODO: Exploration? */
 200
 201                 int ngames = ni->u.playouts;
 202                 int nwins = ni->u.wins;
 203                 int rgames = ni->amaf.playouts;
 204                 int rwins = ni->amaf.wins;
 205                 if (b->rave_prior) {
 206                         rgames += ni->prior.playouts;
 207                         rwins += ni->prior.wins;
 208                 } else {
 209                         ngames += ni->prior.playouts;
 210                         nwins += ni->prior.wins;
 211                 }
 212                 if (parity < 0) {
 213                         nwins = ngames - nwins;
 214                         rwins = rgames - rwins;
 215                 }
 216                 float nval = 0, rval = 0;
 217                 if (ngames) {
 218                         nval = (float) nwins / ngames;
 219                         if (b->explore_p > 0)
 220                                 nval += b->explore_p * conf / fast_sqrt(ngames);
 221                 }
 222                 if (rgames) {
 223                         rval = (float) rwins / rgames;
 224                         if (b->explore_p_rave > 0)
 225                                 rval += b->explore_p_rave * conf / fast_sqrt(rgames);
 226                 }
 227
 228                 float urgency;
 229                 if (ngames) {
 230                         if (rgames) {
 231                                 /* At the beginning, beta is at 1 and RAVE is used.
 232                                  * At b->equiv_rate, beta is at 1/3 and gets steeper on. */
 233                                 float beta = (float) rgames / (rgames + ngames + rave_coef * ngames * rgames);
 234 #if 0
 235                                 fprintf(stderr, "[beta %f = %d / (%d + %d + %f)]\n",
 236                                         beta, rgames, rgames, ngames, rave_coef * ngames * rgames);
 237 #endif
 238                                 urgency = beta * rval + (1 - beta) * nval;
 239                         } else {
 240                                 urgency = nval;
 241                         }
 242                 } else if (rgames) {
 243                         urgency = rval;
 244                 } else {
 245                         urgency = parity < 0 ? 1 - b->fpu : b->fpu;
 246                 }
 247
 248 #if 0
 249                 struct board bb; bb.size = 11;
 250                 fprintf(stderr, "%s urgency %f (r %d / %d, n %d / %d)\n",
 251                         coord2sstr(ni->coord, &bb), urgency, rwins, rgames, nwins, ngames);
 252 #endif
 253                 if (b->urg_randoma)
 254                         urgency += (float)(fast_random(b->urg_randoma) - b->urg_randoma / 2) / 1000;
 255                 if (b->urg_randomm)
 256                         urgency *= (float)(fast_random(b->urg_randomm) + 5) / b->urg_randomm;
 257                 /* The >= is important since we will always choose something
 258                  * else than a pass in case of a tie. pass causes degenerative
 259                  * behaviour. */
 260                 if (urgency >= best_urgency) {
 261                         best_urgency = urgency;
 262                         nbest = ni;
 263                 }
 264         }
 265         return nbest;
 266 }
 267
 268 static void
 269 update_node(struct uct_policy *p, struct tree_node *node, int result)
 270 {
 271         node->u.playouts++;
 272         node->u.wins += result;
 273         tree_update_node_value(node);
 274 }
 275 static void
 276 update_node_amaf(struct uct_policy *p, struct tree_node *node, int result)
 277 {
 278         node->amaf.playouts++;
 279         node->amaf.wins += result;
 280         tree_update_node_value(node);
 281 }
 282
 283 void
 284 ucb1amaf_update(struct uct_policy *p, struct tree *tree, struct tree_node *node, enum stone color, struct playout_amafmap *map, int result)
 285 {
 286         struct ucb1_policy_amaf *b = p->data;
 287
 288         color = stone_other(color); // We will look in CHILDREN of the node!
 289         for (; node; node = node->parent, color = stone_other(color)) {
 290                 if (p->descend != ucb1_descend)
 291                         node->hints |= NODE_HINT_NOAMAF; /* Rave, different update function */
 292                 update_node(p, node, result);
 293                 /* This loop ignores symmetry considerations, but they should
 294                  * matter only at a point when AMAF doesn't help much. */
 295                 for (struct tree_node *ni = node->children; ni; ni = ni->sibling) {
 296                         assert(map->map[ni->coord] != S_OFFBOARD);
 297                         if (map->map[ni->coord] == S_NONE)
 298                                 continue;
 299 #if 0
 300                         struct board bb; bb.size = 9+2;
 301                         fprintf(stderr, "%s -> %s [%d %d => %d]\n", coord2sstr(node->coord, &bb), coord2sstr(ni->coord, &bb), map->map[ni->coord], color, result);
 302 #endif
 303                         if (b->both_colors) {
 304                                 update_node_amaf(p, ni, map->map[ni->coord] == color ? result : !result);
 305                         } else if (map->map[ni->coord] == color) {
 306                                 update_node_amaf(p, ni, result);
 307                         }
 308                 }
 309         }
 310 }
 311
 312
 313 struct uct_policy *
 314 policy_ucb1amaf_init(struct uct *u, char *arg)
 315 {
 316         struct uct_policy *p = calloc(1, sizeof(*p));
 317         struct ucb1_policy_amaf *b = calloc(1, sizeof(*b));
 318         p->uct = u;
 319         p->data = b;
 320         p->descend = ucb1srave_descend;
 321         p->choose = ucb1_choose;
 322         p->update = ucb1amaf_update;
 323         p->wants_amaf = true;
 324
 325         // RAVE: 0.2vs0: 40% (+-7.3) 0.1vs0: 54.7% (+-3.5)
 326         b->explore_p = 0.1;
 327         b->explore_p_rave = -1;
 328         b->equiv_rave = 3000;
 329         b->fpu = INFINITY;
 330         b->gp_eqex = b->policy_eqex = -1;
 331         b->eqex = 50;
 332
 333         if (arg) {
 334                 char *optspec, *next = arg;
 335                 while (*next) {
 336                         optspec = next;
 337                         next += strcspn(next, ":");
 338                         if (*next) { *next++ = 0; } else { *next = 0; }
 339
 340                         char *optname = optspec;
 341                         char *optval = strchr(optspec, '=');
 342                         if (optval) *optval++ = 0;
 343
 344                         if (!strcasecmp(optname, "explore_p")) {
 345                                 b->explore_p = atof(optval);
 346                         } else if (!strcasecmp(optname, "prior")) {
 347                                 if (optval)
 348                                         b->eqex = atoi(optval);
 349                         } else if (!strcasecmp(optname, "prior_gp") && optval) {
 350                                 b->gp_eqex = atoi(optval);
 351                         } else if (!strcasecmp(optname, "prior_policy") && optval) {
 352                                 b->policy_eqex = atoi(optval);
 353                         } else if (!strcasecmp(optname, "fpu") && optval) {
 354                                 b->fpu = atof(optval);
 355                         } else if (!strcasecmp(optname, "urg_randoma") && optval) {
 356                                 b->urg_randoma = atoi(optval);
 357                         } else if (!strcasecmp(optname, "urg_randomm") && optval) {
 358                                 b->urg_randomm = atoi(optval);
 359                         } else if (!strcasecmp(optname, "rave")) {
 360                                 if (optval && *optval == '0')
 361                                         p->descend = ucb1_descend;
 362                                 else if (optval && *optval == 'o')
 363                                         p->descend = ucb1orave_descend;
 364                                 else if (optval && *optval == 's')
 365                                         p->descend = ucb1srave_descend;
 366                         } else if (!strcasecmp(optname, "explore_p_rave") && optval) {
 367                                 b->explore_p_rave = atof(optval);
 368                         } else if (!strcasecmp(optname, "equiv_rave") && optval) {
 369                                 b->equiv_rave = atof(optval);
 370                         } else if (!strcasecmp(optname, "rave_prior")) {
 371                                 b->rave_prior = true;
 372                         } else if (!strcasecmp(optname, "both_colors")) {
 373                                 b->both_colors = true;
 374                         } else {
 375                                 fprintf(stderr, "ucb1: Invalid policy argument %s or missing value\n", optname);
 376                         }
 377                 }
 378         }
 379
 380         if (b->eqex) p->prior = ucb1_prior;
 381         if (b->gp_eqex < 0) b->gp_eqex = b->eqex;
 382         if (b->policy_eqex < 0) b->policy_eqex = b->eqex;
 383         if (b->explore_p_rave < 0) b->explore_p_rave = b->explore_p;
 384
 385         return p;
 386 }