?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
Pattern FEAT_SPATIAL: Don't encode radius in the payload
[pachi.git] / pattern.c
blobd1825a1fd432979a938df3a5e7a54fe23d09446c
1 #define DEBUG
2 #include <assert.h>
3 #include <ctype.h>
4 #include <inttypes.h>
5 #include <stdio.h>
6 #include <stdlib.h>
7
8 #include "board.h"
9 #include "debug.h"
10 #include "pattern.h"
11 #include "patternsp.h"
12 #include "tactics.h"
13
14
15 struct pattern_config DEFAULT_PATTERN_CONFIG = {
16 .spat_min = 3, .spat_max = MAX_PATTERN_DIST,
17 .bdist_max = 4,
18 .ldist_min = 0, .ldist_max = 256,
19 .mcsims = 0, /* Unsupported. */
20 };
21
22 struct pattern_config FAST_PATTERN_CONFIG = {
23 .spat_min = 3, .spat_max = 3,
24 .bdist_max = 4,
25 .ldist_min = 0, .ldist_max = 256,
26 .mcsims = 0,
27 };
28
29 pattern_spec PATTERN_SPEC_MATCHALL = {
30 [FEAT_PASS] = ~0,
31 [FEAT_CAPTURE] = ~0,
32 [FEAT_AESCAPE] = ~0,
33 [FEAT_SELFATARI] = ~0,
34 [FEAT_ATARI] = ~0,
35 [FEAT_BORDER] = ~0,
36 [FEAT_LDIST] = ~0,
37 [FEAT_LLDIST] = ~0,
38 [FEAT_CONTIGUITY] = ~0,
39 [FEAT_SPATIAL] = ~0,
40 [FEAT_MCOWNER] = ~0,
41 };
42
43 #define FAST_NO_LADDER 1 /* 1: Don't match ladders in fast playouts */
44 pattern_spec PATTERN_SPEC_MATCHFAST = {
45 [FEAT_PASS] = ~0,
46 [FEAT_CAPTURE] = ~(1<<PF_CAPTURE_ATARIDEF | 1<<PF_CAPTURE_RECAPTURE | FAST_NO_LADDER<<PF_CAPTURE_LADDER),
47 [FEAT_AESCAPE] = ~(FAST_NO_LADDER<<PF_AESCAPE_LADDER),
48 [FEAT_SELFATARI] = ~(1<<PF_SELFATARI_SMART),
49 [FEAT_ATARI] = ~(FAST_NO_LADDER<<PF_ATARI_LADDER),
50 [FEAT_BORDER] = 0,
51 [FEAT_LDIST] = 0,
52 [FEAT_LLDIST] = 0,
53 [FEAT_CONTIGUITY] = ~0,
54 [FEAT_SPATIAL] = ~0,
55 [FEAT_MCOWNER] = ~0,
56 };
57
58 static const struct feature_info {
59 char *name;
60 int payloads;
61 } features[FEAT_MAX] = {
62 [FEAT_PASS] = { .name = "pass", .payloads = 2 },
63 [FEAT_CAPTURE] = { .name = "capture", .payloads = 16 },
64 [FEAT_AESCAPE] = { .name = "atariescape", .payloads = 2 },
65 [FEAT_SELFATARI] = { .name = "selfatari", .payloads = 2 },
66 [FEAT_ATARI] = { .name = "atari", .payloads = 4 },
67 [FEAT_BORDER] = { .name = "border", .payloads = -1 },
68 [FEAT_LDIST] = { .name = "ldist", .payloads = -1 },
69 [FEAT_LLDIST] = { .name = "lldist", .payloads = -1 },
70 [FEAT_CONTIGUITY] = { .name = "cont", .payloads = 2 },
71 [FEAT_SPATIAL] = { .name = "s", .payloads = -1 },
72 [FEAT_MCOWNER] = { .name = "mcowner", .payloads = 16 },
73 };
74
75 char *
76 feature2str(char *str, struct feature *f)
77 {
78 return str + sprintf(str + strlen(str), "%s:%"PRIx32, features[f->id].name, f->payload);
79 }
80
81 char *
82 str2feature(char *str, struct feature *f)
83 {
84 while (isspace(*str)) str++;
85
86 int flen = strcspn(str, ":");
87 for (int i = 0; i < sizeof(features)/sizeof(features[0]); i++)
88 if (strlen(features[i].name) == flen && !strncmp(features[i].name, str, flen)) {
89 f->id = i;
90 goto found;
91 }
92 fprintf(stderr, "invalid featurespec: %s[%d]\n", str, flen);
93 exit(EXIT_FAILURE);
94
95 found:
96 str += flen + 1;
97 f->payload = strtoull(str, &str, 16);
98 return str;
99 }
100
101
102 /* pattern_spec helpers */
103 #define PS_ANY(F) (ps[FEAT_ ## F] & (1 << 31))
104 #define PS_PF(F, P) (ps[FEAT_ ## F] & (1 << PF_ ## F ## _ ## P))
105
106 static struct feature *
107 pattern_match_capture(struct pattern_config *pc, pattern_spec ps,
108 struct pattern *p, struct feature *f,
109 struct board *b, struct move *m)
110 {
111 foreach_neighbor(b, m->coord, {
112 if (board_at(b, c) != stone_other(m->color))
113 continue;
114 group_t g = group_at(b, c);
115 if (!g || board_group_info(b, g).libs != 1)
116 continue;
117
118 /* Capture! */
119 f->id = FEAT_CAPTURE; f->payload = 0;
120
121 if (PS_PF(CAPTURE, LADDER))
122 f->payload |= is_ladder(b, m->coord, g, true, true) << PF_CAPTURE_LADDER;
123 /* TODO: is_ladder() is too conservative in some
124 * very obvious situations, look at complete.gtp. */
125
126 /* TODO: PF_CAPTURE_RECAPTURE */
127
128 if (PS_PF(CAPTURE, ATARIDEF))
129 foreach_in_group(b, g) {
130 foreach_neighbor(b, c, {
131 assert(board_at(b, c) != S_NONE || c == m->coord);
132 if (board_at(b, c) != m->color)
133 continue;
134 group_t g = group_at(b, c);
135 if (!g || board_group_info(b, g).libs != 1)
136 continue;
137 /* A neighboring group of ours is in atari. */
138 f->payload |= 1 << PF_CAPTURE_ATARIDEF;
139 });
140 } foreach_in_group_end;
141
142 if (PS_PF(CAPTURE, KO)
143 && group_is_onestone(b, g)
144 && neighbor_count_at(b, m->coord, stone_other(m->color))
145 + neighbor_count_at(b, m->coord, S_OFFBOARD) == 4)
146 f->payload |= 1 << PF_CAPTURE_KO;
147
148 (f++, p->n++);
149 });
150 return f;
151 }
152
153 static struct feature *
154 pattern_match_aescape(struct pattern_config *pc, pattern_spec ps,
155 struct pattern *p, struct feature *f,
156 struct board *b, struct move *m)
157 {
158 /* Find if a neighboring group of ours is in atari, AND that we provide
159 * a liberty to connect out. XXX: No connect-and-die check. */
160 group_t in_atari = -1;
161 bool has_extra_lib = false;
162 int payload = 0;
163
164 foreach_neighbor(b, m->coord, {
165 if (board_at(b, c) != m->color) {
166 if (board_at(b, c) == S_NONE)
167 has_extra_lib = true; // free point
168 else if (board_at(b, c) == stone_other(m->color) && board_group_info(b, group_at(b, c)).libs == 1)
169 has_extra_lib = true; // capturable enemy group
170 continue;
171 }
172 group_t g = group_at(b, c); assert(g);
173 if (board_group_info(b, g).libs != 1) {
174 has_extra_lib = true;
175 continue;
176 }
177
178 /* In atari! */
179 in_atari = g;
180
181 if (PS_PF(AESCAPE, LADDER))
182 payload |= is_ladder(b, m->coord, g, true, true) << PF_AESCAPE_LADDER;
183 /* TODO: is_ladder() is too conservative in some
184 * very obvious situations, look at complete.gtp. */
185 });
186 if (in_atari >= 0 && has_extra_lib) {
187 f->id = FEAT_AESCAPE; f->payload = payload;
188 (f++, p->n++);
189 }
190 return f;
191 }
192
193 static struct feature *
194 pattern_match_atari(struct pattern_config *pc, pattern_spec ps,
195 struct pattern *p, struct feature *f,
196 struct board *b, struct move *m)
197 {
198 foreach_neighbor(b, m->coord, {
199 if (board_at(b, c) != stone_other(m->color))
200 continue;
201 group_t g = group_at(b, c);
202 if (!g || board_group_info(b, g).libs != 2)
203 continue;
204
205 /* Can atari! */
206 f->id = FEAT_ATARI; f->payload = 0;
207
208 if (PS_PF(ATARI, LADDER)) {
209 /* Opponent will escape by the other lib. */
210 coord_t lib = board_group_info(b, g).lib[0];
211 if (lib == m->coord) lib = board_group_info(b, g).lib[1];
212 /* TODO: is_ladder() is too conservative in some
213 * very obvious situations, look at complete.gtp. */
214 f->payload |= is_ladder(b, lib, g, true, true) << PF_ATARI_LADDER;
215 }
216
217 if (PS_PF(ATARI, KO) && !is_pass(b->ko.coord))
218 f->payload |= 1 << PF_ATARI_KO;
219
220 (f++, p->n++);
221 });
222 return f;
223 }
224
225 #ifndef BOARD_SPATHASH
226 #undef BOARD_SPATHASH_MAXD
227 #define BOARD_SPATHASH_MAXD 1
228 #endif
229
230 /* Match spatial features that are too distant to be pre-matched
231 * incrementally. */
232 struct feature *
233 pattern_match_spatial_outer(struct pattern_config *pc, pattern_spec ps,
234 struct pattern *p, struct feature *f,
235 struct board *b, struct move *m, hash_t h)
236 {
237 /* We record all spatial patterns black-to-play; simply
238 * reverse all colors if we are white-to-play. */
239 static enum stone bt_black[4] = { S_NONE, S_BLACK, S_WHITE, S_OFFBOARD };
240 static enum stone bt_white[4] = { S_NONE, S_WHITE, S_BLACK, S_OFFBOARD };
241 enum stone (*bt)[4] = m->color == S_WHITE ? &bt_white : &bt_black;
242
243 for (int d = BOARD_SPATHASH_MAXD + 1; d <= pc->spat_max; d++) {
244 /* Recompute missing outer circles:
245 * Go through all points in given distance. */
246 for (int j = ptind[d]; j < ptind[d + 1]; j++) {
247 ptcoords_at(x, y, m->coord, b, j);
248 h ^= pthashes[0][j][(*bt)[board_atxy(b, x, y)]];
249 }
250 if (d < pc->spat_min)
251 continue;
252 /* Record spatial feature, one per distance. */
253 int sid = spatial_dict_get(pc->spat_dict, d, h & spatial_hash_mask);
254 if (sid > 0) {
255 f->id = FEAT_SPATIAL;
256 f->payload = sid;
257 (f++, p->n++);
258 } /* else not found, ignore */
259 }
260 return f;
261 }
262
263 struct feature *
264 pattern_match_spatial(struct pattern_config *pc, pattern_spec ps,
265 struct pattern *p, struct feature *f,
266 struct board *b, struct move *m)
267 {
268 /* XXX: This is partially duplicated from spatial_from_board(), but
269 * we build a hash instead of spatial record. */
270
271 assert(pc->spat_min > 0);
272
273 bool w_to_play = m->color == S_WHITE;
274 hash_t h = pthashes[0][0][S_NONE];
275 for (int d = 2; d <= BOARD_SPATHASH_MAXD; d++) {
276 /* Reuse all incrementally matched data. */
277 h ^= b->spathash[m->coord][d - 1][w_to_play];
278 if (d < pc->spat_min)
279 continue;
280 /* Record spatial feature, one per distance. */
281 int sid = spatial_dict_get(pc->spat_dict, d, h & spatial_hash_mask);
282 if (sid > 0) {
283 f->id = FEAT_SPATIAL;
284 f->payload = sid;
285 (f++, p->n++);
286 } /* else not found, ignore */
287 }
288 if (unlikely(pc->spat_max > BOARD_SPATHASH_MAXD))
289 f = pattern_match_spatial_outer(pc, ps, p, f, b, m, h);
290 return f;
291 }
292
293
294 static bool
295 is_simple_selfatari(struct board *b, enum stone color, coord_t coord)
296 {
297 /* Very rough check, no connect-and-die checks or other trickery. */
298 int libs = immediate_liberty_count(b, coord);
299 if (libs >= 2) return false; // open space
300
301 group_t seen = -1;
302 foreach_neighbor(b, coord, {
303 if (board_at(b, c) == stone_other(color) && board_group_info(b, group_at(b, c)).libs == 1) {
304 return false; // can capture
305
306 } else if (board_at(b, c) == color) {
307 // friendly group, does it have liberties?
308 group_t g = group_at(b, c);
309 if (board_group_info(b, g).libs == 1 || seen == g)
310 continue;
311 libs += board_group_info(b, g).libs - 1;
312 if (libs >= 2) return false;
313 // don't consider the same group twice
314 seen = g;
315 }
316 });
317 return true;
318 }
319
320 void
321 pattern_match(struct pattern_config *pc, pattern_spec ps,
322 struct pattern *p, struct board *b, struct move *m)
323 {
324 p->n = 0;
325 struct feature *f = &p->f[0];
326
327 /* TODO: We should match pretty much all of these features
328 * incrementally. */
329
330 if (is_pass(m->coord)) {
331 if (PS_ANY(PASS)) {
332 f->id = FEAT_PASS; f->payload = 0;
333 if (PS_PF(PASS, LASTPASS))
334 f->payload |= (b->moves > 0 && is_pass(b->last_move.coord))
335 << PF_PASS_LASTPASS;
336 p->n++;
337 }
338 return;
339 }
340
341 if (PS_ANY(CAPTURE)) {
342 f = pattern_match_capture(pc, ps, p, f, b, m);
343 }
344
345 if (PS_ANY(AESCAPE)) {
346 f = pattern_match_aescape(pc, ps, p, f, b, m);
347 }
348
349 if (PS_ANY(SELFATARI)) {
350 bool simple = is_simple_selfatari(b, m->color, m->coord);
351 bool thorough = false;
352 if (PS_PF(SELFATARI, SMART)) {
353 thorough = is_bad_selfatari(b, m->color, m->coord);
354 }
355 if (simple || thorough) {
356 f->id = FEAT_SELFATARI;
357 f->payload = thorough << PF_SELFATARI_SMART;
358 (f++, p->n++);
359 }
360 }
361
362 if (PS_ANY(ATARI)) {
363 f = pattern_match_atari(pc, ps, p, f, b, m);
364 }
365
366 if (PS_ANY(BORDER)) {
367 int bdist = coord_edge_distance(m->coord, b);
368 if (bdist <= pc->bdist_max) {
369 f->id = FEAT_BORDER;
370 f->payload = bdist;
371 (f++, p->n++);
372 }
373 }
374
375 if (PS_ANY(LDIST) && pc->ldist_max > 0 && !is_pass(b->last_move.coord)) {
376 int ldist = coord_gridcular_distance(m->coord, b->last_move.coord, b);
377 if (pc->ldist_min <= ldist && ldist <= pc->ldist_max) {
378 f->id = FEAT_LDIST;
379 f->payload = ldist;
380 (f++, p->n++);
381 }
382 }
383
384 if (PS_ANY(CONTIGUITY) && !is_pass(b->last_move.coord)
385 && coord_is_8adjecent(m->coord, b->last_move.coord, b)) {
386 f->id = FEAT_CONTIGUITY;
387 f->payload = 1;
388 (f++, p->n++);
389 }
390
391 if (PS_ANY(LLDIST) && pc->ldist_max > 0 && !is_pass(b->last_move2.coord)) {
392 int lldist = coord_gridcular_distance(m->coord, b->last_move2.coord, b);
393 if (pc->ldist_min <= lldist && lldist <= pc->ldist_max) {
394 f->id = FEAT_LLDIST;
395 f->payload = lldist;
396 (f++, p->n++);
397 }
398 }
399
400 if (PS_ANY(SPATIAL) && pc->spat_max > 0 && pc->spat_dict) {
401 f = pattern_match_spatial(pc, ps, p, f, b, m);
402 }
403
404 /* FEAT_MCOWNER: TODO */
405 assert(!pc->mcsims);
406 }
407
408 char *
409 pattern2str(char *str, struct pattern *p)
410 {
411 str = stpcpy(str, "(");
412 for (int i = 0; i < p->n; i++) {
413 if (i > 0) str = stpcpy(str, " ");
414 str = feature2str(str, &p->f[i]);
415 }
416 str = stpcpy(str, ")");
417 return str;
418 }
419
420
421
422 /*** Features gamma set */
423
424 static void
425 features_gamma_load(struct features_gamma *fg, const char *filename)
426 {
427 FILE *f = fopen(filename, "r");
428 if (!f) return;
429 char buf[256];
430 while (fgets(buf, 256, f)) {
431 char *bufp = buf;
432 struct feature f;
433 bufp = str2feature(bufp, &f);
434 while (isspace(*bufp)) bufp++;
435 float gamma = strtof(bufp, &bufp);
436 feature_gamma(fg, &f, &gamma);
437 }
438 fclose(f);
439 }
440
441 const char *features_gamma_filename = "patterns.gamma";
442
443 struct features_gamma *
444 features_gamma_init(struct pattern_config *pc, const char *file)
445 {
446 struct features_gamma *fg = calloc(1, sizeof(*fg));
447 fg->pc = pc;
448 for (int i = 0; i < FEAT_MAX; i++) {
449 int n = features[i].payloads;
450 if (n <= 0) {
451 switch (i) {
452 case FEAT_SPATIAL:
453 n = pc->spat_dict->nspatials; break;
454 case FEAT_LDIST:
455 case FEAT_LLDIST:
456 n = pc->ldist_max + 1; break;
457 case FEAT_BORDER:
458 n = pc->bdist_max + 1; break;
459 default:
460 assert(0);
461 }
462 }
463 fg->gamma[i] = malloc(n * sizeof(float));
464 for (int j = 0; j < n; j++) {
465 fg->gamma[i][j] = 1.0f;
466 }
467 }
468 features_gamma_load(fg, file ? file : features_gamma_filename);
469 return fg;
470 }
Pachi Simple Go/Baduk/Weiqi Bot