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