uct/uct.c

   1 #include <assert.h>
   2 #include <stdio.h>
   3 #include <stdlib.h>
   4 #include <string.h>
   5
   6 #define DEBUG
   7
   8 #include "debug.h"
   9 #include "board.h"
  10 #include "move.h"
  11 #include "playout.h"
  12 #include "playout/moggy.h"
  13 #include "playout/old.h"
  14 #include "uct/internal.h"
  15 #include "uct/tree.h"
  16 #include "uct/uct.h"
  17
  18 struct uct_policy *policy_ucb1_init(struct uct *u, char *arg);
  19 struct uct_policy *policy_ucb1tuned_init(struct uct *u, char *arg);
  20 struct uct_policy *policy_ucb1amaf_init(struct uct *u, char *arg);
  21
  22
  23 #define MC_GAMES        40000
  24 #define MC_GAMELEN      400
  25
  26
  27 static void
  28 progress_status(struct uct *u, struct tree *t, enum stone color)
  29 {
  30         if (!UDEBUGL(0))
  31                 return;
  32
  33         struct tree_node *best = u->policy->choose(u->policy, t->root, t->board, color);
  34         if (!best) {
  35                 fprintf(stderr, "... No moves left\n");
  36                 return;
  37         }
  38         fprintf(stderr, "%f ", best->value);
  39
  40         /* Best sequence */
  41         fprintf(stderr, "| seq ");
  42         for (int depth = 0; depth < 6; depth++) {
  43                 if (best && best->playouts >= 25) {
  44                         fprintf(stderr, "%3s ", coord2sstr(best->coord, t->board));
  45                         best = u->policy->choose(u->policy, best, t->board, color);
  46                 } else {
  47                         fprintf(stderr, "    ");
  48                 }
  49         }
  50
  51         /* Best candidates */
  52         fprintf(stderr, "| can ");
  53         int cans = 4;
  54         struct tree_node *can[cans];
  55         memset(can, 0, sizeof(can));
  56         best = t->root->children;
  57         while (best) {
  58                 int c = 0;
  59                 while ((!can[c] || best->playouts > can[c]->playouts) && ++c < cans);
  60                 for (int d = 0; d < c; d++) can[d] = can[d + 1];
  61                 if (c > 0) can[c - 1] = best;
  62                 best = best->sibling;
  63         }
  64         while (--cans >= 0) {
  65                 if (can[cans]) {
  66                         fprintf(stderr, "%3s(%.3f) ", coord2sstr(can[cans]->coord, t->board), can[cans]->value);
  67                 } else {
  68                         fprintf(stderr, "           ");
  69                 }
  70         }
  71
  72         fprintf(stderr, "\n");
  73 }
  74
  75
  76 static coord_t
  77 domainhint_policy(void *playout_policy, struct board *b, enum stone my_color)
  78 {
  79         struct uct *u = playout_policy;
  80         return u->playout(&u->mc, b, my_color);
  81 }
  82
  83 static int
  84 uct_playout(struct uct *u, struct board *b, enum stone color, struct tree *t)
  85 {
  86         struct board b2;
  87         board_copy(&b2, b);
  88
  89         struct playout_amafmap *amaf = NULL;
  90         if (u->policy->wants_amaf) {
  91                 amaf = calloc(1, sizeof(*amaf));
  92                 amaf->map = calloc(b2.size2 + 1, sizeof(*amaf->map));
  93                 amaf->map++; // -1 is pass
  94         }
  95
  96         /* Walk the tree until we find a leaf, then expand it and do
  97          * a random playout. */
  98         struct tree_node *n = t->root;
  99         enum stone orig_color = color;
 100         int result;
 101         int pass_limit = (b2.size - 2) * (b2.size - 2) / 2;
 102         int passes = is_pass(b->last_move.coord);
 103         if (UDEBUGL(8))
 104                 fprintf(stderr, "--- UCT walk with color %d\n", color);
 105         for (; pass; color = stone_other(color)) {
 106                 if (tree_leaf_node(n)) {
 107                         if (n->playouts >= u->expand_p)
 108                                 tree_expand_node(t, n, &b2, color, u->radar_d);
 109
 110                         result = play_random_game(&b2, color, u->gamelen, u->playout_amaf ? amaf : NULL, domainhint_policy, u);
 111                         if (orig_color != color && result >= 0)
 112                                 result = !result;
 113                         if (UDEBUGL(7))
 114                                 fprintf(stderr, "[%d..%d] %s random playout result %d\n", orig_color, color, coord2sstr(n->coord, t->board), result);
 115                         break;
 116                 }
 117
 118                 n = u->policy->descend(u->policy, t, n, (color == orig_color ? 1 : -1), pass_limit);
 119                 assert(n == t->root || n->parent);
 120                 if (UDEBUGL(7))
 121                         fprintf(stderr, "-- UCT sent us to [%s] %f\n", coord2sstr(n->coord, t->board), n->value);
 122                 if (amaf && n->coord >= -1)
 123                         amaf->map[n->coord] = color;
 124                 struct move m = { n->coord, color };
 125                 int res = board_play(&b2, &m);
 126                 if (res < 0 || (!is_pass(m.coord) && !group_at(&b2, m.coord)) /* suicide */
 127                     || b2.superko_violation) {
 128                         if (UDEBUGL(6))
 129                                 fprintf(stderr, "deleting invalid node %d,%d\n", coord_x(n->coord,b), coord_y(n->coord,b));
 130                         tree_delete_node(t, n);
 131                         result = -1;
 132                         goto end;
 133                 }
 134
 135                 if (is_pass(n->coord)) {
 136                         passes++;
 137                         if (passes >= 2) {
 138                                 float score = board_official_score(&b2);
 139                                 result = (orig_color == S_BLACK) ? score < 0 : score > 0;
 140                                 if (UDEBUGL(5))
 141                                         fprintf(stderr, "[%d..%d] %s playout result %d (W %f)\n", orig_color, color, coord2sstr(n->coord, t->board), result, score);
 142                                 if (UDEBUGL(6))
 143                                         board_print(&b2, stderr);
 144                                 break;
 145                         }
 146                 } else {
 147                         passes = 0;
 148                 }
 149         }
 150
 151         assert(n == t->root || n->parent);
 152         if (amaf)
 153                 amaf->color = stone_other(color);
 154         if (result >= 0)
 155                 u->policy->update(u->policy, n, amaf, result);
 156
 157 end:
 158         if (amaf) {
 159                 free(amaf->map - 1);
 160                 free(amaf);
 161         }
 162         board_done_noalloc(&b2);
 163         return result;
 164 }
 165
 166 static coord_t *
 167 uct_genmove(struct engine *e, struct board *b, enum stone color)
 168 {
 169         struct uct *u = e->data;
 170
 171         if (!u->t) {
 172 tree_init:
 173                 u->t = tree_init(b, color);
 174                 //board_print(b, stderr);
 175         } else {
 176                 /* XXX: We hope that the opponent didn't suddenly play
 177                  * several moves in the row. */
 178                 for (struct tree_node *ni = u->t->root->children; ni; ni = ni->sibling)
 179                         if (ni->coord == b->last_move.coord) {
 180                                 tree_promote_node(u->t, ni);
 181                                 goto promoted;
 182                         }
 183                 fprintf(stderr, "CANNOT FIND NODE TO PROMOTE!\n");
 184                 tree_done(u->t);
 185                 goto tree_init;
 186 promoted:;
 187         }
 188
 189         int i;
 190         for (i = 0; i < u->games; i++) {
 191                 int result = uct_playout(u, b, color, u->t);
 192                 if (result < 0) {
 193                         /* Tree descent has hit invalid move. */
 194                         continue;
 195                 }
 196
 197                 if (i > 0 && !(i % 10000)) {
 198                         progress_status(u, u->t, color);
 199                 }
 200
 201                 if (i > 0 && !(i % 1000)) {
 202                         struct tree_node *best = u->policy->choose(u->policy, u->t->root, b, color);
 203                         if (best && best->playouts >= 500 && best->value >= u->loss_threshold)
 204                                 break;
 205                 }
 206         }
 207
 208         progress_status(u, u->t, color);
 209         if (UDEBUGL(2))
 210                 tree_dump(u->t);
 211
 212         struct tree_node *best = u->policy->choose(u->policy, u->t->root, b, color);
 213         if (!best) {
 214                 tree_done(u->t); u->t = NULL;
 215                 return coord_copy(pass);
 216         }
 217         if (UDEBUGL(1))
 218                 fprintf(stderr, "*** WINNER is %d,%d with score %1.4f (%d games)\n", coord_x(best->coord, b), coord_y(best->coord, b), best->value, u->t->root->playouts);
 219         if (best->value < u->resign_ratio && !is_pass(best->coord)) {
 220                 tree_done(u->t); u->t = NULL;
 221                 return coord_copy(resign);
 222         }
 223         tree_promote_node(u->t, best);
 224         return coord_copy(best->coord);
 225 }
 226
 227
 228 struct uct *
 229 uct_state_init(char *arg)
 230 {
 231         struct uct *u = calloc(1, sizeof(struct uct));
 232
 233         u->debug_level = 1;
 234         u->games = MC_GAMES;
 235         u->gamelen = MC_GAMELEN;
 236         u->expand_p = 2;
 237         u->mc.capture_rate = 100;
 238         u->mc.atari_rate = 100;
 239         u->mc.cut_rate = 0;
 240         // Looking at the actual playouts, this just encourages MC to make
 241         // stupid shapes.
 242         u->mc.local_rate = 0;
 243
 244         if (arg) {
 245                 char *optspec, *next = arg;
 246                 while (*next) {
 247                         optspec = next;
 248                         next += strcspn(next, ",");
 249                         if (*next) { *next++ = 0; } else { *next = 0; }
 250
 251                         char *optname = optspec;
 252                         char *optval = strchr(optspec, '=');
 253                         if (optval) *optval++ = 0;
 254
 255                         if (!strcasecmp(optname, "debug")) {
 256                                 if (optval)
 257                                         u->debug_level = atoi(optval);
 258                                 else
 259                                         u->debug_level++;
 260                         } else if (!strcasecmp(optname, "games") && optval) {
 261                                 u->games = atoi(optval);
 262                         } else if (!strcasecmp(optname, "gamelen") && optval) {
 263                                 u->gamelen = atoi(optval);
 264                         } else if (!strcasecmp(optname, "expand_p") && optval) {
 265                                 u->expand_p = atoi(optval);
 266                         } else if (!strcasecmp(optname, "radar_d") && optval) {
 267                                 /* For 19x19, it is good idea to set this to 3. */
 268                                 u->radar_d = atoi(optval);
 269                         } else if (!strcasecmp(optname, "playout_amaf")) {
 270                                 /* Whether to include random playout moves in
 271                                  * AMAF as well. (Otherwise, only tree moves
 272                                  * are included in AMAF. Of course makes sense
 273                                  * only in connection with an AMAF policy.) */
 274                                 u->playout_amaf = true;
 275                         } else if (!strcasecmp(optname, "policy") && optval) {
 276                                 char *policyarg = strchr(optval, ':');
 277                                 if (policyarg)
 278                                         *policyarg++ = 0;
 279                                 if (!strcasecmp(optval, "ucb1")) {
 280                                         u->policy = policy_ucb1_init(u, policyarg);
 281                                 } else if (!strcasecmp(optval, "ucb1tuned")) {
 282                                         u->policy = policy_ucb1tuned_init(u, policyarg);
 283                                 } else if (!strcasecmp(optval, "ucb1amaf")) {
 284                                         u->policy = policy_ucb1amaf_init(u, policyarg);
 285                                 }
 286                         } else if (!strcasecmp(optname, "playout") && optval) {
 287                                 char *playoutarg = strchr(optval, ':');
 288                                 if (playoutarg)
 289                                         *playoutarg++ = 0;
 290                                 if (!strcasecmp(optval, "old")) {
 291                                         u->playout = playout_old;
 292                                 } else if (!strcasecmp(optval, "moggy")) {
 293                                         u->playout = playout_moggy;
 294                                 }
 295                         } else if (!strcasecmp(optname, "pure")) {
 296                                 u->mc.capture_rate = u->mc.local_rate = u->mc.cut_rate = 0;
 297                         } else if (!strcasecmp(optname, "capturerate") && optval) {
 298                                 u->mc.capture_rate = atoi(optval);
 299                         } else if (!strcasecmp(optname, "atarirate") && optval) {
 300                                 u->mc.atari_rate = atoi(optval);
 301                         } else if (!strcasecmp(optname, "localrate") && optval) {
 302                                 u->mc.local_rate = atoi(optval);
 303                         } else if (!strcasecmp(optname, "cutrate") && optval) {
 304                                 u->mc.cut_rate = atoi(optval);
 305                         } else {
 306                                 fprintf(stderr, "uct: Invalid engine argument %s or missing value\n", optname);
 307                         }
 308                 }
 309         }
 310
 311         u->resign_ratio = 0.2; /* Resign when most games are lost. */
 312         u->loss_threshold = 0.95; /* Stop reading if after at least 500 playouts this is best value. */
 313         u->mc.debug_level = u->debug_level;
 314         if (!u->policy)
 315                 u->policy = policy_ucb1_init(u, NULL);
 316         if (!u->playout)
 317                 u->playout = playout_old;
 318
 319         return u;
 320 }
 321
 322
 323 struct engine *
 324 engine_uct_init(char *arg)
 325 {
 326         struct uct *u = uct_state_init(arg);
 327         struct engine *e = calloc(1, sizeof(struct engine));
 328         e->name = "UCT Engine";
 329         e->comment = "I'm playing UCT. When we both pass, I will consider all the stones on the board alive. If you are reading this, write 'yes'. Please bear with me at the game end, I need to fill the whole board; if you help me, we will both be happier. Filling the board will not lose points (NZ rules).";
 330         e->genmove = uct_genmove;
 331         e->data = u;
 332
 333         return e;
 334 }