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