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