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 "tactics/util.h"
  12 #include "uct/internal.h"
  13 #include "uct/tree.h"
  14 #include "uct/policy/generic.h"
  15
  16 /* This implements the UCB1 policy with an extra AMAF heuristics. */
  17
  18 struct ucb1_policy_amaf {
  19         /* This is what the Modification of UCT with Patterns in Monte Carlo Go
  20          * paper calls 'p'. Original UCB has this on 2, but this seems to
  21          * produce way too wide searches; reduce this to get deeper and
  22          * narrower readouts - try 0.2. */
  23         floating_t explore_p;
  24         /* In distributed mode, encourage different slaves to work on different
  25          * parts of the tree by adding virtual wins to different nodes. */
  26         int virtual_win;
  27         int root_virtual_win;
  28         int vwin_min_playouts;
  29         /* First Play Urgency - if set to less than infinity (the MoGo paper
  30          * above reports 1.0 as the best), new branches are explored only
  31          * if none of the existing ones has higher urgency than fpu. */
  32         floating_t fpu;
  33         unsigned int equiv_rave;
  34         bool check_nakade;
  35         bool sylvain_rave;
  36         /* Coefficient of local tree values embedded in RAVE. */
  37         floating_t ltree_rave;
  38         /* Coefficient of criticality embedded in RAVE. */
  39         floating_t crit_rave;
  40         int crit_min_playouts;
  41         bool crit_negative;
  42         bool crit_negflip;
  43         bool crit_amaf;
  44         bool crit_lvalue;
  45 };
  46
  47
  48 static inline floating_t fast_sqrt(unsigned int x)
  49 {
  50         static const floating_t table[] = {
  51                 0, 1, 1.41421356237309504880, 1.73205080756887729352,
  52                 2.00000000000000000000, 2.23606797749978969640,
  53                 2.44948974278317809819, 2.64575131106459059050,
  54                 2.82842712474619009760, 3.00000000000000000000,
  55                 3.16227766016837933199, 3.31662479035539984911,
  56                 3.46410161513775458705, 3.60555127546398929311,
  57                 3.74165738677394138558, 3.87298334620741688517,
  58                 4.00000000000000000000, 4.12310562561766054982,
  59                 4.24264068711928514640, 4.35889894354067355223,
  60                 4.47213595499957939281, 4.58257569495584000658,
  61                 4.69041575982342955456, 4.79583152331271954159,
  62                 4.89897948556635619639, 5.00000000000000000000,
  63                 5.09901951359278483002, 5.19615242270663188058,
  64                 5.29150262212918118100, 5.38516480713450403125,
  65                 5.47722557505166113456, 5.56776436283002192211,
  66                 5.65685424949238019520, 5.74456264653802865985,
  67                 5.83095189484530047087, 5.91607978309961604256,
  68                 6.00000000000000000000, 6.08276253029821968899,
  69                 6.16441400296897645025, 6.24499799839839820584,
  70                 6.32455532033675866399, 6.40312423743284868648,
  71                 6.48074069840786023096, 6.55743852430200065234,
  72                 6.63324958071079969822, 6.70820393249936908922,
  73                 6.78232998312526813906, 6.85565460040104412493,
  74                 6.92820323027550917410, 7.00000000000000000000,
  75                 7.07106781186547524400, 7.14142842854284999799,
  76                 7.21110255092797858623, 7.28010988928051827109,
  77                 7.34846922834953429459, 7.41619848709566294871,
  78                 7.48331477354788277116, 7.54983443527074969723,
  79                 7.61577310586390828566, 7.68114574786860817576,
  80                 7.74596669241483377035, 7.81024967590665439412,
  81                 7.87400787401181101968, 7.93725393319377177150,
  82         };
  83         if (x < sizeof(table) / sizeof(*table)) {
  84                 return table[x];
  85         } else {
  86                 return sqrt(x);
  87         }
  88 }
  89
  90 #define URAVE_DEBUG if (0)
  91 static floating_t inline
  92 ucb1rave_evaluate(struct uct_policy *p, struct tree *tree, struct uct_descent *descent, int parity)
  93 {
  94         struct ucb1_policy_amaf *b = p->data;
  95         struct tree_node *node = descent->node;
  96         struct tree_node *lnode = descent->lnode;
  97
  98         struct move_stats n = node->u, r = node->amaf;
  99         if (p->uct->amaf_prior) {
 100                 stats_merge(&r, &node->prior);
 101         } else {
 102                 stats_merge(&n, &node->prior);
 103         }
 104
 105         /* Local tree heuristics. */
 106         assert(!lnode || lnode->parent);
 107         if (p->uct->local_tree && b->ltree_rave > 0 && lnode
 108             && (p->uct->local_tree_rootchoose || lnode->parent->parent)) {
 109                 struct move_stats l = lnode->u;
 110                 l.playouts = ((floating_t) l.playouts) * b->ltree_rave / LTREE_PLAYOUTS_MULTIPLIER;
 111                 URAVE_DEBUG fprintf(stderr, "[ltree] adding [%s] %f%%%d to [%s] RAVE %f%%%d\n",
 112                         coord2sstr(node_coord(lnode), tree->board), l.value, l.playouts,
 113                         coord2sstr(node_coord(node), tree->board), r.value, r.playouts);
 114                 stats_merge(&r, &l);
 115         }
 116
 117         /* Criticality heuristics. */
 118         if (b->crit_rave > 0 && node->u.playouts > b->crit_min_playouts) {
 119                 floating_t crit = tree_node_criticality(tree, node);
 120                 if (b->crit_negative || crit > 0) {
 121                         floating_t val = 1.0f;
 122                         if (b->crit_negflip && crit < 0) {
 123                                 val = 0;
 124                                 crit = -crit;
 125                         }
 126                         struct move_stats c = {
 127                                 .value = tree_node_get_value(tree, parity, val),
 128                                 .playouts = crit * r.playouts * b->crit_rave
 129                         };
 130                         URAVE_DEBUG fprintf(stderr, "[crit] adding %f%%%d to [%s] RAVE %f%%%d\n",
 131                                 c.value, c.playouts,
 132                                 coord2sstr(node_coord(node), tree->board), r.value, r.playouts);
 133                         stats_merge(&r, &c);
 134                 }
 135         }
 136
 137
 138         floating_t value = 0;
 139         if (n.playouts) {
 140                 if (r.playouts) {
 141                         /* At the beginning, beta is at 1 and RAVE is used.
 142                          * At b->equiv_rate, beta is at 1/3 and gets steeper on. */
 143                         floating_t beta;
 144                         if (b->sylvain_rave) {
 145                                 beta = (floating_t) r.playouts / (r.playouts + n.playouts
 146                                         + (floating_t) n.playouts * r.playouts / b->equiv_rave);
 147                         } else {
 148                                 /* XXX: This can be cached in descend; but we don't use this by default. */
 149                                 beta = sqrt(b->equiv_rave / (3 * node->parent->u.playouts + b->equiv_rave));
 150                         }
 151
 152                         value = beta * r.value + (1.f - beta) * n.value;
 153                         URAVE_DEBUG fprintf(stderr, "\t%s value = %f * %f + (1 - %f) * %f (prior %f)\n",
 154                                 coord2sstr(node_coord(node), tree->board), beta, r.value, beta, n.value, node->prior.value);
 155                 } else {
 156                         value = n.value;
 157                         URAVE_DEBUG fprintf(stderr, "\t%s value = %f (prior %f)\n",
 158                                 coord2sstr(node_coord(node), tree->board), n.value, node->prior.value);
 159                 }
 160         } else if (r.playouts) {
 161                 value = r.value;
 162                 URAVE_DEBUG fprintf(stderr, "\t%s value = rave %f (prior %f)\n",
 163                         coord2sstr(node_coord(node), tree->board), r.value, node->prior.value);
 164         }
 165         descent->value.playouts = r.playouts + n.playouts;
 166         descent->value.value = value;
 167         return tree_node_get_value(tree, parity, value);
 168 }
 169
 170 void
 171 ucb1rave_descend(struct uct_policy *p, struct tree *tree, struct uct_descent *descent, int parity, bool allow_pass)
 172 {
 173         struct ucb1_policy_amaf *b = p->data;
 174         floating_t nconf = 1.f;
 175         if (b->explore_p > 0)
 176                 nconf = sqrt(log(descent->node->u.playouts + descent->node->prior.playouts));
 177         struct uct *u = p->uct;
 178         int vwin = 0;
 179         if (u->max_slaves > 0 && u->slave_index >= 0)
 180                 vwin = descent->node == tree->root ? b->root_virtual_win : b->virtual_win;
 181         int child = 0;
 182
 183         uctd_try_node_children(tree, descent, allow_pass, parity, u->tenuki_d, di, urgency) {
 184                 struct tree_node *ni = di.node;
 185                 urgency = ucb1rave_evaluate(p, tree, &di, parity);
 186
 187                 /* In distributed mode, encourage different slaves to work on different
 188                  * parts of the tree. We rely on the fact that children (if they exist)
 189                  * are the same and in the same order in all slaves. */
 190                 if (vwin > 0 && ni->u.playouts > b->vwin_min_playouts && (child - u->slave_index) % u->max_slaves == 0)
 191                         urgency += vwin / (ni->u.playouts + vwin);
 192
 193                 if (ni->u.playouts > 0 && b->explore_p > 0) {
 194                         urgency += b->explore_p * nconf / fast_sqrt(ni->u.playouts);
 195
 196                 } else if (ni->u.playouts + ni->amaf.playouts + ni->prior.playouts == 0) {
 197                         /* assert(!u->even_eqex); */
 198                         urgency = b->fpu;
 199                 }
 200         } uctd_set_best_child(di, urgency);
 201
 202         uctd_get_best_child(descent);
 203 }
 204
 205
 206 void
 207 ucb1amaf_update(struct uct_policy *p, struct tree *tree, struct tree_node *node,
 208                 enum stone node_color, enum stone player_color,
 209                 struct playout_amafmap *map, struct board *final_board,
 210                 floating_t result)
 211 {
 212         struct ucb1_policy_amaf *b = p->data;
 213         enum stone winner_color = result > 0.5 ? S_BLACK : S_WHITE;
 214         enum stone child_color = stone_other(node_color);
 215
 216 #if 0
 217         struct board bb; bb.size = 9+2;
 218         for (struct tree_node *ni = node; ni; ni = ni->parent)
 219                 fprintf(stderr, "%s ", coord2sstr(node_coord(ni), &bb));
 220         fprintf(stderr, "[color %d] update result %d (color %d)\n",
 221                         node_color, result, player_color);
 222 #endif
 223
 224         while (node) {
 225                 if (node->parent == NULL)
 226                         assert(tree->root_color == stone_other(child_color));
 227
 228                 if (!b->crit_amaf && !is_pass(node_coord(node))) {
 229                         stats_add_result(&node->winner_owner, board_local_value(b->crit_lvalue, final_board, node_coord(node), winner_color), 1);
 230                         stats_add_result(&node->black_owner, board_local_value(b->crit_lvalue, final_board, node_coord(node), S_BLACK), 1);
 231                 }
 232                 stats_add_result(&node->u, result, 1);
 233                 if (!is_pass(node_coord(node)) && amaf_nakade(map->map[node_coord(node)]))
 234                         amaf_op(map->map[node_coord(node)], -);
 235
 236                 /* This loop ignores symmetry considerations, but they should
 237                  * matter only at a point when AMAF doesn't help much. */
 238                 assert(map->game_baselen >= 0);
 239                 for (struct tree_node *ni = node->children; ni; ni = ni->sibling) {
 240                         enum stone amaf_color = map->map[node_coord(ni)];
 241                         assert(amaf_color != S_OFFBOARD);
 242                         if (amaf_color == S_NONE)
 243                                 continue;
 244                         if (amaf_nakade(map->map[node_coord(ni)])) {
 245                                 if (!b->check_nakade)
 246                                         continue;
 247                                 unsigned int i;
 248                                 for (i = map->game_baselen; i < map->gamelen; i++)
 249                                         if (map->game[i].coord == node_coord(ni)
 250                                             && map->game[i].color == child_color)
 251                                                 break;
 252                                 if (i == map->gamelen)
 253                                         continue;
 254                                 amaf_color = child_color;
 255                         }
 256
 257                         floating_t nres = result;
 258                         if (amaf_color != child_color) {
 259                                 continue;
 260                         }
 261                         /* For child_color != player_color, we still want
 262                          * to record the result unmodified; in that case,
 263                          * we will correctly negate them at the descend phase. */
 264
 265                         if (b->crit_amaf && !is_pass(node_coord(node))) {
 266                                 stats_add_result(&ni->winner_owner, board_local_value(b->crit_lvalue, final_board, node_coord(ni), winner_color), 1);
 267                                 stats_add_result(&ni->black_owner, board_local_value(b->crit_lvalue, final_board, node_coord(ni), S_BLACK), 1);
 268                         }
 269                         stats_add_result(&ni->amaf, nres, 1);
 270
 271 #if 0
 272                         struct board bb; bb.size = 9+2;
 273                         fprintf(stderr, "* %s<%"PRIhash"> -> %s<%"PRIhash"> [%d/%f => %d/%f]\n",
 274                                 coord2sstr(node_coord(node), &bb), node->hash,
 275                                 coord2sstr(node_coord(ni), &bb), ni->hash,
 276                                 player_color, result, child_color, nres);
 277 #endif
 278                 }
 279
 280                 if (!is_pass(node_coord(node))) {
 281                         map->game_baselen--;
 282                 }
 283                 node = node->parent; child_color = stone_other(child_color);
 284         }
 285 }
 286
 287
 288 struct uct_policy *
 289 policy_ucb1amaf_init(struct uct *u, char *arg)
 290 {
 291         struct uct_policy *p = calloc2(1, sizeof(*p));
 292         struct ucb1_policy_amaf *b = calloc2(1, sizeof(*b));
 293         p->uct = u;
 294         p->data = b;
 295         p->choose = uctp_generic_choose;
 296         p->winner = uctp_generic_winner;
 297         p->evaluate = ucb1rave_evaluate;
 298         p->descend = ucb1rave_descend;
 299         p->update = ucb1amaf_update;
 300         p->wants_amaf = true;
 301
 302         b->explore_p = 0; // 0.02 can be also good on 19x19 with prior=eqex=40
 303         b->equiv_rave = 3000;
 304         b->fpu = INFINITY;
 305         b->check_nakade = true;
 306         b->sylvain_rave = true;
 307         b->ltree_rave = 0.75f;
 308
 309         b->crit_rave = 1.0f;
 310         b->crit_min_playouts = 2000;
 311         b->crit_negative = 1;
 312         b->crit_amaf = 0;
 313
 314         b->root_virtual_win = -1;
 315         b->vwin_min_playouts = 1000;
 316
 317         if (arg) {
 318                 char *optspec, *next = arg;
 319                 while (*next) {
 320                         optspec = next;
 321                         next += strcspn(next, ":");
 322                         if (*next) { *next++ = 0; } else { *next = 0; }
 323
 324                         char *optname = optspec;
 325                         char *optval = strchr(optspec, '=');
 326                         if (optval) *optval++ = 0;
 327
 328                         if (!strcasecmp(optname, "explore_p")) {
 329                                 b->explore_p = atof(optval);
 330                         } else if (!strcasecmp(optname, "fpu") && optval) {
 331                                 b->fpu = atof(optval);
 332                         } else if (!strcasecmp(optname, "equiv_rave") && optval) {
 333                                 b->equiv_rave = atof(optval);
 334                         } else if (!strcasecmp(optname, "sylvain_rave")) {
 335                                 b->sylvain_rave = !optval || *optval == '1';
 336                         } else if (!strcasecmp(optname, "check_nakade")) {
 337                                 b->check_nakade = !optval || *optval == '1';
 338                         } else if (!strcasecmp(optname, "ltree_rave") && optval) {
 339                                 b->ltree_rave = atof(optval);
 340                         } else if (!strcasecmp(optname, "crit_rave") && optval) {
 341                                 b->crit_rave = atof(optval);
 342                         } else if (!strcasecmp(optname, "crit_min_playouts") && optval) {
 343                                 b->crit_min_playouts = atoi(optval);
 344                         } else if (!strcasecmp(optname, "crit_negative")) {
 345                                 b->crit_negative = !optval || *optval == '1';
 346                         } else if (!strcasecmp(optname, "crit_negflip")) {
 347                                 b->crit_negflip = !optval || *optval == '1';
 348                         } else if (!strcasecmp(optname, "crit_amaf")) {
 349                                 b->crit_amaf = !optval || *optval == '1';
 350                         } else if (!strcasecmp(optname, "crit_lvalue")) {
 351                                 b->crit_lvalue = !optval || *optval == '1';
 352                         } else if (!strcasecmp(optname, "virtual_win") && optval) {
 353                                 b->virtual_win = atoi(optval);
 354                         } else if (!strcasecmp(optname, "root_virtual_win") && optval) {
 355                                 b->root_virtual_win = atoi(optval);
 356                         } else if (!strcasecmp(optname, "vwin_min_playouts") && optval) {
 357                                 b->vwin_min_playouts = atoi(optval);
 358                         } else {
 359                                 fprintf(stderr, "ucb1amaf: Invalid policy argument %s or missing value\n",
 360                                         optname);
 361                                 exit(1);
 362                         }
 363                 }
 364         }
 365         if (b->root_virtual_win < 0)
 366                 b->root_virtual_win = b->virtual_win;
 367
 368         return p;
 369 }