montecarlo/montecarlo.c

   1 #include <assert.h>
   2 #include <stdio.h>
   3 #include <stdlib.h>
   4 #include <string.h>
   5
   6 #include "board.h"
   7 #include "engine.h"
   8 #include "joseki/base.h"
   9 #include "move.h"
  10 #include "playout/moggy.h"
  11 #include "playout/light.h"
  12 #include "montecarlo/internal.h"
  13 #include "montecarlo/montecarlo.h"
  14 #include "playout.h"
  15 #include "timeinfo.h"
  16
  17
  18 /* This is simple monte-carlo engine. It plays MC_GAMES random games from the
  19  * current board and records win/loss ratio for each first move. The move with
  20  * the biggest number of winning games gets played. */
  21 /* Note that while the library is based on New Zealand rules, this engine
  22  * returns moves according to Chinese rules. Thus, it does not return suicide
  23  * moves. It of course respects positional superko too. */
  24
  25 /* Pass me arguments like a=b,c=d,...
  26  * Supported arguments:
  27  * debug[=DEBUG_LEVEL]          1 is the default; more means more debugging prints
  28  * games=MC_GAMES               number of random games to play
  29  * gamelen=MC_GAMELEN           maximal length of played random game
  30  * playout={light,moggy}[:playout_params]
  31  */
  32
  33
  34 #define MC_GAMES        40000
  35 #define MC_GAMELEN      400
  36
  37
  38 /* FIXME: Cutoff rule for simulations. Currently we are so fast that this
  39  * simply does not matter; even 100000 simulations are fast enough to
  40  * play 5 minutes S.D. on 19x19 and anything more sounds too ridiculous
  41  * already. */
  42 /* FIXME: We cannot handle seki. Any good ideas are welcome. A possibility is
  43  * to consider 'pass' among the moves, but this seems tricky. */
  44
  45
  46 void
  47 board_stats_print(struct board *board, struct move_stat *moves, FILE *f)
  48 {
  49         fprintf(f, "\n       ");
  50         int x, y;
  51         char asdf[] = "ABCDEFGHJKLMNOPQRSTUVWXYZ";
  52         for (x = 1; x < board_size(board) - 1; x++)
  53                 fprintf(f, "%c    ", asdf[x - 1]);
  54         fprintf(f, "\n   +-");
  55         for (x = 1; x < board_size(board) - 1; x++)
  56                 fprintf(f, "-----");
  57         fprintf(f, "+\n");
  58         for (y = board_size(board) - 2; y >= 1; y--) {
  59                 fprintf(f, "%2d | ", y);
  60                 for (x = 1; x < board_size(board) - 1; x++)
  61                         if (moves[y * board_size(board) + x].games)
  62                                 fprintf(f, "%0.2f ", (floating_t) moves[y * board_size(board) + x].wins / moves[y * board_size(board) + x].games);
  63                         else
  64                                 fprintf(f, "---- ");
  65                 fprintf(f, "| ");
  66                 for (x = 1; x < board_size(board) - 1; x++)
  67                         fprintf(f, "%4d ", moves[y * board_size(board) + x].games);
  68                 fprintf(f, "|\n");
  69         }
  70         fprintf(f, "   +-");
  71         for (x = 1; x < board_size(board) - 1; x++)
  72                 fprintf(f, "-----");
  73         fprintf(f, "+\n");
  74 }
  75
  76
  77 static coord_t *
  78 montecarlo_genmove(struct engine *e, struct board *b, struct time_info *ti, enum stone color, bool pass_all_alive)
  79 {
  80         struct montecarlo *mc = e->data;
  81
  82         if (ti->dim == TD_WALLTIME) {
  83                 fprintf(stderr, "Warning: TD_WALLTIME time mode not supported, resetting to defaults.\n");
  84                 ti->period = TT_NULL;
  85         }
  86         if (ti->period == TT_NULL) {
  87                 ti->period = TT_MOVE;
  88                 ti->dim = TD_GAMES;
  89                 ti->len.games = MC_GAMES;
  90         }
  91         struct time_stop stop;
  92         time_stop_conditions(ti, b, 20, 40, 3.0, &stop);
  93
  94         /* resign when the hope for win vanishes */
  95         coord_t top_coord = resign;
  96         floating_t top_ratio = mc->resign_ratio;
  97
  98         /* We use [0] for pass. Normally, this is an inaccessible corner
  99          * of board margin. */
 100         struct move_stat moves[board_size2(b)];
 101         memset(moves, 0, sizeof(moves));
 102
 103         int losses = 0;
 104         int i, superko = 0, good_games = 0;
 105         for (i = 0; i < stop.desired.playouts; i++) {
 106                 assert(!b->superko_violation);
 107
 108                 struct board b2;
 109                 board_copy(&b2, b);
 110
 111                 coord_t coord;
 112                 board_play_random(&b2, color, &coord, NULL, NULL);
 113                 if (!is_pass(coord) && !group_at(&b2, coord)) {
 114                         /* Multi-stone suicide. We play chinese rules,
 115                          * so we can't consider this. (Note that we
 116                          * unfortunately still consider this in playouts.) */
 117                         if (DEBUGL(4)) {
 118                                 fprintf(stderr, "SUICIDE DETECTED at %d,%d:\n", coord_x(coord, b), coord_y(coord, b));
 119                                 board_print(b, stderr);
 120                         }
 121                         continue;
 122                 }
 123
 124                 if (DEBUGL(3))
 125                         fprintf(stderr, "[%d,%d color %d] playing random game\n", coord_x(coord, b), coord_y(coord, b), color);
 126
 127                 struct playout_setup ps = { .gamelen = mc->gamelen };
 128                 int result = play_random_game(&ps, &b2, color, NULL, NULL, mc->playout);
 129
 130                 board_done_noalloc(&b2);
 131
 132                 if (result == 0) {
 133                         /* Superko. We just ignore this playout.
 134                          * And play again. */
 135                         if (unlikely(superko > 2 * stop.desired.playouts)) {
 136                                 /* Uhh. Triple ko, or something? */
 137                                 if (MCDEBUGL(0))
 138                                         fprintf(stderr, "SUPERKO LOOP. I will pass. Did we hit triple ko?\n");
 139                                 goto pass_wins;
 140                         }
 141                         /* This playout didn't count; we should not
 142                          * disadvantage moves that lead to a superko.
 143                          * And it is supposed to be rare. */
 144                         i--, superko++;
 145                         continue;
 146                 }
 147
 148                 if (MCDEBUGL(3))
 149                         fprintf(stderr, "\tresult for other player: %d\n", result);
 150
 151                 int pos = is_pass(coord) ? 0 : coord;
 152
 153                 good_games++;
 154                 moves[pos].games++;
 155
 156                 losses += result > 0;
 157                 moves[pos].wins += 1 - (result > 0);
 158
 159                 if (unlikely(!losses && i == mc->loss_threshold)) {
 160                         /* We played out many games and didn't lose once yet.
 161                          * This game is over. */
 162                         break;
 163                 }
 164         }
 165
 166         if (!good_games) {
 167                 /* No moves to try??? */
 168                 if (MCDEBUGL(0)) {
 169                         fprintf(stderr, "OUT OF MOVES! I will pass. But how did this happen?\n");
 170                         board_print(b, stderr);
 171                 }
 172 pass_wins:
 173                 top_coord = pass; top_ratio = 0.5;
 174                 goto move_found;
 175         }
 176
 177         foreach_point(b) {
 178                 if (b->moves < 3) {
 179                         /* Simple heuristic: avoid opening too low. Do not
 180                          * play on second or first line as first white or
 181                          * first two black moves.*/
 182                         if (coord_x(c, b) < 3 || coord_x(c, b) > board_size(b) - 4
 183                             || coord_y(c, b) < 3 || coord_y(c, b) > board_size(b) - 4)
 184                                 continue;
 185                 }
 186
 187                 floating_t ratio = (floating_t) moves[c].wins / moves[c].games;
 188                 /* Since pass is [0,0], we will pass only when we have nothing
 189                  * better to do. */
 190                 if (ratio >= top_ratio) {
 191                         top_ratio = ratio;
 192                         top_coord = c == 0 ? pass : c;
 193                 }
 194         } foreach_point_end;
 195
 196         if (MCDEBUGL(2)) {
 197                 board_stats_print(b, moves, stderr);
 198         }
 199
 200 move_found:
 201         if (MCDEBUGL(1))
 202                 fprintf(stderr, "*** WINNER is %d,%d with score %1.4f (%d games, %d superko)\n", coord_x(top_coord, b), coord_y(top_coord, b), top_ratio, i, superko);
 203
 204         return coord_copy(top_coord);
 205 }
 206
 207
 208 struct montecarlo *
 209 montecarlo_state_init(char *arg, struct board *b)
 210 {
 211         struct montecarlo *mc = calloc2(1, sizeof(struct montecarlo));
 212
 213         mc->debug_level = 1;
 214         mc->gamelen = MC_GAMELEN;
 215
 216         if (arg) {
 217                 char *optspec, *next = arg;
 218                 while (*next) {
 219                         optspec = next;
 220                         next += strcspn(next, ",");
 221                         if (*next) { *next++ = 0; } else { *next = 0; }
 222
 223                         char *optname = optspec;
 224                         char *optval = strchr(optspec, '=');
 225                         if (optval) *optval++ = 0;
 226
 227                         if (!strcasecmp(optname, "debug")) {
 228                                 if (optval)
 229                                         mc->debug_level = atoi(optval);
 230                                 else
 231                                         mc->debug_level++;
 232                         } else if (!strcasecmp(optname, "gamelen") && optval) {
 233                                 mc->gamelen = atoi(optval);
 234                         } else if (!strcasecmp(optname, "playout") && optval) {
 235                                 char *playoutarg = strchr(optval, ':');
 236                                 if (playoutarg)
 237                                         *playoutarg++ = 0;
 238                                 if (!strcasecmp(optval, "moggy")) {
 239                                         mc->playout = playout_moggy_init(playoutarg, b, joseki_load(b->size));
 240                                 } else if (!strcasecmp(optval, "light")) {
 241                                         mc->playout = playout_light_init(playoutarg, b);
 242                                 } else {
 243                                         fprintf(stderr, "MonteCarlo: Invalid playout policy %s\n", optval);
 244                                 }
 245                         } else {
 246                                 fprintf(stderr, "MonteCarlo: Invalid engine argument %s or missing value\n", optname);
 247                         }
 248                 }
 249         }
 250
 251         if (!mc->playout)
 252                 mc->playout = playout_light_init(NULL, b);
 253         mc->playout->debug_level = mc->debug_level;
 254
 255         mc->resign_ratio = 0.1; /* Resign when most games are lost. */
 256         mc->loss_threshold = 5000; /* Stop reading if no loss encountered in first 5000 games. */
 257
 258         return mc;
 259 }
 260
 261
 262 struct engine *
 263 engine_montecarlo_init(char *arg, struct board *b)
 264 {
 265         struct montecarlo *mc = montecarlo_state_init(arg, b);
 266         struct engine *e = calloc2(1, sizeof(struct engine));
 267         e->name = "MonteCarlo";
 268         e->comment = "I'm playing in Monte Carlo. 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).";
 269         e->genmove = montecarlo_genmove;
 270         e->data = mc;
 271
 272         return e;
 273 }