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