playout/moggy.c

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