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