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