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