playout/old.c

   1 #include <stdio.h>
   2 #include <stdlib.h>
   3
   4 #include "debug.h"
   5 #include "board.h"
   6 #include "playout/old.h"
   7 #include "playout.h"
   8 #include "random.h"
   9
  10
  11 /* The following arguments tune domain-specific heuristics.
  12  * capture_rate=MC_CAPTURERATE  how many of 100 moves should be non-random but
  13  *                              fix local atari, if there is any
  14  * atari_rate=MC_ATARIRATE      how many of 100 moves should be non-random but
  15  *                              make an atari, if there is any
  16  * local_rate=MC_LOCALRATE      how many of 100 moves should be contact plays
  17  *                              (tsuke or diagonal)
  18  * cut_rate=MC_CUTRATE          how many of 100 moves should fix local cuts,
  19  *                              if there are any */
  20
  21 #define MC_CAPTURERATE  50
  22 #define MC_ATARIRATE    50
  23 #define MC_CUTRATE      40
  24 #define MC_LOCALRATE    30
  25
  26
  27 /* *** Domain-specific knowledge comes here (that is, any heuristics that perfer
  28  * certain moves, aside of requiring the moves to be according to the rules). */
  29 /* NOTE: This heuristics affects ONLY the random playouts! It does not help the
  30  * engine directly to pick a move, but it makes it pick the hinted moves in the
  31  * random playouts FROM the random initial move. So the engine will not prefer
  32  * to fix atari on the current board, but it will fix it as the other player
  33  * when the next move on current board failed to deal with it. */
  34
  35
  36 struct old_policy {
  37         int capture_rate, atari_rate, cut_rate, local_rate;
  38
  39         coord_t last_hint;
  40         int last_hint_value;
  41 };
  42
  43 #define PLDEBUGL(n) DEBUGL_(p->debug_level, n)
  44
  45
  46 static coord_t
  47 domain_hint_capture(struct playout_policy *p, struct board *b, coord_t coord)
  48 {
  49         /* If we or our neighbors are in atari, fix that, (Capture or escape.)
  50          * This test costs a lot of performance (the whole playout is about 1/4
  51          * slower), but improves the playouts a lot. */
  52
  53         if (PLDEBUGL(8)) {
  54                 fprintf(stderr, "-- Scanning for %d,%d-capture moves:\n", coord_x(coord, b), coord_y(coord, b));
  55                 board_print(b, stderr);
  56         }
  57
  58         coord_t captures[5]; int captures_len = 0, capture_choice = 0;
  59         memset(captures, 0, sizeof(captures));
  60
  61         coord_t fix;
  62         if (unlikely(board_group_in_atari(b, group_at(b, coord), &fix)) && likely(!is_selfatari(b, board_at(b, coord), fix))) {
  63                 /* We can capture the opponent! Don't even think about escaping
  64                  * our own ataris then. */
  65                 captures[captures_len] = fix;
  66                 capture_choice = captures_len++;
  67                 goto choosen;
  68         }
  69         foreach_neighbor(b, coord, {
  70                 /* This can produce duplicate candidates. But we should prefer
  71                  * bigger groups to smaller ones, so I guess that is kinda ok. */
  72                 if (likely(group_at(b, c)) && unlikely(board_group_in_atari(b, group_at(b, c), &fix)) && likely(!is_selfatari(b, board_at(b, c), fix)))
  73                         captures[captures_len++] = fix;
  74         } );
  75
  76         if (unlikely(captures_len)) {
  77                 capture_choice = fast_random(captures_len);
  78 choosen:
  79                 if (PLDEBUGL(8)) {
  80                         fprintf(stderr, "capture moves found:");
  81                         int i = 0;
  82                         for (i = 0; i < captures_len; i++)
  83                                 fprintf(stderr, " %c%d,%d",
  84                                         capture_choice == i ? '*' : ' ',
  85                                         coord_x(captures[i], b), coord_y(captures[i], b));
  86                         fprintf(stderr, "\n");
  87                 }
  88                 return captures[capture_choice];
  89         }
  90         return pass;
  91 }
  92
  93
  94 static bool inline
  95 valid_atari_move(struct board *b, coord_t coord)
  96 {
  97         /* Do not avoid atari moves that the opponent actuall can never
  98          * play because they are one of our eyes. Without this, the
  99          * atari avoidance will actually fill one eye of surrounded
 100          * two-eyed group. */
 101         return board_get_one_point_eye(b, &coord) == S_NONE;
 102 }
 103
 104 static bool inline
 105 validate_atari_pair(struct board *b, coord_t coord[2])
 106 {
 107         /* DTRT if only one of the atari moves is sensible. */
 108         bool v[2] = { valid_atari_move(b, coord[0]), valid_atari_move(b, coord[1]) };
 109         if (likely(v[0] && v[1]))
 110                 return true;
 111         if (v[0]) {
 112                 coord[1] = coord[0];
 113                 return true;
 114         }
 115         if (v[1]) {
 116                 coord[0] = coord[1];
 117                 return true;
 118         }
 119         return false;
 120 }
 121
 122 static coord_t
 123 domain_hint_atari(struct playout_policy *p, struct board *b, coord_t coord)
 124 {
 125         /* If we can put the last-move group in atari, do that. */
 126
 127         if (PLDEBUGL(8)) {
 128                 fprintf(stderr, "-- Scanning for %d,%d-atari moves:\n", coord_x(coord, b), coord_y(coord, b));
 129                 board_print(b, stderr);
 130         }
 131
 132         coord_t ataris[5][2]; int ataris_len = 0, atari_choice = 0;
 133         memset(ataris, 0, sizeof(ataris));
 134
 135         if (unlikely(board_group_can_atari(b, group_at(b, coord), ataris[ataris_len]))) {
 136                 if (likely(validate_atari_pair(b, ataris[ataris_len]))) {
 137                         /* Atari-ing opponent is always better than preventing
 138                          * opponent atari-ing us. */
 139                         atari_choice = ataris_len++;
 140                         goto choosen;
 141                 }
 142         }
 143         foreach_neighbor(b, coord, {
 144                 /* This can produce duplicate candidates. But we should prefer
 145                  * bigger groups to smaller ones, so I guess that is kinda ok. */
 146                 if (likely(group_at(b, c)) && unlikely(board_group_can_atari(b, group_at(b, c), ataris[ataris_len])))
 147                         if (likely(validate_atari_pair(b, ataris[ataris_len])))
 148                                 ataris_len++;
 149         } );
 150
 151         if (unlikely(ataris_len)) {
 152                 atari_choice = fast_random(ataris_len);
 153 choosen:
 154                 if (PLDEBUGL(8)) {
 155                         fprintf(stderr, "atari moves found:");
 156                         int i = 0;
 157                         for (i = 0; i < ataris_len; i++)
 158                                 fprintf(stderr, " %c%d,%d;%d,%d",
 159                                         atari_choice == i ? '*' : ' ',
 160                                         coord_x(ataris[i][0], b), coord_y(ataris[i][0], b),
 161                                         coord_x(ataris[i][1], b), coord_y(ataris[i][1], b));
 162                         fprintf(stderr, "\n");
 163                 }
 164                 return ataris[atari_choice][fast_random(2)];
 165         }
 166         return pass;
 167 }
 168
 169 static coord_t
 170 domain_hint_cut(struct playout_policy *p, struct board *b, coord_t coord)
 171 {
 172         /* Check if this move is cutting kosumi:
 173          * (O) X
 174          *  X  .  */
 175
 176         if (PLDEBUGL(8)) {
 177                 fprintf(stderr, "-- Scanning for %d,%d-cut moves:\n", coord_x(coord, b), coord_y(coord, b));
 178                 board_print(b, stderr);
 179         }
 180
 181         coord_t cuts[4]; int cuts_len = 0;
 182         memset(cuts, 0, sizeof(cuts));
 183
 184         enum stone cutting_color = stone_other(board_at(b, coord));
 185         foreach_diag_neighbor(b, coord) {
 186                 if (board_at(b, c) == S_NONE) {
 187                         if (neighbor_count_at(b, c, cutting_color) != 2) {
 188                                 /* Either this isn't a cut or the opponent has
 189                                  * too many friends there. */
 190                                 continue;
 191                         }
 192
 193                         /* XXX: Some internal board specific magic here... */
 194                         coord_t cutted = coord;
 195                         if (coord_x(c, b) < coord_x(coord, b))
 196                                 coord_raw(cutted)--;
 197                         else
 198                                 coord_raw(cutted)++;
 199                         if (likely(board_at(b, cutted) != cutting_color))
 200                                 continue;
 201                         coord_raw(cutted) = coord_raw(c);
 202                         if (coord_y(c, b) < coord_y(coord, b))
 203                                 coord_raw(cutted) -= board_size(b);
 204                         else
 205                                 coord_raw(cutted) += board_size(b);
 206                         if (likely(board_at(b, cutted) != cutting_color))
 207                                 continue;
 208                         /* Cut kosumi! */
 209                         cuts[cuts_len++] = c;
 210                 }
 211         } foreach_diag_neighbor_end;
 212
 213         if (unlikely(cuts_len)) {
 214                 if (PLDEBUGL(8)) {
 215                         fprintf(stderr, "Cutting moves found:");
 216                         int i = 0;
 217                         for (i = 0; i < cuts_len; i++)
 218                                 fprintf(stderr, " %d,%d", coord_x(cuts[i], b), coord_y(cuts[i], b));
 219                         fprintf(stderr, "\n");
 220                 }
 221                 return cuts[fast_random(cuts_len)];
 222         }
 223         return pass;
 224 }
 225
 226 static coord_t
 227 domain_hint_local(struct playout_policy *p, struct board *b, coord_t coord)
 228 {
 229         /* Pick a suitable move that is directly or diagonally adjecent. In the
 230          * real game, local moves often tend to be the urgent ones, even if they
 231          * aren't atari. */
 232
 233         if (PLDEBUGL(8)) {
 234                 fprintf(stderr, "-- Scanning for %d,%d-local moves:\n", coord_x(coord, b), coord_y(coord, b));
 235                 board_print(b, stderr);
 236         }
 237
 238         coord_t neis[S_MAX][8]; int neis_len[S_MAX];
 239         memset(neis, 0, sizeof(neis));
 240         memset(neis_len, 0, sizeof(neis_len));
 241
 242         foreach_neighbor(b, coord, {
 243                 neis[(enum stone) board_at(b, c)][neis_len[(enum stone) board_at(b, c)]++] = c;
 244         } );
 245
 246         foreach_diag_neighbor(b, coord) {
 247                 neis[(enum stone) board_at(b, c)][neis_len[(enum stone) board_at(b, c)]++] = c;
 248         } foreach_diag_neighbor_end;
 249
 250         if (likely(neis_len[S_NONE])) {
 251                 if (PLDEBUGL(8)) {
 252                         fprintf(stderr, "Local moves found:");
 253                         int i = 0;
 254                         for (i = 0; i < neis_len[S_NONE]; i++)
 255                                 fprintf(stderr, " %d,%d", coord_x(neis[S_NONE][i], b), coord_y(neis[S_NONE][i], b));
 256                         fprintf(stderr, "\n");
 257                 }
 258                 return neis[S_NONE][fast_random(neis_len[S_NONE])];
 259         }
 260         return pass;
 261 }
 262
 263 coord_t
 264 playout_old_choose(struct playout_policy *p, struct board *b, enum stone our_real_color)
 265 {
 266         struct old_policy *pp = p->data;
 267
 268         if (is_pass(b->last_move.coord))
 269                 return pass;
 270
 271         /* Now now, if we ignored an urgent move, the opponent will
 272          * take it! */
 273         /* Note that we should use this only when the _REAL_ us tenukies
 274          * and the _REAL_ opponent comes back. Otherwise we hope in
 275          * opponent's tenuki too much and play out ladders. :-) */
 276         if (!is_pass(pp->last_hint)
 277             && unlikely(!coord_eq(b->last_move.coord, pp->last_hint))
 278             && b->last_move.color == our_real_color
 279             && fast_random(100) < pp->last_hint_value) {
 280                 coord_t urgent = pp->last_hint;
 281                 pp->last_hint = pass;
 282                 return urgent;
 283         }
 284
 285         /* In some of the cases, we pick atari response instead of random move.
 286          * If there is an atari, capturing tends to be huge. */
 287         if (pp->capture_rate && fast_random(100) < pp->capture_rate) {
 288                 pp->last_hint = domain_hint_capture(p, b, b->last_move.coord);
 289                 if (!is_pass(pp->last_hint)) {
 290                         pp->last_hint_value = pp->capture_rate;
 291                         return pp->last_hint;
 292                 }
 293         }
 294
 295         /* Maybe we can _put_ some stones into atari. That's cool. */
 296         if (pp->capture_rate && fast_random(100) < pp->atari_rate) {
 297                 pp->last_hint = domain_hint_atari(p, b, b->last_move.coord);
 298                 if (!is_pass(pp->last_hint)) {
 299                         pp->last_hint_value = pp->capture_rate;
 300                         return pp->last_hint;
 301                 }
 302         }
 303
 304         /* Cutting is kinda urgent, too. */
 305         if (pp->cut_rate && fast_random(100) < pp->cut_rate) {
 306                 pp->last_hint = domain_hint_cut(p, b, b->last_move.coord);
 307                 if (!is_pass(pp->last_hint)) {
 308                         pp->last_hint_value = pp->cut_rate;
 309                         return pp->last_hint;
 310                 }
 311         }
 312
 313         /* For the non-urgent moves, some of them will be contact play (tsuke
 314          * or diagonal). These tend to be likely urgent. */
 315         if (pp->local_rate && fast_random(100) < pp->local_rate) {
 316                 pp->last_hint = domain_hint_local(p, b, b->last_move.coord);
 317                 if (!is_pass(pp->last_hint)) {
 318                         pp->last_hint_value = pp->local_rate;
 319                         return pp->last_hint;
 320                 }
 321         }
 322
 323         return ((pp->last_hint = pass));
 324 }
 325
 326
 327 struct playout_policy *
 328 playout_old_init(char *arg)
 329 {
 330         struct playout_policy *p = calloc(1, sizeof(*p));
 331         struct old_policy *pp = calloc(1, sizeof(*pp));
 332         p->data = pp;
 333         p->choose = playout_old_choose;
 334
 335         pp->last_hint = pass;
 336
 337         pp->capture_rate = MC_CAPTURERATE;
 338         pp->atari_rate = MC_ATARIRATE;
 339         pp->local_rate = MC_LOCALRATE;
 340         pp->cut_rate = MC_CUTRATE;
 341
 342         if (arg) {
 343                 char *optspec, *next = arg;
 344                 while (*next) {
 345                         optspec = next;
 346                         next += strcspn(next, ":");
 347                         if (*next) { *next++ = 0; } else { *next = 0; }
 348
 349                         char *optname = optspec;
 350                         char *optval = strchr(optspec, '=');
 351                         if (optval) *optval++ = 0;
 352
 353                         if (!strcasecmp(optname, "capturerate") && optval) {
 354                                 pp->capture_rate = atoi(optval);
 355                         } else if (!strcasecmp(optname, "atarirate") && optval) {
 356                                 pp->atari_rate = atoi(optval);
 357                         } else if (!strcasecmp(optname, "localrate") && optval) {
 358                                 pp->local_rate = atoi(optval);
 359                         } else if (!strcasecmp(optname, "cutrate") && optval) {
 360                                 pp->cut_rate = atoi(optval);
 361                         } else {
 362                                 fprintf(stderr, "playout-old: Invalid policy argument %s or missing value\n", optname);
 363                         }
 364                 }
 365         }
 366
 367         return p;
 368 }