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