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, even_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         // XXX: Stack overflow danger on big boards?
 193         struct tree_node *nbest[256] = { node->children }; int nbests = 1;
 194         float best_urgency = -9999;
 195
 196         for (struct tree_node *ni = node->children; ni; ni = ni->sibling) {
 197                 /* Do not consider passing early. */
 198                 if (likely(!allow_pass) && unlikely(is_pass(ni->coord)))
 199                         continue;
 200
 201                 /* TODO: Exploration? */
 202
 203                 int ngames = ni->u.playouts;
 204                 int nwins = ni->u.wins;
 205                 int rgames = ni->amaf.playouts;
 206                 int rwins = ni->amaf.wins;
 207                 if (b->rave_prior) {
 208                         rgames += ni->prior.playouts;
 209                         rwins += ni->prior.wins;
 210                 } else {
 211                         ngames += ni->prior.playouts;
 212                         nwins += ni->prior.wins;
 213                 }
 214                 if (parity < 0) {
 215                         nwins = ngames - nwins;
 216                         rwins = rgames - rwins;
 217                 }
 218                 float nval = 0, rval = 0;
 219                 if (ngames) {
 220                         nval = (float) nwins / ngames;
 221                         if (b->explore_p > 0)
 222                                 nval += b->explore_p * conf / fast_sqrt(ngames);
 223                 }
 224                 if (rgames) {
 225                         rval = (float) rwins / rgames;
 226                         if (b->explore_p_rave > 0)
 227                                 rval += b->explore_p_rave * conf / fast_sqrt(rgames);
 228                 }
 229
 230                 /* XXX: We later compare urgency with best_urgency; this can
 231                  * be difficult given that urgency can be in register with
 232                  * higher precision than best_urgency, thus even though
 233                  * the numbers are in fact the same, urgency will be
 234                  * slightly higher (or lower). Thus, we declare urgency
 235                  * as volatile, attempting to force the compiler to keep
 236                  * everything as a float. Ideally, we should do some random
 237                  * __FLT_EPSILON__ magic instead. */
 238                 volatile float urgency;
 239                 if (ngames) {
 240                         if (rgames) {
 241                                 /* At the beginning, beta is at 1 and RAVE is used.
 242                                  * At b->equiv_rate, beta is at 1/3 and gets steeper on. */
 243                                 float beta = (float) rgames / (rgames + ngames + rave_coef * ngames * rgames);
 244 #if 0
 245                                 //if (node->coord == 7*11+4) // D7
 246                                 fprintf(stderr, "[beta %f = %d / (%d + %d + %f)]\n",
 247                                         beta, rgames, rgames, ngames, rave_coef * ngames * rgames);
 248 #endif
 249                                 urgency = beta * rval + (1 - beta) * nval;
 250                         } else {
 251                                 urgency = nval;
 252                         }
 253                 } else if (rgames) {
 254                         urgency = rval;
 255                 } else {
 256                         assert(!b->even_eqex);
 257                         urgency = b->fpu;
 258                 }
 259
 260 #if 0
 261                 struct board bb; bb.size = 11;
 262                 //if (node->coord == 7*11+4) // D7
 263                 fprintf(stderr, "%s<%lld>-%s<%lld> urgency %f (r %d / %d, n %d / %d)\n",
 264                         coord2sstr(ni->parent->coord, &bb), ni->parent->hash,
 265                         coord2sstr(ni->coord, &bb), ni->hash, urgency,
 266                         rwins, rgames, nwins, ngames);
 267 #endif
 268                 if (b->urg_randoma)
 269                         urgency += (float)(fast_random(b->urg_randoma) - b->urg_randoma / 2) / 1000;
 270                 if (b->urg_randomm)
 271                         urgency *= (float)(fast_random(b->urg_randomm) + 5) / b->urg_randomm;
 272
 273                 if (urgency > best_urgency)
 274                         best_urgency = urgency; nbests = 0;
 275                 if (urgency >= best_urgency)
 276                         nbest[nbests++] = ni;
 277         }
 278 #if 0
 279         struct board bb; bb.size = 11;
 280         fprintf(stderr, "[%s %d: ", coord2sstr(node->coord, &bb), nbests);
 281         for (int zz = 0; zz < nbests; zz++)
 282                 fprintf(stderr, "%s", coord2sstr(nbest[zz]->coord, &bb));
 283         fprintf(stderr, "]\n");
 284 #endif
 285         return nbest[fast_random(nbests)];
 286 }
 287
 288 static void
 289 update_node(struct uct_policy *p, struct tree_node *node, int result)
 290 {
 291         node->u.playouts++;
 292         node->u.wins += result;
 293         tree_update_node_value(node);
 294 }
 295 static void
 296 update_node_amaf(struct uct_policy *p, struct tree_node *node, int result)
 297 {
 298         node->amaf.playouts++;
 299         node->amaf.wins += result;
 300         tree_update_node_value(node);
 301 }
 302
 303 void
 304 ucb1amaf_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)
 305 {
 306         struct ucb1_policy_amaf *b = p->data;
 307         enum stone child_color = stone_other(node_color);
 308
 309 #if 0
 310         struct board bb; bb.size = 9+2;
 311         for (struct tree_node *ni = node; ni; ni = ni->parent)
 312                 fprintf(stderr, "%s ", coord2sstr(ni->coord, &bb));
 313         fprintf(stderr, "[color %d] update result %d (color %d)\n",
 314                         node_color, result, player_color);
 315 #endif
 316
 317         while (node) {
 318                 if (p->descend != ucb1_descend)
 319                         node->hints |= NODE_HINT_NOAMAF; /* Rave, different update function */
 320                 update_node(p, node, result);
 321                 if (amaf_nakade(map->map[node->coord]))
 322                         amaf_op(map->map[node->coord], -);
 323
 324                 /* This loop ignores symmetry considerations, but they should
 325                  * matter only at a point when AMAF doesn't help much. */
 326                 for (struct tree_node *ni = node->children; ni; ni = ni->sibling) {
 327                         assert(map->map[ni->coord] != S_OFFBOARD);
 328                         if (map->map[ni->coord] == S_NONE
 329                             || amaf_nakade(map->map[ni->coord]))
 330                                 continue;
 331
 332                         int nres = result;
 333                         if (map->map[ni->coord] != child_color) {
 334                                 if (!b->both_colors)
 335                                         continue;
 336                                 nres = !nres;
 337                         }
 338                         /* For child_color != player_color, we still want
 339                          * to record the result unmodified; in that case,
 340                          * we will correctly negate them at the descend phase. */
 341
 342                         if (p->descend != ucb1_descend)
 343                                 ni->hints |= NODE_HINT_NOAMAF; /* Rave, different update function */
 344                         update_node_amaf(p, ni, nres);
 345
 346 #if 0
 347                         fprintf(stderr, "* %s<%lld> -> %s<%lld> [%d %d => %d/%d]\n", coord2sstr(node->coord, &bb), node->hash, coord2sstr(ni->coord, &bb), ni->hash, player_color, child_color, result);
 348 #endif
 349                 }
 350
 351                 node = node->parent; child_color = stone_other(child_color);
 352         }
 353 }
 354
 355
 356 struct uct_policy *
 357 policy_ucb1amaf_init(struct uct *u, char *arg)
 358 {
 359         struct uct_policy *p = calloc(1, sizeof(*p));
 360         struct ucb1_policy_amaf *b = calloc(1, sizeof(*b));
 361         p->uct = u;
 362         p->data = b;
 363         p->descend = ucb1srave_descend;
 364         p->choose = ucb1_choose;
 365         p->update = ucb1amaf_update;
 366         p->wants_amaf = true;
 367
 368         // RAVE: 0.2vs0: 40% (+-7.3) 0.1vs0: 54.7% (+-3.5)
 369         b->explore_p = 0.1;
 370         b->explore_p_rave = -1;
 371         b->equiv_rave = 3000;
 372         b->fpu = INFINITY;
 373         // gp: 14 vs 0: 44% (+-3.5)
 374         b->gp_eqex = 0;
 375         b->even_eqex = b->policy_eqex = -1;
 376         b->eqex = 50;
 377
 378         if (arg) {
 379                 char *optspec, *next = arg;
 380                 while (*next) {
 381                         optspec = next;
 382                         next += strcspn(next, ":");
 383                         if (*next) { *next++ = 0; } else { *next = 0; }
 384
 385                         char *optname = optspec;
 386                         char *optval = strchr(optspec, '=');
 387                         if (optval) *optval++ = 0;
 388
 389                         if (!strcasecmp(optname, "explore_p")) {
 390                                 b->explore_p = atof(optval);
 391                         } else if (!strcasecmp(optname, "prior")) {
 392                                 if (optval)
 393                                         b->eqex = atoi(optval);
 394                         } else if (!strcasecmp(optname, "prior_even") && optval) {
 395                                 b->even_eqex = atoi(optval);
 396                         } else if (!strcasecmp(optname, "prior_gp") && optval) {
 397                                 b->gp_eqex = atoi(optval);
 398                         } else if (!strcasecmp(optname, "prior_policy") && optval) {
 399                                 b->policy_eqex = atoi(optval);
 400                         } else if (!strcasecmp(optname, "fpu") && optval) {
 401                                 b->fpu = atof(optval);
 402                         } else if (!strcasecmp(optname, "urg_randoma") && optval) {
 403                                 b->urg_randoma = atoi(optval);
 404                         } else if (!strcasecmp(optname, "urg_randomm") && optval) {
 405                                 b->urg_randomm = atoi(optval);
 406                         } else if (!strcasecmp(optname, "rave")) {
 407                                 if (optval && *optval == '0')
 408                                         p->descend = ucb1_descend;
 409                                 else if (optval && *optval == 'o')
 410                                         p->descend = ucb1orave_descend;
 411                                 else if (optval && *optval == 's')
 412                                         p->descend = ucb1srave_descend;
 413                         } else if (!strcasecmp(optname, "explore_p_rave") && optval) {
 414                                 b->explore_p_rave = atof(optval);
 415                         } else if (!strcasecmp(optname, "equiv_rave") && optval) {
 416                                 b->equiv_rave = atof(optval);
 417                         } else if (!strcasecmp(optname, "rave_prior")) {
 418                                 // 46% (+-3.5)
 419                                 b->rave_prior = true;
 420                         } else if (!strcasecmp(optname, "both_colors")) {
 421                                 b->both_colors = true;
 422                         } else {
 423                                 fprintf(stderr, "ucb1: Invalid policy argument %s or missing value\n", optname);
 424                         }
 425                 }
 426         }
 427
 428         if (b->eqex) p->prior = ucb1_prior;
 429         if (b->even_eqex < 0) b->even_eqex = b->eqex;
 430         if (b->gp_eqex < 0) b->gp_eqex = b->eqex;
 431         if (b->policy_eqex < 0) b->policy_eqex = b->eqex;
 432         if (b->explore_p_rave < 0) b->explore_p_rave = b->explore_p;
 433
 434         return p;
 435 }