patternsp.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 "tactics.h"
  13
  14
  15 /* Mapping from point sequence to coordinate offsets (to determine
  16  * coordinates relative to pattern center). The array is ordered
  17  * in the gridcular metric order so that we can go through it
  18  * and incrementally match spatial features in nested circles.
  19  * Within one circle, coordinates are ordered by rows to keep
  20  * good cache behavior. */
  21 struct ptcoord ptcoords[MAX_PATTERN_AREA];
  22
  23 /* For each radius, starting index in ptcoords[]. */
  24 int ptind[MAX_PATTERN_DIST + 2];
  25
  26 /* ptcoords[], ptind[] setup */
  27 static void __attribute__((constructor(140)))
  28 ptcoords_init(void)
  29 {
  30         int i = 0; /* Indexing ptcoords[] */
  31
  32         /* First, center point. */
  33         ptind[0] = ptind[1] = 0;
  34         ptcoords[i].x = ptcoords[i].y = 0; i++;
  35
  36         for (int d = 2; d <= MAX_PATTERN_DIST; d++) {
  37                 ptind[d] = i;
  38                 /* For each y, examine all integer solutions
  39                  * of d = |x| + |y| + max(|x|, |y|). */
  40                 /* TODO: (Stern, 2006) uses a hand-modified
  41                  * circles that are finer for small d. */
  42                 for (short y = d / 2; y >= 0; y--) {
  43                         short x;
  44                         if (y > d / 3) {
  45                                 /* max(|x|, |y|) = |y|, non-zero x */
  46                                 x = d - y * 2;
  47                                 if (x + y * 2 != d) continue;
  48                         } else {
  49                                 /* max(|x|, |y|) = |x| */
  50                                 /* Or, max(|x|, |y|) = |y| and x is zero */
  51                                 x = (d - y) / 2;
  52                                 if (x * 2 + y != d) continue;
  53                         }
  54
  55                         assert((x > y ? x : y) + x + y == d);
  56
  57                         ptcoords[i].x = x; ptcoords[i].y = y; i++;
  58                         if (x != 0) { ptcoords[i].x = -x; ptcoords[i].y = y; i++; }
  59                         if (y != 0) { ptcoords[i].x = x; ptcoords[i].y = -y; i++; }
  60                         if (x != 0 && y != 0) { ptcoords[i].x = -x; ptcoords[i].y = -y; i++; }
  61                 }
  62         }
  63         ptind[MAX_PATTERN_DIST + 1] = i;
  64
  65 #if 0
  66         for (int d = 0; d <= MAX_PATTERN_DIST; d++) {
  67                 fprintf(stderr, "d=%d (%d) ", d, ptind[d]);
  68                 for (int j = ptind[d]; j < ptind[d + 1]; j++) {
  69                         fprintf(stderr, "%d,%d ", ptcoords[j].x, ptcoords[j].y);
  70                 }
  71                 fprintf(stderr, "\n");
  72         }
  73 #endif
  74 }
  75
  76
  77 /* Zobrist hashes used for points in patterns. */
  78 hash_t pthashes[PTH__ROTATIONS][MAX_PATTERN_AREA][S_MAX];
  79
  80 static void __attribute__((constructor(160)))
  81 pthashes_init(void)
  82 {
  83         /* We need fixed hashes for all pattern-relative in
  84          * all pattern users! This is a simple way to generate
  85          * hopefully good ones. Park-Miller powa. :) */
  86
  87         /* We create a virtual board (centered at the sequence start),
  88          * plant the hashes there, then pick them up into the sequence
  89          * with correct coordinates. It would be possible to generate
  90          * the sequence point hashes directly, but the rotations would
  91          * make for enormous headaches. */
  92         hash_t pthboard[MAX_PATTERN_AREA][4];
  93         int pthbc = MAX_PATTERN_AREA / 2; // tengen coord
  94
  95         /* The magic numbers are tuned for minimal collisions. */
  96         hash_t h = 0x313131;
  97         for (int i = 0; i < MAX_PATTERN_AREA; i++) {
  98                 pthboard[i][S_NONE] = (h = h * 16803 - 7);
  99                 pthboard[i][S_BLACK] = (h = h * 16805 + 7);
 100                 pthboard[i][S_WHITE] = (h = h * 16807 + 3);
 101                 pthboard[i][S_OFFBOARD] = (h = h * 16809 - 3);
 102         }
 103
 104         /* Virtual board with hashes created, now fill
 105          * pthashes[] with hashes for points in actual
 106          * sequences, also considering various rotations. */
 107 #define PTH_VMIRROR     1
 108 #define PTH_HMIRROR     2
 109 #define PTH_90ROT       4
 110         for (int r = 0; r < PTH__ROTATIONS; r++) {
 111                 for (int i = 0; i < MAX_PATTERN_AREA; i++) {
 112                         /* Rotate appropriately. */
 113                         int rx = ptcoords[i].x;
 114                         int ry = ptcoords[i].y;
 115                         if (r & PTH_VMIRROR) ry = -ry;
 116                         if (r & PTH_HMIRROR) rx = -rx;
 117                         if (r & PTH_90ROT) {
 118                                 int rs = rx; rx = -ry; ry = rs;
 119                         }
 120                         int bi = pthbc + ry * MAX_PATTERN_DIST + rx;
 121
 122                         /* Copy info. */
 123                         pthashes[r][i][S_NONE] = pthboard[bi][S_NONE];
 124                         pthashes[r][i][S_BLACK] = pthboard[bi][S_BLACK];
 125                         pthashes[r][i][S_WHITE] = pthboard[bi][S_WHITE];
 126                         pthashes[r][i][S_OFFBOARD] = pthboard[bi][S_OFFBOARD];
 127                 }
 128         }
 129 }
 130
 131 inline hash_t
 132 spatial_hash(int rotation, struct spatial *s)
 133 {
 134         hash_t h = 0;
 135         for (int i = 0; i < ptind[s->dist + 1]; i++) {
 136                 h ^= pthashes[rotation][i][spatial_point_at(*s, i)];
 137         }
 138         return h & spatial_hash_mask;
 139 }
 140
 141 char *
 142 spatial2str(struct spatial *s)
 143 {
 144         static char buf[1024];
 145         for (int i = 0; i < ptind[s->dist + 1]; i++) {
 146                 buf[i] = stone2char(spatial_point_at(*s, i));
 147         }
 148         buf[ptind[s->dist + 1]] = 0;
 149         return buf;
 150 }
 151
 152 void
 153 spatial_from_board(struct pattern_config *pc, struct spatial *s,
 154                    struct board *b, struct move *m)
 155 {
 156         assert(pc->spat_min > 0);
 157
 158         /* We record all spatial patterns black-to-play; simply
 159          * reverse all colors if we are white-to-play. */
 160         static enum stone bt_black[4] = { S_NONE, S_BLACK, S_WHITE, S_OFFBOARD };
 161         static enum stone bt_white[4] = { S_NONE, S_WHITE, S_BLACK, S_OFFBOARD };
 162         enum stone (*bt)[4] = m->color == S_WHITE ? &bt_white : &bt_black;
 163
 164         memset(s, 0, sizeof(*s));
 165         for (int j = 0; j < ptind[pc->spat_max + 1]; j++) {
 166                 ptcoords_at(x, y, m->coord, b, j);
 167                 s->points[j / 4] |= (*bt)[board_atxy(b, x, y)] << ((j % 4) * 2);
 168         }
 169         s->dist = pc->spat_max;
 170 }
 171
 172
 173 /* Spatial dict manipulation. */
 174
 175 static int
 176 spatial_dict_addc(struct spatial_dict *dict, struct spatial *s)
 177 {
 178         /* Allocate space in 1024 blocks. */
 179 #define SPATIALS_ALLOC 1024
 180         if (!(dict->nspatials % SPATIALS_ALLOC)) {
 181                 dict->spatials = realloc(dict->spatials,
 182                                 (dict->nspatials + SPATIALS_ALLOC)
 183                                 * sizeof(*dict->spatials));
 184         }
 185         dict->spatials[dict->nspatials] = *s;
 186         return dict->nspatials++;
 187 }
 188
 189 static bool
 190 spatial_dict_addh(struct spatial_dict *dict, hash_t hash, int id)
 191 {
 192         if (dict->hash[hash])
 193                 dict->collisions++;
 194         dict->hash[hash] = id;
 195         return true;
 196 }
 197
 198 /* Spatial dictionary file format:
 199  * /^#/ - comments
 200  * INDEX RADIUS STONES HASH...
 201  * INDEX: index in the spatial table
 202  * RADIUS: @d of the pattern
 203  * STONES: string of ".XO#" chars
 204  * HASH...: space-separated 18bit hash-table indices for the pattern */
 205
 206 static void
 207 spatial_dict_read(struct spatial_dict *dict, char *buf)
 208 {
 209         /* XXX: We trust the data. Bad data will crash us. */
 210         char *bufp = buf;
 211
 212         int index, radius;
 213         index = strtol(bufp, &bufp, 10);
 214         radius = strtol(bufp, &bufp, 10);
 215         while (isspace(*bufp)) bufp++;
 216
 217         /* Load the stone configuration. */
 218         struct spatial s = { .dist = radius };
 219         int sl = 0;
 220         while (!isspace(*bufp)) {
 221                 s.points[sl / 4] |= char2stone(*bufp++) << ((sl % 4)*2);
 222                 sl++;
 223         }
 224         while (isspace(*bufp)) bufp++;
 225
 226         /* Sanity check. */
 227         if (sl != ptind[s.dist + 1]) {
 228                 fprintf(stderr, "Spatial dictionary: Invalid number of stones (%d != %d) on this line: %s\n",
 229                         sl, ptind[radius + 1] - 1, buf);
 230                 exit(EXIT_FAILURE);
 231         }
 232
 233         /* Add to collection. */
 234         int id = spatial_dict_addc(dict, &s);
 235
 236         /* Add to specified hash places. */
 237         while (*bufp) {
 238                 int hash = strtol(bufp, &bufp, 16);
 239                 while (isspace(*bufp)) bufp++;
 240                 spatial_dict_addh(dict, hash & spatial_hash_mask, id);
 241         }
 242 }
 243
 244 void
 245 spatial_write(struct spatial *s, int id, FILE *f)
 246 {
 247         fprintf(f, "%d %d ", id, s->dist);
 248         fputs(spatial2str(s), f);
 249         for (int r = 0; r < PTH__ROTATIONS; r++)
 250                 fprintf(f, " %"PRIhash"", spatial_hash(r, s));
 251         fputc('\n', f);
 252 }
 253
 254 static void
 255 spatial_dict_load(struct spatial_dict *dict, FILE *f)
 256 {
 257         char buf[1024];
 258         while (fgets(buf, sizeof(buf), f)) {
 259                 if (buf[0] == '#') continue;
 260                 spatial_dict_read(dict, buf);
 261         }
 262 }
 263
 264 void
 265 spatial_dict_writeinfo(struct spatial_dict *dict, FILE *f)
 266 {
 267         /* New file. First, create a comment describing order
 268          * of points in the array. This is just for purposes
 269          * of external tools, Pachi never interprets it itself. */
 270         fprintf(f, "# Pachi spatial patterns dictionary v1.0 maxdist %d\n",
 271                 MAX_PATTERN_DIST);
 272         for (int d = 0; d <= MAX_PATTERN_DIST; d++) {
 273                 fprintf(f, "# Point order: d=%d ", d);
 274                 for (int j = ptind[d]; j < ptind[d + 1]; j++) {
 275                         fprintf(f, "%d,%d ", ptcoords[j].x, ptcoords[j].y);
 276                 }
 277                 fprintf(f, "\n");
 278         }
 279 }
 280
 281 const char *spatial_dict_filename = "patterns.spat";
 282 struct spatial_dict *
 283 spatial_dict_init(bool will_append)
 284 {
 285         FILE *f = fopen(spatial_dict_filename, "r");
 286         if (!f && !will_append) {
 287                 if (DEBUGL(1))
 288                         fprintf(stderr, "No spatial dictionary, will not match spatial pattern features.\n");
 289                 return NULL;
 290         }
 291
 292         struct spatial_dict *dict = calloc(1, sizeof(*dict));
 293         /* We create a dummy record for index 0 that we will
 294          * never reference. This is so that hash value 0 can
 295          * represent "no value". */
 296         struct spatial dummy = { .dist = 0 };
 297         spatial_dict_addc(dict, &dummy);
 298
 299         if (f) {
 300                 spatial_dict_load(dict, f);
 301                 fclose(f); f = NULL;
 302         } else {
 303                 assert(will_append);
 304         }
 305
 306         return dict;
 307 }
 308
 309 int
 310 spatial_dict_put(struct spatial_dict *dict, struct spatial *s, hash_t h)
 311 {
 312         int id = spatial_dict_get(dict, s->dist, h);
 313         if (id > 0) {
 314                 /* Check for collisions in append mode. */
 315                 /* Tough job, we simply try if any other rotation
 316                  * is also covered by the existing record. */
 317                 int r; hash_t rhash; int rid;
 318                 for (r = 1; r < PTH__ROTATIONS; r++) {
 319                         rhash = spatial_hash(r, s);
 320                         rid = dict->hash[rhash];
 321                         if (rid != id)
 322                                 goto collision;
 323                 }
 324                 /* All rotations match, id is good to go! */
 325                 return id;
 326
 327 collision:
 328                 if (DEBUGL(1))
 329                         fprintf(stderr, "Collision %d vs %d (hash %d:%"PRIhash")\n",
 330                                 id, dict->nspatials, r, h);
 331                 id = 0;
 332                 /* dict->collisions++; gets done by addh */
 333         }
 334
 335         /* Add new pattern! */
 336         id = spatial_dict_addc(dict, s);
 337         for (int r = 0; r < PTH__ROTATIONS; r++)
 338                 spatial_dict_addh(dict, spatial_hash(r, s), id);
 339         return id;
 340 }
 341
 342
 343 /** Pattern3 helpers */
 344
 345 /* XXX: We have hard-coded this point order:
 346  * # Point order: d=1 0,0
 347  * # Point order: d=2 0,1 0,-1 1,0 -1,0
 348  * # Point order: d=3 1,1 -1,1 1,-1 -1,-1
 349  */
 350 /* p3bits describe location of given point in the
 351  * pattern3 hash word. */
 352 static const int p3bits[] = { -1,  1, 6, 3, 4,  0, 2, 5, 7 };
 353
 354
 355 static hash_t
 356 pattern3_to_spatial(int pat3)
 357 {
 358         hash_t h = pthashes[0][0][S_NONE];
 359         for (int i = 1; i < 9; i++)
 360                 h ^= pthashes[0][i][(pat3 >> (p3bits[i] * 2)) & 0x3];
 361         return h & spatial_hash_mask;
 362 }
 363
 364 static int
 365 spatial_to_pattern3(struct spatial *s)
 366 {
 367         assert(s->dist == 3);
 368         int pat3 = 0;
 369         for (int i = 1; i < 9; i++)
 370                 pat3 |= spatial_point_at(*s, i) << (p3bits[i] * 2);
 371         return pat3;
 372 }
 373
 374 int
 375 pattern3_by_spatial(struct spatial_dict *dict, int pat3)
 376 {
 377         /* Just pull pat3 through the spatial database to generate
 378          * hash of its canonical form. */
 379         hash_t h = pattern3_to_spatial(pat3);
 380         int s = spatial_dict_get(dict, 3, h);
 381         /* XXX: We assume our spatial dictionary is _sane_, that is,
 382          * all valid 3x3 patterns we could encounter are in the
 383          * dictionary. If you hit this assert(), you probably
 384          * generated the spatial dict over too few games; it is best
 385          * to generate it over the same set of games as you match
 386          * patterns on afterwards. */
 387         assert(s > 0);
 388         return spatial_to_pattern3(&dict->spatials[s]);
 389 }