14 struct pattern_config DEFAULT_PATTERN_CONFIG
= {
15 .spat_min
= 3, .spat_max
= MAX_PATTERN_DIST
,
17 .ldist_min
= 0, .ldist_max
= 256,
18 .mcsims
= 0, /* Unsupported. */
21 struct pattern_config FAST_PATTERN_CONFIG
= {
22 .spat_min
= 3, .spat_max
= 5,
24 .ldist_min
= 0, .ldist_max
= 256,
28 pattern_spec PATTERN_SPEC_MATCHALL
= {
32 [FEAT_SELFATARI
] = ~0,
41 pattern_spec PATTERN_SPEC_MATCHFAST
= {
43 [FEAT_CAPTURE
] = ~(1<<PF_CAPTURE_ATARIDEF
)|~(1<<PF_CAPTURE_RECAPTURE
),
45 [FEAT_SELFATARI
] = ~(1<<PF_SELFATARI_SMART
),
54 static const struct feature_info
{
57 } features
[FEAT_MAX
] = {
58 [FEAT_PASS
] = { .name
= "pass", .payloads
= 2 },
59 [FEAT_CAPTURE
] = { .name
= "capture", .payloads
= 16 },
60 [FEAT_AESCAPE
] = { .name
= "atariescape", .payloads
= 2 },
61 [FEAT_SELFATARI
] = { .name
= "selfatari", .payloads
= 2 },
62 [FEAT_ATARI
] = { .name
= "atari", .payloads
= 4 },
63 [FEAT_BORDER
] = { .name
= "border", .payloads
= 1 },
64 [FEAT_LDIST
] = { .name
= "ldist", .payloads
= -1 },
65 [FEAT_LLDIST
] = { .name
= "lldist", .payloads
= -1 },
66 [FEAT_SPATIAL
] = { .name
= "s", .payloads
= -1 },
67 [FEAT_MCOWNER
] = { .name
= "mcowner", .payloads
= 16 },
71 feature2str(char *str
, struct feature
*f
)
73 return str
+ sprintf(str
+ strlen(str
), "%s:%"PRIx32
, features
[f
->id
].name
, f
->payload
);
77 str2feature(char *str
, struct feature
*f
)
79 while (isspace(*str
)) str
++;
81 int flen
= strcspn(str
, ":");
82 for (int i
= 0; i
< sizeof(features
)/sizeof(features
[0]); i
++)
83 if (strlen(features
[i
].name
) == flen
&& !strncmp(features
[i
].name
, str
, flen
)) {
87 fprintf(stderr
, "invalid featurespec: %s[%d]\n", str
, flen
);
92 f
->payload
= strtoull(str
, &str
, 16);
97 /* Mapping from point sequence to coordinate offsets (to determine
98 * coordinates relative to pattern center). The array is ordered
99 * in the gridcular metric order so that we can go through it
100 * and incrementally match spatial features in nested circles.
101 * Within one circle, coordinates are ordered by rows to keep
102 * good cache behavior. */
103 static struct { short x
, y
; } ptcoords
[MAX_PATTERN_AREA
];
104 /* For each radius, starting index in ptcoords[]. */
105 static int ptind
[MAX_PATTERN_DIST
+ 2];
106 static void __attribute__((constructor
)) ptcoords_init(void)
108 int i
= 0; /* Indexing ptcoords[] */
110 /* First, center point. */
111 ptind
[0] = ptind
[1] = 0;
112 ptcoords
[i
].x
= ptcoords
[i
].y
= 0; i
++;
114 for (int d
= 2; d
<= MAX_PATTERN_DIST
; d
++) {
116 /* For each y, examine all integer solutions
117 * of d = |x| + |y| + max(|x|, |y|). */
118 /* TODO: (Stern, 2006) uses a hand-modified
119 * circles that are finer for small d. */
120 for (short y
= d
/ 2; y
>= 0; y
--) {
123 /* max(|x|, |y|) = |y|, non-zero x */
125 if (x
+ y
* 2 != d
) continue;
127 /* max(|x|, |y|) = |x| */
128 /* Or, max(|x|, |y|) = |y| and x is zero */
130 if (x
* 2 + y
!= d
) continue;
133 assert((x
> y
? x
: y
) + x
+ y
== d
);
135 ptcoords
[i
].x
= x
; ptcoords
[i
].y
= y
; i
++;
136 if (x
!= 0) { ptcoords
[i
].x
= -x
; ptcoords
[i
].y
= y
; i
++; }
137 if (y
!= 0) { ptcoords
[i
].x
= x
; ptcoords
[i
].y
= -y
; i
++; }
138 if (x
!= 0 && y
!= 0) { ptcoords
[i
].x
= -x
; ptcoords
[i
].y
= -y
; i
++; }
141 ptind
[MAX_PATTERN_DIST
+ 1] = i
;
144 for (int d
= 0; d
<= MAX_PATTERN_DIST
; d
++) {
145 fprintf(stderr
, "d=%d (%d) ", d
, ptind
[d
]);
146 for (int j
= ptind
[d
]; j
< ptind
[d
+ 1]; j
++) {
147 fprintf(stderr
, "%d,%d ", ptcoords
[j
].x
, ptcoords
[j
].y
);
149 fprintf(stderr
, "\n");
155 /* pattern_spec helpers */
156 #define PS_ANY(F) (ps[FEAT_ ## F] & (1 << 31))
157 #define PS_PF(F, P) (ps[FEAT_ ## F] & (1 << PF_ ## F ## _ ## P))
159 static struct feature
*
160 pattern_match_capture(struct pattern_config
*pc
, pattern_spec ps
,
161 struct pattern
*p
, struct feature
*f
,
162 struct board
*b
, struct move
*m
)
164 foreach_neighbor(b
, m
->coord
, {
165 if (board_at(b
, c
) != stone_other(m
->color
))
167 group_t g
= group_at(b
, c
);
168 if (!g
|| board_group_info(b
, g
).libs
!= 1)
172 f
->id
= FEAT_CAPTURE
; f
->payload
= 0;
174 if (PS_PF(CAPTURE
, LADDER
))
175 f
->payload
|= is_ladder(b
, m
->coord
, g
, true, true) << PF_CAPTURE_LADDER
;
176 /* TODO: is_ladder() is too conservative in some
177 * very obvious situations, look at complete.gtp. */
179 /* TODO: PF_CAPTURE_RECAPTURE */
181 if (PS_PF(CAPTURE
, ATARIDEF
))
182 foreach_in_group(b
, g
) {
183 foreach_neighbor(b
, c
, {
184 assert(board_at(b
, c
) != S_NONE
|| c
== m
->coord
);
185 if (board_at(b
, c
) != m
->color
)
187 group_t g
= group_at(b
, c
);
188 if (!g
|| board_group_info(b
, g
).libs
!= 1)
190 /* A neighboring group of ours is in atari. */
191 f
->payload
|= 1 << PF_CAPTURE_ATARIDEF
;
193 } foreach_in_group_end
;
195 if (PS_PF(CAPTURE
, KO
)
196 && group_is_onestone(b
, g
)
197 && neighbor_count_at(b
, m
->coord
, stone_other(m
->color
))
198 + neighbor_count_at(b
, m
->coord
, S_OFFBOARD
) == 4)
199 f
->payload
|= 1 << PF_CAPTURE_KO
;
206 static struct feature
*
207 pattern_match_aescape(struct pattern_config
*pc
, pattern_spec ps
,
208 struct pattern
*p
, struct feature
*f
,
209 struct board
*b
, struct move
*m
)
211 /* Find if a neighboring group of ours is in atari, AND that we provide
212 * a liberty to connect out. XXX: No connect-and-die check. */
213 group_t in_atari
= -1;
214 bool has_extra_lib
= false;
217 foreach_neighbor(b
, m
->coord
, {
218 if (board_at(b
, c
) != m
->color
) {
219 if (board_at(b
, c
) == S_NONE
)
220 has_extra_lib
= true; // free point
221 else if (board_at(b
, c
) == stone_other(m
->color
) && board_group_info(b
, group_at(b
, c
)).libs
== 1)
222 has_extra_lib
= true; // capturable enemy group
225 group_t g
= group_at(b
, c
); assert(g
);
226 if (board_group_info(b
, g
).libs
!= 1) {
227 has_extra_lib
= true;
234 if (PS_PF(AESCAPE
, LADDER
))
235 payload
|= is_ladder(b
, m
->coord
, g
, true, true) << PF_AESCAPE_LADDER
;
236 /* TODO: is_ladder() is too conservative in some
237 * very obvious situations, look at complete.gtp. */
239 if (in_atari
>= 0 && has_extra_lib
) {
240 f
->id
= FEAT_AESCAPE
; f
->payload
= payload
;
246 static struct feature
*
247 pattern_match_atari(struct pattern_config
*pc
, pattern_spec ps
,
248 struct pattern
*p
, struct feature
*f
,
249 struct board
*b
, struct move
*m
)
251 foreach_neighbor(b
, m
->coord
, {
252 if (board_at(b
, c
) != stone_other(m
->color
))
254 group_t g
= group_at(b
, c
);
255 if (!g
|| board_group_info(b
, g
).libs
!= 2)
259 f
->id
= FEAT_ATARI
; f
->payload
= 0;
261 if (PS_PF(ATARI
, LADDER
)) {
262 /* Opponent will escape by the other lib. */
263 coord_t lib
= board_group_info(b
, g
).lib
[0];
264 if (lib
== m
->coord
) lib
= board_group_info(b
, g
).lib
[1];
265 /* TODO: is_ladder() is too conservative in some
266 * very obvious situations, look at complete.gtp. */
267 f
->payload
|= is_ladder(b
, lib
, g
, true, true) << PF_ATARI_LADDER
;
270 if (PS_PF(ATARI
, KO
) && !is_pass(b
->ko
.coord
))
271 f
->payload
|= 1 << PF_ATARI_KO
;
279 /* We record all spatial patterns black-to-play; simply
280 * reverse all colors if we are white-to-play. */
281 static enum stone bt_black
[4] = { S_NONE
, S_BLACK
, S_WHITE
, S_OFFBOARD
};
282 static enum stone bt_white
[4] = { S_NONE
, S_WHITE
, S_BLACK
, S_OFFBOARD
};
284 static inline hash_t
spatial_hash_one(int rotation
, int i
, enum stone color
);
285 static struct feature
*
286 pattern_match_spatial(struct pattern_config
*pc
, pattern_spec ps
,
287 struct pattern
*p
, struct feature
*f
,
288 struct board
*b
, struct move
*m
)
290 /* XXX: This is partially duplicated from spatial_from_board(), but
291 * we build a hash instead of spatial record. */
293 assert(pc
->spat_min
> 0);
295 enum stone (*bt
)[4] = m
->color
== S_WHITE
? &bt_white
: &bt_black
;
297 hash_t h
= spatial_hash_one(0, 0, S_NONE
);
298 for (int d
= 2; d
<= pc
->spat_max
; d
++) {
299 /* Go through all points in given distance. */
300 for (int j
= ptind
[d
]; j
< ptind
[d
+ 1]; j
++) {
301 int x
= coord_x(m
->coord
, b
) + ptcoords
[j
].x
;
302 int y
= coord_y(m
->coord
, b
) + ptcoords
[j
].y
;
303 if (x
>= board_size(b
)) x
= board_size(b
) - 1; else if (x
< 0) x
= 0;
304 if (y
>= board_size(b
)) y
= board_size(b
) - 1; else if (y
< 0) y
= 0;
305 h
^= spatial_hash_one(0, j
, (*bt
)[board_atxy(b
, x
, y
)]);
307 if (d
< pc
->spat_min
)
309 /* Record spatial feature, one per distance. */
310 f
->id
= FEAT_SPATIAL
;
311 f
->payload
= (d
<< PF_SPATIAL_RADIUS
);
312 int sid
= spatial_dict_get(pc
->spat_dict
, d
, h
& spatial_hash_mask
);
314 f
->payload
|= sid
<< PF_SPATIAL_INDEX
;
316 } /* else not found, ignore */
323 is_simple_selfatari(struct board
*b
, enum stone color
, coord_t coord
)
325 /* Very rough check, no connect-and-die checks or other trickery. */
326 int libs
= immediate_liberty_count(b
, coord
);
327 if (libs
>= 2) return false; // open space
330 foreach_neighbor(b
, coord
, {
331 if (board_at(b
, c
) == stone_other(color
) && board_group_info(b
, group_at(b
, c
)).libs
== 1) {
332 return false; // can capture
334 } else if (board_at(b
, c
) == color
) {
335 // friendly group, does it have liberties?
336 group_t g
= group_at(b
, c
);
337 if (board_group_info(b
, g
).libs
== 1 || seen
== g
)
339 libs
+= board_group_info(b
, g
).libs
- 1;
340 if (libs
>= 2) return false;
341 // don't consider the same group twice
349 pattern_match(struct pattern_config
*pc
, pattern_spec ps
,
350 struct pattern
*p
, struct board
*b
, struct move
*m
)
353 struct feature
*f
= &p
->f
[0];
355 /* TODO: We should match pretty much all of these features
358 if (is_pass(m
->coord
)) {
360 f
->id
= FEAT_PASS
; f
->payload
= 0;
361 if (PS_PF(PASS
, LASTPASS
))
362 f
->payload
|= (b
->moves
> 0 && is_pass(b
->last_move
.coord
))
369 if (PS_ANY(CAPTURE
)) {
370 f
= pattern_match_capture(pc
, ps
, p
, f
, b
, m
);
373 if (PS_ANY(AESCAPE
)) {
374 f
= pattern_match_aescape(pc
, ps
, p
, f
, b
, m
);
377 if (PS_ANY(SELFATARI
)) {
378 bool simple
= is_simple_selfatari(b
, m
->color
, m
->coord
);
379 bool thorough
= false;
380 if (PS_PF(SELFATARI
, SMART
)) {
381 thorough
= is_bad_selfatari(b
, m
->color
, m
->coord
);
383 if (simple
|| thorough
) {
384 f
->id
= FEAT_SELFATARI
;
385 f
->payload
= thorough
<< PF_SELFATARI_SMART
;
391 f
= pattern_match_atari(pc
, ps
, p
, f
, b
, m
);
394 if (PS_ANY(BORDER
)) {
395 int bdist
= coord_edge_distance(m
->coord
, b
);
396 if (bdist
<= pc
->bdist_max
) {
403 if (PS_ANY(LDIST
) && pc
->ldist_max
> 0 && !is_pass(b
->last_move
.coord
)) {
404 int ldist
= coord_gridcular_distance(m
->coord
, b
->last_move
.coord
, b
);
405 if (pc
->ldist_min
<= ldist
&& ldist
<= pc
->ldist_max
) {
412 if (PS_ANY(LLDIST
) && pc
->ldist_max
> 0 && !is_pass(b
->last_move2
.coord
)) {
413 int lldist
= coord_gridcular_distance(m
->coord
, b
->last_move2
.coord
, b
);
414 if (pc
->ldist_min
<= lldist
&& lldist
<= pc
->ldist_max
) {
421 if (PS_ANY(SPATIAL
) && pc
->spat_max
> 0 && pc
->spat_dict
) {
422 f
= pattern_match_spatial(pc
, ps
, p
, f
, b
, m
);
425 /* FEAT_MCOWNER: TODO */
430 pattern2str(char *str
, struct pattern
*p
)
432 str
= stpcpy(str
, "(");
433 for (int i
= 0; i
< p
->n
; i
++) {
434 if (i
> 0) str
= stpcpy(str
, " ");
435 str
= feature2str(str
, &p
->f
[i
]);
437 str
= stpcpy(str
, ")");
443 /*** Features gamma set */
446 features_gamma_load(struct features_gamma
*fg
, const char *filename
)
448 FILE *f
= fopen(filename
, "r");
451 while (fgets(buf
, 256, f
)) {
454 bufp
= str2feature(bufp
, &f
);
455 while (isspace(*bufp
)) bufp
++;
456 float gamma
= strtof(bufp
, &bufp
);
457 feature_gamma(fg
, &f
, &gamma
);
462 const char *features_gamma_filename
= "patterns.gamma";
464 struct features_gamma
*
465 features_gamma_init(struct pattern_config
*pc
, const char *file
)
467 struct features_gamma
*fg
= calloc(1, sizeof(*fg
));
469 for (int i
= 0; i
< FEAT_MAX
; i
++) {
470 int n
= features
[i
].payloads
;
474 n
= pc
->spat_dict
->nspatials
; break;
477 n
= pc
->ldist_max
; break;
482 fg
->gamma
[i
] = malloc(n
* sizeof(float));
483 for (int j
= 0; j
< n
; j
++) {
484 fg
->gamma
[i
][j
] = 1.0f
;
487 features_gamma_load(fg
, file
? file
: features_gamma_filename
);
492 feature_gamma(struct features_gamma
*fg
, struct feature
*f
, float *gamma
)
494 /* XXX: We mask out spatial distance unconditionally since it shouldn't
495 * affect any other feature. */
496 int payid
= f
->payload
& ((1<<24)-1);
497 if (gamma
) fg
->gamma
[f
->id
][payid
] = *gamma
;
498 return fg
->gamma
[f
->id
][payid
];
503 /*** Spatial patterns dictionary */
505 /* Zobrist hashes used for black/white stones in patterns. */
506 #define PTH__ROTATIONS 8
507 static hash_t pthashes
[PTH__ROTATIONS
][MAX_PATTERN_AREA
][4];
508 static void __attribute__((constructor
)) pthashes_init(void)
510 /* We need fixed hashes for all pattern-relative in
511 * all pattern users! This is a simple way to generate
512 * hopefully good ones. Park-Miller powa. :) */
514 /* We create a virtual board (centered at the sequence start),
515 * plant the hashes there, then pick them up into the sequence
516 * with correct coordinates. It would be possible to generate
517 * the sequence point hashes directly, but the rotations would
518 * make for enormous headaches. */
519 hash_t pthboard
[MAX_PATTERN_AREA
][4];
520 int pthbc
= MAX_PATTERN_AREA
/ 2; // tengen coord
522 /* The magic numbers are tuned for minimal collisions. */
524 for (int i
= 0; i
< MAX_PATTERN_AREA
; i
++) {
525 pthboard
[i
][S_NONE
] = (h
= h
* 16803 - 7);
526 pthboard
[i
][S_BLACK
] = (h
= h
* 16805 + 7);
527 pthboard
[i
][S_WHITE
] = (h
= h
* 16807 + 3);
528 pthboard
[i
][S_OFFBOARD
] = (h
= h
* 16809 - 3);
531 /* Virtual board with hashes created, now fill
532 * pthashes[] with hashes for points in actual
533 * sequences, also considering various rotations. */
534 #define PTH_VMIRROR 1
535 #define PTH_HMIRROR 2
537 for (int r
= 0; r
< PTH__ROTATIONS
; r
++) {
538 for (int i
= 0; i
< MAX_PATTERN_AREA
; i
++) {
539 /* Rotate appropriately. */
540 int rx
= ptcoords
[i
].x
;
541 int ry
= ptcoords
[i
].y
;
542 if (r
& PTH_VMIRROR
) ry
= -ry
;
543 if (r
& PTH_HMIRROR
) rx
= -rx
;
545 int rs
= rx
; rx
= -ry
; ry
= rs
;
547 int bi
= pthbc
+ ry
* MAX_PATTERN_DIST
+ rx
;
550 pthashes
[r
][i
][S_NONE
] = pthboard
[bi
][S_NONE
];
551 pthashes
[r
][i
][S_BLACK
] = pthboard
[bi
][S_BLACK
];
552 pthashes
[r
][i
][S_WHITE
] = pthboard
[bi
][S_WHITE
];
553 pthashes
[r
][i
][S_OFFBOARD
] = pthboard
[bi
][S_OFFBOARD
];
559 spatial_hash_one(int rotation
, int i
, enum stone color
)
561 return pthashes
[rotation
][i
][color
];
565 spatial_hash(int rotation
, struct spatial
*s
)
568 for (int i
= 0; i
< ptind
[s
->dist
+ 1]; i
++) {
569 h
^= pthashes
[rotation
][i
][spatial_point_at(*s
, i
)];
571 return h
& spatial_hash_mask
;
575 spatial_dict_addc(struct spatial_dict
*dict
, struct spatial
*s
)
577 /* Allocate space in 1024 blocks. */
578 #define SPATIALS_ALLOC 1024
579 if (!(dict
->nspatials
% SPATIALS_ALLOC
)) {
580 dict
->spatials
= realloc(dict
->spatials
,
581 (dict
->nspatials
+ SPATIALS_ALLOC
)
582 * sizeof(*dict
->spatials
));
584 dict
->spatials
[dict
->nspatials
] = *s
;
585 return dict
->nspatials
++;
589 spatial_dict_addh(struct spatial_dict
*dict
, hash_t hash
, int id
)
591 if (dict
->hash
[hash
]) {
593 /* Give up, not worth the trouble. */
596 dict
->hash
[hash
] = id
;
600 /* Spatial dictionary file format:
602 * INDEX RADIUS STONES HASH...
603 * INDEX: index in the spatial table
604 * RADIUS: @d of the pattern
605 * STONES: string of ".XO#" chars
606 * HASH...: space-separated 18bit hash-table indices for the pattern */
609 spatial_dict_read(struct spatial_dict
*dict
, char *buf
)
611 /* XXX: We trust the data. Bad data will crash us. */
615 index
= strtol(bufp
, &bufp
, 10);
616 radius
= strtol(bufp
, &bufp
, 10);
617 while (isspace(*bufp
)) bufp
++;
619 /* Load the stone configuration. */
620 struct spatial s
= { .dist
= radius
};
622 while (!isspace(*bufp
)) {
623 s
.points
[sl
/ 4] |= char2stone(*bufp
++) << (sl
% 4);
626 while (isspace(*bufp
)) bufp
++;
629 if (sl
!= ptind
[s
.dist
+ 1]) {
630 fprintf(stderr
, "Spatial dictionary: Invalid number of stones (%d != %d) on this line: %s\n",
631 sl
, ptind
[radius
+ 1] - 1, buf
);
635 /* Add to collection. */
636 int id
= spatial_dict_addc(dict
, &s
);
638 /* Add to specified hash places. */
640 int hash
= strtol(bufp
, &bufp
, 16);
641 while (isspace(*bufp
)) bufp
++;
642 spatial_dict_addh(dict
, hash
& spatial_hash_mask
, id
);
647 spatial2str(struct spatial
*s
)
649 static char buf
[1024];
650 for (int i
= 0; i
< ptind
[s
->dist
+ 1]; i
++) {
651 buf
[i
] = stone2char(spatial_point_at(*s
, i
));
653 buf
[ptind
[s
->dist
+ 1]] = 0;
658 spatial_write(struct spatial
*s
, int id
, FILE *f
)
660 fprintf(f
, "%d %d ", id
, s
->dist
);
661 fputs(spatial2str(s
), f
);
662 for (int r
= 0; r
< PTH__ROTATIONS
; r
++)
663 fprintf(f
, " %"PRIhash
"", spatial_hash(r
, s
));
668 spatial_dict_load(struct spatial_dict
*dict
, FILE *f
)
671 while (fgets(buf
, sizeof(buf
), f
)) {
672 if (buf
[0] == '#') continue;
673 spatial_dict_read(dict
, buf
);
678 spatial_dict_writeinfo(struct spatial_dict
*dict
, FILE *f
)
680 /* New file. First, create a comment describing order
681 * of points in the array. This is just for purposes
682 * of external tools, Pachi never interprets it itself. */
683 fprintf(f
, "# Pachi spatial patterns dictionary v1.0 maxdist %d\n",
685 for (int d
= 0; d
<= MAX_PATTERN_DIST
; d
++) {
686 fprintf(f
, "# Point order: d=%d ", d
);
687 for (int j
= ptind
[d
]; j
< ptind
[d
+ 1]; j
++) {
688 fprintf(f
, "%d,%d ", ptcoords
[j
].x
, ptcoords
[j
].y
);
694 const char *spatial_dict_filename
= "patterns.spat";
695 struct spatial_dict
*
696 spatial_dict_init(bool will_append
)
698 FILE *f
= fopen(spatial_dict_filename
, "r");
699 if (!f
&& !will_append
) {
701 fprintf(stderr
, "No spatial dictionary, will not match spatial pattern features.\n");
705 struct spatial_dict
*dict
= calloc(1, sizeof(*dict
));
706 /* We create a dummy record for index 0 that we will
707 * never reference. This is so that hash value 0 can
708 * represent "no value". */
709 struct spatial dummy
= { .dist
= 0 };
710 spatial_dict_addc(dict
, &dummy
);
713 spatial_dict_load(dict
, f
);
723 spatial_from_board(struct pattern_config
*pc
, struct spatial
*s
,
724 struct board
*b
, struct move
*m
)
726 assert(pc
->spat_min
> 0);
728 enum stone (*bt
)[4] = m
->color
== S_WHITE
? &bt_white
: &bt_black
;
730 memset(s
, 0, sizeof(*s
));
731 for (int j
= 0; j
< ptind
[pc
->spat_max
+ 1]; j
++) {
732 int x
= coord_x(m
->coord
, b
) + ptcoords
[j
].x
;
733 int y
= coord_y(m
->coord
, b
) + ptcoords
[j
].y
;
734 if (x
>= board_size(b
)) x
= board_size(b
) - 1; else if (x
< 0) x
= 0;
735 if (y
>= board_size(b
)) y
= board_size(b
) - 1; else if (y
< 0) y
= 0;
736 s
->points
[j
/ 4] |= (*bt
)[board_atxy(b
, x
, y
)] << ((j
% 4) * 2);
738 s
->dist
= pc
->spat_max
;
742 spatial_dict_get(struct spatial_dict
*dict
, int dist
, hash_t hash
)
744 int id
= dict
->hash
[hash
];
745 if (id
&& dict
->spatials
[id
].dist
!= dist
) {
747 fprintf(stderr
, "Collision dist %d vs %d (hash [%d]%"PRIhash
")\n",
748 dist
, dict
->spatials
[id
].dist
, id
, hash
);
755 spatial_dict_put(struct spatial_dict
*dict
, struct spatial
*s
, hash_t h
)
757 int id
= spatial_dict_get(dict
, s
->dist
, h
);
759 /* Check for collisions in append mode. */
760 /* Tough job, we simply try if any other rotation
761 * is also covered by the existing record. */
762 int r
; hash_t rhash
; int rid
;
763 for (r
= 1; r
< PTH__ROTATIONS
; r
++) {
764 rhash
= spatial_hash(r
, s
);
765 rid
= dict
->hash
[rhash
];
769 /* All rotations match, id is good to go! */
774 fprintf(stderr
, "Collision %d vs %d (hash %d:%"PRIhash
")\n",
775 id
, dict
->nspatials
, r
, h
);
777 /* dict->collisions++; gets done by addh */
780 /* Add new pattern! */
781 id
= spatial_dict_addc(dict
, s
);
782 for (int r
= 0; r
< PTH__ROTATIONS
; r
++)
783 spatial_dict_addh(dict
, spatial_hash(r
, s
), id
);