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 "playout/light.h"
  15 #include "uct/internal.h"
  16 #include "uct/tree.h"
  17 #include "uct/uct.h"
  18
  19 struct uct_policy *policy_ucb1_init(struct uct *u, char *arg);
  20 struct uct_policy *policy_ucb1tuned_init(struct uct *u, char *arg);
  21 struct uct_policy *policy_ucb1amaf_init(struct uct *u, char *arg);
  22
  23
  24 #define MC_GAMES        40000
  25 #define MC_GAMELEN      400
  26
  27
  28 static void
  29 progress_status(struct uct *u, struct tree *t, enum stone color, int playouts)
  30 {
  31         if (!UDEBUGL(0))
  32                 return;
  33
  34         /* Best move */
  35         struct tree_node *best = u->policy->choose(u->policy, t->root, t->board, color);
  36         if (!best) {
  37                 fprintf(stderr, "... No moves left\n");
  38                 return;
  39         }
  40         fprintf(stderr, "[%d] ", playouts);
  41         fprintf(stderr, "best %f ", best->u.value);
  42
  43         /* Max depth */
  44         fprintf(stderr, "deepest % 2d ", t->max_depth - t->root->depth);
  45
  46         /* Best sequence */
  47         fprintf(stderr, "| seq ");
  48         for (int depth = 0; depth < 6; depth++) {
  49                 if (best && best->u.playouts >= 25) {
  50                         fprintf(stderr, "%3s ", coord2sstr(best->coord, t->board));
  51                         best = u->policy->choose(u->policy, best, t->board, color);
  52                 } else {
  53                         fprintf(stderr, "    ");
  54                 }
  55         }
  56
  57         /* Best candidates */
  58         fprintf(stderr, "| can ");
  59         int cans = 4;
  60         struct tree_node *can[cans];
  61         memset(can, 0, sizeof(can));
  62         best = t->root->children;
  63         while (best) {
  64                 int c = 0;
  65                 while ((!can[c] || best->u.playouts > can[c]->u.playouts) && ++c < cans);
  66                 for (int d = 0; d < c; d++) can[d] = can[d + 1];
  67                 if (c > 0) can[c - 1] = best;
  68                 best = best->sibling;
  69         }
  70         while (--cans >= 0) {
  71                 if (can[cans]) {
  72                         fprintf(stderr, "%3s(%.3f) ", coord2sstr(can[cans]->coord, t->board), can[cans]->u.value);
  73                 } else {
  74                         fprintf(stderr, "           ");
  75                 }
  76         }
  77
  78         fprintf(stderr, "\n");
  79 }
  80
  81
  82 static int
  83 uct_playout(struct uct *u, struct board *b, enum stone color, struct tree *t)
  84 {
  85         struct board b2;
  86         board_copy(&b2, b);
  87
  88         struct playout_amafmap *amaf = NULL;
  89         if (u->policy->wants_amaf) {
  90                 amaf = calloc(1, sizeof(*amaf));
  91                 amaf->map = calloc(board_size2(&b2) + 1, sizeof(*amaf->map));
  92                 amaf->map++; // -1 is pass
  93         }
  94
  95         /* Walk the tree until we find a leaf, then expand it and do
  96          * a random playout. */
  97         struct tree_node *n = t->root;
  98         enum stone orig_color = color;
  99         int result;
 100         int pass_limit = (board_size(&b2) - 2) * (board_size(&b2) - 2) / 2;
 101         int passes = is_pass(b->last_move.coord);
 102         if (UDEBUGL(8))
 103                 fprintf(stderr, "--- UCT walk with color %d\n", color);
 104         for (; pass; color = stone_other(color)) {
 105                 if (tree_leaf_node(n)) {
 106                         if (n->u.playouts >= u->expand_p)
 107                                 tree_expand_node(t, n, &b2, color, u->radar_d, u->policy, (color == orig_color ? 1 : -1));
 108
 109                         result = play_random_game(&b2, color, u->gamelen, u->playout_amaf ? amaf : NULL, u->playout);
 110                         if (orig_color != color && result >= 0)
 111                                 result = !result;
 112                         if (UDEBUGL(7))
 113                                 fprintf(stderr, "[%d..%d] %s random playout result %d\n", orig_color, color, coord2sstr(n->coord, t->board), result);
 114
 115                         /* Reset color to the @n color. */
 116                         color = stone_other(color);
 117                         break;
 118                 }
 119
 120                 n = u->policy->descend(u->policy, t, n, (color == orig_color ? 1 : -1), pass_limit);
 121                 assert(n == t->root || n->parent);
 122                 if (UDEBUGL(7))
 123                         fprintf(stderr, "-- UCT sent us to [%s] %f\n", coord2sstr(n->coord, t->board), n->u.value);
 124                 if (amaf && n->coord >= -1)
 125                         amaf->map[n->coord] = color;
 126                 struct move m = { n->coord, color };
 127                 int res = board_play(&b2, &m);
 128
 129                 if (res < 0 || (!is_pass(m.coord) && !group_at(&b2, m.coord)) /* suicide */
 130                     || b2.superko_violation) {
 131                         if (UDEBUGL(3)) {
 132                                 for (struct tree_node *ni = n; ni; ni = ni->parent)
 133                                         fprintf(stderr, "%s ", coord2sstr(ni->coord, t->board));
 134                                 fprintf(stderr, "deleting invalid %s node %d,%d res %d group %d spk %d\n",
 135                                         stone2str(color), coord_x(n->coord,b), coord_y(n->coord,b),
 136                                         res, group_at(&b2, m.coord), b2.superko_violation);
 137                         }
 138                         tree_delete_node(t, n);
 139                         result = -1;
 140                         goto end;
 141                 }
 142
 143                 if (is_pass(n->coord)) {
 144                         passes++;
 145                         if (passes >= 2) {
 146                                 float score = board_official_score(&b2);
 147                                 result = (orig_color == S_BLACK) ? score < 0 : score > 0;
 148                                 //if (UDEBUGL(5))
 149                                         fprintf(stderr, "[%d..%d] %s p-p scoring playout result %d (W %f)\n", orig_color, color, coord2sstr(n->coord, t->board), result, score);
 150                                 if (UDEBUGL(6))
 151                                         board_print(&b2, stderr);
 152                                 break;
 153                         }
 154                 } else {
 155                         passes = 0;
 156                 }
 157         }
 158
 159         assert(n == t->root || n->parent);
 160         if (result >= 0)
 161                 u->policy->update(u->policy, t, n, color, amaf, result);
 162
 163 end:
 164         if (amaf) {
 165                 free(amaf->map - 1);
 166                 free(amaf);
 167         }
 168         board_done_noalloc(&b2);
 169         return result;
 170 }
 171
 172 static void
 173 prepare_move(struct engine *e, struct board *b, enum stone color, coord_t promote)
 174 {
 175         struct uct *u = e->data;
 176
 177         if (!b->moves && u->t) {
 178                 /* Stale state from last game */
 179                 tree_done(u->t);
 180                 u->t = NULL;
 181         }
 182
 183         if (!u->t) {
 184                 u->t = tree_init(b, color);
 185                 //board_print(b, stderr);
 186                 tree_load(u->t, b);
 187         }
 188
 189         /* XXX: We hope that the opponent didn't suddenly play
 190          * several moves in the row. */
 191         if (!is_resign(promote) && !tree_promote_at(u->t, b, promote)) {
 192                 fprintf(stderr, "CANNOT FIND NODE TO PROMOTE!\n");
 193                 /* Reset tree */
 194                 tree_done(u->t);
 195                 u->t = tree_init(b, color);
 196         }
 197 }
 198
 199 static void
 200 uct_notify_play(struct engine *e, struct board *b, struct move *m)
 201 {
 202         prepare_move(e, b, stone_other(m->color), m->coord);
 203 }
 204
 205 static coord_t *
 206 uct_genmove(struct engine *e, struct board *b, enum stone color)
 207 {
 208         struct uct *u = e->data;
 209
 210         /* Seed the tree. */
 211         prepare_move(e, b, color, resign);
 212
 213         int i, games = u->games - (u->t->root->u.playouts / 1.5);
 214         for (i = 0; i < games; i++) {
 215                 int result = uct_playout(u, b, color, u->t);
 216                 if (result < 0) {
 217                         /* Tree descent has hit invalid move. */
 218                         continue;
 219                 }
 220
 221                 if (i > 0 && !(i % 10000)) {
 222                         progress_status(u, u->t, color, i);
 223                 }
 224
 225                 if (i > 0 && !(i % 500)) {
 226                         struct tree_node *best = u->policy->choose(u->policy, u->t->root, b, color);
 227                         if (best && best->u.playouts >= 1000 && best->u.value >= u->loss_threshold)
 228                                 break;
 229                 }
 230         }
 231
 232         progress_status(u, u->t, color, i);
 233         if (UDEBUGL(2))
 234                 tree_dump(u->t, u->dumpthres);
 235
 236         struct tree_node *best = u->policy->choose(u->policy, u->t->root, b, color);
 237         if (!best) {
 238                 tree_done(u->t); u->t = NULL;
 239                 return coord_copy(pass);
 240         }
 241         if (UDEBUGL(0))
 242                 fprintf(stderr, "*** WINNER is %s (%d,%d) with score %1.4f (%d/%d:%d games)\n", coord2sstr(best->coord, b), coord_x(best->coord, b), coord_y(best->coord, b), best->u.value, best->u.playouts, u->t->root->u.playouts, i);
 243         if (best->u.value < u->resign_ratio && !is_pass(best->coord)) {
 244                 tree_done(u->t); u->t = NULL;
 245                 return coord_copy(resign);
 246         }
 247         tree_promote_node(u->t, best);
 248         return coord_copy(best->coord);
 249 }
 250
 251 bool
 252 uct_genbook(struct engine *e, struct board *b, enum stone color)
 253 {
 254         struct uct *u = e->data;
 255         u->t = tree_init(b, color);
 256         tree_load(u->t, b);
 257
 258         int i;
 259         for (i = 0; i < u->games; i++) {
 260                 int result = uct_playout(u, b, color, u->t);
 261                 if (result < 0) {
 262                         /* Tree descent has hit invalid move. */
 263                         continue;
 264                 }
 265
 266                 if (i > 0 && !(i % 10000)) {
 267                         progress_status(u, u->t, color, i);
 268                 }
 269         }
 270         progress_status(u, u->t, color, i);
 271
 272         tree_save(u->t, b, u->games / 100);
 273
 274         tree_done(u->t);
 275
 276         return true;
 277 }
 278
 279 void
 280 uct_dumpbook(struct engine *e, struct board *b, enum stone color)
 281 {
 282         struct uct *u = e->data;
 283         u->t = tree_init(b, color);
 284         tree_load(u->t, b);
 285         tree_dump(u->t, 0);
 286         tree_done(u->t);
 287 }
 288
 289
 290 struct uct *
 291 uct_state_init(char *arg)
 292 {
 293         struct uct *u = calloc(1, sizeof(struct uct));
 294
 295         u->debug_level = 1;
 296         u->games = MC_GAMES;
 297         u->gamelen = MC_GAMELEN;
 298         u->expand_p = 2;
 299         u->dumpthres = 500;
 300
 301         if (arg) {
 302                 char *optspec, *next = arg;
 303                 while (*next) {
 304                         optspec = next;
 305                         next += strcspn(next, ",");
 306                         if (*next) { *next++ = 0; } else { *next = 0; }
 307
 308                         char *optname = optspec;
 309                         char *optval = strchr(optspec, '=');
 310                         if (optval) *optval++ = 0;
 311
 312                         if (!strcasecmp(optname, "debug")) {
 313                                 if (optval)
 314                                         u->debug_level = atoi(optval);
 315                                 else
 316                                         u->debug_level++;
 317                         } else if (!strcasecmp(optname, "games") && optval) {
 318                                 u->games = atoi(optval);
 319                         } else if (!strcasecmp(optname, "gamelen") && optval) {
 320                                 u->gamelen = atoi(optval);
 321                         } else if (!strcasecmp(optname, "expand_p") && optval) {
 322                                 u->expand_p = atoi(optval);
 323                         } else if (!strcasecmp(optname, "radar_d") && optval) {
 324                                 /* For 19x19, it is good idea to set this to 3. */
 325                                 u->radar_d = atoi(optval);
 326                         } else if (!strcasecmp(optname, "dumpthres") && optval) {
 327                                 u->dumpthres = atoi(optval);
 328                         } else if (!strcasecmp(optname, "playout_amaf")) {
 329                                 /* Whether to include random playout moves in
 330                                  * AMAF as well. (Otherwise, only tree moves
 331                                  * are included in AMAF. Of course makes sense
 332                                  * only in connection with an AMAF policy.) */
 333                                 u->playout_amaf = true;
 334                         } else if (!strcasecmp(optname, "policy") && optval) {
 335                                 char *policyarg = strchr(optval, ':');
 336                                 if (policyarg)
 337                                         *policyarg++ = 0;
 338                                 if (!strcasecmp(optval, "ucb1")) {
 339                                         u->policy = policy_ucb1_init(u, policyarg);
 340                                 } else if (!strcasecmp(optval, "ucb1tuned")) {
 341                                         u->policy = policy_ucb1tuned_init(u, policyarg);
 342                                 } else if (!strcasecmp(optval, "ucb1amaf")) {
 343                                         u->policy = policy_ucb1amaf_init(u, policyarg);
 344                                 } else {
 345                                         fprintf(stderr, "UCT: Invalid tree policy %s\n", optval);
 346                                 }
 347                         } else if (!strcasecmp(optname, "playout") && optval) {
 348                                 char *playoutarg = strchr(optval, ':');
 349                                 if (playoutarg)
 350                                         *playoutarg++ = 0;
 351                                 if (!strcasecmp(optval, "old")) {
 352                                         u->playout = playout_old_init(playoutarg);
 353                                 } else if (!strcasecmp(optval, "moggy")) {
 354                                         u->playout = playout_moggy_init(playoutarg);
 355                                 } else if (!strcasecmp(optval, "light")) {
 356                                         u->playout = playout_light_init(playoutarg);
 357                                 } else {
 358                                         fprintf(stderr, "UCT: Invalid playout policy %s\n", optval);
 359                                 }
 360                         } else {
 361                                 fprintf(stderr, "uct: Invalid engine argument %s or missing value\n", optname);
 362                         }
 363                 }
 364         }
 365
 366         u->resign_ratio = 0.2; /* Resign when most games are lost. */
 367         u->loss_threshold = 0.95; /* Stop reading if after at least 500 playouts this is best value. */
 368         if (!u->policy)
 369                 u->policy = policy_ucb1_init(u, NULL);
 370
 371         if (!u->playout)
 372                 u->playout = playout_moggy_init(NULL);
 373         u->playout->debug_level = u->debug_level;
 374
 375         return u;
 376 }
 377
 378
 379 struct engine *
 380 engine_uct_init(char *arg)
 381 {
 382         struct uct *u = uct_state_init(arg);
 383         struct engine *e = calloc(1, sizeof(struct engine));
 384         e->name = "UCT Engine";
 385         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).";
 386         e->genmove = uct_genmove;
 387         e->notify_play = uct_notify_play;
 388         e->data = u;
 389
 390         return e;
 391 }