pattern.c

   1 #define DEBUG
   2 #include <assert.h>
   3 #include <ctype.h>
   4 #include <inttypes.h>
   5 #include <stdio.h>
   6 #include <stdlib.h>
   7
   8 #include "board.h"
   9 #include "debug.h"
  10 #include "pattern.h"
  11 #include "patternsp.h"
  12 #include "patternprob.h"
  13 #include "tactics/ladder.h"
  14 #include "tactics/selfatari.h"
  15 #include "tactics/util.h"
  16
  17
  18 struct pattern_config DEFAULT_PATTERN_CONFIG = {
  19         .bdist_max = 4,
  20
  21         .spat_min = 3, .spat_max = MAX_PATTERN_DIST,
  22         .spat_largest = true,
  23 };
  24
  25 #define PF_MATCH 15
  26
  27 pattern_spec PATTERN_SPEC_MATCH_DEFAULT = {
  28         [FEAT_CAPTURE] = ~0,
  29         [FEAT_AESCAPE] = ~0,
  30         [FEAT_SELFATARI] = ~0,
  31         [FEAT_ATARI] = ~0,
  32         [FEAT_BORDER] = ~0,
  33         [FEAT_CONTIGUITY] = 0,
  34         [FEAT_SPATIAL] = ~0,
  35 };
  36
  37 static const struct feature_info {
  38         char *name;
  39         int payloads;
  40 } features[FEAT_MAX] = {
  41         [FEAT_CAPTURE] = { .name = "capture", .payloads = 64 * 1 << CAPTURE_COUNTSTONES_PAYLOAD_SIZE },
  42         [FEAT_AESCAPE] = { .name = "atariescape", .payloads = 16 },
  43         [FEAT_SELFATARI] = { .name = "selfatari", .payloads = 4 },
  44         [FEAT_ATARI] = { .name = "atari", .payloads = 4 },
  45         [FEAT_BORDER] = { .name = "border", .payloads = -1 },
  46         [FEAT_CONTIGUITY] = { .name = "cont", .payloads = 2 },
  47         [FEAT_SPATIAL] = { .name = "s", .payloads = -1 },
  48 };
  49
  50 char *
  51 feature2str(char *str, struct feature *f)
  52 {
  53         return str + sprintf(str + strlen(str), "%s:%d", features[f->id].name, f->payload);
  54 }
  55
  56 char *
  57 str2feature(char *str, struct feature *f)
  58 {
  59         while (isspace(*str)) str++;
  60
  61         int unsigned flen = strcspn(str, ":");
  62         for (unsigned int i = 0; i < sizeof(features)/sizeof(features[0]); i++)
  63                 if (strlen(features[i].name) == flen && !strncmp(features[i].name, str, flen)) {
  64                         f->id = i;
  65                         goto found;
  66                 }
  67         fprintf(stderr, "invalid featurespec: %s[%d]\n", str, flen);
  68         exit(EXIT_FAILURE);
  69
  70 found:
  71         str += flen + 1;
  72         f->payload = strtoull(str, &str, 10);
  73         return str;
  74 }
  75
  76 char *
  77 feature_name(enum feature_id f)
  78 {
  79         return features[f].name;
  80 }
  81
  82 int
  83 feature_payloads(struct pattern_config *pc, enum feature_id f)
  84 {
  85         switch (f) {
  86                 case FEAT_SPATIAL:
  87                         assert(features[f].payloads < 0);
  88                         return pc->spat_dict->nspatials;
  89                 case FEAT_BORDER:
  90                         assert(features[f].payloads < 0);
  91                         return pc->bdist_max + 1;
  92                 default:
  93                         assert(features[f].payloads > 0);
  94                         return features[f].payloads;
  95         }
  96 }
  97
  98
  99 void
 100 patterns_init(struct pattern_setup *pat, char *arg, bool will_append, bool load_prob)
 101 {
 102         char *pdict_file = NULL;
 103
 104         memset(pat, 0, sizeof(*pat));
 105
 106         pat->pc = DEFAULT_PATTERN_CONFIG;
 107         pat->pc.spat_dict = spatial_dict_init(will_append, !load_prob);
 108
 109         memcpy(&pat->ps, PATTERN_SPEC_MATCH_DEFAULT, sizeof(pattern_spec));
 110
 111         if (arg) {
 112                 char *optspec, *next = arg;
 113                 while (*next) {
 114                         optspec = next;
 115                         next += strcspn(next, ":");
 116                         if (*next) { *next++ = 0; } else { *next = 0; }
 117
 118                         char *optname = optspec;
 119                         char *optval = strchr(optspec, '=');
 120                         if (optval) *optval++ = 0;
 121
 122                         /* See pattern.h:pattern_config for description and
 123                          * pattern.c:DEFAULT_PATTERN_CONFIG for default values
 124                          * of the following options. */
 125                         if (!strcasecmp(optname, "bdist_max") && optval) {
 126                                 pat->pc.bdist_max = atoi(optval);
 127                         } else if (!strcasecmp(optname, "spat_min") && optval) {
 128                                 pat->pc.spat_min = atoi(optval);
 129                         } else if (!strcasecmp(optname, "spat_max") && optval) {
 130                                 pat->pc.spat_max = atoi(optval);
 131                         } else if (!strcasecmp(optname, "spat_largest")) {
 132                                 pat->pc.spat_largest = !optval || atoi(optval);
 133
 134                         } else if (!strcasecmp(optname, "pdict_file") && optval) {
 135                                 pdict_file = optval;
 136
 137                         } else {
 138                                 fprintf(stderr, "patterns: Invalid argument %s or missing value\n", optname);
 139                                 exit(EXIT_FAILURE);
 140                         }
 141                 }
 142         }
 143
 144         if (load_prob && pat->pc.spat_dict) {
 145                 pat->pd = pattern_pdict_init(pdict_file, &pat->pc);
 146         }
 147 }
 148
 149
 150 /* pattern_spec helpers */
 151 #define PS_ANY(F) (ps[FEAT_ ## F] & (1 << PF_MATCH))
 152 #define PS_PF(F, P) (ps[FEAT_ ## F] & (1 << PF_ ## F ## _ ## P))
 153
 154 static struct feature *
 155 pattern_match_capture(struct pattern_config *pc, pattern_spec ps,
 156                       struct pattern *p, struct feature *f,
 157                       struct board *b, struct move *m)
 158 {
 159         f->id = FEAT_CAPTURE; f->payload = 0;
 160 #ifdef BOARD_TRAITS
 161         if (!trait_at(b, m->coord, m->color).cap)
 162                 return f;
 163         /* Capturable! */
 164         if ((ps[FEAT_CAPTURE] & ~(1<<PF_CAPTURE_1STONE | 1<<PF_CAPTURE_TRAPPED | 1<<PF_CAPTURE_CONNECTION)) == 1<<PF_MATCH) {
 165                 if (PS_PF(CAPTURE, 1STONE))
 166                         f->payload |= (trait_at(b, m->coord, m->color).cap1 == trait_at(b, m->coord, m->color).cap) << PF_CAPTURE_1STONE;
 167                 if (PS_PF(CAPTURE, TRAPPED))
 168                         f->payload |= (!trait_at(b, m->coord, stone_other(m->color)).safe) << PF_CAPTURE_TRAPPED;
 169                 if (PS_PF(CAPTURE, CONNECTION))
 170                         f->payload |= (trait_at(b, m->coord, m->color).cap < neighbor_count_at(b, m->coord, stone_other(m->color))) << PF_CAPTURE_CONNECTION;
 171                 (f++, p->n++);
 172                 return f;
 173         }
 174         /* We need to know details, so we still have to go through
 175          * the neighbors. */
 176 #endif
 177
 178         /* We look at neighboring groups we could capture, and also if the
 179          * opponent could save them. */
 180         /* This is very similar in spirit to board_safe_to_play(), and almost
 181          * a color inverse of pattern_match_aescape(). */
 182
 183         /* Whether an escape move would be safe for the opponent. */
 184         int captures = 0;
 185         coord_t onelib = -1;
 186         int extra_libs = 0, connectable_groups = 0;
 187         bool onestone = false, multistone = false;
 188         int captured_stones = 0;
 189
 190         foreach_neighbor(b, m->coord, {
 191                 if (board_at(b, c) != stone_other(m->color)) {
 192                         if (board_at(b, c) == S_NONE)
 193                                 extra_libs++; // free point
 194                         else if (board_at(b, c) == m->color && board_group_info(b, group_at(b, c)).libs == 1)
 195                                 extra_libs += 2; // capturable enemy group
 196                         continue;
 197                 }
 198
 199                 group_t g = group_at(b, c); assert(g);
 200                 if (board_group_info(b, g).libs > 1) {
 201                         connectable_groups++;
 202                         if (board_group_info(b, g).libs > 2) {
 203                                 extra_libs += 2; // connected out
 204                         } else {
 205                                 /* This is a bit tricky; we connect our 2-lib
 206                                  * group to another 2-lib group, which counts
 207                                  * as one liberty, but only if the other lib
 208                                  * is not shared too. */
 209                                 if (onelib == -1) {
 210                                         onelib = board_group_other_lib(b, g, c);
 211                                         extra_libs++;
 212                                 } else {
 213                                         if (c == onelib)
 214                                                 extra_libs--; // take that back
 215                                         else
 216                                                 extra_libs++;
 217                                 }
 218                         }
 219                         continue;
 220                 }
 221
 222                 /* Capture! */
 223                 captures++;
 224
 225                 if (PS_PF(CAPTURE, LADDER))
 226                         f->payload |= is_ladder(b, m->coord, g) << PF_CAPTURE_LADDER;
 227                 /* TODO: is_ladder() is too conservative in some
 228                  * very obvious situations, look at complete.gtp. */
 229
 230                 if (PS_PF(CAPTURE, ATARIDEF))
 231                 foreach_in_group(b, g) {
 232                         foreach_neighbor(b, c, {
 233                                 assert(board_at(b, c) != S_NONE || c == m->coord);
 234                                 if (board_at(b, c) != m->color)
 235                                         continue;
 236                                 group_t g = group_at(b, c);
 237                                 if (!g || board_group_info(b, g).libs != 1)
 238                                         continue;
 239                                 /* A neighboring group of ours is in atari. */
 240                                 f->payload |= 1 << PF_CAPTURE_ATARIDEF;
 241                         });
 242                 } foreach_in_group_end;
 243
 244                 if (PS_PF(CAPTURE, KO)
 245                     && group_is_onestone(b, g)
 246                     && neighbor_count_at(b, m->coord, stone_other(m->color))
 247                        + neighbor_count_at(b, m->coord, S_OFFBOARD) == 4)
 248                         f->payload |= 1 << PF_CAPTURE_KO;
 249
 250                 if (PS_PF(CAPTURE, COUNTSTONES)
 251                     && captured_stones < (1 << CAPTURE_COUNTSTONES_PAYLOAD_SIZE) - 1)
 252                         captured_stones += group_stone_count(b, g, (1 << CAPTURE_COUNTSTONES_PAYLOAD_SIZE) - 1 - captured_stones);
 253
 254                 if (group_is_onestone(b, g))
 255                         onestone = true;
 256                 else
 257                         multistone = true;
 258         });
 259
 260         if (captures > 0) {
 261                 if (PS_PF(CAPTURE, 1STONE))
 262                         f->payload |= (onestone && !multistone) << PF_CAPTURE_1STONE;
 263                 if (PS_PF(CAPTURE, TRAPPED))
 264                         f->payload |= (extra_libs < 2) << PF_CAPTURE_TRAPPED;
 265                 if (PS_PF(CAPTURE, CONNECTION))
 266                         f->payload |= (connectable_groups > 0) << PF_CAPTURE_CONNECTION;
 267                 if (PS_PF(CAPTURE, COUNTSTONES))
 268                         f->payload |= captured_stones << PF_CAPTURE_COUNTSTONES;
 269                 (f++, p->n++);
 270         }
 271         return f;
 272 }
 273
 274 static struct feature *
 275 pattern_match_aescape(struct pattern_config *pc, pattern_spec ps,
 276                       struct pattern *p, struct feature *f,
 277                       struct board *b, struct move *m)
 278 {
 279         f->id = FEAT_AESCAPE; f->payload = 0;
 280 #ifdef BOARD_TRAITS
 281         if (!trait_at(b, m->coord, stone_other(m->color)).cap)
 282                 return f;
 283         /* Opponent can capture something! */
 284         if ((ps[FEAT_AESCAPE] & ~(1<<PF_AESCAPE_1STONE | 1<<PF_AESCAPE_TRAPPED | 1<<PF_AESCAPE_CONNECTION)) == 1<<PF_MATCH) {
 285                 if (PS_PF(AESCAPE, 1STONE))
 286                         f->payload |= (trait_at(b, m->coord, stone_other(m->color)).cap1 == trait_at(b, m->coord, stone_other(m->color)).cap) << PF_AESCAPE_1STONE;
 287                 if (PS_PF(AESCAPE, TRAPPED))
 288                         f->payload |= (!trait_at(b, m->coord, m->color).safe) << PF_AESCAPE_TRAPPED;
 289                 if (PS_PF(AESCAPE, CONNECTION))
 290                         f->payload |= (trait_at(b, m->coord, stone_other(m->color)).cap < neighbor_count_at(b, m->coord, m->color)) << PF_AESCAPE_CONNECTION;
 291                 (f++, p->n++);
 292                 return f;
 293         }
 294         /* We need to know details, so we still have to go through
 295          * the neighbors. */
 296 #endif
 297
 298         /* Find if a neighboring group of ours is in atari, AND that we provide
 299          * a liberty to connect out. XXX: No connect-and-die check. */
 300         /* This is very similar in spirit to board_safe_to_play(). */
 301         group_t in_atari = -1;
 302         coord_t onelib = -1;
 303         int extra_libs = 0, connectable_groups = 0;
 304         bool onestone = false, multistone = false;
 305
 306         foreach_neighbor(b, m->coord, {
 307                 if (board_at(b, c) != m->color) {
 308                         if (board_at(b, c) == S_NONE)
 309                                 extra_libs++; // free point
 310                         else if (board_at(b, c) == stone_other(m->color) && board_group_info(b, group_at(b, c)).libs == 1) {
 311                                 extra_libs += 2; // capturable enemy group
 312                                 /* XXX: We just consider this move safe
 313                                  * unconditionally. */
 314                         }
 315                         continue;
 316                 }
 317                 group_t g = group_at(b, c); assert(g);
 318                 if (board_group_info(b, g).libs > 1) {
 319                         connectable_groups++;
 320                         if (board_group_info(b, g).libs > 2) {
 321                                 extra_libs += 2; // connected out
 322                         } else {
 323                                 /* This is a bit tricky; we connect our 2-lib
 324                                  * group to another 2-lib group, which counts
 325                                  * as one liberty, but only if the other lib
 326                                  * is not shared too. */
 327                                 if (onelib == -1) {
 328                                         onelib = board_group_other_lib(b, g, c);
 329                                         extra_libs++;
 330                                 } else {
 331                                         if (c == onelib)
 332                                                 extra_libs--; // take that back
 333                                         else
 334                                                 extra_libs++;
 335                                 }
 336                         }
 337                         continue;
 338                 }
 339
 340                 /* In atari! */
 341                 in_atari = g;
 342
 343                 if (PS_PF(AESCAPE, LADDER))
 344                         f->payload |= is_ladder(b, m->coord, g) << PF_AESCAPE_LADDER;
 345                 /* TODO: is_ladder() is too conservative in some
 346                  * very obvious situations, look at complete.gtp. */
 347
 348                 if (group_is_onestone(b, g))
 349                         onestone = true;
 350                 else
 351                         multistone = true;
 352         });
 353
 354         if (in_atari >= 0) {
 355                 if (PS_PF(AESCAPE, 1STONE))
 356                         f->payload |= (onestone && !multistone) << PF_AESCAPE_1STONE;
 357                 if (PS_PF(AESCAPE, TRAPPED))
 358                         f->payload |= (extra_libs < 2) << PF_AESCAPE_TRAPPED;
 359                 if (PS_PF(AESCAPE, CONNECTION))
 360                         f->payload |= (connectable_groups > 0) << PF_AESCAPE_CONNECTION;
 361                 (f++, p->n++);
 362         }
 363         return f;
 364 }
 365
 366 static struct feature *
 367 pattern_match_atari(struct pattern_config *pc, pattern_spec ps,
 368                     struct pattern *p, struct feature *f,
 369                     struct board *b, struct move *m)
 370 {
 371         foreach_neighbor(b, m->coord, {
 372                 if (board_at(b, c) != stone_other(m->color))
 373                         continue;
 374                 group_t g = group_at(b, c);
 375                 if (!g || board_group_info(b, g).libs != 2)
 376                         continue;
 377
 378                 /* Can atari! */
 379                 f->id = FEAT_ATARI; f->payload = 0;
 380
 381                 if (PS_PF(ATARI, LADDER)) {
 382                         /* Opponent will escape by the other lib. */
 383                         coord_t lib = board_group_other_lib(b, g, m->coord);
 384                         /* TODO: is_ladder() is too conservative in some
 385                          * very obvious situations, look at complete.gtp. */
 386                         f->payload |= is_ladder(b, lib, g) << PF_ATARI_LADDER;
 387                 }
 388
 389                 if (PS_PF(ATARI, KO) && !is_pass(b->ko.coord))
 390                         f->payload |= 1 << PF_ATARI_KO;
 391
 392                 (f++, p->n++);
 393         });
 394         return f;
 395 }
 396
 397 #ifndef BOARD_SPATHASH
 398 #undef BOARD_SPATHASH_MAXD
 399 #define BOARD_SPATHASH_MAXD 1
 400 #endif
 401
 402 /* Match spatial features that are too distant to be pre-matched
 403  * incrementally. */
 404 struct feature *
 405 pattern_match_spatial_outer(struct pattern_config *pc, pattern_spec ps,
 406                             struct pattern *p, struct feature *f,
 407                             struct board *b, struct move *m, hash_t h)
 408 {
 409         /* We record all spatial patterns black-to-play; simply
 410          * reverse all colors if we are white-to-play. */
 411         static enum stone bt_black[4] = { S_NONE, S_BLACK, S_WHITE, S_OFFBOARD };
 412         static enum stone bt_white[4] = { S_NONE, S_WHITE, S_BLACK, S_OFFBOARD };
 413         enum stone (*bt)[4] = m->color == S_WHITE ? &bt_white : &bt_black;
 414
 415         for (unsigned int d = BOARD_SPATHASH_MAXD + 1; d <= pc->spat_max; d++) {
 416                 /* Recompute missing outer circles:
 417                  * Go through all points in given distance. */
 418                 for (unsigned int j = ptind[d]; j < ptind[d + 1]; j++) {
 419                         ptcoords_at(x, y, m->coord, b, j);
 420                         h ^= pthashes[0][j][(*bt)[board_atxy(b, x, y)]];
 421                 }
 422                 if (d < pc->spat_min)
 423                         continue;
 424                 /* Record spatial feature, one per distance. */
 425                 unsigned int sid = spatial_dict_get(pc->spat_dict, d, h & spatial_hash_mask);
 426                 if (sid > 0) {
 427                         f->id = FEAT_SPATIAL;
 428                         f->payload = sid;
 429                         if (!pc->spat_largest)
 430                                 (f++, p->n++);
 431                 } /* else not found, ignore */
 432         }
 433         return f;
 434 }
 435
 436 struct feature *
 437 pattern_match_spatial(struct pattern_config *pc, pattern_spec ps,
 438                       struct pattern *p, struct feature *f,
 439                       struct board *b, struct move *m)
 440 {
 441         /* XXX: This is partially duplicated from spatial_from_board(), but
 442          * we build a hash instead of spatial record. */
 443
 444         assert(pc->spat_min > 0);
 445         f->id = -1;
 446
 447         hash_t h = pthashes[0][0][S_NONE];
 448 #ifdef BOARD_SPATHASH
 449         bool w_to_play = m->color == S_WHITE;
 450         for (int d = 2; d <= BOARD_SPATHASH_MAXD; d++) {
 451                 /* Reuse all incrementally matched data. */
 452                 h ^= b->spathash[m->coord][d - 1][w_to_play];
 453                 if (d < pc->spat_min)
 454                         continue;
 455                 /* Record spatial feature, one per distance. */
 456                 unsigned int sid = spatial_dict_get(pc->spat_dict, d, h & spatial_hash_mask);
 457                 if (sid > 0) {
 458                         f->id = FEAT_SPATIAL;
 459                         f->payload = sid;
 460                         if (!pc->spat_largest)
 461                                 (f++, p->n++);
 462                 } /* else not found, ignore */
 463         }
 464 #else
 465         assert(BOARD_SPATHASH_MAXD < 2);
 466 #endif
 467         if (unlikely(pc->spat_max > BOARD_SPATHASH_MAXD))
 468                 f = pattern_match_spatial_outer(pc, ps, p, f, b, m, h);
 469         if (pc->spat_largest && f->id == FEAT_SPATIAL)
 470                 (f++, p->n++);
 471         return f;
 472 }
 473
 474
 475 void
 476 pattern_match(struct pattern_config *pc, pattern_spec ps,
 477               struct pattern *p, struct board *b, struct move *m)
 478 {
 479         p->n = 0;
 480         struct feature *f = &p->f[0];
 481
 482         /* TODO: We should match pretty much all of these features
 483          * incrementally. */
 484
 485         if (PS_ANY(CAPTURE)) {
 486                 f = pattern_match_capture(pc, ps, p, f, b, m);
 487         }
 488
 489         if (PS_ANY(AESCAPE)) {
 490                 f = pattern_match_aescape(pc, ps, p, f, b, m);
 491         }
 492
 493         if (PS_ANY(SELFATARI)) {
 494                 bool simple = false;
 495                 if (PS_PF(SELFATARI, STUPID)) {
 496 #ifdef BOARD_TRAITS
 497                         if (!b->precise_selfatari)
 498                                 simple = !trait_at(b, m->coord, m->color).safe;
 499                         else
 500 #endif
 501                         simple = !board_safe_to_play(b, m->coord, m->color);
 502                 }
 503                 bool thorough = false;
 504                 if (PS_PF(SELFATARI, SMART)) {
 505 #ifdef BOARD_TRAITS
 506                         if (b->precise_selfatari)
 507                                 thorough = !trait_at(b, m->coord, m->color).safe;
 508                         else
 509 #endif
 510                         thorough = is_bad_selfatari(b, m->color, m->coord);
 511                 }
 512                 if (simple || thorough) {
 513                         f->id = FEAT_SELFATARI;
 514                         f->payload = simple << PF_SELFATARI_STUPID;
 515                         f->payload |= thorough << PF_SELFATARI_SMART;
 516                         (f++, p->n++);
 517                 }
 518         }
 519
 520         if (PS_ANY(ATARI)) {
 521                 f = pattern_match_atari(pc, ps, p, f, b, m);
 522         }
 523
 524         if (PS_ANY(BORDER)) {
 525                 unsigned int bdist = coord_edge_distance(m->coord, b);
 526                 if (bdist <= pc->bdist_max) {
 527                         f->id = FEAT_BORDER;
 528                         f->payload = bdist;
 529                         (f++, p->n++);
 530                 }
 531         }
 532
 533         if (PS_ANY(CONTIGUITY) && !is_pass(b->last_move.coord)
 534             && coord_is_8adjecent(m->coord, b->last_move.coord, b)) {
 535                 f->id = FEAT_CONTIGUITY;
 536                 f->payload = 1;
 537                 (f++, p->n++);
 538         }
 539
 540         if (PS_ANY(SPATIAL) && pc->spat_max > 0 && pc->spat_dict) {
 541                 f = pattern_match_spatial(pc, ps, p, f, b, m);
 542         }
 543 }
 544
 545 char *
 546 pattern2str(char *str, struct pattern *p)
 547 {
 548         str = stpcpy(str, "(");
 549         for (int i = 0; i < p->n; i++) {
 550                 if (i > 0) str = stpcpy(str, " ");
 551                 str = feature2str(str, &p->f[i]);
 552         }
 553         str = stpcpy(str, ")");
 554         return str;
 555 }
 556
 557 char *
 558 str2pattern(char *str, struct pattern *p)
 559 {
 560         p->n = 0;
 561         while (isspace(*str)) str++;
 562         if (*str++ != '(') {
 563                 fprintf(stderr, "invalid patternspec: %s\n", str);
 564                 exit(EXIT_FAILURE);
 565         }
 566
 567         while (*str != ')') {
 568                 str = str2feature(str, &p->f[p->n++]);
 569         }
 570
 571         str++;
 572         return str;
 573 }