11 #include "patternsp.h"
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
];
23 /* For each radius, starting index in ptcoords[]. */
24 int ptind
[MAX_PATTERN_DIST
+ 2];
26 /* ptcoords[], ptind[] setup */
27 static void __attribute__((constructor
))
30 int i
= 0; /* Indexing ptcoords[] */
32 /* First, center point. */
33 ptind
[0] = ptind
[1] = 0;
34 ptcoords
[i
].x
= ptcoords
[i
].y
= 0; i
++;
36 for (int d
= 2; d
<= MAX_PATTERN_DIST
; d
++) {
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
--) {
45 /* max(|x|, |y|) = |y|, non-zero x */
47 if (x
+ y
* 2 != d
) continue;
49 /* max(|x|, |y|) = |x| */
50 /* Or, max(|x|, |y|) = |y| and x is zero */
52 if (x
* 2 + y
!= d
) continue;
55 assert((x
> y
? x
: y
) + x
+ y
== d
);
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
++; }
63 ptind
[MAX_PATTERN_DIST
+ 1] = i
;
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
);
71 fprintf(stderr
, "\n");
77 /* Zobrist hashes used for points in patterns. */
78 hash_t pthashes
[PTH__ROTATIONS
][MAX_PATTERN_AREA
][S_MAX
];
80 static void __attribute__((constructor
))
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. :) */
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
95 /* The magic numbers are tuned for minimal collisions. */
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);
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
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
;
118 int rs
= rx
; rx
= -ry
; ry
= rs
;
120 int bi
= pthbc
+ ry
* MAX_PATTERN_DIST
+ rx
;
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
];
132 spatial_hash(int rotation
, struct spatial
*s
)
135 for (int i
= 0; i
< ptind
[s
->dist
+ 1]; i
++) {
136 h
^= pthashes
[rotation
][i
][spatial_point_at(*s
, i
)];
138 return h
& spatial_hash_mask
;
142 spatial2str(struct spatial
*s
)
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
));
148 buf
[ptind
[s
->dist
+ 1]] = 0;
153 spatial_from_board(struct pattern_config
*pc
, struct spatial
*s
,
154 struct board
*b
, struct move
*m
)
156 assert(pc
->spat_min
> 0);
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
;
164 memset(s
, 0, sizeof(*s
));
165 for (int j
= 0; j
< ptind
[pc
->spat_max
+ 1]; j
++) {
166 int x
= coord_x(m
->coord
, b
) + ptcoords
[j
].x
;
167 int y
= coord_y(m
->coord
, b
) + ptcoords
[j
].y
;
168 if (x
>= board_size(b
)) x
= board_size(b
) - 1; else if (x
< 0) x
= 0;
169 if (y
>= board_size(b
)) y
= board_size(b
) - 1; else if (y
< 0) y
= 0;
170 s
->points
[j
/ 4] |= (*bt
)[board_atxy(b
, x
, y
)] << ((j
% 4) * 2);
172 s
->dist
= pc
->spat_max
;
176 /* Spatial dict manipulation. */
179 spatial_dict_addc(struct spatial_dict
*dict
, struct spatial
*s
)
181 /* Allocate space in 1024 blocks. */
182 #define SPATIALS_ALLOC 1024
183 if (!(dict
->nspatials
% SPATIALS_ALLOC
)) {
184 dict
->spatials
= realloc(dict
->spatials
,
185 (dict
->nspatials
+ SPATIALS_ALLOC
)
186 * sizeof(*dict
->spatials
));
188 dict
->spatials
[dict
->nspatials
] = *s
;
189 return dict
->nspatials
++;
193 spatial_dict_addh(struct spatial_dict
*dict
, hash_t hash
, int id
)
195 if (dict
->hash
[hash
]) {
197 /* Give up, not worth the trouble. */
200 dict
->hash
[hash
] = id
;
204 /* Spatial dictionary file format:
206 * INDEX RADIUS STONES HASH...
207 * INDEX: index in the spatial table
208 * RADIUS: @d of the pattern
209 * STONES: string of ".XO#" chars
210 * HASH...: space-separated 18bit hash-table indices for the pattern */
213 spatial_dict_read(struct spatial_dict
*dict
, char *buf
)
215 /* XXX: We trust the data. Bad data will crash us. */
219 index
= strtol(bufp
, &bufp
, 10);
220 radius
= strtol(bufp
, &bufp
, 10);
221 while (isspace(*bufp
)) bufp
++;
223 /* Load the stone configuration. */
224 struct spatial s
= { .dist
= radius
};
226 while (!isspace(*bufp
)) {
227 s
.points
[sl
/ 4] |= char2stone(*bufp
++) << (sl
% 4);
230 while (isspace(*bufp
)) bufp
++;
233 if (sl
!= ptind
[s
.dist
+ 1]) {
234 fprintf(stderr
, "Spatial dictionary: Invalid number of stones (%d != %d) on this line: %s\n",
235 sl
, ptind
[radius
+ 1] - 1, buf
);
239 /* Add to collection. */
240 int id
= spatial_dict_addc(dict
, &s
);
242 /* Add to specified hash places. */
244 int hash
= strtol(bufp
, &bufp
, 16);
245 while (isspace(*bufp
)) bufp
++;
246 spatial_dict_addh(dict
, hash
& spatial_hash_mask
, id
);
251 spatial_write(struct spatial
*s
, int id
, FILE *f
)
253 fprintf(f
, "%d %d ", id
, s
->dist
);
254 fputs(spatial2str(s
), f
);
255 for (int r
= 0; r
< PTH__ROTATIONS
; r
++)
256 fprintf(f
, " %"PRIhash
"", spatial_hash(r
, s
));
261 spatial_dict_load(struct spatial_dict
*dict
, FILE *f
)
264 while (fgets(buf
, sizeof(buf
), f
)) {
265 if (buf
[0] == '#') continue;
266 spatial_dict_read(dict
, buf
);
271 spatial_dict_writeinfo(struct spatial_dict
*dict
, FILE *f
)
273 /* New file. First, create a comment describing order
274 * of points in the array. This is just for purposes
275 * of external tools, Pachi never interprets it itself. */
276 fprintf(f
, "# Pachi spatial patterns dictionary v1.0 maxdist %d\n",
278 for (int d
= 0; d
<= MAX_PATTERN_DIST
; d
++) {
279 fprintf(f
, "# Point order: d=%d ", d
);
280 for (int j
= ptind
[d
]; j
< ptind
[d
+ 1]; j
++) {
281 fprintf(f
, "%d,%d ", ptcoords
[j
].x
, ptcoords
[j
].y
);
287 const char *spatial_dict_filename
= "patterns.spat";
288 struct spatial_dict
*
289 spatial_dict_init(bool will_append
)
291 FILE *f
= fopen(spatial_dict_filename
, "r");
292 if (!f
&& !will_append
) {
294 fprintf(stderr
, "No spatial dictionary, will not match spatial pattern features.\n");
298 struct spatial_dict
*dict
= calloc(1, sizeof(*dict
));
299 /* We create a dummy record for index 0 that we will
300 * never reference. This is so that hash value 0 can
301 * represent "no value". */
302 struct spatial dummy
= { .dist
= 0 };
303 spatial_dict_addc(dict
, &dummy
);
306 spatial_dict_load(dict
, f
);
316 spatial_dict_get(struct spatial_dict
*dict
, int dist
, hash_t hash
)
318 int id
= dict
->hash
[hash
];
319 if (id
&& dict
->spatials
[id
].dist
!= dist
) {
321 fprintf(stderr
, "Collision dist %d vs %d (hash [%d]%"PRIhash
")\n",
322 dist
, dict
->spatials
[id
].dist
, id
, hash
);
329 spatial_dict_put(struct spatial_dict
*dict
, struct spatial
*s
, hash_t h
)
331 int id
= spatial_dict_get(dict
, s
->dist
, h
);
333 /* Check for collisions in append mode. */
334 /* Tough job, we simply try if any other rotation
335 * is also covered by the existing record. */
336 int r
; hash_t rhash
; int rid
;
337 for (r
= 1; r
< PTH__ROTATIONS
; r
++) {
338 rhash
= spatial_hash(r
, s
);
339 rid
= dict
->hash
[rhash
];
343 /* All rotations match, id is good to go! */
348 fprintf(stderr
, "Collision %d vs %d (hash %d:%"PRIhash
")\n",
349 id
, dict
->nspatials
, r
, h
);
351 /* dict->collisions++; gets done by addh */
354 /* Add new pattern! */
355 id
= spatial_dict_addc(dict
, s
);
356 for (int r
= 0; r
< PTH__ROTATIONS
; r
++)
357 spatial_dict_addh(dict
, spatial_hash(r
, s
), id
);