playout/moggy.c

   1 /* Heuristical playout (and tree prior) policy modelled primarily after
   2  * the description of the Mogo engine. */
   3
   4 #include <assert.h>
   5 #include <math.h>
   6 #include <stdio.h>
   7 #include <stdlib.h>
   8
   9 #define DEBUG
  10 #include "board.h"
  11 #include "debug.h"
  12 #include "joseki/base.h"
  13 #include "mq.h"
  14 #include "pattern3.h"
  15 #include "playout.h"
  16 #include "playout/moggy.h"
  17 #include "random.h"
  18 #include "tactics/1lib.h"
  19 #include "tactics/2lib.h"
  20 #include "tactics/nlib.h"
  21 #include "tactics/ladder.h"
  22 #include "tactics/nakade.h"
  23 #include "tactics/selfatari.h"
  24 #include "uct/prior.h"
  25
  26 #define PLDEBUGL(n) DEBUGL_(p->debug_level, n)
  27
  28
  29 /* In case "seqchoose" move picker is enabled (i.e. no "fullchoose"
  30  * parameter passed), we stochastically apply fixed set of decision
  31  * rules in given order.
  32  *
  33  * In "fullchoose" mode, we instead build a move queue of variously
  34  * tagged candidates, then consider a probability distribution over
  35  * them and pick a move from that. */
  36
  37 /* Move queue tags. Some may be even undesirable - these moves then
  38  * receive a penalty; penalty tags should be used only when it is
  39  * certain the move would be considered anyway. */
  40 enum mq_tag {
  41         MQ_KO = 0,
  42         MQ_LATARI,
  43         MQ_L2LIB,
  44 #define MQ_LADDER MQ_L2LIB /* XXX: We want to fit in char still! */
  45         MQ_LNLIB,
  46         MQ_PAT3,
  47         MQ_GATARI,
  48         MQ_JOSEKI,
  49         MQ_NAKADE,
  50         MQ_MAX
  51 };
  52
  53
  54 /* Note that the context can be shared by multiple threads! */
  55
  56 struct moggy_policy {
  57         unsigned int lcapturerate, atarirate, nlibrate, ladderrate, capturerate, patternrate, korate, josekirate, nakaderate;
  58         unsigned int selfatarirate, eyefillrate, alwaysccaprate;
  59         unsigned int fillboardtries;
  60         int koage;
  61         /* Whether to look for patterns around second-to-last move. */
  62         bool pattern2;
  63         /* Whether, when self-atari attempt is detected, to play the other
  64          * group's liberty if that is non-self-atari. */
  65         bool selfatari_other;
  66         /* Whether to read out ladders elsewhere than near the board
  67          * in the playouts. Note that such ladder testing is currently
  68          * a fairly expensive operation. */
  69         bool middle_ladder;
  70
  71         /* 1lib settings: */
  72         /* Whether to always pick from moves capturing all groups in
  73          * global_atari_check(). */
  74         bool capcheckall;
  75         /* Prior stone weighting. Weight of each stone between
  76          * cap_stone_min and cap_stone_max is (assess*100)/cap_stone_denom. */
  77         int cap_stone_min, cap_stone_max;
  78         int cap_stone_denom;
  79
  80         /* 2lib settings: */
  81         bool atari_def_no_hopeless;
  82         bool atari_miaisafe;
  83
  84         /* nlib settings: */
  85         int nlib_count;
  86
  87         struct joseki_dict *jdict;
  88         struct pattern3s patterns;
  89
  90         /* Gamma values for queue tags - correspond to probabilities. */
  91         /* XXX: Tune. */
  92         double mq_prob[MQ_MAX], tenuki_prob;
  93 };
  94
  95
  96 static char moggy_patterns_src[][11] = {
  97         /* hane pattern - enclosing hane */
  98         "XOX"
  99         "..."
 100         "???",
 101         /* hane pattern - non-cutting hane */
 102         "YO."
 103         "..."
 104         "?.?",
 105         /* hane pattern - magari */
 106         "XO?"
 107         "X.."
 108         "x.?",
 109         /* hane pattern - thin hane */
 110         "XOO"
 111         "..."
 112         "?.?" "X",
 113         /* generic pattern - katatsuke or diagonal attachment; similar to magari */
 114         ".Q."
 115         "Y.."
 116         "...",
 117         /* cut1 pattern (kiri) - unprotected cut */
 118         "XO?"
 119         "O.o"
 120         "?o?",
 121         /* cut1 pattern (kiri) - peeped cut */
 122         "XO?"
 123         "O.X"
 124         "???",
 125         /* cut2 pattern (de) */
 126         "?X?"
 127         "O.O"
 128         "ooo",
 129         /* cut keima (not in Mogo) */
 130         "OX?"
 131         "o.O"
 132         "???", /* o?? has some pathological tsumego cases */
 133         /* side pattern - chase */
 134         "X.?"
 135         "O.?"
 136         "##?",
 137         /* side pattern - block side cut */
 138         "OX?"
 139         "X.O"
 140         "###",
 141         /* side pattern - block side connection */
 142         "?X?"
 143         "x.O"
 144         "###",
 145         /* side pattern - sagari (SUSPICIOUS) */
 146         "?XQ"
 147         "x.x" /* Mogo has "x.?" */
 148         "###" /* Mogo has "X" */,
 149         /* side pattern - throw-in (SUSPICIOUS) */
 150 #if 0
 151         "?OX"
 152         "o.O"
 153         "?##" "X",
 154 #endif
 155         /* side pattern - cut (SUSPICIOUS) */
 156         "?OY"
 157         "Y.O"
 158         "###" /* Mogo has "X" */,
 159         /* side pattern - eye piercing:
 160          * # O O O .
 161          * # O . O .
 162          * # . . . .
 163          * # # # # # */
 164         /* side pattern - make eye */
 165         "?X."
 166         "Q.X"
 167         "###",
 168 #if 0
 169         "Oxx"
 170         "..."
 171         "###",
 172 #endif
 173 };
 174 #define moggy_patterns_src_n sizeof(moggy_patterns_src) / sizeof(moggy_patterns_src[0])
 175
 176 static inline bool
 177 test_pattern3_here(struct playout_policy *p, struct board *b, struct move *m, bool middle_ladder)
 178 {
 179         struct moggy_policy *pp = p->data;
 180         /* Check if 3x3 pattern is matched by given move... */
 181         if (!pattern3_move_here(&pp->patterns, b, m))
 182                 return false;
 183         /* ...and the move is not obviously stupid. */
 184         if (is_bad_selfatari(b, m->color, m->coord))
 185                 return false;
 186         /* Ladder moves are stupid. */
 187         group_t atari_neighbor = board_get_atari_neighbor(b, m->coord, m->color);
 188         if (atari_neighbor && is_ladder(b, m->coord, atari_neighbor, middle_ladder)
 189             && !can_countercapture(b, board_at(b, group_base(atari_neighbor)),
 190                                    atari_neighbor, m->color, NULL, 0))
 191                 return false;
 192         return true;
 193 }
 194
 195 static void
 196 apply_pattern_here(struct playout_policy *p, struct board *b, coord_t c, enum stone color, struct move_queue *q)
 197 {
 198         struct moggy_policy *pp = p->data;
 199         struct move m2 = { .coord = c, .color = color };
 200         if (board_is_valid_move(b, &m2) && test_pattern3_here(p, b, &m2, pp->middle_ladder))
 201                 mq_add(q, c, 1<<MQ_PAT3);
 202 }
 203
 204 /* Check if we match any pattern around given move (with the other color to play). */
 205 static void
 206 apply_pattern(struct playout_policy *p, struct board *b, struct move *m, struct move *mm, struct move_queue *q)
 207 {
 208         /* Suicides do not make any patterns and confuse us. */
 209         if (board_at(b, m->coord) == S_NONE || board_at(b, m->coord) == S_OFFBOARD)
 210                 return;
 211
 212         foreach_8neighbor(b, m->coord) {
 213                 apply_pattern_here(p, b, c, stone_other(m->color), q);
 214         } foreach_8neighbor_end;
 215
 216         if (mm) { /* Second move for pattern searching */
 217                 foreach_8neighbor(b, mm->coord) {
 218                         if (coord_is_8adjecent(m->coord, c, b))
 219                                 continue;
 220                         apply_pattern_here(p, b, c, stone_other(m->color), q);
 221                 } foreach_8neighbor_end;
 222         }
 223
 224         if (PLDEBUGL(5))
 225                 mq_print(q, b, "Pattern");
 226 }
 227
 228
 229 static void
 230 joseki_check(struct playout_policy *p, struct board *b, enum stone to_play, struct move_queue *q)
 231 {
 232         struct moggy_policy *pp = p->data;
 233         if (!pp->jdict)
 234                 return;
 235
 236         for (int i = 0; i < 4; i++) {
 237                 hash_t h = b->qhash[i] & joseki_hash_mask;
 238                 coord_t *cc = pp->jdict->patterns[h].moves[to_play];
 239                 if (!cc) continue;
 240                 for (; !is_pass(*cc); cc++) {
 241                         if (coord_quadrant(*cc, b) != i)
 242                                 continue;
 243                         mq_add(q, *cc, 1<<MQ_JOSEKI);
 244                 }
 245         }
 246
 247         if (q->moves > 0 && PLDEBUGL(5))
 248                 mq_print(q, b, "Joseki");
 249 }
 250
 251 static void
 252 global_atari_check(struct playout_policy *p, struct board *b, enum stone to_play, struct move_queue *q)
 253 {
 254         if (b->clen == 0)
 255                 return;
 256
 257         struct moggy_policy *pp = p->data;
 258         if (pp->capcheckall) {
 259                 for (int g = 0; g < b->clen; g++)
 260                         group_atari_check(pp->alwaysccaprate, b, group_at(b, group_base(b->c[g])), to_play, q, NULL, pp->middle_ladder, 1<<MQ_GATARI);
 261                 if (PLDEBUGL(5))
 262                         mq_print(q, b, "Global atari");
 263                 return;
 264         }
 265
 266         int g_base = fast_random(b->clen);
 267         for (int g = g_base; g < b->clen; g++) {
 268                 group_atari_check(pp->alwaysccaprate, b, group_at(b, group_base(b->c[g])), to_play, q, NULL, pp->middle_ladder, 1<<MQ_GATARI);
 269                 if (q->moves > 0) {
 270                         /* XXX: Try carrying on. */
 271                         if (PLDEBUGL(5))
 272                                 mq_print(q, b, "Global atari");
 273                         return;
 274                 }
 275         }
 276         for (int g = 0; g < g_base; g++) {
 277                 group_atari_check(pp->alwaysccaprate, b, group_at(b, group_base(b->c[g])), to_play, q, NULL, pp->middle_ladder, 1<<MQ_GATARI);
 278                 if (q->moves > 0) {
 279                         /* XXX: Try carrying on. */
 280                         if (PLDEBUGL(5))
 281                                 mq_print(q, b, "Global atari");
 282                         return;
 283                 }
 284         }
 285         return;
 286 }
 287
 288 static void
 289 local_atari_check(struct playout_policy *p, struct board *b, struct move *m, struct move_queue *q)
 290 {
 291         struct moggy_policy *pp = p->data;
 292
 293         /* Did the opponent play a self-atari? */
 294         if (board_group_info(b, group_at(b, m->coord)).libs == 1) {
 295                 group_atari_check(pp->alwaysccaprate, b, group_at(b, m->coord), stone_other(m->color), q, NULL, pp->middle_ladder, 1<<MQ_LATARI);
 296         }
 297
 298         foreach_neighbor(b, m->coord, {
 299                 group_t g = group_at(b, c);
 300                 if (!g || board_group_info(b, g).libs != 1)
 301                         continue;
 302                 group_atari_check(pp->alwaysccaprate, b, g, stone_other(m->color), q, NULL, pp->middle_ladder, 1<<MQ_LATARI);
 303         });
 304
 305         if (PLDEBUGL(5))
 306                 mq_print(q, b, "Local atari");
 307 }
 308
 309
 310 static void
 311 local_ladder_check(struct playout_policy *p, struct board *b, struct move *m, struct move_queue *q)
 312 {
 313         group_t group = group_at(b, m->coord);
 314
 315         if (board_group_info(b, group).libs != 2)
 316                 return;
 317
 318         for (int i = 0; i < 2; i++) {
 319                 coord_t chase = board_group_info(b, group).lib[i];
 320                 coord_t escape = board_group_info(b, group).lib[1 - i];
 321                 if (wouldbe_ladder(b, group, escape, chase, board_at(b, group)))
 322                         mq_add(q, chase, 1<<MQ_LADDER);
 323         }
 324
 325         if (q->moves > 0 && PLDEBUGL(5))
 326                 mq_print(q, b, "Ladder");
 327 }
 328
 329
 330 static void
 331 local_2lib_check(struct playout_policy *p, struct board *b, struct move *m, struct move_queue *q)
 332 {
 333         struct moggy_policy *pp = p->data;
 334         group_t group = group_at(b, m->coord), group2 = 0;
 335
 336         /* Does the opponent have just two liberties? */
 337         if (board_group_info(b, group).libs == 2) {
 338                 group_2lib_check(b, group, stone_other(m->color), q, 1<<MQ_L2LIB, pp->atari_miaisafe, pp->atari_def_no_hopeless);
 339 #if 0
 340                 /* We always prefer to take off an enemy chain liberty
 341                  * before pulling out ourselves. */
 342                 /* XXX: We aren't guaranteed to return to that group
 343                  * later. */
 344                 if (q->moves)
 345                         return q->move[fast_random(q->moves)];
 346 #endif
 347         }
 348
 349         /* Then he took a third liberty from neighboring chain? */
 350         foreach_neighbor(b, m->coord, {
 351                 group_t g = group_at(b, c);
 352                 if (!g || g == group || g == group2 || board_group_info(b, g).libs != 2)
 353                         continue;
 354                 group_2lib_check(b, g, stone_other(m->color), q, 1<<MQ_L2LIB, pp->atari_miaisafe, pp->atari_def_no_hopeless);
 355                 group2 = g; // prevent trivial repeated checks
 356         });
 357
 358         if (PLDEBUGL(5))
 359                 mq_print(q, b, "Local 2lib");
 360 }
 361
 362 static void
 363 local_nlib_check(struct playout_policy *p, struct board *b, struct move *m, struct move_queue *q)
 364 {
 365         struct moggy_policy *pp = p->data;
 366         enum stone color = stone_other(m->color);
 367
 368         /* Attacking N-liberty groups in general is probably
 369          * not feasible. What we are primarily concerned about is
 370          * counter-attacking groups that have two physical liberties,
 371          * but three effective liberties:
 372          *
 373          * . O . . . . #
 374          * O O X X X X #
 375          * . X O O X . #
 376          * . X O . O X #
 377          * . X O O . X #
 378          * # # # # # # #
 379          *
 380          * The time for this to come is when the opponent took a liberty
 381          * of ours, making a few-liberty group. Therefore, we focus
 382          * purely on defense.
 383          *
 384          * There is a tradeoff - down to how many liberties we need to
 385          * be to start looking? nlib_count=3 will work for the left black
 386          * group (2lib-solver will suggest connecting the false eye), but
 387          * not for top black group (it is too late to start playing 3-3
 388          * capturing race). Also, we cannot prevent stupidly taking an
 389          * outside liberty ourselves; the higher nlib_count, the higher
 390          * the chance we withstand this.
 391          *
 392          * However, higher nlib_count means that we will waste more time
 393          * checking non-urgent or alive groups, and we will play silly
 394          * or wasted moves around alive groups. */
 395
 396         group_t group2 = 0;
 397         foreach_8neighbor(b, m->coord) {
 398                 group_t g = group_at(b, c);
 399                 if (!g || group2 == g || board_at(b, c) != color)
 400                         continue;
 401                 if (board_group_info(b, g).libs < 3 || board_group_info(b, g).libs > pp->nlib_count)
 402                         continue;
 403                 group_nlib_defense_check(b, g, color, q, 1<<MQ_LNLIB);
 404                 group2 = g; // prevent trivial repeated checks
 405         } foreach_8neighbor_end;
 406
 407         if (PLDEBUGL(5))
 408                 mq_print(q, b, "Local nlib");
 409 }
 410
 411 static coord_t
 412 nakade_check(struct playout_policy *p, struct board *b, struct move *m, enum stone to_play)
 413 {
 414         coord_t empty = pass;
 415         foreach_neighbor(b, m->coord, {
 416                 if (board_at(b, c) != S_NONE)
 417                         continue;
 418                 if (is_pass(empty)) {
 419                         empty = c;
 420                         continue;
 421                 }
 422                 if (!coord_is_8adjecent(c, empty, b)) {
 423                         /* Seems like impossible nakade
 424                          * shape! */
 425                         return pass;
 426                 }
 427         });
 428         assert(!is_pass(empty));
 429
 430         coord_t nakade = nakade_point(b, empty, stone_other(to_play));
 431         if (PLDEBUGL(5) && !is_pass(nakade))
 432                 fprintf(stderr, "Nakade: %s\n", coord2sstr(nakade, b));
 433         return nakade;
 434 }
 435
 436 coord_t
 437 fillboard_check(struct playout_policy *p, struct board *b)
 438 {
 439         struct moggy_policy *pp = p->data;
 440         unsigned int fbtries = b->flen / 8;
 441         if (pp->fillboardtries < fbtries)
 442                 fbtries = pp->fillboardtries;
 443
 444         for (unsigned int i = 0; i < fbtries; i++) {
 445                 coord_t coord = b->f[fast_random(b->flen)];
 446                 if (immediate_liberty_count(b, coord) != 4)
 447                         continue;
 448                 foreach_diag_neighbor(b, coord) {
 449                         if (board_at(b, c) != S_NONE)
 450                                 goto next_try;
 451                 } foreach_diag_neighbor_end;
 452                 return coord;
 453 next_try:
 454                 ;
 455         }
 456         return pass;
 457 }
 458
 459 coord_t
 460 playout_moggy_seqchoose(struct playout_policy *p, struct playout_setup *s, struct board *b, enum stone to_play)
 461 {
 462         struct moggy_policy *pp = p->data;
 463
 464         if (PLDEBUGL(5))
 465                 board_print(b, stderr);
 466
 467         /* Ko fight check */
 468         if (!is_pass(b->last_ko.coord) && is_pass(b->ko.coord)
 469             && b->moves - b->last_ko_age < pp->koage
 470             && pp->korate > fast_random(100)) {
 471                 if (board_is_valid_play(b, to_play, b->last_ko.coord)
 472                     && !is_bad_selfatari(b, to_play, b->last_ko.coord))
 473                         return b->last_ko.coord;
 474         }
 475
 476         /* Local checks */
 477         if (!is_pass(b->last_move.coord)) {
 478                 /* Nakade check */
 479                 if (pp->nakaderate > fast_random(100)
 480                     && immediate_liberty_count(b, b->last_move.coord) > 0) {
 481                         coord_t nakade = nakade_check(p, b, &b->last_move, to_play);
 482                         if (!is_pass(nakade))
 483                                 return nakade;
 484                 }
 485
 486                 /* Local group in atari? */
 487                 if (pp->lcapturerate > fast_random(100)) {
 488                         struct move_queue q;  q.moves = 0;
 489                         local_atari_check(p, b, &b->last_move, &q);
 490                         if (q.moves > 0)
 491                                 return mq_pick(&q);
 492                 }
 493
 494                 /* Local group trying to escape ladder? */
 495                 if (pp->ladderrate > fast_random(100)) {
 496                         struct move_queue q; q.moves = 0;
 497                         local_ladder_check(p, b, &b->last_move, &q);
 498                         if (q.moves > 0)
 499                                 return mq_pick(&q);
 500                 }
 501
 502                 /* Local group can be PUT in atari? */
 503                 if (pp->atarirate > fast_random(100)) {
 504                         struct move_queue q; q.moves = 0;
 505                         local_2lib_check(p, b, &b->last_move, &q);
 506                         if (q.moves > 0)
 507                                 return mq_pick(&q);
 508                 }
 509
 510                 /* Local group reduced some of our groups to 3 libs? */
 511                 if (pp->nlibrate > fast_random(100)) {
 512                         struct move_queue q; q.moves = 0;
 513                         local_nlib_check(p, b, &b->last_move, &q);
 514                         if (q.moves > 0)
 515                                 return mq_pick(&q);
 516                 }
 517
 518                 /* Check for patterns we know */
 519                 if (pp->patternrate > fast_random(100)) {
 520                         struct move_queue q; q.moves = 0;
 521                         apply_pattern(p, b, &b->last_move,
 522                                           pp->pattern2 && b->last_move2.coord >= 0 ? &b->last_move2 : NULL,
 523                                           &q);
 524                         if (q.moves > 0)
 525                                 return mq_pick(&q);
 526                 }
 527         }
 528
 529         /* Global checks */
 530
 531         /* Any groups in atari? */
 532         if (pp->capturerate > fast_random(100)) {
 533                 struct move_queue q; q.moves = 0;
 534                 global_atari_check(p, b, to_play, &q);
 535                 if (q.moves > 0)
 536                         return mq_pick(&q);
 537         }
 538
 539         /* Joseki moves? */
 540         if (pp->josekirate > fast_random(100)) {
 541                 struct move_queue q; q.moves = 0;
 542                 joseki_check(p, b, to_play, &q);
 543                 if (q.moves > 0)
 544                         return mq_pick(&q);
 545         }
 546
 547         /* Fill board */
 548         if (pp->fillboardtries > 0) {
 549                 coord_t c = fillboard_check(p, b);
 550                 if (!is_pass(c))
 551                         return c;
 552         }
 553
 554         return pass;
 555 }
 556
 557 /* Pick a move from queue q, giving different likelihoods to moves
 558  * based on their tags. */
 559 coord_t
 560 mq_tagged_choose(struct playout_policy *p, struct board *b, enum stone to_play, struct move_queue *q)
 561 {
 562         struct moggy_policy *pp = p->data;
 563
 564         /* First, merge all entries for a move. */
 565         /* We use a naive O(N^2) since the average length of the queue
 566          * is about 1.4. */
 567         for (unsigned int i = 0; i < q->moves; i++) {
 568                 for (unsigned int j = i + 1; j < q->moves; j++) {
 569                         if (q->move[i] != q->move[j])
 570                                 continue;
 571                         q->tag[i] |= q->tag[j];
 572                         q->moves--;
 573                         q->tag[j] = q->tag[q->moves];
 574                         q->move[j] = q->move[q->moves];
 575                 }
 576         }
 577
 578         /* Now, construct a probdist. */
 579         fixp_t total = 0;
 580         fixp_t pd[q->moves];
 581         for (unsigned int i = 0; i < q->moves; i++) {
 582                 double val = 1.0;
 583                 assert(q->tag[i] != 0);
 584                 for (int j = 0; j < MQ_MAX; j++)
 585                         if (q->tag[i] & (1<<j)) {
 586                                 //fprintf(stderr, "%s(%x) %d %f *= %f\n", coord2sstr(q->move[i], b), q->tag[i], j, val, pp->mq_prob[j]);
 587                                 val *= pp->mq_prob[j];
 588                         }
 589                 pd[i] = double_to_fixp(val);
 590                 total += pd[i];
 591         }
 592         total += double_to_fixp(pp->tenuki_prob);
 593
 594         /* Finally, pick a move! */
 595         fixp_t stab = fast_irandom(total);
 596         for (unsigned int i = 0; i < q->moves; i++) {
 597                 //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));
 598                 if (stab < pd[i])
 599                         return q->move[i];
 600                 stab -= pd[i];
 601         }
 602
 603         /* Tenuki. */
 604         assert(stab < double_to_fixp(pp->tenuki_prob));
 605         return pass;
 606 }
 607
 608 coord_t
 609 playout_moggy_fullchoose(struct playout_policy *p, struct playout_setup *s, struct board *b, enum stone to_play)
 610 {
 611         struct moggy_policy *pp = p->data;
 612         struct move_queue q; q.moves = 0;
 613
 614         if (PLDEBUGL(5))
 615                 board_print(b, stderr);
 616
 617         /* Ko fight check */
 618         if (!is_pass(b->last_ko.coord) && is_pass(b->ko.coord)
 619             && b->moves - b->last_ko_age < pp->koage) {
 620                 if (board_is_valid_play(b, to_play, b->last_ko.coord)
 621                     && !is_bad_selfatari(b, to_play, b->last_ko.coord))
 622                         mq_add(&q, b->last_ko.coord, 1<<MQ_KO);
 623         }
 624
 625         /* Local checks */
 626         if (!is_pass(b->last_move.coord)) {
 627                 /* Nakade check */
 628                 if (immediate_liberty_count(b, b->last_move.coord) > 0) {
 629                         coord_t nakade = nakade_check(p, b, &b->last_move, to_play);
 630                         if (!is_pass(nakade))
 631                                 mq_add(&q, nakade, 1<<MQ_NAKADE);
 632                 }
 633
 634                 /* Local group in atari? */
 635                 local_atari_check(p, b, &b->last_move, &q);
 636
 637                 /* Local group trying to escape ladder? */
 638                 local_ladder_check(p, b, &b->last_move, &q);
 639
 640                 /* Local group can be PUT in atari? */
 641                 local_2lib_check(p, b, &b->last_move, &q);
 642
 643                 /* Local group reduced some of our groups to 3 libs? */
 644                 local_nlib_check(p, b, &b->last_move, &q);
 645
 646                 /* Check for patterns we know */
 647                 apply_pattern(p, b, &b->last_move,
 648                                 pp->pattern2 && b->last_move2.coord >= 0 ? &b->last_move2 : NULL,
 649                                 &q);
 650         }
 651
 652         /* Global checks */
 653
 654         /* Any groups in atari? */
 655         global_atari_check(p, b, to_play, &q);
 656
 657         /* Joseki moves? */
 658         joseki_check(p, b, to_play, &q);
 659
 660 #if 0
 661         /* Average length of the queue is 1.4 move. */
 662         printf("MQL %d ", q.moves);
 663         for (unsigned int i = 0; i < q.moves; i++)
 664                 printf("%s ", coord2sstr(q.move[i], b));
 665         printf("\n");
 666 #endif
 667
 668         if (q.moves > 0)
 669                 return mq_tagged_choose(p, b, to_play, &q);
 670
 671         /* Fill board */
 672         if (pp->fillboardtries > 0) {
 673                 coord_t c = fillboard_check(p, b);
 674                 if (!is_pass(c))
 675                         return c;
 676         }
 677
 678         return pass;
 679 }
 680
 681
 682 void
 683 playout_moggy_assess_group(struct playout_policy *p, struct prior_map *map, group_t g, int games)
 684 {
 685         struct moggy_policy *pp = p->data;
 686         struct board *b = map->b;
 687         struct move_queue q; q.moves = 0;
 688
 689         if (board_group_info(b, g).libs > pp->nlib_count)
 690                 return;
 691
 692         if (PLDEBUGL(5)) {
 693                 fprintf(stderr, "ASSESS of group %s:\n", coord2sstr(g, b));
 694                 board_print(b, stderr);
 695         }
 696
 697         if (board_group_info(b, g).libs > 2) {
 698                 if (!pp->nlibrate)
 699                         return;
 700                 if (board_at(b, g) != map->to_play)
 701                         return; // we do only defense
 702                 group_nlib_defense_check(b, g, map->to_play, &q, 0);
 703                 while (q.moves--) {
 704                         coord_t coord = q.move[q.moves];
 705                         if (PLDEBUGL(5))
 706                                 fprintf(stderr, "1.0: nlib %s\n", coord2sstr(coord, b));
 707                         int assess = games / 2;
 708                         add_prior_value(map, coord, 1, assess);
 709                 }
 710                 return;
 711         }
 712
 713         if (board_group_info(b, g).libs == 2) {
 714                 if (pp->ladderrate) {
 715                         /* Make sure to play the correct liberty in case
 716                          * this is a group that can be caught in a ladder. */
 717                         bool ladderable = false;
 718                         for (int i = 0; i < 2; i++) {
 719                                 coord_t chase = board_group_info(b, g).lib[i];
 720                                 coord_t escape = board_group_info(b, g).lib[1 - i];
 721                                 if (wouldbe_ladder(b, g, escape, chase, board_at(b, g))) {
 722                                         add_prior_value(map, chase, 1, games);
 723                                         ladderable = true;
 724                                 }
 725                         }
 726                         if (ladderable)
 727                                 return; // do not suggest the other lib at all
 728                 }
 729
 730                 if (!pp->atarirate)
 731                         return;
 732                 group_2lib_check(b, g, map->to_play, &q, 0, pp->atari_miaisafe, pp->atari_def_no_hopeless);
 733                 while (q.moves--) {
 734                         coord_t coord = q.move[q.moves];
 735                         if (PLDEBUGL(5))
 736                                 fprintf(stderr, "1.0: 2lib %s\n", coord2sstr(coord, b));
 737                         int assess = games / 2;
 738                         add_prior_value(map, coord, 1, assess);
 739                 }
 740                 return;
 741         }
 742
 743         /* This group, sir, is in atari! */
 744
 745         coord_t ladder = pass;
 746         group_atari_check(pp->alwaysccaprate, b, g, map->to_play, &q, &ladder, true, 0);
 747         while (q.moves--) {
 748                 coord_t coord = q.move[q.moves];
 749
 750                 /* _Never_ play here if this move plays out
 751                  * a caught ladder. */
 752                 if (coord == ladder && !board_playing_ko_threat(b)) {
 753                         /* Note that the opposite is not guarded against;
 754                          * we do not advise against capturing a laddered
 755                          * group (but we don't encourage it either). Such
 756                          * a move can simplify tactical situations if we
 757                          * can afford it. */
 758                         if (map->to_play != board_at(b, g))
 759                                 continue;
 760                         /* FIXME: We give the malus even if this move
 761                          * captures another group. */
 762                         if (PLDEBUGL(5))
 763                                 fprintf(stderr, "0.0: ladder %s\n", coord2sstr(coord, b));
 764                         add_prior_value(map, coord, 0, games);
 765                         continue;
 766                 }
 767
 768                 if (!pp->capturerate && !pp->lcapturerate)
 769                         continue;
 770
 771                 int assess = games * 2;
 772                 if (pp->cap_stone_denom > 0) {
 773                         int stones = group_stone_count(b, g, pp->cap_stone_max) - (pp->cap_stone_min-1);
 774                         assess += (stones > 0 ? stones : 0) * games * 100 / pp->cap_stone_denom;
 775                 }
 776                 if (PLDEBUGL(5))
 777                         fprintf(stderr, "1.0 (%d): atari %s\n", assess, coord2sstr(coord, b));
 778                 add_prior_value(map, coord, 1, assess);
 779         }
 780 }
 781
 782 void
 783 playout_moggy_assess_one(struct playout_policy *p, struct prior_map *map, coord_t coord, int games)
 784 {
 785         struct moggy_policy *pp = p->data;
 786         struct board *b = map->b;
 787
 788         if (PLDEBUGL(5)) {
 789                 fprintf(stderr, "ASSESS of move %s:\n", coord2sstr(coord, b));
 790                 board_print(b, stderr);
 791         }
 792
 793         /* Is this move a self-atari? */
 794         if (pp->selfatarirate) {
 795                 if (!board_playing_ko_threat(b) && is_bad_selfatari(b, map->to_play, coord)) {
 796                         if (PLDEBUGL(5))
 797                                 fprintf(stderr, "0.0: self-atari\n");
 798                         add_prior_value(map, coord, 0, games);
 799                         if (!pp->selfatari_other)
 800                                 return;
 801                         /* If we can play on the other liberty of the
 802                          * endangered group, do! */
 803                         coord = selfatari_cousin(b, map->to_play, coord, NULL);
 804                         if (is_pass(coord))
 805                                 return;
 806                         if (PLDEBUGL(5))
 807                                 fprintf(stderr, "1.0: self-atari redirect %s\n", coord2sstr(coord, b));
 808                         add_prior_value(map, coord, 1.0, games);
 809                         return;
 810                 }
 811         }
 812
 813         /* Pattern check */
 814         if (pp->patternrate) {
 815                 struct move m = { .color = map->to_play, .coord = coord };
 816                 if (test_pattern3_here(p, b, &m, true)) {
 817                         if (PLDEBUGL(5))
 818                                 fprintf(stderr, "1.0: pattern\n");
 819                         add_prior_value(map, coord, 1, games);
 820                 }
 821         }
 822
 823         return;
 824 }
 825
 826 void
 827 playout_moggy_assess(struct playout_policy *p, struct prior_map *map, int games)
 828 {
 829         struct moggy_policy *pp = p->data;
 830
 831         /* First, go through all endangered groups. */
 832         for (group_t g = 1; g < board_size2(map->b); g++)
 833                 if (group_at(map->b, g) == g)
 834                         playout_moggy_assess_group(p, map, g, games);
 835
 836         /* Then, assess individual moves. */
 837         if (!pp->patternrate && !pp->selfatarirate)
 838                 return;
 839         foreach_free_point(map->b) {
 840                 if (map->consider[c])
 841                         playout_moggy_assess_one(p, map, c, games);
 842         } foreach_free_point_end;
 843 }
 844
 845 bool
 846 playout_moggy_permit(struct playout_policy *p, struct board *b, struct move *m)
 847 {
 848         struct moggy_policy *pp = p->data;
 849
 850         /* The idea is simple for now - never allow self-atari moves.
 851          * They suck in general, but this also permits us to actually
 852          * handle seki in the playout stage. */
 853
 854         if (fast_random(100) >= pp->selfatarirate) {
 855                 if (PLDEBUGL(5))
 856                         fprintf(stderr, "skipping sar test\n");
 857                 goto sar_skip;
 858         }
 859         bool selfatari = is_bad_selfatari(b, m->color, m->coord);
 860         if (selfatari) {
 861                 if (PLDEBUGL(5))
 862                         fprintf(stderr, "__ Prohibiting self-atari %s %s\n",
 863                                 stone2str(m->color), coord2sstr(m->coord, b));
 864                 if (pp->selfatari_other) {
 865                         /* Ok, try the other liberty of the atari'd group. */
 866                         coord_t c = selfatari_cousin(b, m->color, m->coord, NULL);
 867                         if (is_pass(c)) return false;
 868                         if (PLDEBUGL(5))
 869                                 fprintf(stderr, "___ Redirecting to other lib %s\n",
 870                                         coord2sstr(c, b));
 871                         m->coord = c;
 872                         return true;
 873                 }
 874                 return false;
 875         }
 876 sar_skip:
 877
 878         /* Check if we don't seem to be filling our eye. This should
 879          * happen only for false eyes, but some of them are in fact
 880          * real eyes with diagonal filled by a dead stone. Prefer
 881          * to counter-capture in that case. */
 882         if (fast_random(100) >= pp->eyefillrate) {
 883                 if (PLDEBUGL(5))
 884                         fprintf(stderr, "skipping eyefill test\n");
 885                 goto eyefill_skip;
 886         }
 887         bool eyefill = board_is_eyelike(b, m->coord, m->color);
 888         if (eyefill) {
 889                 foreach_diag_neighbor(b, m->coord) {
 890                         if (board_at(b, c) != stone_other(m->color))
 891                                 continue;
 892                         switch (board_group_info(b, group_at(b, c)).libs) {
 893                         case 1: /* Capture! */
 894                                 c = board_group_info(b, group_at(b, c)).lib[0];
 895                                 if (PLDEBUGL(5))
 896                                         fprintf(stderr, "___ Redirecting to capture %s\n",
 897                                                 coord2sstr(c, b));
 898                                 m->coord = c;
 899                                 return true;
 900                         case 2: /* Try to switch to some 2-lib neighbor. */
 901                                 for (int i = 0; i < 2; i++) {
 902                                         coord_t l = board_group_info(b, group_at(b, c)).lib[i];
 903                                         if (board_is_one_point_eye(b, l, board_at(b, c)))
 904                                                 continue;
 905                                         if (is_bad_selfatari(b, m->color, l))
 906                                                 continue;
 907                                         m->coord = l;
 908                                         return true;
 909                                 }
 910                                 break;
 911                         }
 912                 } foreach_diag_neighbor_end;
 913         }
 914
 915 eyefill_skip:
 916         return true;
 917 }
 918
 919
 920 struct playout_policy *
 921 playout_moggy_init(char *arg, struct board *b, struct joseki_dict *jdict)
 922 {
 923         struct playout_policy *p = calloc2(1, sizeof(*p));
 924         struct moggy_policy *pp = calloc2(1, sizeof(*pp));
 925         p->data = pp;
 926         p->choose = playout_moggy_seqchoose;
 927         p->assess = playout_moggy_assess;
 928         p->permit = playout_moggy_permit;
 929
 930         pp->jdict = jdict;
 931
 932         /* These settings are tuned for 19x19 play with several threads
 933          * on reasonable time limits (i.e., rather large number of playouts).
 934          * XXX: no 9x9 tuning has been done recently. */
 935         int rate = board_large(b) ? 80 : 90;
 936
 937         pp->lcapturerate = pp->atarirate = pp->nlibrate
 938                 = pp->selfatarirate = pp->josekirate = -1U;
 939         pp->patternrate = 100;
 940         pp->nlibrate = 20;
 941         pp->nakaderate = 20;
 942         pp->pattern2 = true;
 943         pp->lcapturerate = 90;
 944         pp->korate = 20; pp->koage = 4;
 945         pp->alwaysccaprate = 40;
 946         pp->eyefillrate = 60;
 947         pp->selfatari_other = true;
 948
 949         pp->cap_stone_min = 2;
 950         pp->cap_stone_max = 15;
 951         pp->cap_stone_denom = 200;
 952
 953         pp->atari_def_no_hopeless = !board_large(b);
 954         pp->atari_miaisafe = true;
 955         pp->nlib_count = 4;
 956
 957         /* C is stupid. */
 958         double mq_prob_default[MQ_MAX] = {
 959                 [MQ_KO] = 6.0,
 960                 [MQ_NAKADE] = 5.5,
 961                 [MQ_LATARI] = 5.0,
 962                 [MQ_L2LIB] = 4.0,
 963                 [MQ_LNLIB] = 3.5,
 964                 [MQ_PAT3] = 3.0,
 965                 [MQ_GATARI] = 2.0,
 966                 [MQ_JOSEKI] = 1.0,
 967         };
 968         memcpy(pp->mq_prob, mq_prob_default, sizeof(pp->mq_prob));
 969
 970         if (arg) {
 971                 char *optspec, *next = arg;
 972                 while (*next) {
 973                         optspec = next;
 974                         next += strcspn(next, ":");
 975                         if (*next) { *next++ = 0; } else { *next = 0; }
 976
 977                         char *optname = optspec;
 978                         char *optval = strchr(optspec, '=');
 979                         if (optval) *optval++ = 0;
 980
 981                         if (!strcasecmp(optname, "debug") && optval) {
 982                                 p->debug_level = atoi(optval);
 983                         } else if (!strcasecmp(optname, "lcapturerate") && optval) {
 984                                 pp->lcapturerate = atoi(optval);
 985                         } else if (!strcasecmp(optname, "ladderrate") && optval) {
 986                                 pp->ladderrate = atoi(optval);
 987                         } else if (!strcasecmp(optname, "atarirate") && optval) {
 988                                 pp->atarirate = atoi(optval);
 989                         } else if (!strcasecmp(optname, "nlibrate") && optval) {
 990                                 pp->nlibrate = atoi(optval);
 991                         } else if (!strcasecmp(optname, "capturerate") && optval) {
 992                                 pp->capturerate = atoi(optval);
 993                         } else if (!strcasecmp(optname, "patternrate") && optval) {
 994                                 pp->patternrate = atoi(optval);
 995                         } else if (!strcasecmp(optname, "selfatarirate") && optval) {
 996                                 pp->selfatarirate = atoi(optval);
 997                         } else if (!strcasecmp(optname, "eyefillrate") && optval) {
 998                                 pp->eyefillrate = atoi(optval);
 999                         } else if (!strcasecmp(optname, "korate") && optval) {
1000                                 pp->korate = atoi(optval);
1001                         } else if (!strcasecmp(optname, "josekirate") && optval) {
1002                                 pp->josekirate = atoi(optval);
1003                         } else if (!strcasecmp(optname, "nakaderate") && optval) {
1004                                 pp->nakaderate = atoi(optval);
1005                         } else if (!strcasecmp(optname, "alwaysccaprate") && optval) {
1006                                 pp->alwaysccaprate = atoi(optval);
1007                         } else if (!strcasecmp(optname, "rate") && optval) {
1008                                 rate = atoi(optval);
1009                         } else if (!strcasecmp(optname, "fillboardtries")) {
1010                                 pp->fillboardtries = atoi(optval);
1011                         } else if (!strcasecmp(optname, "koage") && optval) {
1012                                 pp->koage = atoi(optval);
1013                         } else if (!strcasecmp(optname, "pattern2")) {
1014                                 pp->pattern2 = optval && *optval == '0' ? false : true;
1015                         } else if (!strcasecmp(optname, "selfatari_other")) {
1016                                 pp->selfatari_other = optval && *optval == '0' ? false : true;
1017                         } else if (!strcasecmp(optname, "capcheckall")) {
1018                                 pp->capcheckall = optval && *optval == '0' ? false : true;
1019                         } else if (!strcasecmp(optname, "cap_stone_min") && optval) {
1020                                 pp->cap_stone_min = atoi(optval);
1021                         } else if (!strcasecmp(optname, "cap_stone_max") && optval) {
1022                                 pp->cap_stone_max = atoi(optval);
1023                         } else if (!strcasecmp(optname, "cap_stone_denom") && optval) {
1024                                 pp->cap_stone_denom = atoi(optval);
1025                         } else if (!strcasecmp(optname, "atari_miaisafe")) {
1026                                 pp->atari_miaisafe = optval && *optval == '0' ? false : true;
1027                         } else if (!strcasecmp(optname, "atari_def_no_hopeless")) {
1028                                 pp->atari_def_no_hopeless = optval && *optval == '0' ? false : true;
1029                         } else if (!strcasecmp(optname, "nlib_count") && optval) {
1030                                 pp->nlib_count = atoi(optval);
1031                         } else if (!strcasecmp(optname, "middle_ladder")) {
1032                                 pp->middle_ladder = optval && *optval == '0' ? false : true;
1033                         } else if (!strcasecmp(optname, "fullchoose")) {
1034                                 p->choose = optval && *optval == '0' ? playout_moggy_seqchoose : playout_moggy_fullchoose;
1035                         } else if (!strcasecmp(optname, "mqprob") && optval) {
1036                                 /* KO%LATARI%L2LIB%LNLIB%PAT3%GATARI%JOSEKI%NAKADE */
1037                                 for (int i = 0; *optval && i < MQ_MAX; i++) {
1038                                         pp->mq_prob[i] = atof(optval);
1039                                         optval += strcspn(optval, "%");
1040                                         if (*optval) optval++;
1041                                 }
1042                         } else if (!strcasecmp(optname, "tenukiprob") && optval) {
1043                                 pp->tenuki_prob = atof(optval);
1044                         } else {
1045                                 fprintf(stderr, "playout-moggy: Invalid policy argument %s or missing value\n", optname);
1046                                 exit(1);
1047                         }
1048                 }
1049         }
1050         if (pp->lcapturerate == -1U) pp->lcapturerate = rate;
1051         if (pp->atarirate == -1U) pp->atarirate = rate;
1052         if (pp->nlibrate == -1U) pp->nlibrate = rate;
1053         if (pp->capturerate == -1U) pp->capturerate = rate;
1054         if (pp->patternrate == -1U) pp->patternrate = rate;
1055         if (pp->selfatarirate == -1U) pp->selfatarirate = rate;
1056         if (pp->eyefillrate == -1U) pp->eyefillrate = rate;
1057         if (pp->korate == -1U) pp->korate = rate;
1058         if (pp->josekirate == -1U) pp->josekirate = rate;
1059         if (pp->ladderrate == -1U) pp->ladderrate = rate;
1060         if (pp->nakaderate == -1U) pp->nakaderate = rate;
1061         if (pp->alwaysccaprate == -1U) pp->alwaysccaprate = rate;
1062
1063         pattern3s_init(&pp->patterns, moggy_patterns_src, moggy_patterns_src_n);
1064
1065         return p;
1066 }