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