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