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)
 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                 return;
 437         }
 438         if (PLDEBUGL(6))
 439                 fprintf(stderr, "...no ladder\n");
 440
 441         if (to_play != color) {
 442                 /* We are the attacker! In that case, throw away the moves
 443                  * that defend our groups, since we can capture the culprit. */
 444                 q->moves = qmoves_prev;
 445         }
 446
 447         q->move[q->moves++] = lib;
 448         mq_nodup(q);
 449 }
 450
 451 static coord_t
 452 global_atari_check(struct playout_policy *p, struct board *b, enum stone to_play)
 453 {
 454         struct move_queue q;
 455         q.moves = 0;
 456
 457         if (b->clen == 0)
 458                 return pass;
 459
 460         int g_base = fast_random(b->clen);
 461         for (int g = g_base; g < b->clen; g++) {
 462                 group_atari_check(p, b, group_at(b, group_base(b->c[g])), to_play, &q);
 463                 if (q.moves > 0)
 464                         return q.move[fast_random(q.moves)];
 465         }
 466         for (int g = 0; g < g_base; g++) {
 467                 group_atari_check(p, b, group_at(b, group_base(b->c[g])), to_play, &q);
 468                 if (q.moves > 0)
 469                         return q.move[fast_random(q.moves)];
 470         }
 471         return pass;
 472 }
 473
 474 static coord_t
 475 local_atari_check(struct playout_policy *p, struct board *b, struct move *m)
 476 {
 477         struct move_queue q;
 478         q.moves = 0;
 479
 480         /* Did the opponent play a self-atari? */
 481         if (board_group_info(b, group_at(b, m->coord)).libs == 1) {
 482                 group_atari_check(p, b, group_at(b, m->coord), stone_other(m->color), &q);
 483         }
 484
 485         foreach_neighbor(b, m->coord, {
 486                 group_t g = group_at(b, c);
 487                 if (!g || board_group_info(b, g).libs != 1)
 488                         continue;
 489                 group_atari_check(p, b, g, stone_other(m->color), &q);
 490         });
 491
 492         if (PLDEBUGL(5)) {
 493                 fprintf(stderr, "Local atari candidate moves: ");
 494                 for (int i = 0; i < q.moves; i++) {
 495                         fprintf(stderr, "%s ", coord2sstr(q.move[i], b));
 496                 }
 497                 fprintf(stderr, "\n");
 498         }
 499
 500         int i = fast_random(q.moves);
 501         return q.moves ? q.move[i] : pass;
 502 }
 503
 504 static bool
 505 miai_2lib(struct board *b, group_t group, enum stone color)
 506 {
 507         bool can_connect = false, can_pull_out = false;
 508         /* We have miai if we can either connect on both libs,
 509          * or connect on one lib and escape on another. (Just
 510          * having two escape routes can be risky.) */
 511         foreach_neighbor(b, board_group_info(b, group).lib[0], {
 512                 enum stone cc = board_at(b, c);
 513                 if (cc == S_NONE && cc != board_group_info(b, group).lib[1]) {
 514                         can_pull_out = true;
 515                 } else if (cc != color) {
 516                         continue;
 517                 }
 518
 519                 group_t cg = group_at(b, c);
 520                 if (cg && cg != group && board_group_info(b, cg).libs > 1)
 521                         can_connect = true;
 522         });
 523         foreach_neighbor(b, board_group_info(b, group).lib[1], {
 524                 enum stone cc = board_at(b, c);
 525                 if (cc == S_NONE && cc != board_group_info(b, group).lib[0] && can_connect) {
 526                         return true;
 527                 } else if (cc != color) {
 528                         continue;
 529                 }
 530
 531                 group_t cg = group_at(b, c);
 532                 if (cg && cg != group && board_group_info(b, cg).libs > 1)
 533                         return (can_connect || can_pull_out);
 534         });
 535         return false;
 536 }
 537
 538 static void
 539 group_2lib_check(struct playout_policy *p, struct board *b, group_t group, enum stone to_play, struct move_queue *q)
 540 {
 541         enum stone color = board_at(b, group_base(group));
 542         assert(color != S_OFFBOARD && color != S_NONE);
 543
 544         if (PLDEBUGL(5))
 545                 fprintf(stderr, "[%s] 2lib check of color %d\n",
 546                         coord2sstr(group, b), color);
 547
 548         /* Do not try to atari groups that cannot be harmed. */
 549         if (miai_2lib(b, group, color))
 550                 return;
 551
 552         for (int i = 0; i < 2; i++) {
 553                 coord_t lib = board_group_info(b, group).lib[i];
 554                 assert(board_at(b, lib) == S_NONE);
 555                 struct move m; m.color = to_play; m.coord = lib;
 556                 if (!board_is_valid_move(b, &m))
 557                         continue;
 558
 559                 /* Don't play at the spot if it is extremely short
 560                  * of liberties... */
 561                 /* XXX: This looks harmful, could significantly
 562                  * prefer atari to throwin:
 563                  *
 564                  * XXXOOOOOXX
 565                  * .OO.....OX
 566                  * XXXOOOOOOX */
 567 #if 0
 568                 if (neighbor_count_at(b, lib, stone_other(color)) + immediate_liberty_count(b, lib) < 2)
 569                         continue;
 570 #endif
 571
 572                 /* If the owner can't play at the spot, we don't want
 573                  * to bother either. */
 574                 if (is_bad_selfatari(b, color, lib))
 575                         continue;
 576
 577                 /* Of course we don't want to play bad selfatari
 578                  * ourselves, if we are the attacker... */
 579                 if (to_play != color && is_bad_selfatari(b, to_play, lib))
 580                         continue;
 581
 582                 /* Tasty! Crispy! Good! */
 583                 q->move[q->moves++] = lib;
 584         }
 585 }
 586
 587 static coord_t
 588 local_2lib_check(struct playout_policy *p, struct board *b, struct move *m)
 589 {
 590         struct move_queue q;
 591         q.moves = 0;
 592
 593         /* Does the opponent have just two liberties? */
 594         if (board_group_info(b, group_at(b, m->coord)).libs == 2) {
 595                 group_2lib_check(p, b, group_at(b, m->coord), stone_other(m->color), &q);
 596 #if 0
 597                 /* We always prefer to take off an enemy chain liberty
 598                  * before pulling out ourselves. */
 599                 /* XXX: We aren't guaranteed to return to that group
 600                  * later. */
 601                 if (q.moves)
 602                         return q.move[fast_random(q.moves)];
 603 #endif
 604         }
 605
 606         /* Then he took a third liberty from neighboring chain? */
 607         foreach_neighbor(b, m->coord, {
 608                 group_t g = group_at(b, c);
 609                 if (!g || board_group_info(b, g).libs != 2)
 610                         continue;
 611                 group_2lib_check(p, b, g, stone_other(m->color), &q);
 612         });
 613
 614         if (PLDEBUGL(5)) {
 615                 fprintf(stderr, "Local 2lib candidate moves: ");
 616                 for (int i = 0; i < q.moves; i++) {
 617                         fprintf(stderr, "%s ", coord2sstr(q.move[i], b));
 618                 }
 619                 fprintf(stderr, "\n");
 620         }
 621
 622         int i = fast_random(q.moves);
 623         return q.moves ? q.move[i] : pass;
 624 }
 625
 626 coord_t
 627 playout_moggy_choose(struct playout_policy *p, struct board *b, enum stone to_play)
 628 {
 629         struct moggy_policy *pp = p->data;
 630         coord_t c;
 631
 632         if (PLDEBUGL(5))
 633                 board_print(b, stderr);
 634
 635         /* Local checks */
 636         if (!is_pass(b->last_move.coord)) {
 637                 /* Local group in atari? */
 638                 if (pp->lcapturerate > fast_random(100)) {
 639                         c = local_atari_check(p, b, &b->last_move);
 640                         if (!is_pass(c))
 641                                 return c;
 642                 }
 643
 644                 /* Local group can be PUT in atari? */
 645                 if (pp->atarirate > fast_random(100)) {
 646                         c = local_2lib_check(p, b, &b->last_move);
 647                         if (!is_pass(c))
 648                                 return c;
 649                 }
 650
 651                 /* Check for patterns we know */
 652                 if (pp->patternrate > fast_random(100)) {
 653                         c = apply_pattern(p, b, &b->last_move,
 654                                           pp->pattern2 && b->last_move2.coord >= 0 ? &b->last_move2 : NULL);
 655                         if (!is_pass(c))
 656                                 return c;
 657                 }
 658         }
 659
 660         /* Global checks */
 661
 662         /* Any groups in atari? */
 663         if (pp->capturerate > fast_random(100)) {
 664                 c = global_atari_check(p, b, to_play);
 665                 if (!is_pass(c))
 666                         return c;
 667         }
 668
 669         /* Fill board */
 670         int fbtries = b->flen / 8;
 671         for (int i = 0; i < (fbtries < pp->fillboardtries ? fbtries : pp->fillboardtries); i++) {
 672                 coord_t coord = b->f[fast_random(b->flen)];
 673                 if (immediate_liberty_count(b, coord) != 4)
 674                         continue;
 675                 foreach_diag_neighbor(b, coord) {
 676                         if (board_at(b, c) != S_NONE)
 677                                 goto next_try;
 678                 } foreach_diag_neighbor_end;
 679                 return coord;
 680 next_try:;
 681         }
 682
 683         return pass;
 684 }
 685
 686 static int
 687 assess_local_bonus(struct playout_policy *p, struct board *board, struct move *a, struct move *b, int games)
 688 {
 689         struct moggy_policy *pp = p->data;
 690         if (!pp->assess_local)
 691                 return games;
 692
 693         int dx = abs(coord_x(a->coord, board) - coord_x(b->coord, board));
 694         int dy = abs(coord_y(a->coord, board) - coord_y(b->coord, board));
 695         /* adjecent move, directly or diagonally? */
 696         if (dx + dy <= 1 + (dx && dy))
 697                 return games;
 698         else
 699                 return games / 2;
 700 }
 701
 702 int
 703 playout_moggy_assess_one(struct playout_policy *p, struct board *b, struct move *m, int games)
 704 {
 705         struct moggy_policy *pp = p->data;
 706
 707         if (is_pass(m->coord) || !board_is_valid_move(b, m))
 708                 return 0;
 709
 710         if (PLDEBUGL(5)) {
 711                 fprintf(stderr, "ASSESS of %s:\n", coord2sstr(m->coord, b));
 712                 board_print(b, stderr);
 713         }
 714
 715         /* Are we dealing with atari? */
 716         if (pp->lcapturerate || pp->capturerate || pp->atarirate) {
 717                 bool ladder = false;
 718
 719                 foreach_neighbor(b, m->coord, {
 720                         group_t g = group_at(b, c);
 721                         if (!g || board_group_info(b, g).libs > 2)
 722                                 continue;
 723
 724                         if (board_group_info(b, g).libs == 2) {
 725                                 if (!pp->atarirate)
 726                                         continue;
 727                                 struct move_queue q; q.moves = 0;
 728                                 group_2lib_check(p, b, g, m->color, &q);
 729                                 while (q.moves--)
 730                                         if (q.move[q.moves] == m->coord) {
 731                                                 if (PLDEBUGL(5))
 732                                                         fprintf(stderr, "1.0: 2lib\n");
 733                                                 return assess_local_bonus(p, b, &b->last_move, m, games) / 2;
 734                                         }
 735                         }
 736
 737                         if (!pp->capturerate && !pp->lcapturerate)
 738                                 continue;
 739
 740                         /* _Never_ play here if this move plays out
 741                          * a caught ladder. (Unless it captures another
 742                          * group. :-) */
 743                         if (pp->ladderassess && ladder_catches(p, b, m->coord, g)) {
 744                                 /* Note that the opposite is not guarded against;
 745                                  * we do not advise against capturing a laddered
 746                                  * group (but we don't encourage it either). Such
 747                                  * a move can simplify tactical situations if we
 748                                  * can afford it. */
 749                                 if (m->color == board_at(b, c))
 750                                         ladder = true;
 751                                 continue;
 752                         }
 753
 754                         struct move_queue q; q.moves = 0;
 755                         group_atari_check(p, b, g, m->color, &q);
 756                         while (q.moves--)
 757                                 if (q.move[q.moves] == m->coord) {
 758                                         if (PLDEBUGL(5))
 759                                                 fprintf(stderr, "1.0: atari\n");
 760                                         return assess_local_bonus(p, b, &b->last_move, m, games) * 2;
 761                                 }
 762                 });
 763
 764                 if (ladder) {
 765                         if (PLDEBUGL(5))
 766                                 fprintf(stderr, "0.0: ladder\n");
 767                         return -games;
 768                 }
 769         }
 770
 771         /* Is this move a self-atari? */
 772         if (pp->selfatarirate) {
 773                 if (is_bad_selfatari(b, m->color, m->coord)) {
 774                         if (PLDEBUGL(5))
 775                                 fprintf(stderr, "0.0: self-atari\n");
 776                         return -games;
 777                 }
 778         }
 779
 780         /* Pattern check */
 781         if (pp->patternrate) {
 782                 if (test_pattern3_here(&pp->patterns, b, m)) {
 783                         if (PLDEBUGL(5))
 784                                 fprintf(stderr, "1.0: pattern\n");
 785                         return assess_local_bonus(p, b, &b->last_move, m, games);
 786                 }
 787         }
 788
 789         return 0;
 790 }
 791
 792 void
 793 playout_moggy_assess(struct playout_policy *p, struct prior_map *map, int games)
 794 {
 795         /* TODO: Optimize this! */
 796         foreach_point_and_pass(map->b) {
 797                 if (!map->consider[c])
 798                         continue;
 799                 int assess = 0;
 800                 struct move m = { c, map->to_play };
 801                 assess = playout_moggy_assess_one(p, map->b, &m, games);
 802                 if (!assess)
 803                         continue;
 804                 add_prior_value(map, c, assess, abs(assess));
 805         } foreach_point_end;
 806 }
 807
 808 bool
 809 playout_moggy_permit(struct playout_policy *p, struct board *b, struct move *m)
 810 {
 811         struct moggy_policy *pp = p->data;
 812
 813         /* The idea is simple for now - never allow self-atari moves.
 814          * They suck in general, but this also permits us to actually
 815          * handle seki in the playout stage. */
 816
 817         if (fast_random(100) >= pp->selfatarirate) {
 818                 if (PLDEBUGL(5))
 819                         fprintf(stderr, "skipping sar test\n");
 820                 return true;
 821         }
 822         bool selfatari = is_bad_selfatari(b, m->color, m->coord);
 823         if (PLDEBUGL(5) && selfatari)
 824                 fprintf(stderr, "__ Prohibiting self-atari %s %s\n",
 825                         stone2str(m->color), coord2sstr(m->coord, b));
 826         return !selfatari;
 827 }
 828
 829
 830 struct playout_policy *
 831 playout_moggy_init(char *arg)
 832 {
 833         struct playout_policy *p = calloc(1, sizeof(*p));
 834         struct moggy_policy *pp = calloc(1, sizeof(*pp));
 835         p->data = pp;
 836         p->choose = playout_moggy_choose;
 837         p->assess = playout_moggy_assess;
 838         p->permit = playout_moggy_permit;
 839
 840         int rate = 90;
 841
 842         pp->lcapturerate = pp->atarirate = pp->capturerate = pp->patternrate = pp->selfatarirate = -1;
 843         pp->pattern2 = true;
 844         pp->ladders = pp->borderladders = true;
 845         pp->ladderassess = true;
 846
 847         if (arg) {
 848                 char *optspec, *next = arg;
 849                 while (*next) {
 850                         optspec = next;
 851                         next += strcspn(next, ":");
 852                         if (*next) { *next++ = 0; } else { *next = 0; }
 853
 854                         char *optname = optspec;
 855                         char *optval = strchr(optspec, '=');
 856                         if (optval) *optval++ = 0;
 857
 858                         if (!strcasecmp(optname, "lcapturerate") && optval) {
 859                                 pp->lcapturerate = atoi(optval);
 860                         } else if (!strcasecmp(optname, "atarirate") && optval) {
 861                                 pp->atarirate = atoi(optval);
 862                         } else if (!strcasecmp(optname, "capturerate") && optval) {
 863                                 pp->capturerate = atoi(optval);
 864                         } else if (!strcasecmp(optname, "patternrate") && optval) {
 865                                 pp->patternrate = atoi(optval);
 866                         } else if (!strcasecmp(optname, "selfatarirate") && optval) {
 867                                 pp->selfatarirate = atoi(optval);
 868                         } else if (!strcasecmp(optname, "rate") && optval) {
 869                                 rate = atoi(optval);
 870                         } else if (!strcasecmp(optname, "fillboardtries")) {
 871                                 pp->fillboardtries = atoi(optval);
 872                         } else if (!strcasecmp(optname, "ladders")) {
 873                                 pp->ladders = optval && *optval == '0' ? false : true;
 874                         } else if (!strcasecmp(optname, "borderladders")) {
 875                                 pp->borderladders = optval && *optval == '0' ? false : true;
 876                         } else if (!strcasecmp(optname, "ladderassess")) {
 877                                 pp->ladderassess = optval && *optval == '0' ? false : true;
 878                         } else if (!strcasecmp(optname, "assess_local")) {
 879                                 pp->assess_local = optval && *optval == '0' ? false : true;
 880                         } else if (!strcasecmp(optname, "pattern2")) {
 881                                 pp->pattern2 = optval && *optval == '0' ? false : true;
 882                         } else {
 883                                 fprintf(stderr, "playout-moggy: Invalid policy argument %s or missing value\n", optname);
 884                         }
 885                 }
 886         }
 887         if (pp->lcapturerate == -1) pp->lcapturerate = rate;
 888         if (pp->atarirate == -1) pp->atarirate = rate;
 889         if (pp->capturerate == -1) pp->capturerate = rate;
 890         if (pp->patternrate == -1) pp->patternrate = rate;
 891         if (pp->selfatarirate == -1) pp->selfatarirate = rate;
 892
 893         pattern3s_init(&pp->patterns, moggy_patterns_src, moggy_patterns_src_n);
 894
 895         return p;
 896 }