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