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