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