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