4 /* Matching of multi-featured patterns. */
9 /* When someone says "pattern", you imagine a configuration of stones in given
10 * area (e.g. as matched very efficiently by pattern3 in case of 3x3 area).
11 * However, we use a richer definition of pattern, where this is merely one
12 * pattern _feature_. Another features may be is-a-selfatari, is-a-capture,
13 * number of liberties, distance from last move, etc. */
15 /* Each feature is represented by its id and an optional 32-bit payload;
16 * when matching, discrete (id,payload) pairs are considered. */
18 /* This is heavily influenced by (Coulom, 2007), of course. */
19 /* TODO: Try completely separate ko / no-ko features. */
21 /* See the HACKING file for another description of the pattern matcher and
22 * instructions on how to harvest and inspect patterns. */
24 /* If you add a payload bit for a feature, don't forget to update the value
30 /* Payload: [bit0] Last move was also pass? */
31 #define PF_PASS_LASTPASS 0
34 /* Simple capture move. */
35 /* Payload: [bit0] Capturing laddered group? */
36 #define PF_CAPTURE_LADDER 0
37 /* [bit1] Re-capturing last move? */
38 #define PF_CAPTURE_RECAPTURE 1 /* TODO */
39 /* [bit2] Enables our atari group get more libs? */
40 #define PF_CAPTURE_ATARIDEF 2
41 /* [bit3] Capturing ko? */
42 #define PF_CAPTURE_KO 3
45 /* Atari escape (extension). */
46 /* Payload: [bit0] Escaping with laddered group? */
47 #define PF_AESCAPE_LADDER 0
50 /* Self-atari move. */
51 /* Payload: [bit0] Also using our complex definition? */
52 #define PF_SELFATARI_SMART 0
56 /* Payload: [bit0] The atari'd group gets laddered? */
57 #define PF_ATARI_LADDER 0
58 /* [bit1] Playing ko? */
62 /* Border distance. */
63 /* Payload: The distance - "line number". Only up to 4. */
66 /* Last move distance. */
67 /* Payload: The distance - gridcular metric. */
70 /* Next-to-last move distance. */
71 /* Payload: The distance - gridcular metric. */
74 /* Spatial configuration of stones in certain board area,
75 * with black to play. */
76 /* Payload: [bits 31-24] Pattern radius (gridcular) */
77 #define PF_SPATIAL_RADIUS 24
78 /* [other bits] Index in the spatial_dict. */
79 #define PF_SPATIAL_INDEX 0
83 /* Unimplemented - TODO: */
85 /* Monte-carlo owner. */
86 /* Payload: #of playouts owning this point at the final
87 * position, scaled to 0..15 (lowest 4 bits). */
99 /* Pattern (matched) is set of features. */
102 struct feature f
[FEATURES
];
106 struct pattern_config
{
107 /* FEAT_SPATIAL: Generate patterns only for these sizes (gridcular). */
108 int spat_min
, spat_max
;
109 /* FEAT_BORDER: Generate features only up to this board distance. */
111 /* FEAT_LDIST, FEAT_LLDIST: Generate features only for these move
113 int ldist_min
, ldist_max
;
114 /* FEAT_MCOWNER: Generate feature after this number of simulations. */
117 /* The spatial patterns dictionary, used by FEAT_SPATIAL. */
118 struct spatial_dict
*spat_dict
;
120 extern struct pattern_config DEFAULT_PATTERN_CONFIG
;
121 extern struct pattern_config FAST_PATTERN_CONFIG
;
123 /* The pattern_spec[] specifies which features to tests for;
124 * highest bit controls whether to test for the feature at all,
125 * then for bitmap features (except FEAT_SPATIAL) the rest
126 * of the bits controls various PF tests; for non-bitmap
127 * features, you will need to tweak the patternconfig to
129 typedef uint32_t pattern_spec
[FEAT_MAX
];
130 /* Match all supported features. */
131 extern pattern_spec PATTERN_SPEC_MATCHALL
;
132 /* Match only "quick" features, suitable for MC simulations. */
133 extern pattern_spec PATTERN_SPEC_MATCHFAST
;
136 /* Append feature to string. */
137 char *feature2str(char *str
, struct feature
*f
);
138 /* Convert string to feature, return pointer after the featurespec. */
139 char *str2feature(char *str
, struct feature
*f
);
141 /* Append pattern as feature spec string. */
142 char *pattern2str(char *str
, struct pattern
*p
);
144 /* Initialize p and fill it with features matched by the
145 * given board move. */
146 void pattern_match(struct pattern_config
*pc
, pattern_spec ps
, struct pattern
*p
, struct board
*b
, struct move
*m
);
149 /* Comparative strengths of all feature-payload pairs (initialized to 1 for
150 * unspecified pairs). */
151 struct features_gamma
{
152 /* Indexed by feature and payload; each feature array is allocated for
153 * all possible payloads to fit in. */
154 float *gamma
[FEAT_MAX
];
155 struct pattern_config
*pc
;
157 /* Default gamma filename to use. */
158 extern const char *features_gamma_filename
;
160 /* Initializes gamma values, pre-loading existing records from given file
161 * (NULL for default), falling back to gamma==1 for unspecified values. */
162 struct features_gamma
*features_gamma_init(struct pattern_config
*pc
, const char *file
);
164 /* Look up gamma of given feature, or set one if gamma is not NULL. */
165 float feature_gamma(struct features_gamma
*fg
, struct feature
*f
, float *gamma
);
168 /* Spatial pattern dictionary. */
170 /* For each encountered configuration of stones, we keep it "spelled out"
171 * in these records, index them and refer just the indices in the feature
172 * payloads. This achieves several things:
173 * * We can handle patterns of arbitrary length.
174 * * We can recognize isomorphous configurations (color reversions,
175 * rotations) within the dataset.
176 * * We can visualise patterns corresponding to chosen features.
178 * Thus, it goes like this:
180 * +----------------+ +----------------+
181 * | struct pattern | - | struct feature |
182 * +----------------+ | payload id |
188 * +-----------------------------------------+
189 * | struct spatial_dict spatials[] hash[] |
190 * +-----------------------------------------+
197 /* Maximum spatial pattern diameter. */
198 #define MAX_PATTERN_DIST 10
199 /* Maximum number of points in spatial pattern (upper bound).
200 * TODO: Better upper bound to save more data. */
201 #define MAX_PATTERN_AREA (MAX_PATTERN_DIST*MAX_PATTERN_DIST)
203 /* Record for single stone configuration. */
205 /* Gridcular radius of matched pattern. */
207 /* The points; each point is two bits, corresponding
208 * to {enum stone}. Points are ordered in gridcular-defined
209 * spiral from middle to the edge; the dictionary file has
210 * a comment describing the ordering at the top. */
211 char points
[MAX_PATTERN_AREA
/ 4];
212 #define spatial_point_at(s, i) (((s).points[(i) / 4] >> (((i) % 4) * 2)) & 3)
215 /* Collection of stone configurations, with two ways of lookup:
216 * (i) by index (ii) by hash of the configuration. */
217 struct spatial_dict
{
218 /* Indexed base store */
219 int nspatials
; /* Number of records. */
220 struct spatial
*spatials
; /* Actual records. */
222 /* Hashed access; all isomorphous configurations
224 #define spatial_hash_bits 24 // ~64mib array
225 #define spatial_hash_mask ((1 << spatial_hash_bits) - 1)
226 /* Maps to spatials[] indices. The hash function
227 * used is zobrist hashing with fixed values. */
228 uint32_t hash
[1 << spatial_hash_bits
];
229 /* Auxiliary collision counter, for statistics. */
232 /* Default spatial dict filename to use. */
233 extern const char *spatial_dict_filename
;
235 /* Initializes spatial dictionary, pre-loading existing records from
236 * default filename if exists. If will_append is true, it will not
237 * complain about non-existing file and initialize the dictionary anyway. */
238 struct spatial_dict
*spatial_dict_init(bool will_append
);
240 /* Fill up the spatial record from @m vincinity, up to full distance
241 * given by pattern config. */
242 void spatial_from_board(struct pattern_config
*pc
, struct spatial
*s
, struct board
*b
, struct move
*m
);
244 /* Compute hash of given spatial pattern. */
245 hash_t
spatial_hash(int rotation
, struct spatial
*s
);
246 /* Convert given spatial pattern to string. */
247 char *spatial2str(struct spatial
*s
);
248 /* Append specified spatial pattern to the given file. */
249 void spatial_write(struct spatial
*s
, int id
, FILE *f
);
251 /* Lookup specified spatial pattern in the dictionary; return index
252 * of the pattern. If the pattern is not found, 0 will be returned. */
253 int spatial_dict_get(struct spatial_dict
*dict
, int dist
, hash_t h
);
255 /* Store specified spatial pattern in the dictionary if it is not known yet.
256 * Returns pattern id. Note that the pattern is NOT written to the underlying
257 * file automatically. */
258 int spatial_dict_put(struct spatial_dict
*dict
, struct spatial
*s
, hash_t
);
260 /* Write comment lines describing the dictionary (e.g. point order
261 * in patterns) to given file. */
262 void spatial_dict_writeinfo(struct spatial_dict
*dict
, FILE *f
);