uct_genmoves(): Directly execute search instead of calling uct_bestmove()
[pachi/derm.git] / patternsp.h
blob9e98a3b05b7747567bc9f5fd25f3b25322930db7
1 #ifndef ZZGO_PATTERNSP_H
2 #define ZZGO_PATTERNSP_H
4 /* Matching of spatial pattern features. */
6 #include "board.h"
7 #include "move.h"
8 #include "pattern.h"
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]). */
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)
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.
31 * Thus, it goes like this:
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 * +----------------+
51 /* Spatial record - single stone configuration. */
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)
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);
69 /* Compute hash of given spatial pattern. */
70 hash_t spatial_hash(int rotation, struct spatial *s);
72 /* Convert given spatial pattern to string. */
73 char *spatial2str(struct spatial *s);
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];
81 /* Zobrist hashes used for points in patterns. */
82 #define PTH__ROTATIONS 8
83 hash_t pthashes[PTH__ROTATIONS][MAX_PATTERN_AREA][S_MAX];
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;
91 /* Spatial dictionary - collection of stone configurations. */
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. */
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;
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);
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);
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);
124 /* Special helpers for 3x3 patterns (pattern3.h) processing: */
126 /* Return 3x3 pattern hash matching dist=3 spatial. */
127 int spatial_to_pattern3(struct spatial *s);
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 int pattern3_by_spatial(struct spatial_dict *dict, int pat3);
135 /* Spatial dictionary file manipulation. */
137 /* Loading routine is not exported, it is called automatically within
138 * spatial_dict_init(). */
140 /* Default spatial dict filename to use. */
141 extern const char *spatial_dict_filename;
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);
147 /* Append specified spatial pattern to the given file. */
148 void spatial_write(struct spatial_dict *dict, struct spatial *s, int id, FILE *f);
151 static inline int
152 spatial_dict_get(struct spatial_dict *dict, int dist, hash_t hash)
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;
162 #endif
163 return id;
166 #endif