playout/moggy.c

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