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