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 "mq.h"
  14 #include "pattern3.h"
  15 #include "playout.h"
  16 #include "playout/moggy.h"
  17 #include "random.h"
  18 #include "tactics.h"
  19 #include "uct/prior.h"
  20
  21 #define PLDEBUGL(n) DEBUGL_(p->debug_level, n)
  22
  23 /* Whether to avoid capturing/atariing doomed groups (this is big
  24  * performance hit and may reduce playouts balance; it does increase
  25  * the strength, but not quite proportionally to the performance). */
  26 //#define NO_DOOMED_GROUPS
  27
  28
  29 /* Note that the context can be shared by multiple threads! */
  30
  31 struct moggy_policy {
  32         bool ladders, ladderassess, borderladders, assess_local;
  33         unsigned int lcapturerate, atarirate, capturerate, patternrate, korate;
  34         unsigned int selfatarirate, alwaysccaprate;
  35         unsigned int fillboardtries;
  36         int koage;
  37         /* Whether to look for patterns around second-to-last move. */
  38         bool pattern2;
  39
  40         struct pattern3s patterns;
  41 };
  42
  43
  44 struct group_state {
  45         enum {
  46                 G_ATARI,
  47                 G_2LIB, /* Unused. */
  48                 G_SAFE /* Unused. */
  49         } status:2;
  50
  51         /* Below, we keep track of each trait for each |color_to_play */
  52         int capturable_ready:2; // is @capturable meaningful?
  53         int capturable:2;
  54
  55         int can_countercapture_ready:2;
  56         int can_countercapture:2;
  57 };
  58
  59 /* Cache of evaluation of various board features. */
  60 struct board_state {
  61         int bsize2;
  62         hash_t hash;
  63         struct group_state *groups; /* [board_size2()], indexed by group_t */
  64         unsigned char *groups_known; /* Bitmap of known groups. */
  65 };
  66
  67 /* Using board cache: this turns out to be actually a 10% slowdown,
  68  * since we reuse data in the cache only very little within single
  69  * move. */
  70 // #define CACHE_STATE
  71 /* Reusing board cache across moves if they are successive on the
  72  * board; only cache entries within cfg distance 2 of the last move
  73  * are cleared. */
  74 // #define PERSISTENT_STATE
  75
  76 #ifdef CACHE_STATE
  77 static __thread struct board_state *ss;
  78
  79 static bool
  80 board_state_reuse(struct board_state *s, struct board *b)
  81 {
  82         /* Decide how much of the board state we can reuse. */
  83         /* We do not cache ladder decisions, so we don't have
  84          * to worry about this. */
  85         coord_t c = b->last_move.coord;
  86
  87         if (unlikely(is_pass(c))) {
  88                 /* Passes don't change anything. */
  89                 return true;
  90         }
  91
  92         if (unlikely(board_at(b, c) == S_NONE)) {
  93                 /* Suicide is hopeless. */
  94                 return false;
  95         }
  96
  97         /* XXX: we can make some moves self-atari. */
  98
  99         if (neighbor_count_at(b, c, S_BLACK) + neighbor_count_at(b, c, S_WHITE) == 0) {
 100                 /* We are not taking off liberties of any other stones. */
 101                 return true;
 102         }
 103
 104         return false;
 105 }
 106
 107 static inline struct board_state *
 108 board_state_init(struct board *b)
 109 {
 110         if (ss) {
 111                 if (ss->bsize2 != board_size2(b)) {
 112                         free(ss->groups);
 113                         free(ss->groups_known);
 114                         free(ss); ss = NULL;
 115                 }
 116 #ifdef PERSISTENT_STATE
 117                 /* Only one stone added to the board, nothing removed. */
 118                 else if (ss->hash == (b->hash ^ hash_at(b, b->last_move.coord, b->last_move.color))) {
 119                         ss->hash = b->hash;
 120                         if (likely(board_state_reuse(ss, b)))
 121                                 return ss;
 122                 }
 123 #endif
 124         }
 125         if (!ss) {
 126                 ss = malloc2(sizeof(*ss));
 127                 ss->bsize2 = board_size2(b);
 128                 ss->groups = malloc2(board_size2(b) * sizeof(*ss->groups));
 129                 ss->groups_known = malloc2(board_size2(b) / 8 + 1);
 130         }
 131         ss->hash = b->hash;
 132         memset(ss->groups_known, 0, board_size2(b) / 8 + 1);
 133         return ss;
 134 }
 135
 136 #define group_is_known(s, g) (s->groups_known[g >> 3] & (1 << (g & 7)))
 137 #define group_set_known(s, g) (s->groups_known[g >> 3] |= (1 << (g & 7)))
 138 #define group_trait_ready(s, g, color, gstat, trait) do { \
 139         if (!group_is_known(s, g)) { \
 140                 memset(&s->groups[g], 0, sizeof(s->groups[g])); \
 141                 group_set_known(s, g); \
 142         } \
 143         s->groups[g].status = gstat; \
 144         s->groups[g].trait ## _ready |= color; \
 145 } while (0)
 146 #define group_trait_is_ready(s, g, color, trait) (s->groups[g].trait ## _ready & color)
 147 #define group_trait_set(s, g, color, trait, val) s->groups[g].trait = (s->groups[g].trait & ~color) | (!!val * color)
 148 #define group_trait_get(s, g, color, trait) (s->groups[g].trait & color)
 149
 150 #else
 151
 152 #define board_state_init(b) NULL
 153 #define group_is_known(s, g) false
 154 #define group_set_known(s, g)
 155 #define group_trait_ready(s, g, color, gstat, trait)
 156 #define group_trait_is_ready(s, g, color, trait) false
 157 #define group_trait_set(s, g, color, trait, val)
 158 #define group_trait_get(s, g, color, trait) false
 159 #endif
 160
 161
 162 static char moggy_patterns_src[][11] = {
 163         /* hane pattern - enclosing hane */
 164         "XOX"
 165         "..."
 166         "???",
 167         /* hane pattern - non-cutting hane */
 168         "XO."
 169         "..."
 170         "?.?",
 171         /* hane pattern - magari */
 172         "XO?"
 173         "X.."
 174         "x.?",
 175         /* hane pattern - thin hane */
 176         "XOO"
 177         "..."
 178         "?.?" "X",
 179         /* generic pattern - katatsuke or diagonal attachment; similar to magari */
 180         ".O."
 181         "X.."
 182         "...",
 183         /* cut1 pattern (kiri) - unprotected cut */
 184         "XO?"
 185         "O.o"
 186         "?o?",
 187         /* cut1 pattern (kiri) - peeped cut */
 188         "XO?"
 189         "O.X"
 190         "???",
 191         /* cut2 pattern (de) */
 192         "?X?"
 193         "O.O"
 194         "ooo",
 195         /* cut keima (not in Mogo) */
 196         "OX?"
 197         "o.O"
 198         "???", /* o?? has some pathological tsumego cases */
 199         /* side pattern - chase */
 200         "X.?"
 201         "O.?"
 202         "##?",
 203         /* side pattern - weirdness (SUSPICIOUS) */
 204         "?X?"
 205         "X.O"
 206         "###",
 207         /* side pattern - sagari (SUSPICIOUS) */
 208         "?XO"
 209         "x.x" /* Mogo has "x.?" */
 210         "###" /* Mogo has "X" */,
 211         /* side pattern - throw-in (SUSPICIOUS) */
 212 #if 0
 213         "?OX"
 214         "o.O"
 215         "?##" "X",
 216 #endif
 217         /* side pattern - cut (SUSPICIOUS) */
 218         "?OX"
 219         "X.O"
 220         "###" /* Mogo has "X" */,
 221 };
 222 #define moggy_patterns_src_n sizeof(moggy_patterns_src) / sizeof(moggy_patterns_src[0])
 223
 224 static inline bool
 225 test_pattern3_here(struct playout_policy *p, struct board *b, struct move *m)
 226 {
 227         struct moggy_policy *pp = p->data;
 228         /* Check if 3x3 pattern is matched by given move... */
 229         if (!pattern3_move_here(&pp->patterns, b, m))
 230                 return false;
 231         /* ...and the move is not obviously stupid. */
 232         if (is_bad_selfatari(b, m->color, m->coord))
 233                 return false;
 234         /* Ladder moves are stupid. */
 235         group_t atari_neighbor = board_get_atari_neighbor(b, m->coord, m->color);
 236         if (atari_neighbor && is_ladder(b, m->coord, atari_neighbor, pp->borderladders, pp->ladders))
 237                 return false;
 238         return true;
 239 }
 240
 241 static void
 242 apply_pattern_here(struct playout_policy *p, struct board *b, coord_t c, enum stone color, struct move_queue *q)
 243 {
 244         struct move m2 = { .coord = c, .color = color };
 245         if (board_is_valid_move(b, &m2) && test_pattern3_here(p, b, &m2))
 246                 mq_add(q, c);
 247 }
 248
 249 /* Check if we match any pattern around given move (with the other color to play). */
 250 static coord_t
 251 apply_pattern(struct playout_policy *p, struct board *b, struct move *m, struct move *mm)
 252 {
 253         struct move_queue q;
 254         q.moves = 0;
 255
 256         /* Suicides do not make any patterns and confuse us. */
 257         if (board_at(b, m->coord) == S_NONE || board_at(b, m->coord) == S_OFFBOARD)
 258                 return pass;
 259
 260         foreach_8neighbor(b, m->coord) {
 261                 apply_pattern_here(p, b, c, stone_other(m->color), &q);
 262         } foreach_8neighbor_end;
 263
 264         if (mm) { /* Second move for pattern searching */
 265                 foreach_8neighbor(b, mm->coord) {
 266                         if (coord_is_8adjecent(m->coord, c, b))
 267                                 continue;
 268                         apply_pattern_here(p, b, c, stone_other(m->color), &q);
 269                 } foreach_8neighbor_end;
 270         }
 271
 272         if (PLDEBUGL(5))
 273                 mq_print(&q, b, "Pattern");
 274
 275         return mq_pick(&q);
 276 }
 277
 278
 279 static bool
 280 can_play_on_lib(struct playout_policy *p, struct board_state *s,
 281                 struct board *b, group_t g, enum stone to_play)
 282 {
 283         if (group_is_known(s, g) && group_trait_is_ready(s, g, to_play, capturable)) {
 284                 /* We have already seen this group. */
 285                 assert(s->groups[g].status == G_ATARI);
 286                 if (group_trait_get(s, g, to_play, capturable))
 287                         return true;
 288                 else
 289                         return false;
 290         }
 291
 292         /* Cache miss. Set up cache entry, default at capturable = false. */
 293         group_trait_ready(s, g, to_play, G_ATARI, capturable);
 294
 295         coord_t capture = board_group_info(b, g).lib[0];
 296         if (PLDEBUGL(6))
 297                 fprintf(stderr, "can capture group %d (%s)?\n",
 298                         g, coord2sstr(capture, b));
 299         /* Does playing on the liberty usefully capture the group? */
 300         if (board_is_valid_play(b, to_play, capture)
 301             && !is_bad_selfatari(b, to_play, capture)) {
 302                 group_trait_set(s, g, to_play, capturable, true);
 303                 return true;
 304         }
 305
 306         return false;
 307 }
 308
 309 /* For given position @c, decide if this is a group that is in danger from
 310  * @capturer and @to_play can do anything about it (play at the last
 311  * liberty to either capture or escape). */
 312 /* Note that @to_play is important; e.g. consider snapback, it's good
 313  * to play at the last liberty by attacker, but not defender. */
 314 static __attribute__((always_inline)) bool
 315 capturable_group(struct playout_policy *p, struct board_state *s,
 316                  struct board *b, enum stone capturer, coord_t c,
 317                  enum stone to_play)
 318 {
 319         group_t g = group_at(b, c);
 320         if (likely(board_at(b, c) != stone_other(capturer)
 321                    || board_group_info(b, g).libs > 1))
 322                 return false;
 323
 324         return can_play_on_lib(p, s, b, g, to_play);
 325 }
 326
 327 /* For given atari group @group owned by @owner, decide if @to_play
 328  * can save it / keep it in danger by dealing with one of the
 329  * neighboring groups. */
 330 static bool
 331 can_countercapture(struct playout_policy *p, struct board_state *s,
 332                    struct board *b, enum stone owner, group_t g,
 333                    enum stone to_play, struct move_queue *q)
 334 {
 335         if (b->clen < 2)
 336                 return false;
 337         if (group_is_known(s, g) && group_trait_is_ready(s, g, to_play, can_countercapture)) {
 338                 /* We have already seen this group. */
 339                 assert(s->groups[g].status == G_ATARI);
 340                 if (group_trait_get(s, g, to_play, can_countercapture)) {
 341                         if (q) { /* Scan for countercapture liberties. */
 342                                 goto scan;
 343                         }
 344                         return true;
 345                 } else {
 346                         return false;
 347                 }
 348         }
 349
 350         /* Cache miss. Set up cache entry, default at can_countercapture = true. */
 351         group_trait_ready(s, g, to_play, G_ATARI, can_countercapture);
 352         group_trait_set(s, g, to_play, can_countercapture, true);
 353
 354 scan:;
 355         unsigned int qmoves_prev = q ? q->moves : 0;
 356
 357         foreach_in_group(b, g) {
 358                 foreach_neighbor(b, c, {
 359                         if (!capturable_group(p, s, b, owner, c, to_play))
 360                                 continue;
 361
 362                         if (!q) {
 363                                 return true;
 364                         }
 365                         mq_add(q, board_group_info(b, group_at(b, c)).lib[0]);
 366                         mq_nodup(q);
 367                 });
 368         } foreach_in_group_end;
 369
 370         bool can = q ? q->moves > qmoves_prev : false;
 371         group_trait_set(s, g, to_play, can_countercapture, can);
 372         return can;
 373 }
 374
 375 #ifdef NO_DOOMED_GROUPS
 376 static bool
 377 can_be_rescued(struct playout_policy *p, struct board_state *s,
 378                struct board *b, group_t group, enum stone color)
 379 {
 380         /* Does playing on the liberty rescue the group? */
 381         if (can_play_on_lib(p, s, b, group, color))
 382                 return true;
 383
 384         /* Then, maybe we can capture one of our neighbors? */
 385         return can_countercapture(p, s, b, color, group, color, NULL);
 386 }
 387 #endif
 388
 389 /* ladder != NULL implies to always enqueue all relevant moves. */
 390 static void
 391 group_atari_check(struct playout_policy *p, struct board *b, group_t group, enum stone to_play,
 392                   struct move_queue *q, coord_t *ladder, struct board_state *s)
 393 {
 394         struct moggy_policy *pp = p->data;
 395         int qmoves_prev = q->moves;
 396
 397         /* We don't use @to_play almost anywhere since any moves here are good
 398          * for both defender and attacker. */
 399
 400         enum stone color = board_at(b, group_base(group));
 401         coord_t lib = board_group_info(b, group).lib[0];
 402
 403         assert(color != S_OFFBOARD && color != S_NONE);
 404         if (PLDEBUGL(5))
 405                 fprintf(stderr, "[%s] atariiiiiiiii %s of color %d\n",
 406                         coord2sstr(group, b), coord2sstr(lib, b), color);
 407         assert(board_at(b, lib) == S_NONE);
 408
 409         /* Do not bother with kos. */
 410         if (group_is_onestone(b, group)
 411             && neighbor_count_at(b, lib, color) + neighbor_count_at(b, lib, S_OFFBOARD) == 4)
 412                 return;
 413
 414         /* Can we capture some neighbor? */
 415         bool ccap = can_countercapture(p, s, b, color, group, to_play, q);
 416         if (ccap && !ladder && pp->alwaysccaprate > fast_random(100))
 417                 return;
 418
 419         /* Do not suicide... */
 420         if (!can_play_on_lib(p, s, b, group, to_play))
 421                 return;
 422 #ifdef NO_DOOMED_GROUPS
 423         /* Do not remove group that cannot be saved by the opponent. */
 424         if (to_play != color && !can_be_rescued(p, s, b, group, color))
 425                 return;
 426 #endif
 427         if (PLDEBUGL(6))
 428                 fprintf(stderr, "...escape route valid\n");
 429
 430         /* ...or play out ladders. */
 431         if (is_ladder(b, lib, group, pp->borderladders, pp->ladders)) {
 432                 /* Sometimes we want to keep the ladder move in the
 433                  * queue in order to discourage it. */
 434                 if (!ladder)
 435                         return;
 436                 else
 437                         *ladder = lib;
 438         }
 439         if (PLDEBUGL(6))
 440                 fprintf(stderr, "...no ladder\n");
 441
 442         if (to_play != color) {
 443                 /* We are the attacker! In that case, throw away the moves
 444                  * that defend our groups, since we can capture the culprit. */
 445                 q->moves = qmoves_prev;
 446         }
 447
 448         mq_add(q, lib);
 449         mq_nodup(q);
 450 }
 451
 452 static coord_t
 453 global_atari_check(struct playout_policy *p, struct board *b, enum stone to_play, struct board_state *s)
 454 {
 455         struct move_queue q;
 456         q.moves = 0;
 457
 458         if (b->clen == 0)
 459                 return pass;
 460
 461         int g_base = fast_random(b->clen);
 462         for (int g = g_base; g < b->clen; g++) {
 463                 group_atari_check(p, b, group_at(b, group_base(b->c[g])), to_play, &q, NULL, s);
 464                 if (q.moves > 0) {
 465                         if (PLDEBUGL(5))
 466                                 mq_print(&q, b, "Global atari");
 467                         return mq_pick(&q);
 468                 }
 469         }
 470         for (int g = 0; g < g_base; g++) {
 471                 group_atari_check(p, b, group_at(b, group_base(b->c[g])), to_play, &q, NULL, s);
 472                 if (q.moves > 0) {
 473                         if (PLDEBUGL(5))
 474                                 mq_print(&q, b, "Global atari");
 475                         return mq_pick(&q);
 476                 }
 477         }
 478         return pass;
 479 }
 480
 481 static coord_t
 482 local_atari_check(struct playout_policy *p, struct board *b, struct move *m, struct board_state *s)
 483 {
 484         struct move_queue q;
 485         q.moves = 0;
 486
 487         /* Did the opponent play a self-atari? */
 488         if (board_group_info(b, group_at(b, m->coord)).libs == 1) {
 489                 group_atari_check(p, b, group_at(b, m->coord), stone_other(m->color), &q, NULL, s);
 490         }
 491
 492         foreach_neighbor(b, m->coord, {
 493                 group_t g = group_at(b, c);
 494                 if (!g || board_group_info(b, g).libs != 1)
 495                         continue;
 496                 group_atari_check(p, b, g, stone_other(m->color), &q, NULL, s);
 497         });
 498
 499         if (PLDEBUGL(5))
 500                 mq_print(&q, b, "Local atari");
 501
 502         return mq_pick(&q);
 503 }
 504
 505 static bool
 506 miai_2lib(struct board *b, group_t group, enum stone color)
 507 {
 508         bool can_connect = false, can_pull_out = false;
 509         /* We have miai if we can either connect on both libs,
 510          * or connect on one lib and escape on another. (Just
 511          * having two escape routes can be risky.) We must make
 512          * sure that we don't consider following as miai:
 513          * X X X O
 514          * X . . O
 515          * O O X O - left dot would be pull-out, right dot connect */
 516         foreach_neighbor(b, board_group_info(b, group).lib[0], {
 517                 enum stone cc = board_at(b, c);
 518                 if (cc == S_NONE && cc != board_at(b, board_group_info(b, group).lib[1])) {
 519                         can_pull_out = true;
 520                 } else if (cc != color) {
 521                         continue;
 522                 }
 523
 524                 group_t cg = group_at(b, c);
 525                 if (cg && cg != group && board_group_info(b, cg).libs > 1)
 526                         can_connect = true;
 527         });
 528         foreach_neighbor(b, board_group_info(b, group).lib[1], {
 529                 enum stone cc = board_at(b, c);
 530                 if (c == board_group_info(b, group).lib[0])
 531                         continue;
 532                 if (cc == S_NONE && can_connect) {
 533                         return true;
 534                 } else if (cc != color) {
 535                         continue;
 536                 }
 537
 538                 group_t cg = group_at(b, c);
 539                 if (cg && cg != group && board_group_info(b, cg).libs > 1)
 540                         return (can_connect || can_pull_out);
 541         });
 542         return false;
 543 }
 544
 545 static void
 546 check_group_atari(struct board *b, group_t group, enum stone owner,
 547                   enum stone to_play, struct move_queue *q)
 548 {
 549         for (int i = 0; i < 2; i++) {
 550                 coord_t lib = board_group_info(b, group).lib[i];
 551                 assert(board_at(b, lib) == S_NONE);
 552                 if (!board_is_valid_play(b, to_play, lib))
 553                         continue;
 554
 555                 /* Don't play at the spot if it is extremely short
 556                  * of liberties... */
 557                 /* XXX: This looks harmful, could significantly
 558                  * prefer atari to throwin:
 559                  *
 560                  * XXXOOOOOXX
 561                  * .OO.....OX
 562                  * XXXOOOOOOX */
 563 #if 0
 564                 if (neighbor_count_at(b, lib, stone_other(owner)) + immediate_liberty_count(b, lib) < 2)
 565                         continue;
 566 #endif
 567
 568 #ifdef NO_DOOMED_GROUPS
 569                 /* If the owner can't play at the spot, we don't want
 570                  * to bother either. */
 571                 if (is_bad_selfatari(b, owner, lib))
 572                         continue;
 573 #endif
 574
 575                 /* Of course we don't want to play bad selfatari
 576                  * ourselves, if we are the attacker... */
 577                 if (
 578 #ifdef NO_DOOMED_GROUPS
 579                     to_play != owner &&
 580 #endif
 581                     is_bad_selfatari(b, to_play, lib))
 582                         continue;
 583
 584                 /* Tasty! Crispy! Good! */
 585                 mq_add(q, lib);
 586                 mq_nodup(q);
 587         }
 588 }
 589
 590 static void
 591 group_2lib_check(struct playout_policy *p, struct board *b, group_t group, enum stone to_play,
 592                  struct move_queue *q, struct board_state *s)
 593 {
 594         enum stone color = board_at(b, group_base(group));
 595         assert(color != S_OFFBOARD && color != S_NONE);
 596
 597         if (PLDEBUGL(5))
 598                 fprintf(stderr, "[%s] 2lib check of color %d\n",
 599                         coord2sstr(group, b), color);
 600
 601         /* Do not try to atari groups that cannot be harmed. */
 602         if (miai_2lib(b, group, color))
 603                 return;
 604
 605         check_group_atari(b, group, color, to_play, q);
 606
 607         /* Can we counter-atari another group, if we are the defender? */
 608         if (to_play != color)
 609                 return;
 610         foreach_in_group(b, group) {
 611                 foreach_neighbor(b, c, {
 612                         if (board_at(b, c) != stone_other(color))
 613                                 continue;
 614                         group_t g2 = group_at(b, c);
 615                         if (board_group_info(b, g2).libs != 2)
 616                                 continue;
 617                         check_group_atari(b, g2, color, to_play, q);
 618                 });
 619         } foreach_in_group_end;
 620 }
 621
 622 static coord_t
 623 local_2lib_check(struct playout_policy *p, struct board *b, struct move *m, struct board_state *s)
 624 {
 625         struct move_queue q;
 626         q.moves = 0;
 627
 628         /* Does the opponent have just two liberties? */
 629         if (board_group_info(b, group_at(b, m->coord)).libs == 2) {
 630                 group_2lib_check(p, b, group_at(b, m->coord), stone_other(m->color), &q, s);
 631 #if 0
 632                 /* We always prefer to take off an enemy chain liberty
 633                  * before pulling out ourselves. */
 634                 /* XXX: We aren't guaranteed to return to that group
 635                  * later. */
 636                 if (q.moves)
 637                         return q.move[fast_random(q.moves)];
 638 #endif
 639         }
 640
 641         /* Then he took a third liberty from neighboring chain? */
 642         foreach_neighbor(b, m->coord, {
 643                 group_t g = group_at(b, c);
 644                 if (!g || board_group_info(b, g).libs != 2)
 645                         continue;
 646                 group_2lib_check(p, b, g, stone_other(m->color), &q, s);
 647         });
 648
 649         if (PLDEBUGL(5))
 650                 mq_print(&q, b, "Local 2lib");
 651
 652         return mq_pick(&q);
 653 }
 654
 655 coord_t
 656 playout_moggy_choose(struct playout_policy *p, struct board *b, enum stone to_play)
 657 {
 658         struct moggy_policy *pp = p->data;
 659         coord_t c;
 660
 661         struct board_state *s = board_state_init(b);
 662
 663         if (PLDEBUGL(5))
 664                 board_print(b, stderr);
 665
 666         /* Ko fight check */
 667         if (!is_pass(b->last_ko.coord) && is_pass(b->ko.coord)
 668             && b->moves - b->last_ko_age < pp->koage
 669             && pp->korate > fast_random(100)) {
 670                 if (board_is_valid_play(b, to_play, b->last_ko.coord)
 671                     && !is_bad_selfatari(b, to_play, b->last_ko.coord))
 672                         return b->last_ko.coord;
 673         }
 674
 675         /* Local checks */
 676         if (!is_pass(b->last_move.coord)) {
 677                 /* Local group in atari? */
 678                 if (pp->lcapturerate > fast_random(100)) {
 679                         c = local_atari_check(p, b, &b->last_move, s);
 680                         if (!is_pass(c))
 681                                 return c;
 682                 }
 683
 684                 /* Local group can be PUT in atari? */
 685                 if (pp->atarirate > fast_random(100)) {
 686                         c = local_2lib_check(p, b, &b->last_move, s);
 687                         if (!is_pass(c))
 688                                 return c;
 689                 }
 690
 691                 /* Check for patterns we know */
 692                 if (pp->patternrate > fast_random(100)) {
 693                         c = apply_pattern(p, b, &b->last_move,
 694                                           pp->pattern2 && b->last_move2.coord >= 0 ? &b->last_move2 : NULL);
 695                         if (!is_pass(c))
 696                                 return c;
 697                 }
 698         }
 699
 700         /* Global checks */
 701
 702         /* Any groups in atari? */
 703         if (pp->capturerate > fast_random(100)) {
 704                 c = global_atari_check(p, b, to_play, s);
 705                 if (!is_pass(c))
 706                         return c;
 707         }
 708
 709         /* Fill board */
 710         unsigned int fbtries = b->flen / 8;
 711         for (unsigned int i = 0; i < (fbtries < pp->fillboardtries ? fbtries : pp->fillboardtries); i++) {
 712                 coord_t coord = b->f[fast_random(b->flen)];
 713                 if (immediate_liberty_count(b, coord) != 4)
 714                         continue;
 715                 foreach_diag_neighbor(b, coord) {
 716                         if (board_at(b, c) != S_NONE)
 717                                 goto next_try;
 718                 } foreach_diag_neighbor_end;
 719                 return coord;
 720 next_try:;
 721         }
 722
 723         return pass;
 724 }
 725
 726
 727 static int
 728 assess_local_bonus(struct playout_policy *p, struct board *board, coord_t a, coord_t b, int games)
 729 {
 730         struct moggy_policy *pp = p->data;
 731         if (!pp->assess_local)
 732                 return games;
 733
 734         int dx = abs(coord_x(a, board) - coord_x(b, board));
 735         int dy = abs(coord_y(a, board) - coord_y(b, board));
 736         /* adjecent move, directly or diagonally? */
 737         if (dx + dy <= 1 + (dx && dy))
 738                 return games;
 739         else
 740                 return games / 2;
 741 }
 742
 743 void
 744 playout_moggy_assess_group(struct playout_policy *p, struct prior_map *map, group_t g, int games,
 745                            struct board_state *s)
 746 {
 747         struct moggy_policy *pp = p->data;
 748         struct board *b = map->b;
 749         struct move_queue q; q.moves = 0;
 750
 751         if (board_group_info(b, g).libs > 2)
 752                 return;
 753
 754         if (PLDEBUGL(5)) {
 755                 fprintf(stderr, "ASSESS of group %s:\n", coord2sstr(g, b));
 756                 board_print(b, stderr);
 757         }
 758
 759         if (board_group_info(b, g).libs == 2) {
 760                 if (!pp->atarirate)
 761                         return;
 762                 group_2lib_check(p, b, g, map->to_play, &q, s);
 763                 while (q.moves--) {
 764                         coord_t coord = q.move[q.moves];
 765                         if (PLDEBUGL(5))
 766                                 fprintf(stderr, "1.0: 2lib %s\n", coord2sstr(coord, b));
 767                         int assess = assess_local_bonus(p, b, b->last_move.coord, coord, games) / 2;
 768                         add_prior_value(map, coord, 1, assess);
 769                 }
 770                 return;
 771         }
 772
 773         /* This group, sir, is in atari! */
 774
 775         if (!pp->capturerate && !pp->lcapturerate && !pp->ladderassess)
 776                 return;
 777
 778         coord_t ladder = pass;
 779         group_atari_check(p, b, g, map->to_play, &q, &ladder, s);
 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 (!pp->ladderassess || 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                 if (PLDEBUGL(5))
 805                         fprintf(stderr, "1.0: atari %s\n", coord2sstr(coord, b));
 806                 int assess = assess_local_bonus(p, b, b->last_move.coord, coord, games) * 2;
 807                 add_prior_value(map, coord, 1, assess);
 808         }
 809 }
 810
 811 void
 812 playout_moggy_assess_one(struct playout_policy *p, struct prior_map *map, coord_t coord, int games)
 813 {
 814         struct moggy_policy *pp = p->data;
 815         struct board *b = map->b;
 816
 817         if (PLDEBUGL(5)) {
 818                 fprintf(stderr, "ASSESS of move %s:\n", coord2sstr(coord, b));
 819                 board_print(b, stderr);
 820         }
 821
 822         /* Is this move a self-atari? */
 823         if (pp->selfatarirate) {
 824                 if (!board_playing_ko_threat(b) && is_bad_selfatari(b, map->to_play, coord)) {
 825                         if (PLDEBUGL(5))
 826                                 fprintf(stderr, "0.0: self-atari\n");
 827                         add_prior_value(map, coord, 0, games);
 828                         return;
 829                 }
 830         }
 831
 832         /* Pattern check */
 833         if (pp->patternrate) {
 834                 struct move m = { .color = map->to_play, .coord = coord };
 835                 if (test_pattern3_here(p, b, &m)) {
 836                         if (PLDEBUGL(5))
 837                                 fprintf(stderr, "1.0: pattern\n");
 838                         int assess = assess_local_bonus(p, b, b->last_move.coord, coord, games);
 839                         add_prior_value(map, coord, 1, assess);
 840                 }
 841         }
 842
 843         return;
 844 }
 845
 846 void
 847 playout_moggy_assess(struct playout_policy *p, struct prior_map *map, int games)
 848 {
 849         struct moggy_policy *pp = p->data;
 850
 851         struct board_state *s = board_state_init(map->b);
 852
 853         /* First, go through all endangered groups. */
 854         if (pp->lcapturerate || pp->capturerate || pp->atarirate || pp->ladderassess)
 855                 for (group_t g = 1; g < board_size2(map->b); g++)
 856                         if (group_at(map->b, g) == g)
 857                                 playout_moggy_assess_group(p, map, g, games, s);
 858
 859         /* Then, assess individual moves. */
 860         if (!pp->patternrate && !pp->selfatarirate)
 861                 return;
 862         foreach_point(map->b) {
 863                 if (map->consider[c])
 864                         playout_moggy_assess_one(p, map, c, games);
 865         } foreach_point_end;
 866 }
 867
 868 bool
 869 playout_moggy_permit(struct playout_policy *p, struct board *b, struct move *m)
 870 {
 871         struct moggy_policy *pp = p->data;
 872
 873         /* The idea is simple for now - never allow self-atari moves.
 874          * They suck in general, but this also permits us to actually
 875          * handle seki in the playout stage. */
 876
 877         if (fast_random(100) >= pp->selfatarirate) {
 878                 if (PLDEBUGL(5))
 879                         fprintf(stderr, "skipping sar test\n");
 880                 return true;
 881         }
 882         bool selfatari = is_bad_selfatari(b, m->color, m->coord);
 883         if (PLDEBUGL(5) && selfatari)
 884                 fprintf(stderr, "__ Prohibiting self-atari %s %s\n",
 885                         stone2str(m->color), coord2sstr(m->coord, b));
 886         return !selfatari;
 887 }
 888
 889
 890 struct playout_policy *
 891 playout_moggy_init(char *arg, struct board *b)
 892 {
 893         struct playout_policy *p = calloc2(1, sizeof(*p));
 894         struct moggy_policy *pp = calloc2(1, sizeof(*pp));
 895         p->data = pp;
 896         p->choose = playout_moggy_choose;
 897         p->assess = playout_moggy_assess;
 898         p->permit = playout_moggy_permit;
 899
 900         int rate = 90;
 901
 902         pp->lcapturerate = pp->atarirate = pp->capturerate = pp->patternrate = pp->selfatarirate
 903                         = -1U;
 904         pp->korate = 0; pp->koage = 4;
 905         pp->alwaysccaprate = 0;
 906         pp->ladders = pp->borderladders = true;
 907         pp->ladderassess = true;
 908
 909         if (arg) {
 910                 char *optspec, *next = arg;
 911                 while (*next) {
 912                         optspec = next;
 913                         next += strcspn(next, ":");
 914                         if (*next) { *next++ = 0; } else { *next = 0; }
 915
 916                         char *optname = optspec;
 917                         char *optval = strchr(optspec, '=');
 918                         if (optval) *optval++ = 0;
 919
 920                         if (!strcasecmp(optname, "lcapturerate") && optval) {
 921                                 pp->lcapturerate = atoi(optval);
 922                         } else if (!strcasecmp(optname, "atarirate") && optval) {
 923                                 pp->atarirate = atoi(optval);
 924                         } else if (!strcasecmp(optname, "capturerate") && optval) {
 925                                 pp->capturerate = atoi(optval);
 926                         } else if (!strcasecmp(optname, "patternrate") && optval) {
 927                                 pp->patternrate = atoi(optval);
 928                         } else if (!strcasecmp(optname, "selfatarirate") && optval) {
 929                                 pp->selfatarirate = atoi(optval);
 930                         } else if (!strcasecmp(optname, "korate") && optval) {
 931                                 pp->korate = atoi(optval);
 932                         } else if (!strcasecmp(optname, "alwaysccaprate") && optval) {
 933                                 pp->alwaysccaprate = atoi(optval);
 934                         } else if (!strcasecmp(optname, "rate") && optval) {
 935                                 rate = atoi(optval);
 936                         } else if (!strcasecmp(optname, "fillboardtries")) {
 937                                 pp->fillboardtries = atoi(optval);
 938                         } else if (!strcasecmp(optname, "koage") && optval) {
 939                                 pp->koage = atoi(optval);
 940                         } else if (!strcasecmp(optname, "ladders")) {
 941                                 pp->ladders = optval && *optval == '0' ? false : true;
 942                         } else if (!strcasecmp(optname, "borderladders")) {
 943                                 pp->borderladders = optval && *optval == '0' ? false : true;
 944                         } else if (!strcasecmp(optname, "ladderassess")) {
 945                                 pp->ladderassess = optval && *optval == '0' ? false : true;
 946                         } else if (!strcasecmp(optname, "assess_local")) {
 947                                 pp->assess_local = optval && *optval == '0' ? false : true;
 948                         } else if (!strcasecmp(optname, "pattern2")) {
 949                                 pp->pattern2 = optval && *optval == '0' ? false : true;
 950                         } else {
 951                                 fprintf(stderr, "playout-moggy: Invalid policy argument %s or missing value\n", optname);
 952                                 exit(1);
 953                         }
 954                 }
 955         }
 956         if (pp->lcapturerate == -1U) pp->lcapturerate = rate;
 957         if (pp->atarirate == -1U) pp->atarirate = rate;
 958         if (pp->capturerate == -1U) pp->capturerate = rate;
 959         if (pp->patternrate == -1U) pp->patternrate = rate;
 960         if (pp->selfatarirate == -1U) pp->selfatarirate = rate;
 961         if (pp->korate == -1U) pp->korate = rate;
 962         if (pp->alwaysccaprate == -1U) pp->alwaysccaprate = rate;
 963
 964         pattern3s_init(&pp->patterns, moggy_patterns_src, moggy_patterns_src_n);
 965
 966         return p;
 967 }