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