14 struct pattern_config DEFAULT_PATTERN_CONFIG
= {
15 .spat_min
= 2, .spat_max
= MAX_PATTERN_DIST
,
17 .ldist_min
= 0, .ldist_max
= 256,
18 .mcsims
= 0, /* Unsupported. */
22 static const char *fnames
[] = {
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",
36 feature2str(char *str
, struct feature
*f
)
38 return str
+ sprintf(str
+ strlen(str
), "%s:%"PRIx32
, fnames
[f
->id
], f
->payload
);
42 str2feature(char *str
, struct feature
*f
)
44 while (isspace(*str
)) str
++;
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
)) {
52 fprintf(stderr
, "invalid featurespec: %s\n", str
);
57 f
->payload
= strtoull(str
, &str
, 10);
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)
73 int i
= 0; /* Indexing ptcoords[] */
75 /* First, center point. */
76 ptind
[0] = ptind
[1] = 0;
77 ptcoords
[i
].x
= ptcoords
[i
].y
= 0; i
++;
79 for (int d
= 2; d
< MAX_PATTERN_DIST
+ 1; d
++) {
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
--) {
88 /* max(|x|, |y|) = |y|, non-zero x */
90 if (x
+ y
* 2 != d
) continue;
92 /* max(|x|, |y|) = |x| */
93 /* Or, max(|x|, |y|) = |y| and x is zero */
95 if (x
* 2 + y
!= d
) continue;
98 assert((x
> y
? x
: y
) + x
+ y
== d
);
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
++; }
106 ptind
[MAX_PATTERN_DIST
] = i
;
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
);
114 fprintf(stderr
, "\n");
121 pattern_match(struct pattern_config
*pc
, struct pattern
*p
, struct board
*b
, struct move
*m
)
124 struct feature
*f
= &p
->f
[0];
126 /* TODO: We should match pretty much all of these features
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
;
139 foreach_neighbor(b
, m
->coord
, {
140 if (board_at(b
, c
) != stone_other(m
->color
))
142 group_t g
= group_at(b
, c
);
143 if (!g
|| board_group_info(b
, g
).libs
!= 1)
147 f
->id
= FEAT_CAPTURE
; f
->payload
= 0;
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. */
153 /* TODO: PF_CAPTURE_RECAPTURE */
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
)
160 group_t g
= group_at(b
, c
);
161 if (!g
|| board_group_info(b
, g
).libs
!= 1)
163 /* A neighboring group of ours is in atari. */
164 f
->payload
|= 1 << PF_CAPTURE_ATARIDEF
;
166 } foreach_in_group_end
;
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
;
180 foreach_neighbor(b
, m
->coord
, {
181 if (board_at(b
, c
) != m
->color
)
183 group_t g
= group_at(b
, c
);
184 if (!g
|| board_group_info(b
, g
).libs
!= 1)
188 f
->id
= FEAT_AESCAPE
; f
->payload
= 0;
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. */
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
;
208 foreach_neighbor(b
, m
->coord
, {
209 if (board_at(b
, c
) != stone_other(m
->color
))
211 group_t g
= group_at(b
, c
);
212 if (!g
|| board_group_info(b
, g
).libs
!= 2)
216 f
->id
= FEAT_ATARI
; f
->payload
= 0;
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. */
222 if (!is_pass(b
->ko
.coord
))
223 f
->payload
|= 1 << PF_CAPTURE_KO
;
230 int bdist
= coord_edge_distance(m
->coord
, b
);
231 if (bdist
<= pc
->bdist_max
) {
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
) {
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
) {
258 if (pc
->spat_max
> 0 && pc
->spat_dict
) {
259 assert(pc
->spat_min
> 0);
261 struct spatial s
= { .points
= {0} };
262 for (int d
= 2; d
< pc
->spat_max
; d
++) {
263 /* Go through all points in given distance. */
264 for (int j
= ptind
[d
]; j
< ptind
[d
+ 1]; j
++) {
265 int x
= coord_x(m
->coord
, b
) + ptcoords
[j
].x
;
266 int y
= coord_y(m
->coord
, b
) + ptcoords
[j
].y
;
267 if (x
>= board_size(b
)) x
= board_size(b
) - 1; else if (x
< 0) x
= 0;
268 if (y
>= board_size(b
)) y
= board_size(b
) - 1; else if (y
< 0) y
= 0;
270 s
.points
[j
/ 4] |= board_atxy(b
, x
, y
) << ((j
% 4) * 2);
272 if (d
< pc
->spat_min
)
274 /* Record spatial feature, one per distance. */
275 f
->id
= FEAT_SPATIAL
;
276 f
->payload
= (d
<< 24) | ((m
->color
== S_WHITE
) << 23);
278 f
->payload
|= spatial_dict_get(pc
->spat_dict
, &s
);
289 pattern2str(char *str
, struct pattern
*p
)
292 for (int i
= 0; i
< p
->n
; i
++) {
293 if (i
> 0) strcat(str
++, " ");
294 str
= feature2str(str
, &p
->f
[i
]);
302 /*** Spatial patterns dictionary */
304 /* Zobrist hashes used for black/white stones in patterns. */
305 #define PTH__ROTATIONS 16
306 static hash_t pthashes
[PTH__ROTATIONS
][MAX_PATTERN_AREA
][4];
307 static void __attribute__((constructor
)) pthashes_init(void)
309 /* We need fixed hashes for all pattern-relative in
310 * all pattern users! This is a simple way to generate
311 * hopefully good ones. Park-Miller powa. :) */
313 /* We create a virtual board (centered at the sequence start),
314 * plant the hashes there, then pick them up into the sequence
315 * with correct coordinates. It would be possible to generate
316 * the sequence point hashes directly, but the rotations would
317 * make for enormous headaches. */
318 hash_t pthboard
[MAX_PATTERN_AREA
][4];
319 int pthbc
= MAX_PATTERN_AREA
/ 2; // tengen coord
321 /* The magic numbers are tuned for minimal collisions. */
323 for (int i
= 0; i
< MAX_PATTERN_AREA
; i
++) {
324 pthboard
[i
][S_NONE
] = (h
= h
* 16803 - 7);
325 pthboard
[i
][S_BLACK
] = (h
= h
* 16805 + 7);
326 pthboard
[i
][S_WHITE
] = (h
= h
* 16807 + 3);
327 pthboard
[i
][S_OFFBOARD
] = (h
= h
* 16809 - 3);
330 /* Virtual board with hashes created, now fill
331 * pthashes[] with hashes for points in actual
332 * sequences, also considering various rotations. */
333 #define PTH_VMIRROR 1
334 #define PTH_HMIRROR 2
336 #define PTH_REVCOLOR 8
337 for (int r
= 0; r
< PTH__ROTATIONS
; r
++) {
338 for (int i
= 0; i
< MAX_PATTERN_AREA
; i
++) {
339 /* Rotate appropriately. */
340 int rx
= ptcoords
[i
].x
;
341 int ry
= ptcoords
[i
].y
;
342 if (r
& PTH_VMIRROR
) ry
= -ry
;
343 if (r
& PTH_HMIRROR
) rx
= -rx
;
345 int rs
= rx
; rx
= -ry
; ry
= rs
;
347 int bi
= pthbc
+ ry
* MAX_PATTERN_DIST
+ rx
;
350 pthashes
[r
][i
][S_NONE
] = pthboard
[bi
][S_NONE
];
351 if (r
& PTH_REVCOLOR
) {
352 pthashes
[r
][i
][S_WHITE
] = pthboard
[bi
][S_BLACK
];
353 pthashes
[r
][i
][S_BLACK
] = pthboard
[bi
][S_WHITE
];
355 pthashes
[r
][i
][S_BLACK
] = pthboard
[bi
][S_BLACK
];
356 pthashes
[r
][i
][S_WHITE
] = pthboard
[bi
][S_WHITE
];
358 pthashes
[r
][i
][S_OFFBOARD
] = pthboard
[bi
][S_OFFBOARD
];
364 spatial_hash(int rotation
, struct spatial
*s
)
367 for (int i
= 0; i
< ptind
[s
->dist
+ 1]; i
++) {
368 h
^= pthashes
[rotation
][i
][spatial_point_at(*s
, i
)];
370 return h
& spatial_hash_mask
;
374 spatial_dict_addc(struct spatial_dict
*dict
, struct spatial
*s
)
376 /* Allocate space in 1024 blocks. */
377 #define SPATIALS_ALLOC 1024
378 if (!(dict
->nspatials
% SPATIALS_ALLOC
)) {
379 dict
->spatials
= realloc(dict
->spatials
,
380 (dict
->nspatials
+ SPATIALS_ALLOC
)
381 * sizeof(*dict
->spatials
));
383 dict
->spatials
[dict
->nspatials
] = *s
;
384 return dict
->nspatials
++;
388 spatial_dict_addh(struct spatial_dict
*dict
, hash_t hash
, int id
)
390 if (dict
->hash
[hash
]) {
392 /* Give up, not worth the trouble. */
395 dict
->hash
[hash
] = id
;
399 /* Spatial dictionary file format:
401 * INDEX RADIUS STONES HASH...
402 * INDEX: index in the spatial table
403 * RADIUS: @d of the pattern
404 * STONES: string of ".XO#" chars
405 * HASH...: space-separated 18bit hash-table indices for the pattern */
408 spatial_dict_read(struct spatial_dict
*dict
, char *buf
)
410 /* XXX: We trust the data. Bad data will crash us. */
414 index
= strtol(bufp
, &bufp
, 10);
415 radius
= strtol(bufp
, &bufp
, 10);
416 while (isspace(*bufp
)) bufp
++;
418 /* Load the stone configuration. */
419 struct spatial s
= { .dist
= radius
};
421 while (!isspace(*bufp
)) {
422 s
.points
[sl
/ 4] |= char2stone(*bufp
++) << (sl
% 4);
425 while (isspace(*bufp
)) bufp
++;
428 if (sl
!= ptind
[s
.dist
+ 1]) {
429 fprintf(stderr
, "Spatial dictionary: Invalid number of stones (%d != %d) on this line: %s\n",
430 sl
, ptind
[radius
+ 1] - 1, buf
);
434 /* Add to collection. */
435 int id
= spatial_dict_addc(dict
, &s
);
437 /* Add to specified hash places. */
439 int hash
= strtol(bufp
, &bufp
, 16);
440 while (isspace(*bufp
)) bufp
++;
441 spatial_dict_addh(dict
, hash
& spatial_hash_mask
, id
);
446 spatial2str(struct spatial
*s
)
448 static char buf
[1024];
449 for (int i
= 0; i
< ptind
[s
->dist
+ 1]; i
++) {
450 buf
[i
] = stone2char(spatial_point_at(*s
, i
));
452 buf
[ptind
[s
->dist
+ 1]] = 0;
457 spatial_dict_write(struct spatial_dict
*dict
, int id
, FILE *f
)
459 struct spatial
*s
= &dict
->spatials
[id
];
460 fprintf(f
, "%d %d ", id
, s
->dist
);
461 fputs(spatial2str(s
), f
);
462 for (int r
= 0; r
< PTH__ROTATIONS
; r
++)
463 fprintf(f
, " %"PRIhash
"", spatial_hash(r
, s
));
468 spatial_dict_load(struct spatial_dict
*dict
, FILE *f
)
471 while (fgets(buf
, sizeof(buf
), f
)) {
472 if (buf
[0] == '#') continue;
473 spatial_dict_read(dict
, buf
);
477 struct spatial_dict
*
478 spatial_dict_init(bool will_append
)
480 static const char *filename
= "spatial.dict";
481 FILE *f
= fopen(filename
, "r");
482 if (!f
&& !will_append
) {
484 fprintf(stderr
, "No spatial dictionary, will not match spatial pattern features.\n");
488 struct spatial_dict
*dict
= calloc(1, sizeof(*dict
));
489 /* We create a dummy record for index 0 that we will
490 * never reference. This is so that hash value 0 can
491 * represent "no value". */
492 struct spatial dummy
= { .dist
= 0 };
493 spatial_dict_addc(dict
, &dummy
);
496 /* Existing file. Load it up! */
497 spatial_dict_load(dict
, f
);
500 f
= fopen(filename
, "a");
503 f
= fopen(filename
, "a");
504 /* New file. First, create a comment describing order
505 * of points in the array. This is just for purposes
506 * of external tools, Pachi never interprets it itself. */
507 fprintf(f
, "# Pachi spatial patterns dictionary v1.0 maxdist %d\n",
509 for (int d
= 0; d
< MAX_PATTERN_DIST
; d
++) {
510 fprintf(f
, "# Point order: d=%d ", d
);
511 for (int j
= ptind
[d
]; j
< ptind
[d
+ 1]; j
++) {
512 fprintf(f
, "%d,%d ", ptcoords
[j
].x
, ptcoords
[j
].y
);
523 spatial_dict_get(struct spatial_dict
*dict
, struct spatial
*s
)
525 hash_t hash
= spatial_hash(0, s
);
526 int id
= dict
->hash
[hash
];
528 /* Check for collisions in append mode. */
529 /* Tough job, we simply try if all rotations
530 * are also covered by the existing record. */
531 for (int r
= 0; r
< PTH__ROTATIONS
; r
++) {
532 hash_t rhash
= spatial_hash(r
, s
);
533 int rid
= dict
->hash
[rhash
];
537 fprintf(stderr
, "Collision %d vs %d (hash %d:%"PRIhash
")\n",
538 rid
, dict
->nspatials
, r
, rhash
);
540 /* dict->collisions++; gets done by addh */
544 if (!dict
->f
) return -1;
546 /* Add new pattern! */
547 id
= spatial_dict_addc(dict
, s
);
548 for (int r
= 0; r
< PTH__ROTATIONS
; r
++)
549 spatial_dict_addh(dict
, spatial_hash(r
, s
), id
);
550 spatial_dict_write(dict
, id
, dict
->f
);