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 enum feature_id {
  22         /* Implemented: */
  23
  24         /* This is a pass. */
  25         /* Payload: [bit0] Last move was also pass? */
  26 #define PF_PASS_LASTPASS        0
  27         FEAT_PASS,
  28
  29         /* Simple capture move. */
  30         /* Payload: [bit0] Capturing laddered group? */
  31 #define PF_CAPTURE_LADDER       0
  32         /*          [bit1] Re-capturing last move? */
  33 #define PF_CAPTURE_RECAPTURE    1 /* TODO */
  34         /*          [bit2] Enables our atari group get more libs? */
  35 #define PF_CAPTURE_ATARIDEF     2
  36         /*          [bit3] Capturing ko? */
  37 #define PF_CAPTURE_KO           3
  38         FEAT_CAPTURE,
  39
  40         /* Atari escape (extension). */
  41         /* Payload: [bit0] Escaping with laddered group? */
  42 #define PF_AESCAPE_LADDER       0
  43         FEAT_AESCAPE,
  44
  45         /* Self-atari move. */
  46         /* Payload: [bit0] Also using our complex definition? */
  47 #define PF_SELFATARI_SMART      0 /* TODO: Non-smart */
  48         FEAT_SELFATARI,
  49
  50         /* Atari move. */
  51         /* Payload: [bit0] The atari'd group gets laddered? */
  52 #define PF_ATARI_LADDER         0
  53         /*          [bit1] Playing ko? */
  54 #define PF_ATARI_KO             1
  55         FEAT_ATARI,
  56
  57         /* Border distance. */
  58         /* Payload: The distance - "line number". Only up to 4. */
  59         FEAT_BORDER,
  60
  61         /* Last move distance. */
  62         /* Payload: The distance - gridcular metric. */
  63         FEAT_LDIST,
  64
  65         /* Next-to-last move distance. */
  66         /* Payload: The distance - gridcular metric. */
  67         FEAT_LLDIST,
  68
  69         /* Spatial configuration of stones in certain board area. */
  70         /* Payload: [bits 31-24] Pattern radius (gridcular) */
  71 #define PF_SPATIAL_RADIUS       (255 << 24)
  72         /*          [bit 23]     Who to play? (1: White) */
  73 #define PF_SPATIAL_TOPLAY       (1 << 23)
  74         /*          [other bits] Index in the spatial_dict. */
  75 #define PF_SPATIAL_INDEX        ((1 << 23) - 1)
  76         FEAT_SPATIAL,
  77
  78
  79         /* Unimplemented - TODO: */
  80
  81         /* Monte-carlo owner. */
  82         /* Payload: #of playouts owning this point at the final
  83          * position, scaled to 0..15 (lowest 4 bits). */
  84         FEAT_MCOWNER,
  85 };
  86
  87 struct feature {
  88         enum feature_id id;
  89         uint32_t payload;
  90 };
  91
  92 struct pattern {
  93         /* Pattern (matched) is set of features. */
  94         int n;
  95 #define FEATURES 32
  96         struct feature f[FEATURES];
  97 };
  98
  99 struct spatial_dict;
 100 struct pattern_config {
 101         /* FEAT_SPATIAL: Generate patterns only for these sizes (gridcular). */
 102         int spat_min, spat_max;
 103         /* FEAT_BORDER: Generate features only up to this board distance. */
 104         int bdist_max;
 105         /* FEAT_LDIST, FEAT_LLDIST: Generate features only for these move
 106          * distances. */
 107         int ldist_min, ldist_max;
 108         /* FEAT_MCOWNER: Generate feature after this number of simulations. */
 109         int mcsims;
 110
 111         /* The spatial patterns dictionary, used by FEAT_SPATIAL. */
 112         struct spatial_dict *spat_dict;
 113 };
 114 extern struct pattern_config DEFAULT_PATTERN_CONFIG;
 115
 116
 117 /* Append feature to string. */
 118 char *feature2str(char *str, struct feature *f);
 119 /* Convert string to feature, return pointer after the featurespec. */
 120 char *str2feature(char *str, struct feature *f);
 121
 122 /* Append pattern as feature spec string. */
 123 char *pattern2str(char *str, struct pattern *p);
 124
 125 /* Initialize p and fill it with features matched by the
 126  * given board move. */
 127 void pattern_match(struct pattern_config *pc, struct pattern *p, struct board *b, struct move *m);
 128
 129
 130 /* Spatial pattern dictionary. */
 131
 132 /* For each encountered configuration of stones, we keep it "spelled out"
 133  * in these records, index them and refer just the indices in the feature
 134  * payloads. This achieves several things:
 135  * * We can handle patterns of arbitrary length.
 136  * * We can recognize isomorphous configurations (color reversions,
 137  *   rotations) within the dataset.
 138  * * We can visualise patterns corresponding to chosen features.
 139  *
 140  * Thus, it goes like this:
 141  *
 142  * +----------------+   +----------------+
 143  * | struct pattern | - | struct feature |
 144  * +----------------+   |  payload    id |
 145  *                      +----------------+
 146  *                            |       FEAT_SPATIAL
 147  *                            |
 148  *                            |   ,--<--.
 149  *                            |   |     |
 150  * +-----------------------------------------+
 151  * | struct spatial_dict  spatials[]  hash[] |
 152  * +-----------------------------------------+
 153  *                            |
 154  *                    +----------------+
 155  *                    | struct spatial |
 156  *                    +----------------+
 157  */
 158
 159 /* Maximum spatial pattern diameter. */
 160 #define MAX_PATTERN_DIST 21
 161 /* Maximum number of points in spatial pattern (upper bound).
 162  * TODO: Better upper bound to save more data. */
 163 #define MAX_PATTERN_AREA (MAX_PATTERN_DIST*MAX_PATTERN_DIST)
 164
 165 /* Record for single stone configuration. */
 166 struct spatial {
 167         /* Gridcular radius of matched pattern. */
 168         uint16_t dist;
 169         /* The points; each point is two bits, corresponding
 170          * to {enum stone}. Points are ordered in gridcular-defined
 171          * spiral from middle to the edge; the dictionary file has
 172          * a comment describing the ordering at the top. */
 173         char points[MAX_PATTERN_AREA / 4];
 174 #define spatial_point_at(s, i) (((s).points[(i) / 4] >> (((i) % 4) * 2)) & 3)
 175 };
 176
 177 /* Collection of stone configurations, with two ways of lookup:
 178  * (i) by index (ii) by hash of the configuration. */
 179 struct spatial_dict {
 180         /* Indexed base store */
 181         int nspatials; /* Number of records. */
 182         struct spatial *spatials; /* Actual records. */
 183
 184         /* Hashed access; all isomorphous configurations
 185          * are also hashed */
 186 #define spatial_hash_bits 24 // ~64mib array
 187 #define spatial_hash_mask ((1 << spatial_hash_bits) - 1)
 188         /* Maps to spatials[] indices. The hash function
 189          * used is zobrist hashing with fixed values. */
 190         uint32_t hash[1 << spatial_hash_bits];
 191         /* Auxiliary collision counter, for statistics. */
 192         int collisions;
 193
 194         /* Backing store for appending patterns. */
 195         FILE *f;
 196 };
 197
 198 /* Initializes spatial dictionary, pre-loading existing records from
 199  * default filename if exists. If will_append is true, it will open
 200  * the file for appending. */
 201 struct spatial_dict *spatial_dict_init(bool will_append);
 202
 203 /* Lookup specified spatial pattern in the dictionary; return index
 204  * of the pattern. If the pattern is not found, in read-only mode
 205  * -1 will be returned, in append mode it will be added both to the
 206  * dictionary and its file. */
 207 int spatial_dict_get(struct spatial_dict *dict, struct spatial *s);
 208
 209 #endif