Merge branch 'master' of git+ssh://repo.or.cz/srv/git/pachi
[pachi/json.git] / pattern.h
blob0a75a92f9124f3c84f5f47bc2d254f9c160273f4
1 #ifndef ZZGO_PATTERN_H
2 #define ZZGO_PATTERN_H
4 /* Matching of multi-featured patterns. */
6 #include "board.h"
7 #include "move.h"
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 /* ! NOTE NOTE NOTE ! We provide infrastructure for matching patterns, but we
16 * also replicate the most bare-bone part of it for tiny subset of features
17 * in board.c:board_gamma_update() for fast incremental probability
18 * distribution maintenance. Aside of using the constants defined here, that
19 * implementation is completely independent and does not call back here. */
21 /* Each feature is represented by its id and an optional 32-bit payload;
22 * when matching, discrete (id,payload) pairs are considered. */
24 /* This is heavily influenced by (Coulom, 2007), of course. */
25 /* TODO: Try completely separate ko / no-ko features. */
27 /* See the HACKING file for another description of the pattern matcher and
28 * instructions on how to harvest and inspect patterns. */
30 /* If you add a payload bit for a feature, don't forget to update the value
31 * in feature_info. */
32 enum feature_id {
33 /* Implemented: */
35 /* This is a pass. */
36 /* Payload: [bit0] Last move was also pass? */
37 #define PF_PASS_LASTPASS 0
38 FEAT_PASS,
40 /* Simple capture move. */
41 /* Payload: [bit0] Capturing laddered group? */
42 #define PF_CAPTURE_LADDER 0
43 /* [bit1] Re-capturing last move? */
44 #define PF_CAPTURE_RECAPTURE 1 /* TODO */
45 /* [bit2] Enables our atari group get more libs? */
46 #define PF_CAPTURE_ATARIDEF 2
47 /* [bit3] Capturing ko? */
48 #define PF_CAPTURE_KO 3
49 /* [bit4] Single-stone group? */
50 #define PF_CAPTURE_1STONE 4
51 /* [bit5] Unsafe move for opponent? */
52 #define PF_CAPTURE_TRAPPED 5
53 /* [bit6] Preventing connection to an outside group. */
54 #define PF_CAPTURE_CONNECTION 6
55 FEAT_CAPTURE,
57 /* Atari escape (extension). */
58 /* Payload: [bit0] Escaping with laddered group? */
59 #define PF_AESCAPE_LADDER 0
60 /* [bit1] Single-stone group? */
61 #define PF_AESCAPE_1STONE 1
62 /* [bit2] Unsafe move for us? */
63 #define PF_AESCAPE_TRAPPED 2
64 /* [bit3] Connecting out to an outside group. */
65 #define PF_AESCAPE_CONNECTION 3
66 FEAT_AESCAPE,
68 /* Self-atari move. */
69 /* Payload: [bit0] Matched by trivial definition? */
70 /* [bit1] Matched by complex definition? (tries to be aware of nakade, throwins, ...) */
71 #define PF_SELFATARI_STUPID 0
72 #define PF_SELFATARI_SMART 1
73 FEAT_SELFATARI,
75 /* Atari move. */
76 /* Payload: [bit0] The atari'd group gets laddered? */
77 #define PF_ATARI_LADDER 0
78 /* [bit1] Playing ko? */
79 #define PF_ATARI_KO 1
80 FEAT_ATARI,
82 /* Border distance. */
83 /* Payload: The distance - "line number". Only up to 4. */
84 FEAT_BORDER,
86 /* Last move distance. */
87 /* Payload: The distance - gridcular metric. */
88 FEAT_LDIST,
90 /* Next-to-last move distance. */
91 /* Payload: The distance - gridcular metric. */
92 FEAT_LLDIST,
94 /* Continuity. */
95 /* Payload: [bit0] The move is in 8-neighborhood of last move (ldist<=3) */
96 /* This is a fast substitution to ldist/lldist. */
97 FEAT_CONTIGUITY,
99 /* Spatial configuration of stones in certain board area,
100 * with black to play. */
101 /* Payload: Index in the spatial_dict. */
102 FEAT_SPATIAL,
104 /* Spatial configuration of stones in fixed 3x3 square,
105 * with black to play. */
106 /* This is a fast substitution to spatial. */
107 /* Payload: Pattern3 hash (see pattern3.h). */
108 /* Note that the hash describes only one particular rotation;
109 * no normalization across rotations and transpositions is done
110 * during the matching, only color normalization. The patternscan
111 * and gamma machineries is taking care of the rotations. */
112 FEAT_PATTERN3,
115 /* Unimplemented - TODO: */
117 /* Monte-carlo owner. */
118 /* Payload: #of playouts owning this point at the final
119 * position, scaled to 0..15 (lowest 4 bits). */
120 FEAT_MCOWNER,
122 FEAT_MAX
125 struct feature {
126 enum feature_id id;
127 uint16_t payload;
130 struct pattern {
131 /* Pattern (matched) is set of features. */
132 int n;
133 #define FEATURES 32
134 struct feature f[FEATURES];
137 struct spatial_dict;
138 struct pattern_config {
139 /* FEAT_SPATIAL: Generate patterns only for these sizes (gridcular). */
140 int spat_min, spat_max;
141 /* FEAT_BORDER: Generate features only up to this board distance. */
142 int bdist_max;
143 /* FEAT_LDIST, FEAT_LLDIST: Generate features only for these move
144 * distances. */
145 int ldist_min, ldist_max;
146 /* FEAT_MCOWNER: Generate feature after this number of simulations. */
147 int mcsims;
149 /* The spatial patterns dictionary, used by FEAT_SPATIAL. */
150 struct spatial_dict *spat_dict;
152 extern struct pattern_config DEFAULT_PATTERN_CONFIG;
153 extern struct pattern_config FAST_PATTERN_CONFIG;
155 /* The pattern_spec[] specifies which features to tests for;
156 * highest bit controls whether to test for the feature at all,
157 * then for bitmap features (except FEAT_SPATIAL) the rest
158 * of the bits controls various PF tests; for non-bitmap
159 * features, you will need to tweak the patternconfig to
160 * fine-tune them. */
161 typedef uint16_t pattern_spec[FEAT_MAX];
162 /* Match all supported features. */
163 extern pattern_spec PATTERN_SPEC_MATCHALL;
164 /* Match only "quick" features, suitable for MC simulations. */
165 extern pattern_spec PATTERN_SPEC_MATCHFAST;
168 /* Append feature to string. */
169 char *feature2str(char *str, struct feature *f);
170 /* Convert string to feature, return pointer after the featurespec. */
171 char *str2feature(char *str, struct feature *f);
172 /* Get name of given feature. */
173 char *feature_name(enum feature_id f);
174 /* Get number of possible payload values associated with the feature. */
175 int feature_payloads(struct pattern_config *pc, enum feature_id f);
177 /* Append pattern as feature spec string. */
178 char *pattern2str(char *str, struct pattern *p);
180 /* Initialize p and fill it with features matched by the
181 * given board move. */
182 void pattern_match(struct pattern_config *pc, pattern_spec ps, struct pattern *p, struct board *b, struct move *m);
185 /* Comparative strengths of all feature-payload pairs (initialized to 1 for
186 * unspecified pairs). */
187 struct features_gamma {
188 /* Indexed by feature and payload; each feature array is allocated for
189 * all possible payloads to fit in. */
190 double *gamma[FEAT_MAX];
191 struct pattern_config *pc;
193 /* Default gamma filename to use. */
194 extern const char *features_gamma_filename;
196 /* Initializes gamma values, pre-loading existing records from given file
197 * (NULL for default), falling back to gamma==1 for unspecified values. */
198 struct features_gamma *features_gamma_init(struct pattern_config *pc, const char *file);
200 /* Look up gamma of given feature, or set one if gamma is not NULL. */
201 static double feature_gamma(struct features_gamma *fg, struct feature *f, double *gamma);
203 /* Destroy the structure. */
204 void features_gamma_done(struct features_gamma *fg);
207 static inline double
208 feature_gamma(struct features_gamma *fg, struct feature *f, double *gamma)
210 if (gamma) fg->gamma[f->id][f->payload] = *gamma;
211 return fg->gamma[f->id][f->payload];
214 #endif