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 "tactics.h"
  12
  13
  14 struct pattern_config DEFAULT_PATTERN_CONFIG = {
  15         .spat_min = 2, .spat_max = MAX_PATTERN_DIST,
  16         .bdist_max = 4,
  17         .ldist_min = 0, .ldist_max = 256,
  18         .mcsims = 0, /* Unsupported. */
  19 };
  20
  21
  22 static const char *fnames[] = {
  23         [FEAT_SPATIAL] = "s",
  24         [FEAT_PASS] = "pass",
  25         [FEAT_CAPTURE] = "capture",
  26         [FEAT_AESCAPE] = "atariescape",
  27         [FEAT_SELFATARI] = "selfatari",
  28         [FEAT_ATARI] = "atari",
  29         [FEAT_BORDER] = "border",
  30         [FEAT_LDIST] = "ldist",
  31         [FEAT_LLDIST] = "lldist",
  32         [FEAT_MCOWNER] = "mcowner",
  33 };
  34
  35 char *
  36 feature2str(char *str, struct feature *f)
  37 {
  38         return str + sprintf(str + strlen(str), "%s:%"PRIx32, fnames[f->id], f->payload);
  39 }
  40
  41 char *
  42 str2feature(char *str, struct feature *f)
  43 {
  44         while (isspace(*str)) str++;
  45
  46         int flen = strcspn(str, ":");
  47         for (int i = 0; i < sizeof(fnames)/sizeof(fnames[0]); i++)
  48                 if (strlen(fnames[i]) == flen && strncmp(fnames[i], str, flen)) {
  49                         f->id = i;
  50                         goto found;
  51                 }
  52         fprintf(stderr, "invalid featurespec: %s\n", str);
  53         exit(EXIT_FAILURE);
  54
  55 found:
  56         str += flen + 1;
  57         f->payload = strtoull(str, &str, 10);
  58         return str;
  59 }
  60
  61
  62 /* Mapping from point sequence to coordinate offsets (to determine
  63  * coordinates relative to pattern center). The array is ordered
  64  * in the gridcular metric order so that we can go through it
  65  * and incrementally match spatial features in nested circles.
  66  * Within one circle, coordinates are ordered by rows to keep
  67  * good cache behavior. */
  68 static struct { short x, y; } ptcoords[MAX_PATTERN_AREA];
  69 /* For each radius, starting index in ptcoords[]. */
  70 static int ptind[MAX_PATTERN_DIST + 1];
  71 static void __attribute__((constructor)) ptcoords_init(void)
  72 {
  73         int i = 0; /* Indexing ptcoords[] */
  74
  75         /* First, center point. */
  76         ptind[0] = ptind[1] = 0;
  77         ptcoords[i].x = ptcoords[i].y = 0; i++;
  78
  79         for (int d = 2; d < MAX_PATTERN_DIST + 1; d++) {
  80                 ptind[d] = i;
  81                 /* For each y, examine all integer solutions
  82                  * of d = |x| + |y| + max(|x|, |y|). */
  83                 /* TODO: (Stern, 2006) uses a hand-modified
  84                  * circles that are finer for small d. */
  85                 for (short y = d / 2; y >= 0; y--) {
  86                         short x;
  87                         if (y > d / 3) {
  88                                 /* max(|x|, |y|) = |y|, non-zero x */
  89                                 x = d - y * 2;
  90                                 if (x + y * 2 != d) continue;
  91                         } else {
  92                                 /* max(|x|, |y|) = |x| */
  93                                 /* Or, max(|x|, |y|) = |y| and x is zero */
  94                                 x = (d - y) / 2;
  95                                 if (x * 2 + y != d) continue;
  96                         }
  97
  98                         assert((x > y ? x : y) + x + y == d);
  99
 100                         ptcoords[i].x = x; ptcoords[i].y = y; i++;
 101                         if (x != 0) { ptcoords[i].x = -x; ptcoords[i].y = y; i++; }
 102                         if (y != 0) { ptcoords[i].x = x; ptcoords[i].y = -y; i++; }
 103                         if (x != 0 && y != 0) { ptcoords[i].x = -x; ptcoords[i].y = -y; i++; }
 104                 }
 105         }
 106         ptind[MAX_PATTERN_DIST] = i;
 107
 108 #if 0
 109         for (int d = 0; d < MAX_PATTERN_DIST; d++) {
 110                 fprintf(stderr, "d=%d (%d) ", d, ptind[d]);
 111                 for (int j = ptind[d]; j < ptind[d + 1]; j++) {
 112                         fprintf(stderr, "%d,%d ", ptcoords[j].x, ptcoords[j].y);
 113                 }
 114                 fprintf(stderr, "\n");
 115         }
 116 #endif
 117 }
 118
 119
 120 void
 121 pattern_match(struct pattern_config *pc, struct pattern *p, struct board *b, struct move *m)
 122 {
 123         p->n = 0;
 124         struct feature *f = &p->f[0];
 125
 126         /* TODO: We should match pretty much all of these features
 127          * incrementally. */
 128
 129         /* FEAT_PASS */
 130         if (is_pass(m->coord)) {
 131                 f->id = FEAT_PASS; f->payload = 0;
 132                 f->payload |= (b->moves > 0 && is_pass(b->last_move.coord)) << PF_PASS_LASTPASS;
 133                 p->n++;
 134                 return;
 135         }
 136
 137         /* FEAT_CAPTURE */
 138         {
 139                 foreach_neighbor(b, m->coord, {
 140                         if (board_at(b, c) != stone_other(m->color))
 141                                 continue;
 142                         group_t g = group_at(b, c);
 143                         if (!g || board_group_info(b, g).libs != 1)
 144                                 continue;
 145
 146                         /* Capture! */
 147                         f->id = FEAT_CAPTURE; f->payload = 0;
 148
 149                         f->payload |= is_ladder(b, m->coord, g, true, true) << PF_CAPTURE_LADDER;
 150                         /* TODO: is_ladder() is too conservative in some
 151                          * very obvious situations, look at complete.gtp. */
 152
 153                         /* TODO: PF_CAPTURE_RECAPTURE */
 154
 155                         foreach_in_group(b, g) {
 156                                 foreach_neighbor(b, c, {
 157                                         assert(board_at(b, c) != S_NONE || c == m->coord);
 158                                         if (board_at(b, c) != m->color)
 159                                                 continue;
 160                                         group_t g = group_at(b, c);
 161                                         if (!g || board_group_info(b, g).libs != 1)
 162                                                 continue;
 163                                         /* A neighboring group of ours is in atari. */
 164                                         f->payload |= 1 << PF_CAPTURE_ATARIDEF;
 165                                 });
 166                         } foreach_in_group_end;
 167
 168                         if (group_is_onestone(b, g)
 169                             && neighbor_count_at(b, m->coord, stone_other(m->color))
 170                                + neighbor_count_at(b, m->coord, S_OFFBOARD) == 4)
 171                                 f->payload |= 1 << PF_CAPTURE_KO;
 172
 173                         (f++, p->n++);
 174                 });
 175         }
 176
 177
 178         /* FEAT_AESCAPE */
 179         {
 180                 foreach_neighbor(b, m->coord, {
 181                         if (board_at(b, c) != m->color)
 182                                 continue;
 183                         group_t g = group_at(b, c);
 184                         if (!g || board_group_info(b, g).libs != 1)
 185                                 continue;
 186
 187                         /* In atari! */
 188                         f->id = FEAT_AESCAPE; f->payload = 0;
 189
 190                         f->payload |= is_ladder(b, m->coord, g, true, true) << PF_AESCAPE_LADDER;
 191                         /* TODO: is_ladder() is too conservative in some
 192                          * very obvious situations, look at complete.gtp. */
 193
 194                         (f++, p->n++);
 195                 });
 196         }
 197
 198
 199         /* FEAT_SELFATARI */
 200         if (is_bad_selfatari(b, m->color, m->coord)) {
 201                 f->id = FEAT_SELFATARI;
 202                 /* TODO: Dumb selfatari detection. */
 203                 f->payload = 1 << PF_SELFATARI_SMART;
 204         }
 205
 206         /* FEAT_ATARI */
 207         {
 208                 foreach_neighbor(b, m->coord, {
 209                         if (board_at(b, c) != stone_other(m->color))
 210                                 continue;
 211                         group_t g = group_at(b, c);
 212                         if (!g || board_group_info(b, g).libs != 2)
 213                                 continue;
 214
 215                         /* Can atari! */
 216                         f->id = FEAT_ATARI; f->payload = 0;
 217
 218                         f->payload |= is_ladder(b, m->coord, g, true, true) << PF_ATARI_LADDER;
 219                         /* TODO: is_ladder() is too conservative in some
 220                          * very obvious situations, look at complete.gtp. */
 221
 222                         if (!is_pass(b->ko.coord))
 223                                 f->payload |= 1 << PF_CAPTURE_KO;
 224
 225                         (f++, p->n++);
 226                 });
 227         }
 228
 229         /* FEAT_BORDER */
 230         int bdist = coord_edge_distance(m->coord, b);
 231         if (bdist <= pc->bdist_max) {
 232                 f->id = FEAT_BORDER;
 233                 f->payload = bdist;
 234                 (f++, p->n++);
 235         }
 236
 237         /* FEAT_LDIST */
 238         if (pc->ldist_max > 0 && !is_pass(b->last_move.coord)) {
 239                 int ldist = coord_gridcular_distance(m->coord, b->last_move.coord, b);
 240                 if (pc->ldist_min <= ldist && ldist <= pc->ldist_max) {
 241                         f->id = FEAT_LDIST;
 242                         f->payload = ldist;
 243                         (f++, p->n++);
 244                 }
 245         }
 246
 247         /* FEAT_LLDIST */
 248         if (pc->ldist_max > 0 && !is_pass(b->last_move.coord)) {
 249                 int lldist = coord_gridcular_distance(m->coord, b->last_move2.coord, b);
 250                 if (pc->ldist_min <= lldist && lldist <= pc->ldist_max) {
 251                         f->id = FEAT_LLDIST;
 252                         f->payload = lldist;
 253                         (f++, p->n++);
 254                 }
 255         }
 256
 257         /* FEAT_SPATIAL */
 258         if (pc->spat_max > 0 && pc->spat_dict) {
 259                 assert(pc->spat_min > 0);
 260
 261                 /* We record all spatial patterns black-to-play; simply
 262                  * reverse all colors if we are white-to-play. */
 263                 enum stone bt[4] = { S_NONE, S_BLACK, S_WHITE, S_OFFBOARD };
 264                 if (m->color == S_WHITE) {
 265                         bt[1] = S_WHITE; bt[2] = S_BLACK;
 266                 }
 267
 268                 struct spatial s = { .points = {0} };
 269                 for (int d = 2; d < pc->spat_max; d++) {
 270                         /* Go through all points in given distance. */
 271                         for (int j = ptind[d]; j < ptind[d + 1]; j++) {
 272                                 int x = coord_x(m->coord, b) + ptcoords[j].x;
 273                                 int y = coord_y(m->coord, b) + ptcoords[j].y;
 274                                 if (x >= board_size(b)) x = board_size(b) - 1; else if (x < 0) x = 0;
 275                                 if (y >= board_size(b)) y = board_size(b) - 1; else if (y < 0) y = 0;
 276                                 /* Append point. */
 277                                 s.points[j / 4] |= bt[board_atxy(b, x, y)] << ((j % 4) * 2);
 278                         }
 279                         if (d < pc->spat_min)
 280                                 continue;
 281                         /* Record spatial feature, one per distance. */
 282                         f->id = FEAT_SPATIAL;
 283                         f->payload = (d << PF_SPATIAL_RADIUS);
 284                         s.dist = d;
 285                         int sid = spatial_dict_get(pc->spat_dict, &s);
 286                         if (sid > 0) {
 287                                 f->payload |= sid << PF_SPATIAL_INDEX;
 288                                 (f++, p->n++);
 289                         } /* else not found, ignore */
 290                 }
 291         }
 292
 293         /* FEAT_MCOWNER */
 294         /* TODO */
 295         assert(!pc->mcsims);
 296 }
 297
 298 char *
 299 pattern2str(char *str, struct pattern *p)
 300 {
 301         str = stpcpy(str, "(");
 302         for (int i = 0; i < p->n; i++) {
 303                 if (i > 0) str = stpcpy(str, " ");
 304                 str = feature2str(str, &p->f[i]);
 305         }
 306         str = stpcpy(str, ")");
 307         return str;
 308 }
 309
 310
 311
 312 /*** Spatial patterns dictionary */
 313
 314 /* Zobrist hashes used for black/white stones in patterns. */
 315 #define PTH__ROTATIONS  8
 316 static hash_t pthashes[PTH__ROTATIONS][MAX_PATTERN_AREA][4];
 317 static void __attribute__((constructor)) pthashes_init(void)
 318 {
 319         /* We need fixed hashes for all pattern-relative in
 320          * all pattern users! This is a simple way to generate
 321          * hopefully good ones. Park-Miller powa. :) */
 322
 323         /* We create a virtual board (centered at the sequence start),
 324          * plant the hashes there, then pick them up into the sequence
 325          * with correct coordinates. It would be possible to generate
 326          * the sequence point hashes directly, but the rotations would
 327          * make for enormous headaches. */
 328         hash_t pthboard[MAX_PATTERN_AREA][4];
 329         int pthbc = MAX_PATTERN_AREA / 2; // tengen coord
 330
 331         /* The magic numbers are tuned for minimal collisions. */
 332         hash_t h = 0x313131;
 333         for (int i = 0; i < MAX_PATTERN_AREA; i++) {
 334                 pthboard[i][S_NONE] = (h = h * 16803 - 7);
 335                 pthboard[i][S_BLACK] = (h = h * 16805 + 7);
 336                 pthboard[i][S_WHITE] = (h = h * 16807 + 3);
 337                 pthboard[i][S_OFFBOARD] = (h = h * 16809 - 3);
 338         }
 339
 340         /* Virtual board with hashes created, now fill
 341          * pthashes[] with hashes for points in actual
 342          * sequences, also considering various rotations. */
 343 #define PTH_VMIRROR     1
 344 #define PTH_HMIRROR     2
 345 #define PTH_90ROT       4
 346         for (int r = 0; r < PTH__ROTATIONS; r++) {
 347                 for (int i = 0; i < MAX_PATTERN_AREA; i++) {
 348                         /* Rotate appropriately. */
 349                         int rx = ptcoords[i].x;
 350                         int ry = ptcoords[i].y;
 351                         if (r & PTH_VMIRROR) ry = -ry;
 352                         if (r & PTH_HMIRROR) rx = -rx;
 353                         if (r & PTH_90ROT) {
 354                                 int rs = rx; rx = -ry; ry = rs;
 355                         }
 356                         int bi = pthbc + ry * MAX_PATTERN_DIST + rx;
 357
 358                         /* Copy info. */
 359                         pthashes[r][i][S_NONE] = pthboard[bi][S_NONE];
 360                         pthashes[r][i][S_BLACK] = pthboard[bi][S_BLACK];
 361                         pthashes[r][i][S_WHITE] = pthboard[bi][S_WHITE];
 362                         pthashes[r][i][S_OFFBOARD] = pthboard[bi][S_OFFBOARD];
 363                 }
 364         }
 365 }
 366
 367 static hash_t
 368 spatial_hash(int rotation, struct spatial *s)
 369 {
 370         hash_t h = 0;
 371         for (int i = 0; i < ptind[s->dist + 1]; i++) {
 372                 h ^= pthashes[rotation][i][spatial_point_at(*s, i)];
 373         }
 374         return h & spatial_hash_mask;
 375 }
 376
 377 static int
 378 spatial_dict_addc(struct spatial_dict *dict, struct spatial *s)
 379 {
 380         /* Allocate space in 1024 blocks. */
 381 #define SPATIALS_ALLOC 1024
 382         if (!(dict->nspatials % SPATIALS_ALLOC)) {
 383                 dict->spatials = realloc(dict->spatials,
 384                                 (dict->nspatials + SPATIALS_ALLOC)
 385                                 * sizeof(*dict->spatials));
 386         }
 387         dict->spatials[dict->nspatials] = *s;
 388         return dict->nspatials++;
 389 }
 390
 391 static bool
 392 spatial_dict_addh(struct spatial_dict *dict, hash_t hash, int id)
 393 {
 394         if (dict->hash[hash]) {
 395                 dict->collisions++;
 396                 /* Give up, not worth the trouble. */
 397                 return false;
 398         }
 399         dict->hash[hash] = id;
 400         return true;
 401 }
 402
 403 /* Spatial dictionary file format:
 404  * /^#/ - comments
 405  * INDEX RADIUS STONES HASH...
 406  * INDEX: index in the spatial table
 407  * RADIUS: @d of the pattern
 408  * STONES: string of ".XO#" chars
 409  * HASH...: space-separated 18bit hash-table indices for the pattern */
 410
 411 static void
 412 spatial_dict_read(struct spatial_dict *dict, char *buf)
 413 {
 414         /* XXX: We trust the data. Bad data will crash us. */
 415         char *bufp = buf;
 416
 417         int index, radius;
 418         index = strtol(bufp, &bufp, 10);
 419         radius = strtol(bufp, &bufp, 10);
 420         while (isspace(*bufp)) bufp++;
 421
 422         /* Load the stone configuration. */
 423         struct spatial s = { .dist = radius };
 424         int sl = 0;
 425         while (!isspace(*bufp)) {
 426                 s.points[sl / 4] |= char2stone(*bufp++) << (sl % 4);
 427                 sl++;
 428         }
 429         while (isspace(*bufp)) bufp++;
 430
 431         /* Sanity check. */
 432         if (sl != ptind[s.dist + 1]) {
 433                 fprintf(stderr, "Spatial dictionary: Invalid number of stones (%d != %d) on this line: %s\n",
 434                         sl, ptind[radius + 1] - 1, buf);
 435                 exit(EXIT_FAILURE);
 436         }
 437
 438         /* Add to collection. */
 439         int id = spatial_dict_addc(dict, &s);
 440
 441         /* Add to specified hash places. */
 442         while (*bufp) {
 443                 int hash = strtol(bufp, &bufp, 16);
 444                 while (isspace(*bufp)) bufp++;
 445                 spatial_dict_addh(dict, hash & spatial_hash_mask, id);
 446         }
 447 }
 448
 449 static char *
 450 spatial2str(struct spatial *s)
 451 {
 452         static char buf[1024];
 453         for (int i = 0; i < ptind[s->dist + 1]; i++) {
 454                 buf[i] = stone2char(spatial_point_at(*s, i));
 455         }
 456         buf[ptind[s->dist + 1]] = 0;
 457         return buf;
 458 }
 459
 460 static void
 461 spatial_dict_write(struct spatial_dict *dict, int id, FILE *f)
 462 {
 463         struct spatial *s = &dict->spatials[id];
 464         fprintf(f, "%d %d ", id, s->dist);
 465         fputs(spatial2str(s), f);
 466         for (int r = 0; r < PTH__ROTATIONS; r++)
 467                 fprintf(f, " %"PRIhash"", spatial_hash(r, s));
 468         fputc('\n', f);
 469 }
 470
 471 static void
 472 spatial_dict_load(struct spatial_dict *dict, FILE *f)
 473 {
 474         char buf[1024];
 475         while (fgets(buf, sizeof(buf), f)) {
 476                 if (buf[0] == '#') continue;
 477                 spatial_dict_read(dict, buf);
 478         }
 479 }
 480
 481 struct spatial_dict *
 482 spatial_dict_init(bool will_append)
 483 {
 484         static const char *filename = "spatial.dict";
 485         FILE *f = fopen(filename, "r");
 486         if (!f && !will_append) {
 487                 if (DEBUGL(1))
 488                         fprintf(stderr, "No spatial dictionary, will not match spatial pattern features.\n");
 489                 return NULL;
 490         }
 491
 492         struct spatial_dict *dict = calloc(1, sizeof(*dict));
 493         /* We create a dummy record for index 0 that we will
 494          * never reference. This is so that hash value 0 can
 495          * represent "no value". */
 496         struct spatial dummy = { .dist = 0 };
 497         spatial_dict_addc(dict, &dummy);
 498
 499         if (f) {
 500                 /* Existing file. Load it up! */
 501                 spatial_dict_load(dict, f);
 502                 fclose(f); f = NULL;
 503                 if (will_append)
 504                         f = fopen(filename, "a");
 505         } else {
 506                 assert(will_append);
 507                 f = fopen(filename, "a");
 508                 /* New file. First, create a comment describing order
 509                  * of points in the array. This is just for purposes
 510                  * of external tools, Pachi never interprets it itself. */
 511                 fprintf(f, "# Pachi spatial patterns dictionary v1.0 maxdist %d\n",
 512                         MAX_PATTERN_DIST);
 513                 for (int d = 0; d < MAX_PATTERN_DIST; d++) {
 514                         fprintf(f, "# Point order: d=%d ", d);
 515                         for (int j = ptind[d]; j < ptind[d + 1]; j++) {
 516                                 fprintf(f, "%d,%d ", ptcoords[j].x, ptcoords[j].y);
 517                         }
 518                         fprintf(f, "\n");
 519                 }
 520         }
 521
 522         dict->f = f;
 523         return dict;
 524 }
 525
 526 int
 527 spatial_dict_get(struct spatial_dict *dict, struct spatial *s)
 528 {
 529         hash_t hash = spatial_hash(0, s);
 530         int id = dict->hash[hash];
 531         if (id && dict->f) {
 532                 /* Check for collisions in append mode. */
 533                 /* Tough job, we simply try if any other rotation
 534                  * is also covered by the existing record. */
 535                 int r; hash_t rhash; int rid;
 536                 for (r = 1; r < PTH__ROTATIONS; r++) {
 537                         rhash = spatial_hash(r, s);
 538                         rid = dict->hash[rhash];
 539                         if (rid == id)
 540                                 goto no_collision;
 541                 }
 542                 if (DEBUGL(1))
 543                         fprintf(stderr, "Collision %d vs %d (hash %d:%"PRIhash")\n",
 544                                 id, dict->nspatials, r, hash);
 545                 id = 0;
 546                 /* dict->collisions++; gets done by addh */
 547 no_collision:;
 548         }
 549         if (id) return id;
 550         if (!dict->f) return -1;
 551
 552         /* Add new pattern! */
 553         id = spatial_dict_addc(dict, s);
 554         for (int r = 0; r < PTH__ROTATIONS; r++)
 555                 spatial_dict_addh(dict, spatial_hash(r, s), id);
 556         spatial_dict_write(dict, id, dict->f);
 557         return id;
 558 }