playout/moggy.c

   1 #include <assert.h>
   2 #include <math.h>
   3 #include <stdio.h>
   4 #include <stdlib.h>
   5
   6 #define DEBUG
   7 #include "board.h"
   8 #include "debug.h"
   9 #include "playout.h"
  10 #include "playout/moggy.h"
  11 #include "random.h"
  12
  13 #define PLDEBUGL(n) DEBUGL_(p->debug_level, n)
  14
  15
  16 /* Note that the context can be shared by multiple threads! */
  17
  18 struct moggy_policy {
  19         bool ladders, ladderassess, borderladders, assess_local;
  20         int lcapturerate, capturerate, patternrate;
  21         int selfatarirate;
  22
  23         /* Hashtable: 2*8 bits (ignore middle point, 2 bits per intersection) */
  24         /* Value: 0: no pattern, 1: black pattern,
  25          * 2: white pattern, 3: both patterns */
  26         char patterns[65536];
  27 };
  28
  29 #define MQL 64
  30 struct move_queue {
  31         int moves;
  32         coord_t move[MQL];
  33 };
  34
  35 static void
  36 mq_nodup(struct move_queue *q)
  37 {
  38         if ((q->moves > 1 && q->move[q->moves - 2] == q->move[q->moves - 1])
  39             || (q->moves > 2 && q->move[q->moves - 3] == q->move[q->moves - 1])
  40             || (q->moves > 3 && q->move[q->moves - 4] == q->move[q->moves - 1]))
  41                 q->moves--;
  42 }
  43
  44
  45 /* Pattern encoding:
  46  * X: black;  O: white;  .: empty;  #: edge
  47  * x: !black; o: !white; ?: any
  48  *
  49  * extra X: pattern valid only for one side;
  50  * middle point ignored. */
  51
  52 static char moggy_patterns_src[][11] = {
  53         /* hane pattern - enclosing hane */
  54         "XOX"
  55         "..."
  56         "???",
  57         /* hane pattern - non-cutting hane */
  58         "XO."
  59         "..."
  60         "?.?",
  61         /* hane pattern - magari */
  62         "XO?"
  63         "X.."
  64         "x.?",
  65         /* hane pattern - thin hane */
  66         "XOO"
  67         "..."
  68         "?.?" "X",
  69         /* generic pattern - katatsuke or diagonal attachment; similar to magari */
  70         ".O."
  71         "X.."
  72         "...",
  73         /* cut1 pattern (kiri) - unprotected cut */
  74         "XO?"
  75         "O.o"
  76         "?o?",
  77         /* cut1 pattern (kiri) - peeped cut */
  78         "XO?"
  79         "O.X"
  80         "???",
  81         /* cut2 pattern (de) */
  82         "?X?"
  83         "O.O"
  84         "ooo",
  85         /* cut keima (not in Mogo) */
  86         "OX?"
  87         "o.O"
  88         "o??",
  89         /* side pattern - chase */
  90         "X.?"
  91         "O.?"
  92         "##?",
  93         /* side pattern - weirdness (SUSPICIOUS) */
  94         "?X?"
  95         "X.O"
  96         "###",
  97         /* side pattern - sagari (SUSPICIOUS) */
  98         "?XO"
  99         "x.x" /* Mogo has "x.?" */
 100         "###" /* Mogo has "X" */,
 101         /* side pattern - throw-in (SUSPICIOUS) */
 102 #if 0
 103         "?OX"
 104         "o.O"
 105         "?##" "X",
 106 #endif
 107         /* side pattern - cut (SUSPICIOUS) */
 108         "?OX"
 109         "X.O"
 110         "###" /* Mogo has "X" */,
 111 };
 112 #define moggy_patterns_src_n sizeof(moggy_patterns_src) / sizeof(moggy_patterns_src[0])
 113
 114 static void
 115 pattern_record(char *table, char *str, int pat, int fixed_color)
 116 {
 117         /* Original color assignment */
 118         table[pat] = fixed_color ? fixed_color : 3;
 119         //fprintf(stderr, "[%s] %04x %d\n", str, pat, fixed_color);
 120
 121         /* Reverse color assignment - achieved by swapping odd and even bits */
 122         pat = ((pat >> 1) & 0x5555) | ((pat & 0x5555) << 1);
 123         table[pat] = fixed_color ? 2 - (fixed_color == 2) : 3;
 124         //fprintf(stderr, "[%s] %04x %d\n", str, pat, fixed_color);
 125 }
 126
 127 static int
 128 pat_vmirror(int pat)
 129 {
 130         /* V mirror pattern; reverse order of 3-2-3 chunks */
 131         return ((pat & 0xfc00) >> 10) | (pat & 0x03c0) | ((pat & 0x003f) << 10);
 132 }
 133
 134 static int
 135 pat_hmirror(int pat)
 136 {
 137         /* H mirror pattern; reverse order of 2-bit values within the chunks */
 138 #define rev3(p) ((p >> 4) | (p & 0xc) | ((p & 0x3) << 4))
 139 #define rev2(p) ((p >> 2) | ((p & 0x3) << 2))
 140         return (rev3((pat & 0xfc00) >> 10) << 10)
 141                 | (rev2((pat & 0x03c0) >> 6) << 6)
 142                 | rev3((pat & 0x003f));
 143 #undef rev3
 144 #undef rev2
 145 }
 146
 147 static int
 148 pat_90rot(int pat)
 149 {
 150         /* Rotate by 90 degrees:
 151          * 5 6 7    7 4 2
 152          * 3   4 -> 6   1
 153          * 0 1 2    5 3 0 */
 154         /* I'm too lazy to optimize this :) */
 155         int vals[8];
 156         for (int i = 0; i < 8; i++)
 157                 vals[i] = (pat >> (i * 2)) & 0x3;
 158         int vals2[8];
 159         vals2[0] = vals[5]; vals2[1] = vals[3]; vals2[2] = vals[0];
 160         vals2[3] = vals[6];                     vals2[4] = vals[1];
 161         vals2[5] = vals[7]; vals2[6] = vals[4]; vals2[7] = vals[2];
 162         int p2 = 0;
 163         for (int i = 0; i < 8; i++)
 164                 p2 |= vals2[i] << (i * 2);
 165         return p2;
 166 }
 167
 168 static void
 169 pattern_gen(char *table, int pat, char *src, int srclen, int fixed_color)
 170 {
 171         for (; srclen > 0; src++, srclen--) {
 172                 if (srclen == 5)
 173                         continue;
 174                 int patofs = (srclen > 5 ? srclen - 1 : srclen) - 1;
 175                 switch (*src) {
 176                         case '?':
 177                                 *src = '.'; pattern_gen(table, pat, src, srclen, fixed_color);
 178                                 *src = 'X'; pattern_gen(table, pat, src, srclen, fixed_color);
 179                                 *src = 'O'; pattern_gen(table, pat, src, srclen, fixed_color);
 180                                 *src = '#'; pattern_gen(table, pat, src, srclen, fixed_color);
 181                                 *src = '?'; // for future recursions
 182                                 return;
 183                         case 'x':
 184                                 *src = '.'; pattern_gen(table, pat, src, srclen, fixed_color);
 185                                 *src = 'O'; pattern_gen(table, pat, src, srclen, fixed_color);
 186                                 *src = '#'; pattern_gen(table, pat, src, srclen, fixed_color);
 187                                 *src = 'x'; // for future recursions
 188                                 return;
 189                         case 'o':
 190                                 *src = '.'; pattern_gen(table, pat, src, srclen, fixed_color);
 191                                 *src = 'X'; pattern_gen(table, pat, src, srclen, fixed_color);
 192                                 *src = '#'; pattern_gen(table, pat, src, srclen, fixed_color);
 193                                 *src = 'o'; // for future recursions
 194                                 return;
 195                         case '.': /* 0 */ break;
 196                         case 'X': pat |= S_BLACK << (patofs * 2); break;
 197                         case 'O': pat |= S_WHITE << (patofs * 2); break;
 198                         case '#': pat |= S_OFFBOARD << (patofs * 2); break;
 199                 }
 200         }
 201
 202         /* Original pattern, all transpositions and rotations */
 203         pattern_record(table, src - 9, pat, fixed_color);
 204         pattern_record(table, src - 9, pat_vmirror(pat), fixed_color);
 205         pattern_record(table, src - 9, pat_hmirror(pat), fixed_color);
 206         pattern_record(table, src - 9, pat_vmirror(pat_hmirror(pat)), fixed_color);
 207         pattern_record(table, src - 9, pat_90rot(pat), fixed_color);
 208         pattern_record(table, src - 9, pat_90rot(pat_vmirror(pat)), fixed_color);
 209         pattern_record(table, src - 9, pat_90rot(pat_hmirror(pat)), fixed_color);
 210         pattern_record(table, src - 9, pat_90rot(pat_vmirror(pat_hmirror(pat))), fixed_color);
 211 }
 212
 213 #warning gcc is stupid; ignore following out-of-bounds warnings
 214
 215 static void
 216 patterns_gen(struct playout_policy *p, char src[][11], int src_n)
 217 {
 218         struct moggy_policy *pp = p->data;
 219
 220         for (int i = 0; i < src_n; i++) {
 221                 //printf("<%s>\n", src[i]);
 222                 int fixed_color = 0;
 223                 switch (src[i][9]) {
 224                         case 'X': fixed_color = S_BLACK; break;
 225                         case 'O': fixed_color = S_WHITE; break;
 226                 }
 227                 //fprintf(stderr, "** %s **\n", src[i]);
 228                 pattern_gen(pp->patterns, 0, src[i], 9, fixed_color);
 229         }
 230 }
 231
 232 static bool
 233 patterns_load(char src[][11], int src_n, char *filename)
 234 {
 235         FILE *f = fopen("moggy.patterns", "r");
 236         if (!f) return false;
 237
 238         int i;
 239         for (i = 0; i < moggy_patterns_src_n; i++) {
 240                 char line[32];
 241                 if (!fgets(line, sizeof(line), f))
 242                         goto error;
 243                 int l = strlen(line);
 244                 if (l != 10 + (line[l - 1] == '\n'))
 245                         goto error;
 246                 memcpy(src[i], line, 10);
 247         }
 248         fprintf(stderr, "moggy.patterns: %d patterns loaded\n", i);
 249         fclose(f);
 250         return true;
 251 error:
 252         fprintf(stderr, "Error loading moggy.patterns.\n");
 253         fclose(f);
 254         return false;
 255 }
 256
 257 static void
 258 patterns_init(struct playout_policy *p)
 259 {
 260         char src[moggy_patterns_src_n][11];
 261
 262         if (!patterns_load(src, moggy_patterns_src_n, "moggy.patterns")) {
 263                 /* Use default pattern set. */
 264                 for (int i = 0; i < moggy_patterns_src_n; i++)
 265                         strcpy(src[i], moggy_patterns_src[i]);
 266         }
 267
 268         patterns_gen(p, src, moggy_patterns_src_n);
 269 }
 270
 271
 272 /* Check if we match any pattern centered on given move. */
 273 static bool
 274 test_pattern_here(struct playout_policy *p, char *hashtable,
 275                 struct board *b, struct move *m)
 276 {
 277         int pat = 0;
 278         int x = coord_x(m->coord, b), y = coord_y(m->coord, b);
 279         pat |= (board_atxy(b, x - 1, y - 1) << 14)
 280                 | (board_atxy(b, x, y - 1) << 12)
 281                 | (board_atxy(b, x + 1, y - 1) << 10);
 282         pat |= (board_atxy(b, x - 1, y) << 8)
 283                 | (board_atxy(b, x + 1, y) << 6);
 284         pat |= (board_atxy(b, x - 1, y + 1) << 4)
 285                 | (board_atxy(b, x, y + 1) << 2)
 286                 | (board_atxy(b, x + 1, y + 1));
 287         //fprintf(stderr, "(%d,%d) hashtable[%04x] = %d\n", x, y, pat, hashtable[pat]);
 288         return (hashtable[pat] & m->color) && !is_bad_selfatari(b, m->color, m->coord);
 289 }
 290
 291 static void
 292 apply_pattern_here(struct playout_policy *p, char *hashtable,
 293                 struct board *b, struct move *m, struct move_queue *q)
 294 {
 295         if (test_pattern_here(p, hashtable, b, m))
 296                 q->move[q->moves++] = m->coord;
 297 }
 298
 299 /* Check if we match any pattern around given move (with the other color to play). */
 300 static coord_t
 301 apply_pattern(struct playout_policy *p, struct board *b, struct move *m)
 302 {
 303         struct moggy_policy *pp = p->data;
 304         struct move_queue q;
 305         q.moves = 0;
 306
 307         /* Suicides do not make any patterns and confuse us. */
 308         if (board_at(b, m->coord) == S_NONE || board_at(b, m->coord) == S_OFFBOARD)
 309                 return pass;
 310
 311         foreach_neighbor(b, m->coord, {
 312                 struct move m2; m2.coord = c; m2.color = stone_other(m->color);
 313                 if (board_is_valid_move(b, &m2))
 314                         apply_pattern_here(p, pp->patterns, b, &m2, &q);
 315         });
 316         foreach_diag_neighbor(b, m->coord) {
 317                 struct move m2; m2.coord = c; m2.color = stone_other(m->color);
 318                 if (board_is_valid_move(b, &m2))
 319                         apply_pattern_here(p, pp->patterns, b, &m2, &q);
 320         } foreach_diag_neighbor_end;
 321
 322         if (PLDEBUGL(5)) {
 323                 fprintf(stderr, "Pattern candidate moves: ");
 324                 for (int i = 0; i < q.moves; i++) {
 325                         fprintf(stderr, "%s ", coord2sstr(q.move[i], b));
 326                 }
 327                 fprintf(stderr, "\n");
 328         }
 329
 330         int i = fast_random(q.moves);
 331         return q.moves ? q.move[i] : pass;
 332 }
 333
 334
 335
 336 /* Is this ladder breaker friendly for the one who catches ladder. */
 337 static bool
 338 ladder_catcher(struct board *b, int x, int y, enum stone laddered)
 339 {
 340         enum stone breaker = board_atxy(b, x, y);
 341         return breaker == stone_other(laddered) || breaker == S_OFFBOARD;
 342 }
 343
 344 static bool
 345 ladder_catches(struct playout_policy *p, struct board *b, coord_t coord, group_t laddered)
 346 {
 347         struct moggy_policy *pp = p->data;
 348
 349         /* This is very trivial and gets a lot of corner cases wrong.
 350          * We need this to be just very fast. One important point is
 351          * that we sometimes might not notice a ladder but if we do,
 352          * it should always work; thus we can use this for strong
 353          * negative hinting safely. */
 354
 355         enum stone lcolor = board_at(b, group_base(laddered));
 356         int x = coord_x(coord, b), y = coord_y(coord, b);
 357
 358         if (PLDEBUGL(6))
 359                 fprintf(stderr, "ladder check - does %s play out %s's laddered group %s?\n",
 360                         coord2sstr(coord, b), stone2str(lcolor), coord2sstr(laddered, b));
 361
 362         /* First, special-case first-line "ladders". This is a huge chunk
 363          * of ladders we actually meet and want to play. */
 364         if (pp->borderladders
 365             && neighbor_count_at(b, coord, S_OFFBOARD) == 1
 366             && neighbor_count_at(b, coord, lcolor) == 1) {
 367                 if (PLDEBUGL(5))
 368                         fprintf(stderr, "border ladder\n");
 369                 /* Direction along border; xd is horiz. border, yd vertical. */
 370                 int xd = 0, yd = 0;
 371                 if (board_atxy(b, x + 1, y) == S_OFFBOARD || board_atxy(b, x - 1, y) == S_OFFBOARD)
 372                         yd = 1;
 373                 else
 374                         xd = 1;
 375                 /* Direction from the border; -1 is above/left, 1 is below/right. */
 376                 int dd = (board_atxy(b, x + yd, y + xd) == S_OFFBOARD) ? 1 : -1;
 377                 if (PLDEBUGL(6))
 378                         fprintf(stderr, "xd %d yd %d dd %d\n", xd, yd, dd);
 379                 /* | ? ?
 380                  * | . O #
 381                  * | c X #
 382                  * | . O #
 383                  * | ? ?   */
 384                 /* This is normally caught, unless we have friends both above
 385                  * and below... */
 386                 if (board_atxy(b, x + xd * 2, y + yd * 2) == lcolor
 387                     && board_atxy(b, x - xd * 2, y - yd * 2) == lcolor)
 388                         return false;
 389                 /* ...or can't block where we need because of shortage
 390                  * of liberties. */
 391                 int libs1 = board_group_info(b, group_atxy(b, x + xd - yd * dd, y + yd - xd * dd)).libs;
 392                 int libs2 = board_group_info(b, group_atxy(b, x - xd - yd * dd, y - yd - xd * dd)).libs;
 393                 if (PLDEBUGL(6))
 394                         fprintf(stderr, "libs1 %d libs2 %d\n", libs1, libs2);
 395                 if (libs1 < 2 && libs2 < 2)
 396                         return false;
 397                 if (board_atxy(b, x + xd * 2, y + yd * 2) == lcolor && libs1 < 3)
 398                         return false;
 399                 if (board_atxy(b, x - xd * 2, y - yd * 2) == lcolor && libs2 < 3)
 400                         return false;
 401                 return true;
 402         }
 403
 404         if (!pp->ladders)
 405                 return false;
 406
 407         /* Figure out the ladder direction */
 408         int xd, yd;
 409         xd = board_atxy(b, x + 1, y) == S_NONE ? 1 : board_atxy(b, x - 1, y) == S_NONE ? -1 : 0;
 410         yd = board_atxy(b, x, y + 1) == S_NONE ? 1 : board_atxy(b, x, y - 1) == S_NONE ? -1 : 0;
 411
 412         if (!xd || !yd) {
 413                 if (PLDEBUGL(5))
 414                         fprintf(stderr, "no ladder, too little space; self-atari?\n");
 415                 return false;
 416         }
 417
 418         /* For given (xd,yd), we have two possibilities where to move
 419          * next. Consider (-1,-1):
 420          * n X .   n c X
 421          * c O X   X O #
 422          * X # #   . X #
 423          */
 424         bool horiz_first = ladder_catcher(b, x, y - yd, lcolor); // left case
 425         bool vert_first = ladder_catcher(b, x - xd, y, lcolor); // right case
 426
 427         /* We don't have to look at the other 'X' in the position - if it
 428          * wouldn't be there, the group wouldn't be in atari. */
 429
 430         /* We do only tight ladders, not loose ladders. Furthermore,
 431          * the ladders need to be simple:
 432          * . X .             . . X
 433          * c O X supported   . c O unsupported
 434          * X # #             X O #
 435          */
 436         assert(!(horiz_first && vert_first));
 437         if (!horiz_first && !vert_first) {
 438                 /* TODO: In case of basic non-simple ladder, play out both variants. */
 439                 if (PLDEBUGL(5))
 440                         fprintf(stderr, "non-simple ladder\n");
 441                 return false;
 442         }
 443
 444         /* We do that below for further moves, but now initially - check
 445          * that at 'c', we aren't putting any of the catching stones
 446          * in atari. */
 447 #if 1 // this might be broken?
 448 #define check_catcher_danger(b, x_, y_) do { \
 449         if (board_atxy(b, (x_), (y_)) != S_OFFBOARD \
 450             && board_group_info(b, group_atxy(b, (x_), (y_))).libs <= 2) { \
 451                 if (PLDEBUGL(5)) \
 452                         fprintf(stderr, "ladder failed - atari at the beginning\n"); \
 453                 return false; \
 454         } } while (0)
 455
 456         if (horiz_first) {
 457                 check_catcher_danger(b, x, y - yd);
 458                 check_catcher_danger(b, x - xd, y + yd);
 459         } else {
 460                 check_catcher_danger(b, x - xd, y);
 461                 check_catcher_danger(b, x + xd, y - yd);
 462         }
 463 #undef check_catcher_danger
 464 #endif
 465
 466 #define ladder_check(xd1_, yd1_, xd2_, yd2_, xd3_, yd3_)        \
 467         if (board_atxy(b, x, y) != S_NONE) { \
 468                 /* Did we hit a stone when playing out ladder? */ \
 469                 if (ladder_catcher(b, x, y, lcolor)) \
 470                         return true; /* ladder works */ \
 471                 if (board_group_info(b, group_atxy(b, x, y)).lib[0] > 0) \
 472                         return false; /* friend that's not in atari himself */ \
 473         } else { \
 474                 /* No. So we are at new position. \
 475                  * We need to check indirect ladder breakers. */ \
 476                 /* . 2 x 3 . \
 477                  * . x o O 1 <- only at O we can check for o at 2 \
 478                  * x o o x .    otherwise x at O would be still deadly \
 479                  * o o x . . \
 480                  * We check for o and x at 1, these are vital. \
 481                  * We check only for o at 2; x at 2 would mean we \
 482                  * need to fork (one step earlier). */ \
 483                 coord_t c1 = coord_xy(b, x + (xd1_), y + (yd1_)); \
 484                 enum stone s1 = board_at(b, c1); \
 485                 if (s1 == lcolor) return false; \
 486                 if (s1 == stone_other(lcolor)) { \
 487                         /* One more thing - if the position at 3 is \
 488                          * friendly and safe, we escaped anyway! */ \
 489                         coord_t c3 = coord_xy(b, x + (xd3_), y + (yd3_)); \
 490                         return board_at(b, c3) != lcolor \
 491                                || board_group_info(b, group_at(b, c3)).libs < 2; \
 492                 } \
 493                 enum stone s2 = board_atxy(b, x + (xd2_), y + (yd2_)); \
 494                 if (s2 == lcolor) return false; \
 495                 /* Then, can X actually "play" 1 in the ladder? */ \
 496                 if (neighbor_count_at(b, c1, lcolor) + neighbor_count_at(b, c1, S_OFFBOARD) >= 2) \
 497                         return false; /* It would be self-atari! */ \
 498         }
 499 #define ladder_horiz    do { if (PLDEBUGL(6)) fprintf(stderr, "%d,%d horiz step (%d,%d)\n", x, y, xd, yd); x += xd; ladder_check(xd, 0, -2 * xd, yd, 0, yd); } while (0)
 500 #define ladder_vert     do { if (PLDEBUGL(6)) fprintf(stderr, "%d,%d vert step of (%d,%d)\n", x, y, xd, yd); y += yd; ladder_check(0, yd, xd, -2 * yd, xd, 0); } while (0)
 501
 502         if (ladder_catcher(b, x - xd, y, lcolor))
 503                 ladder_horiz;
 504         do {
 505                 ladder_vert;
 506                 ladder_horiz;
 507         } while (1);
 508 }
 509
 510
 511 static coord_t
 512 can_be_captured(struct playout_policy *p, struct board *b, enum stone capturer, coord_t c, enum stone to_play)
 513 {
 514         if (board_at(b, c) != stone_other(capturer)
 515             || board_group_info(b, group_at(b, c)).libs > 1)
 516                 return pass;
 517
 518         coord_t capture = board_group_info(b, group_at(b, c)).lib[0];
 519         if (PLDEBUGL(6))
 520                 fprintf(stderr, "can capture group %d (%s)?\n",
 521                         group_at(b, c), coord2sstr(capture, b));
 522         struct move m; m.color = to_play; m.coord = capture;
 523         /* Does that move even make sense? */
 524         if (!board_is_valid_move(b, &m))
 525                 return pass;
 526         /* Make sure capturing the group will actually
 527          * do us any good. */
 528         else if (is_bad_selfatari(b, to_play, capture))
 529                 return pass;
 530
 531         return capture;
 532 }
 533
 534 static bool
 535 can_be_rescued(struct playout_policy *p, struct board *b, group_t group, enum stone color, coord_t lib)
 536 {
 537         /* Does playing on the liberty rescue the group? */
 538         if (!is_bad_selfatari(b, color, lib))
 539                 return true;
 540
 541         /* Then, maybe we can capture one of our neighbors? */
 542         foreach_in_group(b, group) {
 543                 foreach_neighbor(b, c, {
 544                         if (!is_pass(can_be_captured(p, b, color, c, color)))
 545                                 return true;
 546                 });
 547         } foreach_in_group_end;
 548         return false;
 549 }
 550
 551 static void
 552 group_atari_check(struct playout_policy *p, struct board *b, group_t group, enum stone to_play, struct move_queue *q)
 553 {
 554         int qmoves_prev = q->moves;
 555
 556         /* We don't use @to_play almost anywhere since any moves here are good
 557          * for both defender and attacker. */
 558
 559         enum stone color = board_at(b, group_base(group));
 560         coord_t lib = board_group_info(b, group).lib[0];
 561
 562         assert(color != S_OFFBOARD && color != S_NONE);
 563         if (PLDEBUGL(5))
 564                 fprintf(stderr, "[%s] atariiiiiiiii %s of color %d\n", coord2sstr(group, b), coord2sstr(lib, b), color);
 565         assert(board_at(b, lib) == S_NONE);
 566
 567         /* Do not bother with kos. */
 568         if (group_is_onestone(b, group)
 569             && neighbor_count_at(b, lib, color) + neighbor_count_at(b, lib, S_OFFBOARD) == 4)
 570                 return;
 571
 572         /* Can we capture some neighbor? */
 573         foreach_in_group(b, group) {
 574                 foreach_neighbor(b, c, {
 575                         coord_t capture = can_be_captured(p, b, color, c, to_play);
 576                         if (is_pass(capture))
 577                                 continue;
 578
 579                         q->move[q->moves++] = capture;
 580                         mq_nodup(q);
 581                 });
 582         } foreach_in_group_end;
 583
 584         struct move m; m.color = to_play; m.coord = lib;
 585         if (!board_is_valid_move(b, &m))
 586                 return;
 587
 588         /* Do not suicide... */
 589         if (is_bad_selfatari(b, to_play, lib))
 590                 return;
 591         /* Do not remove group that cannot be saved by the opponent. */
 592         if (to_play != color && !can_be_rescued(p, b, group, color, lib))
 593                 return;
 594         if (PLDEBUGL(6))
 595                 fprintf(stderr, "...escape route valid\n");
 596
 597         /* ...or play out ladders. */
 598         if (ladder_catches(p, b, lib, group)) {
 599                 return;
 600         }
 601         if (PLDEBUGL(6))
 602                 fprintf(stderr, "...no ladder\n");
 603
 604         if (to_play != color) {
 605                 /* We are the attacker! In that case, throw away the moves
 606                  * that defend our groups, since we can capture the culprit. */
 607                 q->moves = qmoves_prev;
 608         }
 609
 610         q->move[q->moves++] = lib;
 611         mq_nodup(q);
 612 }
 613
 614 static coord_t
 615 global_atari_check(struct playout_policy *p, struct board *b, enum stone to_play)
 616 {
 617         struct move_queue q;
 618         q.moves = 0;
 619
 620         if (b->clen == 0)
 621                 return pass;
 622
 623         int g_base = fast_random(b->clen);
 624         for (int g = g_base; g < b->clen; g++) {
 625                 group_atari_check(p, b, group_at(b, group_base(b->c[g])), to_play, &q);
 626                 if (q.moves > 0)
 627                         return q.move[fast_random(q.moves)];
 628         }
 629         for (int g = 0; g < g_base; g++) {
 630                 group_atari_check(p, b, group_at(b, group_base(b->c[g])), to_play, &q);
 631                 if (q.moves > 0)
 632                         return q.move[fast_random(q.moves)];
 633         }
 634         return pass;
 635 }
 636
 637 static coord_t
 638 local_atari_check(struct playout_policy *p, struct board *b, struct move *m)
 639 {
 640         struct move_queue q;
 641         q.moves = 0;
 642
 643         /* Did the opponent play a self-atari? */
 644         if (board_group_info(b, group_at(b, m->coord)).libs == 1) {
 645                 group_atari_check(p, b, group_at(b, m->coord), stone_other(m->color), &q);
 646         }
 647
 648         foreach_neighbor(b, m->coord, {
 649                 group_t g = group_at(b, c);
 650                 if (!g || board_group_info(b, g).libs != 1)
 651                         continue;
 652                 group_atari_check(p, b, g, stone_other(m->color), &q);
 653         });
 654
 655         if (PLDEBUGL(5)) {
 656                 fprintf(stderr, "Local atari candidate moves: ");
 657                 for (int i = 0; i < q.moves; i++) {
 658                         fprintf(stderr, "%s ", coord2sstr(q.move[i], b));
 659                 }
 660                 fprintf(stderr, "\n");
 661         }
 662
 663         int i = fast_random(q.moves);
 664         return q.moves ? q.move[i] : pass;
 665 }
 666
 667 coord_t
 668 playout_moggy_choose(struct playout_policy *p, struct board *b, enum stone to_play)
 669 {
 670         struct moggy_policy *pp = p->data;
 671         coord_t c;
 672
 673         if (PLDEBUGL(5))
 674                 board_print(b, stderr);
 675
 676         /* Local checks */
 677         if (!is_pass(b->last_move.coord)) {
 678                 /* Local group in atari? */
 679                 if (pp->lcapturerate > fast_random(100)) {
 680                         c = local_atari_check(p, b, &b->last_move);
 681                         if (!is_pass(c))
 682                                 return c;
 683                 }
 684
 685                 /* Check for patterns we know */
 686                 if (pp->patternrate > fast_random(100)) {
 687                         c = apply_pattern(p, b, &b->last_move);
 688                         if (!is_pass(c))
 689                                 return c;
 690                 }
 691         }
 692
 693         /* Global checks */
 694
 695         /* Any groups in atari? */
 696         if (pp->capturerate > fast_random(100)) {
 697                 c = global_atari_check(p, b, to_play);
 698                 if (!is_pass(c))
 699                         return c;
 700         }
 701
 702         return pass;
 703 }
 704
 705 static int
 706 assess_local_bonus(struct playout_policy *p, struct board *board, struct move *a, struct move *b, int games)
 707 {
 708         struct moggy_policy *pp = p->data;
 709         if (!pp->assess_local)
 710                 return games;
 711
 712         int dx = abs(coord_x(a->coord, board) - coord_x(b->coord, board));
 713         int dy = abs(coord_y(a->coord, board) - coord_y(b->coord, board));
 714         /* adjecent move, directly or diagonally? */
 715         if (dx + dy <= 1 + (dx && dy))
 716                 return games;
 717         else
 718                 return games / 2;
 719 }
 720
 721 int
 722 playout_moggy_assess(struct playout_policy *p, struct board *b, struct move *m, int games)
 723 {
 724         struct moggy_policy *pp = p->data;
 725
 726         if (is_pass(m->coord))
 727                 return 0;
 728
 729         if (PLDEBUGL(5)) {
 730                 fprintf(stderr, "ASSESS of %s:\n", coord2sstr(m->coord, b));
 731                 board_print(b, stderr);
 732         }
 733
 734         /* Are we dealing with atari? */
 735         if (pp->lcapturerate || pp->capturerate) {
 736                 bool ladder = false;
 737
 738                 foreach_neighbor(b, m->coord, {
 739                         group_t g = group_at(b, c);
 740                         if (!g || board_group_info(b, g).libs != 1)
 741                                 continue;
 742
 743                         /* _Never_ play here if this move plays out
 744                          * a caught ladder. (Unless it captures another
 745                          * group. :-) */
 746                         if (pp->ladderassess && ladder_catches(p, b, m->coord, g)) {
 747                                 /* Note that the opposite is not guarded against;
 748                                  * we do not advise against capturing a laddered
 749                                  * group (but we don't encourage it either). Such
 750                                  * a move can simplify tactical situations if we
 751                                  * can afford it. */
 752                                 if (m->color == board_at(b, c))
 753                                         ladder = true;
 754                                 continue;
 755                         }
 756
 757                         struct move_queue q; q.moves = 0;
 758                         group_atari_check(p, b, g, m->color, &q);
 759                         while (q.moves--)
 760                                 if (q.move[q.moves] == m->coord) {
 761                                         if (PLDEBUGL(5))
 762                                                 fprintf(stderr, "1.0: atari\n");
 763                                         return assess_local_bonus(p, b, &b->last_move, m, games) * 2;
 764                                 }
 765                 });
 766
 767                 if (ladder) {
 768                         if (PLDEBUGL(5))
 769                                 fprintf(stderr, "0.0: ladder\n");
 770                         return -games;
 771                 }
 772         }
 773
 774         /* Is this move a self-atari? */
 775         if (pp->selfatarirate) {
 776                 if (is_bad_selfatari(b, m->color, m->coord)) {
 777                         if (PLDEBUGL(5))
 778                                 fprintf(stderr, "0.0: self-atari\n");
 779                         return -games;
 780                 }
 781         }
 782
 783         /* Pattern check */
 784         if (pp->patternrate) {
 785                 if (test_pattern_here(p, pp->patterns, b, m)) {
 786                         if (PLDEBUGL(5))
 787                                 fprintf(stderr, "1.0: pattern\n");
 788                         return assess_local_bonus(p, b, &b->last_move, m, games);
 789                 }
 790         }
 791
 792         return 0;
 793 }
 794
 795 bool
 796 playout_moggy_permit(struct playout_policy *p, struct board *b, struct move *m)
 797 {
 798         struct moggy_policy *pp = p->data;
 799
 800         /* The idea is simple for now - never allow self-atari moves.
 801          * They suck in general, but this also permits us to actually
 802          * handle seki in the playout stage. */
 803
 804         if (fast_random(100) >= pp->selfatarirate) {
 805                 if (PLDEBUGL(5))
 806                         fprintf(stderr, "skipping sar test\n");
 807                 return true;
 808         }
 809         bool selfatari = is_bad_selfatari(b, m->color, m->coord);
 810         if (PLDEBUGL(5) && selfatari)
 811                 fprintf(stderr, "__ Prohibiting self-atari %s %s\n",
 812                         stone2str(m->color), coord2sstr(m->coord, b));
 813         return !selfatari;
 814 }
 815
 816
 817 struct playout_policy *
 818 playout_moggy_init(char *arg)
 819 {
 820         struct playout_policy *p = calloc(1, sizeof(*p));
 821         struct moggy_policy *pp = calloc(1, sizeof(*pp));
 822         p->data = pp;
 823         p->choose = playout_moggy_choose;
 824         p->assess = playout_moggy_assess;
 825         p->permit = playout_moggy_permit;
 826
 827         int rate = 90;
 828
 829         pp->lcapturerate = pp->capturerate = pp->patternrate = pp->selfatarirate = -1;
 830         pp->ladders = pp->borderladders = true;
 831         pp->ladderassess = true;
 832
 833         if (arg) {
 834                 char *optspec, *next = arg;
 835                 while (*next) {
 836                         optspec = next;
 837                         next += strcspn(next, ":");
 838                         if (*next) { *next++ = 0; } else { *next = 0; }
 839
 840                         char *optname = optspec;
 841                         char *optval = strchr(optspec, '=');
 842                         if (optval) *optval++ = 0;
 843
 844                         if (!strcasecmp(optname, "lcapturerate") && optval) {
 845                                 pp->lcapturerate = atoi(optval);
 846                         } else if (!strcasecmp(optname, "capturerate") && optval) {
 847                                 pp->capturerate = atoi(optval);
 848                         } else if (!strcasecmp(optname, "patternrate") && optval) {
 849                                 pp->patternrate = atoi(optval);
 850                         } else if (!strcasecmp(optname, "selfatarirate") && optval) {
 851                                 pp->selfatarirate = atoi(optval);
 852                         } else if (!strcasecmp(optname, "rate") && optval) {
 853                                 rate = atoi(optval);
 854                         } else if (!strcasecmp(optname, "ladders")) {
 855                                 pp->ladders = optval && *optval == '0' ? false : true;
 856                         } else if (!strcasecmp(optname, "borderladders")) {
 857                                 pp->borderladders = optval && *optval == '0' ? false : true;
 858                         } else if (!strcasecmp(optname, "ladderassess")) {
 859                                 pp->ladderassess = optval && *optval == '0' ? false : true;
 860                         } else if (!strcasecmp(optname, "assess_local")) {
 861                                 pp->assess_local = optval && *optval == '0' ? false : true;
 862                         } else {
 863                                 fprintf(stderr, "playout-moggy: Invalid policy argument %s or missing value\n", optname);
 864                         }
 865                 }
 866         }
 867         if (pp->lcapturerate == -1) pp->lcapturerate = rate;
 868         if (pp->capturerate == -1) pp->capturerate = rate;
 869         if (pp->patternrate == -1) pp->patternrate = rate;
 870         if (pp->selfatarirate == -1) pp->selfatarirate = rate;
 871
 872         patterns_init(p);
 873
 874         return p;
 875 }