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