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