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 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 hash_t pthboard
[MAX_PATTERN_AREA
][4];
92 int pthbc
= MAX_PATTERN_AREA
/ 2; // tengen coord
94 /* The magic numbers are tuned for minimal collisions. */
95 hash_t h1
= 0xd6d6d6d1;
96 hash_t h2
= 0xd6d6d6d2;
97 hash_t h3
= 0xd6d6d6d3;
98 hash_t h4
= 0xd6d6d6d4;
99 for (int i
= 0; i
< MAX_PATTERN_AREA
; i
++) {
100 pthboard
[i
][S_NONE
] = (h1
= h1
* 16787);
101 pthboard
[i
][S_BLACK
] = (h2
= h2
* 16823);
102 pthboard
[i
][S_WHITE
] = (h3
= h3
* 16811 - 13);
103 pthboard
[i
][S_OFFBOARD
] = (h4
= h4
* 16811);
106 /* Virtual board with hashes created, now fill
107 * pthashes[] with hashes for points in actual
108 * sequences, also considering various rotations. */
109 #define PTH_VMIRROR 1
110 #define PTH_HMIRROR 2
112 for (int r
= 0; r
< PTH__ROTATIONS
; r
++) {
113 for (int i
= 0; i
< MAX_PATTERN_AREA
; i
++) {
114 /* Rotate appropriately. */
115 int rx
= ptcoords
[i
].x
;
116 int ry
= ptcoords
[i
].y
;
117 if (r
& PTH_VMIRROR
) ry
= -ry
;
118 if (r
& PTH_HMIRROR
) rx
= -rx
;
120 int rs
= rx
; rx
= -ry
; ry
= rs
;
122 int bi
= pthbc
+ ry
* MAX_PATTERN_DIST
+ rx
;
125 pthashes
[r
][i
][S_NONE
] = pthboard
[bi
][S_NONE
];
126 pthashes
[r
][i
][S_BLACK
] = pthboard
[bi
][S_BLACK
];
127 pthashes
[r
][i
][S_WHITE
] = pthboard
[bi
][S_WHITE
];
128 pthashes
[r
][i
][S_OFFBOARD
] = pthboard
[bi
][S_OFFBOARD
];
133 static void __attribute__((constructor
))
136 /* Initialization of various static data structures for
137 * fast pattern processing. */
143 spatial_hash(int rotation
, struct spatial
*s
)
146 for (int i
= 0; i
< ptind
[s
->dist
+ 1]; i
++) {
147 h
^= pthashes
[rotation
][i
][spatial_point_at(*s
, i
)];
149 return h
& spatial_hash_mask
;
153 spatial2str(struct spatial
*s
)
155 static char buf
[1024];
156 for (int i
= 0; i
< ptind
[s
->dist
+ 1]; i
++) {
157 buf
[i
] = stone2char(spatial_point_at(*s
, i
));
159 buf
[ptind
[s
->dist
+ 1]] = 0;
164 spatial_from_board(struct pattern_config
*pc
, struct spatial
*s
,
165 struct board
*b
, struct move
*m
)
167 assert(pc
->spat_min
> 0);
169 /* We record all spatial patterns black-to-play; simply
170 * reverse all colors if we are white-to-play. */
171 static enum stone bt_black
[4] = { S_NONE
, S_BLACK
, S_WHITE
, S_OFFBOARD
};
172 static enum stone bt_white
[4] = { S_NONE
, S_WHITE
, S_BLACK
, S_OFFBOARD
};
173 enum stone (*bt
)[4] = m
->color
== S_WHITE
? &bt_white
: &bt_black
;
175 memset(s
, 0, sizeof(*s
));
176 for (int j
= 0; j
< ptind
[pc
->spat_max
+ 1]; j
++) {
177 ptcoords_at(x
, y
, m
->coord
, b
, j
);
178 s
->points
[j
/ 4] |= (*bt
)[board_atxy(b
, x
, y
)] << ((j
% 4) * 2);
180 s
->dist
= pc
->spat_max
;
183 /* Compare two spatials, allowing for differences up to isomorphism.
184 * True means the spatials are equivalent. */
186 spatial_cmp(struct spatial
*s1
, struct spatial
*s2
)
188 /* Quick preliminary check. */
189 if (s1
->dist
!= s2
->dist
)
192 /* We could create complex transposition tables, but it seems most
193 * foolproof to just check if the sets of rotation hashes are the
195 hash_t s1r
[PTH__ROTATIONS
];
196 for (int r
= 0; r
< PTH__ROTATIONS
; r
++)
197 s1r
[r
] = spatial_hash(r
, s1
);
198 for (int r
= 0; r
< PTH__ROTATIONS
; r
++) {
199 hash_t s2r
= spatial_hash(r
, s2
);
200 for (int p
= 0; p
< PTH__ROTATIONS
; p
++)
203 /* Rotation hash s2r does not correspond to s1r. */
208 /* All rotation hashes of s2 occur in s1. Hopefully that
209 * indicates something. */
214 /* Spatial dict manipulation. */
217 spatial_dict_addc(struct spatial_dict
*dict
, struct spatial
*s
)
219 /* Allocate space in 1024 blocks. */
220 #define SPATIALS_ALLOC 1024
221 if (!(dict
->nspatials
% SPATIALS_ALLOC
)) {
222 dict
->spatials
= realloc(dict
->spatials
,
223 (dict
->nspatials
+ SPATIALS_ALLOC
)
224 * sizeof(*dict
->spatials
));
226 dict
->spatials
[dict
->nspatials
] = *s
;
227 return dict
->nspatials
++;
231 spatial_dict_addh(struct spatial_dict
*dict
, hash_t hash
, unsigned int id
)
233 if (dict
->hash
[hash
] && dict
->hash
[hash
] != id
)
235 dict
->hash
[hash
] = id
;
239 /* Spatial dictionary file format:
241 * INDEX RADIUS STONES HASH...
242 * INDEX: index in the spatial table
243 * RADIUS: @d of the pattern
244 * STONES: string of ".XO#" chars
245 * HASH...: space-separated 18bit hash-table indices for the pattern */
248 spatial_dict_read(struct spatial_dict
*dict
, char *buf
)
250 /* XXX: We trust the data. Bad data will crash us. */
254 index
= strtol(bufp
, &bufp
, 10);
255 radius
= strtol(bufp
, &bufp
, 10);
256 while (isspace(*bufp
)) bufp
++;
258 /* Load the stone configuration. */
259 struct spatial s
= { .dist
= radius
};
261 while (!isspace(*bufp
)) {
262 s
.points
[sl
/ 4] |= char2stone(*bufp
++) << ((sl
% 4)*2);
265 while (isspace(*bufp
)) bufp
++;
268 if (sl
!= ptind
[s
.dist
+ 1]) {
269 fprintf(stderr
, "Spatial dictionary: Invalid number of stones (%d != %d) on this line: %s\n",
270 sl
, ptind
[radius
+ 1] - 1, buf
);
274 /* Add to collection. */
275 unsigned int id
= spatial_dict_addc(dict
, &s
);
277 /* Add to specified hash places. */
278 for (int r
= 0; r
< PTH__ROTATIONS
; r
++)
279 spatial_dict_addh(dict
, spatial_hash(r
, &s
), id
);
283 spatial_write(struct spatial_dict
*dict
, struct spatial
*s
, int id
, FILE *f
)
285 fprintf(f
, "%d %d ", id
, s
->dist
);
286 fputs(spatial2str(s
), f
);
287 for (int r
= 0; r
< PTH__ROTATIONS
; r
++) {
288 hash_t rhash
= spatial_hash(r
, s
);
289 int id2
= dict
->hash
[rhash
];
291 /* This hash does not belong to us. Decide whether
292 * we or the current owner is better owner. */
293 /* TODO: Compare also # of patternscan encounters? */
294 struct spatial
*s2
= &dict
->spatials
[id2
];
295 if (s2
->dist
< s
->dist
)
297 if (s2
->dist
== s
->dist
&& id2
< id
)
300 fprintf(f
, " %"PRIhash
"", spatial_hash(r
, s
));
306 spatial_dict_load(struct spatial_dict
*dict
, FILE *f
)
309 while (fgets(buf
, sizeof(buf
), f
)) {
310 if (buf
[0] == '#') continue;
311 spatial_dict_read(dict
, buf
);
314 fprintf(stderr
, "Loaded spatial dictionary of %d patterns (hash: %d coll., %d effective, %.2f%% fill rate).\n",
315 dict
->nspatials
, dict
->collisions
, dict
->collisions
/ PTH__ROTATIONS
,
316 (double) dict
->nspatials
* 100 / (sizeof(dict
->hash
) / sizeof(dict
->hash
[0])));
320 spatial_dict_writeinfo(struct spatial_dict
*dict
, FILE *f
)
322 /* New file. First, create a comment describing order
323 * of points in the array. This is just for purposes
324 * of external tools, Pachi never interprets it itself. */
325 fprintf(f
, "# Pachi spatial patterns dictionary v1.0 maxdist %d\n",
327 for (int d
= 0; d
<= MAX_PATTERN_DIST
; d
++) {
328 fprintf(f
, "# Point order: d=%d ", d
);
329 for (int j
= ptind
[d
]; j
< ptind
[d
+ 1]; j
++) {
330 fprintf(f
, "%d,%d ", ptcoords
[j
].x
, ptcoords
[j
].y
);
336 const char *spatial_dict_filename
= "patterns.spat";
337 struct spatial_dict
*
338 spatial_dict_init(bool will_append
)
340 FILE *f
= fopen(spatial_dict_filename
, "r");
341 if (!f
&& !will_append
) {
343 fprintf(stderr
, "No spatial dictionary, will not match spatial pattern features.\n");
347 struct spatial_dict
*dict
= calloc2(1, sizeof(*dict
));
348 /* We create a dummy record for index 0 that we will
349 * never reference. This is so that hash value 0 can
350 * represent "no value". */
351 struct spatial dummy
= { .dist
= 0 };
352 spatial_dict_addc(dict
, &dummy
);
355 spatial_dict_load(dict
, f
);
365 spatial_dict_put(struct spatial_dict
*dict
, struct spatial
*s
, hash_t h
)
367 /* We avoid spatial_dict_get() here, since we want to ignore radius
368 * differences - we have custom collision detection. */
369 int id
= dict
->hash
[h
];
371 /* Is this the same or isomorphous spatial? */
372 if (spatial_cmp(s
, &dict
->spatials
[id
]))
375 /* Look a bit harder - perhaps one of our rotations still
376 * points at the correct spatial. */
377 for (int r
= 0; r
< PTH__ROTATIONS
; r
++) {
378 hash_t rhash
= spatial_hash(r
, s
);
379 int rid
= dict
->hash
[rhash
];
380 /* No match means we definitely aren't stored yet. */
383 if (id
!= rid
&& spatial_cmp(s
, &dict
->spatials
[rid
])) {
384 /* Yay, this is us! */
386 fprintf(stderr
, "Repeated collision %d vs %d\n", id
, rid
);
388 /* Point the hashes back to us. */
394 fprintf(stderr
, "Collision %d vs %d\n", id
, dict
->nspatials
);
396 /* dict->collisions++; gets done by addh */
399 /* Add new pattern! */
400 id
= spatial_dict_addc(dict
, s
);
402 fprintf(stderr
, "new spat %d(%d) %s <%"PRIhash
"> ", id
, s
->dist
, spatial2str(s
), h
);
403 for (int r
= 0; r
< 8; r
++)
404 fprintf(stderr
,"[%"PRIhash
"] ", spatial_hash(r
, s
));
405 fprintf(stderr
, "\n");
408 /* Store new pattern in the hash. */
410 for (int r
= 0; r
< PTH__ROTATIONS
; r
++)
411 spatial_dict_addh(dict
, spatial_hash(r
, s
), id
);