pattern.h

   1 #ifndef ZZGO_PATTERN_H
   2 #define ZZGO_PATTERN_H
   3
   4 /* Matching of multi-featured patterns. */
   5
   6 #include "board.h"
   7 #include "move.h"
   8
   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. */
  14
  15 /* Each feature is represented by its id and an optional 32-bit payload;
  16  * when matching, discrete (id,payload) pairs are considered. */
  17
  18 /* This is heavily influenced by (Coulom, 2007), of course. */
  19 /* TODO: Try completely separate ko / no-ko features. */
  20
  21 /* See the HACKING file for another description of the pattern matcher and
  22  * instructions on how to harvest and inspect patterns. */
  23
  24 /* If you add a payload bit for a feature, don't forget to update the value
  25  * in feature_info. */
  26 enum feature_id {
  27         /* Implemented: */
  28
  29         /* This is a pass. */
  30         /* Payload: [bit0] Last move was also pass? */
  31 #define PF_PASS_LASTPASS        0
  32         FEAT_PASS,
  33
  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
  43         FEAT_CAPTURE,
  44
  45         /* Atari escape (extension). */
  46         /* Payload: [bit0] Escaping with laddered group? */
  47 #define PF_AESCAPE_LADDER       0
  48         FEAT_AESCAPE,
  49
  50         /* Self-atari move. */
  51         /* Payload: [bit0] Also using our complex definition? */
  52 #define PF_SELFATARI_SMART      0
  53         FEAT_SELFATARI,
  54
  55         /* Atari move. */
  56         /* Payload: [bit0] The atari'd group gets laddered? */
  57 #define PF_ATARI_LADDER         0
  58         /*          [bit1] Playing ko? */
  59 #define PF_ATARI_KO             1
  60         FEAT_ATARI,
  61
  62         /* Border distance. */
  63         /* Payload: The distance - "line number". Only up to 4. */
  64         FEAT_BORDER,
  65
  66         /* Last move distance. */
  67         /* Payload: The distance - gridcular metric. */
  68         FEAT_LDIST,
  69
  70         /* Next-to-last move distance. */
  71         /* Payload: The distance - gridcular metric. */
  72         FEAT_LLDIST,
  73
  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
  80         FEAT_SPATIAL,
  81
  82
  83         /* Unimplemented - TODO: */
  84
  85         /* Monte-carlo owner. */
  86         /* Payload: #of playouts owning this point at the final
  87          * position, scaled to 0..15 (lowest 4 bits). */
  88         FEAT_MCOWNER,
  89
  90         FEAT_MAX
  91 };
  92
  93 struct feature {
  94         enum feature_id id;
  95         uint32_t payload;
  96 };
  97
  98 struct pattern {
  99         /* Pattern (matched) is set of features. */
 100         int n;
 101 #define FEATURES 32
 102         struct feature f[FEATURES];
 103 };
 104
 105 struct spatial_dict;
 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. */
 110         int bdist_max;
 111         /* FEAT_LDIST, FEAT_LLDIST: Generate features only for these move
 112          * distances. */
 113         int ldist_min, ldist_max;
 114         /* FEAT_MCOWNER: Generate feature after this number of simulations. */
 115         int mcsims;
 116
 117         /* The spatial patterns dictionary, used by FEAT_SPATIAL. */
 118         struct spatial_dict *spat_dict;
 119 };
 120 extern struct pattern_config DEFAULT_PATTERN_CONFIG;
 121 extern struct pattern_config FAST_PATTERN_CONFIG;
 122
 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
 128  * fine-tune them. */
 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;
 134
 135
 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);
 140
 141 /* Append pattern as feature spec string. */
 142 char *pattern2str(char *str, struct pattern *p);
 143
 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);
 147
 148
 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;
 156 };
 157 /* Default gamma filename to use. */
 158 extern const char *features_gamma_filename;
 159
 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);
 163
 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);
 166
 167
 168 /* Spatial pattern dictionary. */
 169
 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.
 177  *
 178  * Thus, it goes like this:
 179  *
 180  * +----------------+   +----------------+
 181  * | struct pattern | - | struct feature |
 182  * +----------------+   |  payload    id |
 183  *                      +----------------+
 184  *                            |       FEAT_SPATIAL
 185  *                            |
 186  *                            |   ,--<--.
 187  *                            |   |     |
 188  * +-----------------------------------------+
 189  * | struct spatial_dict  spatials[]  hash[] |
 190  * +-----------------------------------------+
 191  *                            |
 192  *                    +----------------+
 193  *                    | struct spatial |
 194  *                    +----------------+
 195  */
 196
 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)
 202
 203 /* Record for single stone configuration. */
 204 struct spatial {
 205         /* Gridcular radius of matched pattern. */
 206         char dist;
 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)
 213 };
 214
 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. */
 221
 222         /* Hashed access; all isomorphous configurations
 223          * are also hashed */
 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. */
 230         int collisions;
 231 };
 232 /* Default spatial dict filename to use. */
 233 extern const char *spatial_dict_filename;
 234
 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);
 239
 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);
 243
 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);
 250
 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);
 254
 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);
 259
 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);
 263
 264 #endif