patternsp.h

   1 #ifndef ZZGO_PATTERNSP_H
   2 #define ZZGO_PATTERNSP_H
   3
   4 /* Matching of spatial pattern features. */
   5
   6 #include "board.h"
   7 #include "move.h"
   8 #include "pattern.h"
   9
  10 /* Spatial stone configuration pattern features - like pattern3 handles
  11  * 3x3-area, this handles general N-area (where N is distance in
  12  * gridcular metric). These routines define the dictionary of spatial
  13  * configurations (accessible by zobrist hashes or indices) and related
  14  * data structures; eventually, they support the FEAT_SPATIAL pattern
  15  * feature implementation in the General Pattern Matcher (pattern.[ch]). */
  16
  17 /* Maximum spatial pattern diameter. */
  18 #define MAX_PATTERN_DIST 5
  19 /* Maximum number of points in spatial pattern (upper bound).
  20  * TODO: Better upper bound to save more data. */
  21 #define MAX_PATTERN_AREA (MAX_PATTERN_DIST*MAX_PATTERN_DIST)
  22
  23 /* For each encountered configuration of stones, we keep it "spelled out"
  24  * in the spatial dictionary records, index them and refer just the indices
  25  * in the feature payloads. This achieves several things:
  26  * * We can handle patterns of arbitrary length.
  27  * * We can recognize isomorphous configurations (color reversions,
  28  *   rotations) within the dataset.
  29  * * We can visualise patterns corresponding to chosen features.
  30  *
  31  * Thus, it goes like this:
  32  *
  33  * +----------------+   +----------------+
  34  * | struct pattern | - | struct feature |
  35  * +----------------+   |  payload    id |
  36  *                      +----------------+
  37  *                            |       FEAT_SPATIAL
  38  *                            |
  39  *                            |   ,--<--.
  40  *                            |   |     |
  41  * +-----------------------------------------+
  42  * | struct spatial_dict  spatials[]  hash[] |
  43  * +-----------------------------------------+
  44  *                            |
  45  *                    +----------------+
  46  *                    | struct spatial |
  47  *                    +----------------+
  48  */
  49
  50
  51 /* Spatial record - single stone configuration. */
  52
  53 struct spatial {
  54         /* Gridcular radius of matched pattern. */
  55         char dist;
  56         /* The points; each point is two bits, corresponding
  57          * to {enum stone}. Points are ordered in gridcular-defined
  58          * spiral from middle to the edge; the dictionary file has
  59          * a comment describing the ordering at the top. */
  60         char points[MAX_PATTERN_AREA / 4];
  61 #define spatial_point_at(s, i) (((s).points[(i) / 4] >> (((i) % 4) * 2)) & 3)
  62 };
  63
  64 /* Fill up the spatial record from @m vincinity, up to full distance
  65  * given by pattern config. */
  66 struct pattern_config;
  67 void spatial_from_board(struct pattern_config *pc, struct spatial *s, struct board *b, struct move *m);
  68
  69 /* Compute hash of given spatial pattern. */
  70 hash_t spatial_hash(int rotation, struct spatial *s);
  71
  72 /* Convert given spatial pattern to string. */
  73 char *spatial2str(struct spatial *s);
  74
  75 /* Mapping from point sequence to coordinate offsets (to determine
  76  * coordinates relative to pattern center). */
  77 struct ptcoord { short x, y; } ptcoords[MAX_PATTERN_AREA];
  78 /* For each radius, starting index in ptcoords[]. */
  79 int ptind[MAX_PATTERN_DIST + 2];
  80
  81 /* Zobrist hashes used for points in patterns. */
  82 #define PTH__ROTATIONS  8
  83 hash_t pthashes[PTH__ROTATIONS][MAX_PATTERN_AREA][S_MAX];
  84
  85 #define ptcoords_at(x_, y_, c_, b_, j_) \
  86         int x_ = coord_x((c_), (b_)) + ptcoords[j_].x; \
  87         int y_ = coord_y((c_), (b_)) + ptcoords[j_].y; \
  88         if (x_ >= board_size(b_)) x_ = board_size(b_) - 1; else if (x_ < 0) x_ = 0; \
  89         if (y_ >= board_size(b_)) y_ = board_size(b_) - 1; else if (y_ < 0) y_ = 0;
  90
  91 /* Spatial dictionary - collection of stone configurations. */
  92
  93 /* Two ways of lookup: (i) by index (ii) by hash of the configuration. */
  94 struct spatial_dict {
  95         /* Indexed base store */
  96         int nspatials; /* Number of records. */
  97         struct spatial *spatials; /* Actual records. */
  98
  99         /* Hashed access; all isomorphous configurations
 100          * are also hashed */
 101 #define spatial_hash_bits 24 // ~64mib array
 102 #define spatial_hash_mask ((1 << spatial_hash_bits) - 1)
 103         /* Maps to spatials[] indices. The hash function
 104          * used is zobrist hashing with fixed values. */
 105         uint32_t hash[1 << spatial_hash_bits];
 106         /* Auxiliary collision counter, for statistics. */
 107         int collisions;
 108 };
 109
 110 /* Initializes spatial dictionary, pre-loading existing records from
 111  * default filename if exists. If will_append is true, it will not
 112  * complain about non-existing file and initialize the dictionary anyway. */
 113 struct spatial_dict *spatial_dict_init(bool will_append);
 114
 115 /* Lookup specified spatial pattern in the dictionary; return index
 116  * of the pattern. If the pattern is not found, 0 will be returned. */
 117 static int spatial_dict_get(struct spatial_dict *dict, int dist, hash_t h);
 118
 119 /* Store specified spatial pattern in the dictionary if it is not known yet.
 120  * Returns pattern id. Note that the pattern is NOT written to the underlying
 121  * file automatically. */
 122 int spatial_dict_put(struct spatial_dict *dict, struct spatial *s, hash_t);
 123
 124 /* Special helpers for 3x3 patterns (pattern3.h) processing: */
 125
 126 /* Return 3x3 pattern hash matching dist=3 spatial. */
 127 hash3_t spatial_to_pattern3(struct spatial *s);
 128
 129 /* Return canonical 3x3 pattern hash (from space of rotations and
 130  * transpositions) based on the appropriate master record in the spatial
 131  * dictionary. */
 132 hash3_t pattern3_by_spatial(struct spatial_dict *dict, hash3_t pat3);
 133
 134
 135 /* Spatial dictionary file manipulation. */
 136
 137 /* Loading routine is not exported, it is called automatically within
 138  * spatial_dict_init(). */
 139
 140 /* Default spatial dict filename to use. */
 141 extern const char *spatial_dict_filename;
 142
 143 /* Write comment lines describing the dictionary (e.g. point order
 144  * in patterns) to given file. */
 145 void spatial_dict_writeinfo(struct spatial_dict *dict, FILE *f);
 146
 147 /* Append specified spatial pattern to the given file. */
 148 void spatial_write(struct spatial_dict *dict, struct spatial *s, int id, FILE *f);
 149
 150
 151 static inline int
 152 spatial_dict_get(struct spatial_dict *dict, int dist, hash_t hash)
 153 {
 154         int id = dict->hash[hash];
 155 #ifdef DEBUG
 156         if (id && dict->spatials[id].dist != dist) {
 157                 if (DEBUGL(6))
 158                         fprintf(stderr, "Collision dist %d vs %d (hash [%d]%"PRIhash")\n",
 159                                 dist, dict->spatials[id].dist, id, hash);
 160                 return 0;
 161         }
 162 #endif
 163         return id;
 164 }
 165
 166 #endif