playout/moggy.c

   1 #include <assert.h>
   2 #include <math.h>
   3 #include <stdio.h>
   4 #include <stdlib.h>
   5
   6 #define DEBUG
   7 #include "board.h"
   8 #include "debug.h"
   9 #include "playout.h"
  10 #include "playout/moggy.h"
  11 #include "random.h"
  12
  13 #define PLDEBUGL(n) DEBUGL_(p->debug_level, n)
  14
  15
  16 struct moggy_policy {
  17         bool ladders, localassess, ladderassess;
  18         int lcapturerate, capturerate, patternrate;
  19         /* These are relative to patternrate. */
  20         int hanerate, cut1rate, cut2rate;
  21 };
  22
  23 #define MQL 64
  24 struct move_queue {
  25         int moves;
  26         coord_t move[MQL];
  27 };
  28
  29
  30 static bool
  31 cut1_test_cut(struct playout_policy *p, struct board *b, coord_t base, coord_t cut)
  32 {
  33         /* X O ?
  34          * O(.)?   X is base, (.) is cut
  35          * ? ? ? */
  36         int x = coord_x(base, b), y = coord_y(base, b);
  37         enum stone color = board_at(b, base);
  38         int xc = coord_x(cut, b), yc = coord_y(cut, b);
  39
  40         if (PLDEBUGL(5))
  41                 fprintf(stderr, "Probing CUT1 %s -> %s\n", coord2sstr(base, b), coord2sstr(cut, b));
  42
  43         /* Kosumi available. Is it cutting? */
  44         if (board_atxy(b, x, yc) != stone_other(color)
  45             || board_atxy(b, xc, y) != stone_other(color))
  46                 return false;
  47
  48         /* It is! Is the cut protected? */
  49         enum stone fix1 = board_atxy(b, xc, yc - (y - yc));
  50         enum stone fix2 = board_atxy(b, xc - (x - xc), yc);
  51         if (PLDEBUGL(6))
  52                 fprintf(stderr, "Protection check: %d,%d\n", fix1, fix2);
  53         if ((fix1 == stone_other(color) || fix1 == S_OFFBOARD) && fix2 != color)
  54                 return false;
  55         if ((fix2 == stone_other(color) || fix2 == S_OFFBOARD) && fix1 != color)
  56                 return false;
  57
  58         /* Unprotected cut. Feast! */
  59         if (PLDEBUGL(6))
  60                 fprintf(stderr, "Passed.\n");
  61         return true;
  62 }
  63
  64 static void
  65 cut1_test(struct playout_policy *p, struct board *b, struct move *m, struct move_queue *q)
  66 {
  67         coord_t coord = m->coord;
  68         int x = coord_x(coord, b), y = coord_y(coord, b);
  69         enum stone color = board_at(b, coord);
  70
  71         /* Either last move was cutting threat... */
  72         foreach_diag_neighbor(b, coord) {
  73                 if (board_at(b, c) != S_NONE)
  74                         continue;
  75                 /* X O ?
  76                  * O(.)?   X is coord, (.) is c
  77                  * ? ? ? */
  78                 if (cut1_test_cut(p, b, coord, c))
  79                         q->move[q->moves++] = c;
  80         } foreach_diag_neighbor_end;
  81
  82         /* ...or a cuttable hane. */
  83 #define cutbase_test(xb_, yb_) \
  84                 base = coord_xy_otf(xb_, yb_, b); \
  85                 if (board_at(b, base) == stone_other(color)) \
  86                         if (cut1_test_cut(p, b, base, c)) \
  87                                 q->move[q->moves++] = c;
  88         foreach_neighbor(b, coord, {
  89                 if (board_at(b, c) != S_NONE)
  90                         continue;
  91                 /* X O ?
  92                  * O(.)?   O is coord, (.) is c
  93                  * ? ? ? */
  94                 /* Check for X on both sides of O. */
  95                 int xc = coord_x(c, b);
  96                 int yc = coord_y(c, b);
  97                 coord_t base;
  98                 /* Either x == xc or y == yc. */
  99                 cutbase_test(x - (yc - y), y - (xc - x));
 100                 cutbase_test(x + (yc - y), y + (xc - x));
 101         });
 102 #undef cutbase_test
 103 }
 104
 105 static bool
 106 cut2_test_cut(struct playout_policy *p, struct board *b, coord_t base, coord_t cut)
 107 {
 108         /* ? X ?
 109          * O(.)O   X is base, (.) is cut
 110          * ? ? ? */
 111         int x = coord_x(base, b), y = coord_y(base, b);
 112         enum stone color = board_at(b, base);
 113         int xc = coord_x(cut, b), yc = coord_y(cut, b);
 114
 115         if (PLDEBUGL(5))
 116                 fprintf(stderr, "Probing CUT2 %s -> %s\n", coord2sstr(base, b), coord2sstr(cut, b));
 117
 118         /* Nobi available. Is it cutting? */
 119         if (board_atxy(b, xc - (yc - y), yc - (xc - x)) != stone_other(color)
 120             || board_atxy(b, xc + (yc - y), yc + (xc - x)) != stone_other(color))
 121                 return false;
 122
 123         /* It is! Is the cut protected? */
 124         enum stone ocolor = stone_other(color);
 125         if (x == xc) {
 126                 if (PLDEBUGL(6))
 127                         fprintf(stderr, "Protection check - row [%d,%d].\n", xc, yc + (yc - y));
 128                 if (board_atxy(b, xc - 1, yc + (yc - y)) == ocolor
 129                     || board_atxy(b, xc, yc + (yc - y)) == ocolor
 130                     || board_atxy(b, xc + 1, yc + (yc - y)) == ocolor)
 131                         return false;
 132         } else {
 133                 if (PLDEBUGL(6))
 134                         fprintf(stderr, "Protection check - column [%d,%d].\n", xc + (xc - x), yc);
 135                 if (board_atxy(b, xc + (xc - x), yc - 1) == ocolor
 136                     || board_atxy(b, xc + (xc - x), yc) == ocolor
 137                     || board_atxy(b, xc + (xc - x), yc + 1) == ocolor)
 138                         return false;
 139         }
 140
 141         /* Unprotected cut. Feast! */
 142         if (PLDEBUGL(6))
 143                 fprintf(stderr, "Passed.\n");
 144         return true;
 145 }
 146
 147 static void
 148 cut2_test(struct playout_policy *p, struct board *b, struct move *m, struct move_queue *q)
 149 {
 150         coord_t coord = m->coord;
 151         int x = coord_x(coord, b), y = coord_y(coord, b);
 152         enum stone color = board_at(b, coord);
 153
 154         /* Either last move was cutting threat... */
 155         foreach_neighbor(b, coord, {
 156                 if (board_at(b, c) != S_NONE)
 157                         continue;
 158                 /* ? X ?
 159                  * O(.)O   X is coord, (.) is c
 160                  * ? ? ? */
 161                 if (cut2_test_cut(p, b, coord, c))
 162                         q->move[q->moves++] = c;
 163         });
 164
 165         /* ...or a cuttable ikken tobi. */
 166 #define cutbase_test(xb_, yb_) \
 167                 base = coord_xy_otf(xb_, yb_, b); \
 168                 if (board_at(b, base) == stone_other(color)) \
 169                         if (cut2_test_cut(p, b, base, c)) \
 170                                 q->move[q->moves++] = c;
 171         foreach_neighbor(b, coord, {
 172                 if (board_at(b, c) != S_NONE)
 173                         continue;
 174                 /* ? X ?
 175                  * O(.)O   O is coord, (.) is c
 176                  * ? ? ? */
 177                 /* Check for X on both sides of (.). */
 178                 int xc = coord_x(c, b);
 179                 int yc = coord_y(c, b);
 180                 coord_t base;
 181                 /* Either x == xc or y == yc. */
 182                 cutbase_test(xc - (yc - y), yc - (xc - x));
 183                 cutbase_test(xc + (yc - y), yc + (xc - x));
 184         });
 185 #undef cutbase_test
 186 }
 187
 188 /* Check if we match a certain pattern centered on given move. */
 189 static coord_t
 190 apply_pattern(struct playout_policy *p, struct board *b, struct move *m, struct move *testmove)
 191 {
 192         struct moggy_policy *pp = p->data;
 193         struct move_queue q;
 194         q.moves = 0;
 195
 196         /* Suicides do not make any patterns and confuse us. */
 197         if (board_at(b, m->coord) == S_NONE || board_at(b, m->coord) == S_OFFBOARD)
 198                 return pass;
 199
 200         if (pp->hanerate > fast_random(100)) {
 201                 /* TODO */
 202         }
 203
 204         if (pp->cut1rate > fast_random(100)) {
 205                 cut1_test(p, b, m, &q);
 206         }
 207
 208         if (pp->cut2rate > fast_random(100)) {
 209                 cut2_test(p, b, m, &q);
 210         }
 211
 212         if (PLDEBUGL(4)) {
 213                 fprintf(stderr, "Pattern candidate moves: ");
 214                 for (int i = 0; i < q.moves; i++) {
 215                         fprintf(stderr, "%s ", coord2sstr(q.move[i], b));
 216                 }
 217                 fprintf(stderr, "\n");
 218         }
 219
 220         if (testmove) {
 221                 while (q.moves--)
 222                         if (q.move[q.moves] == testmove->coord) {
 223                                 if (PLDEBUGL(4))
 224                                         fprintf(stderr, "Found queried move.\n");
 225                                 return testmove->coord;
 226                         }
 227                 return pass;
 228         }
 229
 230         int i = fast_random(q.moves);
 231         return q.moves ? q.move[i] : pass;
 232 }
 233
 234
 235
 236 /* Is this ladder breaker friendly for the one who catches ladder. */
 237 static bool
 238 ladder_catcher(struct board *b, int x, int y, enum stone laddered)
 239 {
 240         enum stone breaker = board_atxy(b, x, y);
 241         return breaker == stone_other(laddered) || breaker == S_OFFBOARD;
 242 }
 243
 244 static bool
 245 ladder_catches(struct playout_policy *p, struct board *b, coord_t coord, group_t laddered)
 246 {
 247         /* This is very trivial and gets a lot of corner cases wrong.
 248          * We need this to be just very fast. */
 249         //fprintf(stderr, "ladder check\n");
 250
 251         enum stone lcolor = board_at(b, laddered);
 252
 253         /* Figure out the ladder direction */
 254         int x = coord_x(coord, b), y = coord_y(coord, b);
 255         int xd, yd;
 256         xd = board_atxy(b, x + 1, y) == S_NONE ? 1 : board_atxy(b, x - 1, y) == S_NONE ? -1 : 0;
 257         yd = board_atxy(b, x, y + 1) == S_NONE ? 1 : board_atxy(b, x, y - 1) == S_NONE ? -1 : 0;
 258
 259         /* We do only tight ladders, not loose ladders. Furthermore,
 260          * the ladders need to be simple:
 261          * . X .             . . X
 262          * c O X supported   . c O unsupported
 263          * X # #             X O #
 264          */
 265
 266         /* For given (xd,yd), we have two possibilities where to move
 267          * next. Consider (-1,1):
 268          * n X .   n c X
 269          * c O X   X O #
 270          * X # #   . X #
 271          */
 272         if (!xd || !yd || !(ladder_catcher(b, x - xd, y, lcolor) ^ ladder_catcher(b, x, y - yd, lcolor))) {
 273                 /* Silly situation, probably non-simple ladder or suicide. */
 274                 /* TODO: In case of basic non-simple ladder, play out both variants. */
 275                 if (PLDEBUGL(5))
 276                         fprintf(stderr, "non-simple ladder\n");
 277                 return false;
 278         }
 279
 280 #define ladder_check(xd1_, yd1_, xd2_, yd2_)    \
 281         if (board_atxy(b, x, y) != S_NONE) { \
 282                 /* Did we hit a stone when playing out ladder? */ \
 283                 if (ladder_catcher(b, x, y, lcolor)) \
 284                         return true; /* ladder works */ \
 285                 if (board_group_info(b, group_atxy(b, x, y)).lib[0] > 0) \
 286                         return false; /* friend that's not in atari himself */ \
 287         } else { \
 288                 /* No. So we are at new position. \
 289                  * We need to check indirect ladder breakers. */ \
 290                 /* . 2 x . . \
 291                  * . x o O 1 <- only at O we can check for o at 2 \
 292                  * x o o x .    otherwise x at O would be still deadly \
 293                  * o o x . . \
 294                  * We check for o and x at 1, these are vital. \
 295                  * We check only for o at 2; x at 2 would mean we \
 296                  * need to fork (one step earlier). */ \
 297                 enum stone s1 = board_atxy(b, x + (xd1_), y + (yd1_)); \
 298                 if (s1 == lcolor) return false; \
 299                 if (s1 == stone_other(lcolor)) return true; \
 300                 enum stone s2 = board_atxy(b, x + (xd2_), y + (yd2_)); \
 301                 if (s2 == lcolor) return false; \
 302         }
 303 #define ladder_horiz    do { if (PLDEBUGL(6)) fprintf(stderr, "%d,%d horiz step %d\n", x, y, xd); x += xd; ladder_check(xd, 0, -2 * xd, yd); } while (0)
 304 #define ladder_vert     do { if (PLDEBUGL(6)) fprintf(stderr, "%d,%d vert step %d\n", x, y, yd); y += yd; ladder_check(0, yd, xd, -2 * yd); } while (0)
 305
 306         if (ladder_catcher(b, x - xd, y, lcolor))
 307                 ladder_horiz;
 308         do {
 309                 ladder_vert;
 310                 ladder_horiz;
 311         } while (1);
 312 }
 313
 314
 315 static coord_t
 316 group_atari_check(struct playout_policy *p, struct board *b, group_t group, bool *ladder)
 317 {
 318         struct moggy_policy *pp = p->data;
 319         enum stone color = board_at(b, group);
 320         coord_t lib = board_group_info(b, group).lib[0];
 321
 322         if (board_at(b, group) == S_OFFBOARD) {
 323                 /* Bogus group. */
 324                 return pass;
 325         }
 326         if (PLDEBUGL(4))
 327                 fprintf(stderr, "atariiiiiiiii %s of color %d\n", coord2sstr(lib, b), color);
 328         assert(board_at(b, lib) == S_NONE);
 329
 330         /* Do not suicide... */
 331         if (!valid_escape_route(b, color, lib))
 332                 return pass;
 333         if (PLDEBUGL(4))
 334                 fprintf(stderr, "...escape route valid\n");
 335
 336         /* ...or play out ladders. */
 337         if (pp->ladders && ladder_catches(p, b, lib, group)) {
 338                 if (ladder)
 339                         *ladder = true;
 340                 return pass;
 341         }
 342         if (PLDEBUGL(4))
 343                 fprintf(stderr, "...no ladder\n");
 344
 345         return lib;
 346 }
 347
 348 static coord_t
 349 global_atari_check(struct playout_policy *p, struct board *b)
 350 {
 351         if (b->clen == 0)
 352                 return pass;
 353
 354         int g_base = fast_random(b->clen);
 355         for (int g = g_base; g < b->clen; g++) {
 356                 coord_t c = group_atari_check(p, b, b->c[g], NULL);
 357                 if (!is_pass(c))
 358                         return c;
 359         }
 360         for (int g = 0; g < g_base; g++) {
 361                 coord_t c = group_atari_check(p, b, b->c[g], NULL);
 362                 if (!is_pass(c))
 363                         return c;
 364         }
 365         return pass;
 366 }
 367
 368 static coord_t
 369 local_atari_check(struct playout_policy *p, struct board *b, struct move *m, struct move *testmove, bool *ladder)
 370 {
 371         bool ladders[MQL];
 372         struct move_queue q;
 373         q.moves = 0;
 374         memset(ladders, 0, sizeof(ladders));
 375
 376         /* Did the opponent play a self-atari? */
 377         if (board_group_info(b, group_at(b, m->coord)).libs == 1) {
 378                 coord_t l = group_atari_check(p, b, group_at(b, m->coord), &ladders[q.moves]);
 379                 if (!is_pass(l) || (ladder && ladders[q.moves]))
 380                         q.move[q.moves++] = l;
 381         }
 382
 383         foreach_neighbor(b, m->coord, {
 384                 if (board_group_info(b, group_at(b, c)).libs != 1)
 385                         continue;
 386                 coord_t l = group_atari_check(p, b, group_at(b, c), &ladders[q.moves]);
 387                 if (!is_pass(l) || (ladder && ladders[q.moves]))
 388                         q.move[q.moves++] = l;
 389         });
 390
 391         if (PLDEBUGL(4)) {
 392                 fprintf(stderr, "Local atari candidate moves: ");
 393                 for (int i = 0; i < q.moves; i++) {
 394                         fprintf(stderr, "%s ", coord2sstr(q.move[i], b));
 395                 }
 396                 fprintf(stderr, "\n");
 397         }
 398
 399         if (testmove) {
 400                 while (q.moves--)
 401                         if (q.move[q.moves] == testmove->coord) {
 402                                 if (PLDEBUGL(4))
 403                                         fprintf(stderr, "Found queried move.\n");
 404                                 if (ladder)
 405                                         *ladder = ladders[q.moves];
 406                                 return testmove->coord;
 407                         }
 408                 return pass;
 409         }
 410
 411         int i = fast_random(q.moves);
 412         return q.moves ? q.move[i] : pass;
 413 }
 414
 415 coord_t
 416 playout_moggy_choose(struct playout_policy *p, struct board *b, enum stone our_real_color)
 417 {
 418         struct moggy_policy *pp = p->data;
 419         coord_t c;
 420
 421         if (PLDEBUGL(4))
 422                 board_print(b, stderr);
 423
 424         /* Local checks */
 425         if (!is_pass(b->last_move.coord)) {
 426                 /* Local group in atari? */
 427                 if (pp->lcapturerate > fast_random(100)) {
 428                         c = local_atari_check(p, b, &b->last_move, NULL, NULL);
 429                         if (!is_pass(c))
 430                                 return c;
 431                 }
 432
 433                 /* Check for patterns we know */
 434                 if (pp->patternrate > fast_random(100)) {
 435                         c = apply_pattern(p, b, &b->last_move, NULL);
 436                         if (!is_pass(c))
 437                                 return c;
 438                 }
 439         }
 440
 441         /* Global checks */
 442
 443         /* Any groups in atari? */
 444         if (pp->capturerate > fast_random(100)) {
 445                 c = global_atari_check(p, b);
 446                 if (!is_pass(c))
 447                         return c;
 448         }
 449
 450         return pass;
 451 }
 452
 453 float
 454 playout_moggy_assess(struct playout_policy *p, struct board *b, struct move *m)
 455 {
 456         struct moggy_policy *pp = p->data;
 457
 458         if (is_pass(m->coord))
 459                 return NAN;
 460
 461         if (PLDEBUGL(4))
 462                 board_print(b, stderr);
 463
 464         /* Are we dealing with atari? */
 465         if (pp->lcapturerate > fast_random(100)) {
 466                 if (pp->localassess) {
 467                         bool ladder = false;
 468                         if (local_atari_check(p, b, &b->last_move, m, pp->ladderassess ? &ladder : NULL) == m->coord)
 469                                 return ladder ? 0.0 : 1.0;
 470                 } else {
 471                         foreach_neighbor(b, m->coord, {
 472                                 bool ladder = false;
 473                                 struct move m2;
 474                                 m2.coord = c; m2.color = stone_other(m->color);
 475                                 if (local_atari_check(p, b, &m2, m, pp->ladderassess ? &ladder : NULL) == m->coord)
 476                                         return ladder ? 0.0 : 1.0;
 477                         });
 478                 }
 479         }
 480
 481         /* Pattern check */
 482         if (pp->patternrate > fast_random(100)) {
 483                 if (pp->localassess) {
 484                         if (apply_pattern(p, b, &b->last_move, m) == m->coord)
 485                                 return 1.0;
 486                 } else {
 487                         foreach_neighbor(b, m->coord, {
 488                                 struct move m2;
 489                                 m2.coord = c; m2.color = stone_other(m->color);
 490                                 if (apply_pattern(p, b, &m2, m) == m->coord)
 491                                         return 1.0;
 492                         });
 493                         foreach_diag_neighbor(b, m->coord) {
 494                                 struct move m2;
 495                                 m2.coord = c; m2.color = stone_other(m->color);
 496                                 if (apply_pattern(p, b, &m2, m) == m->coord)
 497                                         return 1.0;
 498                         } foreach_diag_neighbor_end;
 499                 }
 500         }
 501
 502         return NAN;
 503 }
 504
 505
 506 struct playout_policy *
 507 playout_moggy_init(char *arg)
 508 {
 509         struct playout_policy *p = calloc(1, sizeof(*p));
 510         struct moggy_policy *pp = calloc(1, sizeof(*pp));
 511         p->data = pp;
 512         p->choose = playout_moggy_choose;
 513         p->assess = playout_moggy_assess;
 514
 515         pp->lcapturerate = 75;
 516         pp->capturerate = 75;
 517         pp->patternrate = 75;
 518         pp->hanerate = pp->cut1rate = pp->cut2rate = 75;
 519
 520         if (arg) {
 521                 char *optspec, *next = arg;
 522                 while (*next) {
 523                         optspec = next;
 524                         next += strcspn(next, ":");
 525                         if (*next) { *next++ = 0; } else { *next = 0; }
 526
 527                         char *optname = optspec;
 528                         char *optval = strchr(optspec, '=');
 529                         if (optval) *optval++ = 0;
 530
 531                         if (!strcasecmp(optname, "lcapturerate") && optval) {
 532                                 pp->lcapturerate = atoi(optval);
 533                         } else if (!strcasecmp(optname, "capturerate") && optval) {
 534                                 pp->capturerate = atoi(optval);
 535                         } else if (!strcasecmp(optname, "ladders")) {
 536                                 pp->ladders = true;
 537                         } else if (!strcasecmp(optname, "patternrate") && optval) {
 538                                 pp->patternrate = atoi(optval);
 539                         } else if (!strcasecmp(optname, "hanerate") && optval) {
 540                                 pp->hanerate = atoi(optval);
 541                         } else if (!strcasecmp(optname, "cut1rate") && optval) {
 542                                 pp->cut1rate = atoi(optval);
 543                         } else if (!strcasecmp(optname, "cut2rate") && optval) {
 544                                 pp->cut2rate = atoi(optval);
 545                         } else if (!strcasecmp(optname, "localassess")) {
 546                                 pp->localassess = true;
 547                         } else if (!strcasecmp(optname, "ladderassess")) {
 548                                 pp->ladderassess = true;
 549                         } else {
 550                                 fprintf(stderr, "playout-moggy: Invalid policy argument %s or missing value\n", optname);
 551                         }
 552                 }
 553         }
 554
 555         return p;
 556 }