11 #include "patternsp.h"
13 /* Mapping from point sequence to coordinate offsets (to determine
14 * coordinates relative to pattern center). The array is ordered
15 * in the gridcular metric order so that we can go through it
16 * and incrementally match spatial features in nested circles.
17 * Within one circle, coordinates are ordered by rows to keep
18 * good cache behavior. */
19 struct ptcoord ptcoords
[MAX_PATTERN_AREA
];
21 /* For each radius, starting index in ptcoords[]. */
22 unsigned int ptind
[MAX_PATTERN_DIST
+ 2];
24 /* ptcoords[], ptind[] setup */
28 int i
= 0; /* Indexing ptcoords[] */
30 /* First, center point. */
31 ptind
[0] = ptind
[1] = 0;
32 ptcoords
[i
].x
= ptcoords
[i
].y
= 0; i
++;
34 for (int d
= 2; d
<= MAX_PATTERN_DIST
; d
++) {
36 /* For each y, examine all integer solutions
37 * of d = |x| + |y| + max(|x|, |y|). */
38 /* TODO: (Stern, 2006) uses a hand-modified
39 * circles that are finer for small d and more
40 * coarse for large d. */
41 for (short y
= d
/ 2; y
>= 0; y
--) {
44 /* max(|x|, |y|) = |y|, non-zero x */
46 if (x
+ y
* 2 != d
) continue;
48 /* max(|x|, |y|) = |x| */
49 /* Or, max(|x|, |y|) = |y| and x is zero */
51 if (x
* 2 + y
!= d
) continue;
54 assert((x
> y
? x
: y
) + x
+ y
== d
);
56 ptcoords
[i
].x
= x
; ptcoords
[i
].y
= y
; i
++;
57 if (x
!= 0) { ptcoords
[i
].x
= -x
; ptcoords
[i
].y
= y
; i
++; }
58 if (y
!= 0) { ptcoords
[i
].x
= x
; ptcoords
[i
].y
= -y
; i
++; }
59 if (x
!= 0 && y
!= 0) { ptcoords
[i
].x
= -x
; ptcoords
[i
].y
= -y
; i
++; }
62 ptind
[MAX_PATTERN_DIST
+ 1] = i
;
65 for (int d
= 0; d
<= MAX_PATTERN_DIST
; d
++) {
66 fprintf(stderr
, "d=%d (%d) ", d
, ptind
[d
]);
67 for (int j
= ptind
[d
]; j
< ptind
[d
+ 1]; j
++) {
68 fprintf(stderr
, "%d,%d ", ptcoords
[j
].x
, ptcoords
[j
].y
);
70 fprintf(stderr
, "\n");
76 /* Zobrist hashes used for points in patterns. */
77 hash_t pthashes
[PTH__ROTATIONS
][MAX_PATTERN_AREA
][S_MAX
];
82 /* We need fixed hashes for all pattern-relative in
83 * all pattern users! This is a simple way to generate
84 * hopefully good ones. Park-Miller powa. :) */
86 /* We create a virtual board (centered at the sequence start),
87 * plant the hashes there, then pick them up into the sequence
88 * with correct coordinates. It would be possible to generate
89 * the sequence point hashes directly, but the rotations would
90 * make for enormous headaches. */
91 #define PATTERN_BOARD_SIZE ((MAX_PATTERN_DIST + 1) * (MAX_PATTERN_DIST + 1))
92 hash_t pthboard
[PATTERN_BOARD_SIZE
][4];
93 int pthbc
= PATTERN_BOARD_SIZE
/ 2; // tengen coord
95 /* The magic numbers are tuned for minimal collisions. */
96 hash_t h1
= 0xd6d6d6d1;
97 hash_t h2
= 0xd6d6d6d2;
98 hash_t h3
= 0xd6d6d6d3;
99 hash_t h4
= 0xd6d6d6d4;
101 /* TODO: Uncomment this version the next time we are regenerating
102 * our pattern base. It should result in less collisions. */
103 for (int i
= 1; i
< PATTERN_BOARD_SIZE
; i
++) {
104 pthboard
[i
][S_NONE
] = (h1
= h1
* 16787);
105 pthboard
[i
][S_BLACK
] = (h2
= h2
* 16823);
106 pthboard
[i
][S_WHITE
] = (h3
= h3
* 16811 - 13);
107 pthboard
[i
][S_OFFBOARD
] = (h4
= h4
* 16811);
110 for (int i
= 1; i
< PATTERN_BOARD_SIZE
; i
++) {
112 pthboard
[i
][S_NONE
] = (pthboard
[i
][S_NONE
] >> (hs
% 64)) | (pthboard
[i
][S_NONE
] << (64 - hs
% 64));
114 pthboard
[i
][S_BLACK
] = (pthboard
[i
][S_BLACK
] >> (hs
% 64)) | (pthboard
[i
][S_BLACK
] << (64 - hs
% 64));
116 pthboard
[i
][S_WHITE
] = (pthboard
[i
][S_WHITE
] >> (hs
% 64)) | (pthboard
[i
][S_WHITE
] << (64 - hs
% 64));
118 pthboard
[i
][S_OFFBOARD
] = (pthboard
[i
][S_OFFBOARD
] >> (hs
% 64)) | (pthboard
[i
][S_OFFBOARD
] << (64 - hs
% 64));
121 for (int i
= 0; i
< PATTERN_BOARD_SIZE
; i
++) {
122 pthboard
[i
][S_NONE
] = (h1
= h1
* 16787);
123 pthboard
[i
][S_BLACK
] = (h2
= h2
* 16823);
124 pthboard
[i
][S_WHITE
] = (h3
= h3
* 16811 - 13);
125 pthboard
[i
][S_OFFBOARD
] = (h4
= h4
* 16811);
129 /* Virtual board with hashes created, now fill
130 * pthashes[] with hashes for points in actual
131 * sequences, also considering various rotations. */
132 #define PTH_VMIRROR 1
133 #define PTH_HMIRROR 2
135 for (int r
= 0; r
< PTH__ROTATIONS
; r
++) {
136 for (int i
= 0; i
< MAX_PATTERN_AREA
; i
++) {
137 /* Rotate appropriately. */
138 int rx
= ptcoords
[i
].x
;
139 int ry
= ptcoords
[i
].y
;
140 if (r
& PTH_VMIRROR
) ry
= -ry
;
141 if (r
& PTH_HMIRROR
) rx
= -rx
;
143 int rs
= rx
; rx
= -ry
; ry
= rs
;
145 int bi
= pthbc
+ ry
* (MAX_PATTERN_DIST
+ 1) + rx
;
148 pthashes
[r
][i
][S_NONE
] = pthboard
[bi
][S_NONE
];
149 pthashes
[r
][i
][S_BLACK
] = pthboard
[bi
][S_BLACK
];
150 pthashes
[r
][i
][S_WHITE
] = pthboard
[bi
][S_WHITE
];
151 pthashes
[r
][i
][S_OFFBOARD
] = pthboard
[bi
][S_OFFBOARD
];
156 static void __attribute__((constructor
))
159 /* Initialization of various static data structures for
160 * fast pattern processing. */
166 spatial_hash(unsigned int rotation
, struct spatial
*s
)
169 for (unsigned int i
= 0; i
< ptind
[s
->dist
+ 1]; i
++) {
170 h
^= pthashes
[rotation
][i
][spatial_point_at(*s
, i
)];
172 return h
& spatial_hash_mask
;
176 spatial2str(struct spatial
*s
)
178 static char buf
[1024];
179 for (unsigned int i
= 0; i
< ptind
[s
->dist
+ 1]; i
++) {
180 buf
[i
] = stone2char(spatial_point_at(*s
, i
));
182 buf
[ptind
[s
->dist
+ 1]] = 0;
187 spatial_from_board(struct pattern_config
*pc
, struct spatial
*s
,
188 struct board
*b
, struct move
*m
)
190 assert(pc
->spat_min
> 0);
192 /* We record all spatial patterns black-to-play; simply
193 * reverse all colors if we are white-to-play. */
194 static enum stone bt_black
[4] = { S_NONE
, S_BLACK
, S_WHITE
, S_OFFBOARD
};
195 static enum stone bt_white
[4] = { S_NONE
, S_WHITE
, S_BLACK
, S_OFFBOARD
};
196 enum stone (*bt
)[4] = m
->color
== S_WHITE
? &bt_white
: &bt_black
;
198 memset(s
, 0, sizeof(*s
));
199 for (unsigned int j
= 0; j
< ptind
[pc
->spat_max
+ 1]; j
++) {
200 ptcoords_at(x
, y
, m
->coord
, b
, j
);
201 s
->points
[j
/ 4] |= (*bt
)[board_atxy(b
, x
, y
)] << ((j
% 4) * 2);
203 s
->dist
= pc
->spat_max
;
206 /* Compare two spatials, allowing for differences up to isomorphism.
207 * True means the spatials are equivalent. */
209 spatial_cmp(struct spatial
*s1
, struct spatial
*s2
)
211 /* Quick preliminary check. */
212 if (s1
->dist
!= s2
->dist
)
215 /* We could create complex transposition tables, but it seems most
216 * foolproof to just check if the sets of rotation hashes are the
218 hash_t s1r
[PTH__ROTATIONS
];
219 for (unsigned int r
= 0; r
< PTH__ROTATIONS
; r
++)
220 s1r
[r
] = spatial_hash(r
, s1
);
221 for (unsigned int r
= 0; r
< PTH__ROTATIONS
; r
++) {
222 hash_t s2r
= spatial_hash(r
, s2
);
223 for (unsigned int p
= 0; p
< PTH__ROTATIONS
; p
++)
226 /* Rotation hash s2r does not correspond to s1r. */
231 /* All rotation hashes of s2 occur in s1. Hopefully that
232 * indicates something. */
237 /* Spatial dict manipulation. */
240 spatial_dict_addc(struct spatial_dict
*dict
, struct spatial
*s
)
242 /* Allocate space in 1024 blocks. */
243 #define SPATIALS_ALLOC 1024
244 if (!(dict
->nspatials
% SPATIALS_ALLOC
)) {
245 dict
->spatials
= realloc(dict
->spatials
,
246 (dict
->nspatials
+ SPATIALS_ALLOC
)
247 * sizeof(*dict
->spatials
));
249 dict
->spatials
[dict
->nspatials
] = *s
;
250 return dict
->nspatials
++;
254 spatial_dict_addh(struct spatial_dict
*dict
, hash_t hash
, unsigned int id
)
256 if (dict
->hash
[hash
]) {
257 if (dict
->hash
[hash
] != id
)
262 dict
->hash
[hash
] = id
;
266 /* Spatial dictionary file format:
268 * INDEX RADIUS STONES HASH...
269 * INDEX: index in the spatial table
270 * RADIUS: @d of the pattern
271 * STONES: string of ".XO#" chars
272 * HASH...: space-separated 18bit hash-table indices for the pattern */
275 spatial_dict_read(struct spatial_dict
*dict
, char *buf
, bool hash
)
277 /* XXX: We trust the data. Bad data will crash us. */
280 unsigned int index
, radius
;
281 index
= strtoul(bufp
, &bufp
, 10);
282 radius
= strtoul(bufp
, &bufp
, 10);
283 while (isspace(*bufp
)) bufp
++;
285 if (radius
> MAX_PATTERN_DIST
) {
286 /* Too large spatial, skip. */
287 struct spatial s
= { .dist
= 0 };
288 unsigned int id
= spatial_dict_addc(dict
, &s
);
293 /* Load the stone configuration. */
294 struct spatial s
= { .dist
= radius
};
296 while (!isspace(*bufp
)) {
297 s
.points
[sl
/ 4] |= char2stone(*bufp
++) << ((sl
% 4)*2);
300 while (isspace(*bufp
)) bufp
++;
303 if (sl
!= ptind
[s
.dist
+ 1]) {
304 fprintf(stderr
, "Spatial dictionary: Invalid number of stones (%d != %d) on this line: %s\n",
305 sl
, ptind
[radius
+ 1] - 1, buf
);
309 /* Add to collection. */
310 unsigned int id
= spatial_dict_addc(dict
, &s
);
313 /* Add to specified hash places. */
315 for (unsigned int r
= 0; r
< PTH__ROTATIONS
; r
++)
316 spatial_dict_addh(dict
, spatial_hash(r
, &s
), id
);
320 spatial_write(struct spatial_dict
*dict
, struct spatial
*s
, unsigned int id
, FILE *f
)
322 fprintf(f
, "%d %d ", id
, s
->dist
);
323 fputs(spatial2str(s
), f
);
324 for (unsigned int r
= 0; r
< PTH__ROTATIONS
; r
++) {
325 hash_t rhash
= spatial_hash(r
, s
);
326 unsigned int id2
= dict
->hash
[rhash
];
328 /* This hash does not belong to us. Decide whether
329 * we or the current owner is better owner. */
330 /* TODO: Compare also # of patternscan encounters? */
331 struct spatial
*s2
= &dict
->spatials
[id2
];
332 if (s2
->dist
< s
->dist
)
334 if (s2
->dist
== s
->dist
&& id2
< id
)
337 fprintf(f
, " %"PRIhash
"", spatial_hash(r
, s
));
343 spatial_dict_load(struct spatial_dict
*dict
, FILE *f
, bool hash
)
346 while (fgets(buf
, sizeof(buf
), f
)) {
347 if (buf
[0] == '#') continue;
348 spatial_dict_read(dict
, buf
, hash
);
351 fprintf(stderr
, "Loaded spatial dictionary of %d patterns.\n", dict
->nspatials
);
353 spatial_dict_hashstats(dict
);
358 spatial_dict_hashstats(struct spatial_dict
*dict
)
360 /* m hash size, n number of patterns; is zobrist universal hash?
362 * Not so rigorous analysis, but it should give a good approximation:
363 * Probability of empty bucket is (1-1/m)^n ~ e^(-n/m)
364 * Probability of non-empty bucket is 1-e^(-n/m)
365 * Expected number of non-empty buckets is m*(1-e^(-n/m))
366 * Number of collisions is n-m*(1-e^(-n/m)). */
368 /* The result: Reality matches these expectations pretty well!
371 * Loaded spatial dictionary of 1064482 patterns.
372 * (Spatial dictionary hash: 513997 collisions (incl. repetitions), 11.88% (7970033/67108864) fill rate).
376 * n <= 8*1064482 (some patterns may have some identical rotations)
377 * n = 513997+7970033 = 8484030 should be the correct number
378 * n-m*(1-e^(-n/m)) = 514381
380 * To verify, make sure to turn patternprob off (e.g. use
381 * -e patternscan), since it will insert a pattern multiple times,
382 * multiplying the reported number of collisions. */
384 unsigned long buckets
= (sizeof(dict
->hash
) / sizeof(dict
->hash
[0]));
385 fprintf(stderr
, "\t(Spatial dictionary hash: %d collisions (incl. repetitions), %.2f%% (%d/%lu) fill rate).\n",
387 (double) dict
->fills
* 100 / buckets
,
388 dict
->fills
, buckets
);
392 spatial_dict_writeinfo(struct spatial_dict
*dict
, FILE *f
)
394 /* New file. First, create a comment describing order
395 * of points in the array. This is just for purposes
396 * of external tools, Pachi never interprets it itself. */
397 fprintf(f
, "# Pachi spatial patterns dictionary v1.0 maxdist %d\n",
399 for (unsigned int d
= 0; d
<= MAX_PATTERN_DIST
; d
++) {
400 fprintf(f
, "# Point order: d=%d ", d
);
401 for (unsigned int j
= ptind
[d
]; j
< ptind
[d
+ 1]; j
++) {
402 fprintf(f
, "%d,%d ", ptcoords
[j
].x
, ptcoords
[j
].y
);
408 /* We try to avoid needlessly reloading spatial dictionary
409 * since it may take rather long time. */
410 static struct spatial_dict
*cached_dict
;
412 const char *spatial_dict_filename
= "patterns.spat";
413 struct spatial_dict
*
414 spatial_dict_init(bool will_append
, bool hash
)
416 if (cached_dict
&& !will_append
)
419 FILE *f
= fopen(spatial_dict_filename
, "r");
420 if (!f
&& !will_append
) {
422 fprintf(stderr
, "No spatial dictionary, will not match spatial pattern features.\n");
426 struct spatial_dict
*dict
= calloc2(1, sizeof(*dict
));
427 /* We create a dummy record for index 0 that we will
428 * never reference. This is so that hash value 0 can
429 * represent "no value". */
430 struct spatial dummy
= { .dist
= 0 };
431 spatial_dict_addc(dict
, &dummy
);
434 spatial_dict_load(dict
, f
, hash
);
445 spatial_dict_put(struct spatial_dict
*dict
, struct spatial
*s
, hash_t h
)
447 /* We avoid spatial_dict_get() here, since we want to ignore radius
448 * differences - we have custom collision detection. */
449 unsigned int id
= dict
->hash
[h
];
451 /* Is this the same or isomorphous spatial? */
452 if (spatial_cmp(s
, &dict
->spatials
[id
]))
455 /* Look a bit harder - perhaps one of our rotations still
456 * points at the correct spatial. */
457 for (unsigned int r
= 0; r
< PTH__ROTATIONS
; r
++) {
458 hash_t rhash
= spatial_hash(r
, s
);
459 unsigned int rid
= dict
->hash
[rhash
];
460 /* No match means we definitely aren't stored yet. */
463 if (id
!= rid
&& spatial_cmp(s
, &dict
->spatials
[rid
])) {
464 /* Yay, this is us! */
466 fprintf(stderr
, "Repeated collision %d vs %d\n", id
, rid
);
468 /* Point the hashes back to us. */
474 fprintf(stderr
, "Collision %d vs %d\n", id
, dict
->nspatials
);
476 /* dict->collisions++; gets done by addh */
479 /* Add new pattern! */
480 id
= spatial_dict_addc(dict
, s
);
482 fprintf(stderr
, "new spat %d(%d) %s <%"PRIhash
"> ", id
, s
->dist
, spatial2str(s
), h
);
483 for (unsigned int r
= 0; r
< 8; r
++)
484 fprintf(stderr
,"[%"PRIhash
"] ", spatial_hash(r
, s
));
485 fprintf(stderr
, "\n");
488 /* Store new pattern in the hash. */
490 for (unsigned int r
= 0; r
< PTH__ROTATIONS
; r
++)
491 spatial_dict_addh(dict
, spatial_hash(r
, s
), id
);