Moggy: Raise default patternrate from 75 to 95, since we have better patterns now
[pachi/peepo.git] / playout / moggy.c
blob09157bfbdd8d23a51dd1149578c814083886de55
1 #include <assert.h>
2 #include <math.h>
3 #include <stdio.h>
4 #include <stdlib.h>
6 #define DEBUG
7 #include "board.h"
8 #include "debug.h"
9 #include "playout.h"
10 #include "playout/moggy.h"
11 #include "random.h"
13 #define PLDEBUGL(n) DEBUGL_(p->debug_level, n)
16 struct moggy_policy {
17 bool ladders, ladderassess, borderladders;
18 int lcapturerate, capturerate, patternrate;
21 #define MQL 64
22 struct move_queue {
23 int moves;
24 coord_t move[MQL];
28 /* Pattern encoding:
29 * X: black; O: white; .: empty; #: edge
30 * x: !black; o: !white; ?: any
32 * extra X: pattern valid only for one side;
33 * middle point ignored. */
35 static char moggy_patterns_src[][11] = {
36 /* hane pattern - enclosing hane */
37 "XOX"
38 "..."
39 "???",
40 /* hane pattern - non-cutting hane */
41 "XO."
42 "..."
43 "?.?",
44 /* hane pattern - magari */
45 "XO?"
46 "X.."
47 "?.?",
48 /* hane pattern - thin hane (SUSPICIOUS) */
49 "XOO"
50 "..."
51 "?.?" "X",
52 /* cut1 pattern (kiri) - unprotected cut */
53 "XO?"
54 "O.o"
55 "?o?",
56 /* cut1 pattern (kiri) - peeped cut */
57 "XO?"
58 "O.X"
59 "???",
60 /* cut2 pattern (de) */
61 "?X?"
62 "O.O"
63 "ooo",
64 /* side pattern - chase */
65 "X.?"
66 "O.?"
67 "##?",
68 /* side pattern - weirdness (SUSPICIOUS) */
69 "?X?"
70 "X.O"
71 "###",
72 /* side pattern - sagari (SUSPICIOUS) */
73 "?XO"
74 "?.?" /* "?.x" ? */
75 "###" "X",
76 /* side pattern - weirdcut (SUSPICIOUS) */
77 "?OX"
78 "?.O"
79 "?##" "X",
80 /* side pattern - cut (SUSPICIOUS) */
81 "?OX"
82 "X.O"
83 "###" "X" /* no "X"? */,
85 #define moggy_patterns_src_n sizeof(moggy_patterns_src) / sizeof(moggy_patterns_src[0])
87 /* Hashtable: 2*8 bits (ignore middle point, 2 bits per intersection) */
88 /* Value: 0: no pattern, 1: black pattern, 2: white pattern, 3: both patterns */
89 static char moggy_patterns[65536];
91 static void
92 _record_pattern(char *table, int pat, int fixed_color)
94 /* Original color assignment */
95 table[pat] = fixed_color ? fixed_color : 3;
97 /* Reverse color assignment - achieved by swapping odd and even bits */
98 pat = ((pat >> 1) & 0x5555) | ((pat & 0x5555) << 1);
99 table[pat] = fixed_color ? 2 - (fixed_color == 2) : 3;
102 static void
103 _gen_pattern(char *table, int pat, char *src, int srclen, int fixed_color)
105 for (; srclen > 0; src++, srclen--) {
106 if (srclen == 5)
107 continue;
108 int patofs = (srclen > 5 ? srclen - 1 : srclen) - 1;
109 switch (*src) {
110 case '?':
111 *src = '.'; _gen_pattern(table, pat, src, srclen, fixed_color);
112 *src = 'X'; _gen_pattern(table, pat, src, srclen, fixed_color);
113 *src = 'O'; _gen_pattern(table, pat, src, srclen, fixed_color);
114 *src = '#'; _gen_pattern(table, pat, src, srclen, fixed_color);
115 *src = '?'; // for future recursions
116 return;
117 case 'x':
118 *src = '.'; _gen_pattern(table, pat, src, srclen, fixed_color);
119 *src = 'O'; _gen_pattern(table, pat, src, srclen, fixed_color);
120 *src = '#'; _gen_pattern(table, pat, src, srclen, fixed_color);
121 *src = 'x'; // for future recursions
122 return;
123 case 'o':
124 *src = '.'; _gen_pattern(table, pat, src, srclen, fixed_color);
125 *src = 'X'; _gen_pattern(table, pat, src, srclen, fixed_color);
126 *src = '#'; _gen_pattern(table, pat, src, srclen, fixed_color);
127 *src = 'o'; // for future recursions
128 return;
129 case '.': /* 0 */ break;
130 case 'X': pat |= S_BLACK << (patofs * 2); break;
131 case 'O': pat |= S_WHITE << (patofs * 2); break;
132 case '#': pat |= S_OFFBOARD << (patofs * 2); break;
136 /* Original pattern */
137 //fprintf(stderr, "[%s] %04x\n", src - 9, pat);
138 _record_pattern(table, pat, fixed_color);
139 /* V/H mirror pattern; reverse order of all 2-bit values */
141 int p2 = pat;
142 p2 = ((p2 >> 2) & 0x3333) | ((p2 & 0x3333) << 2);
143 p2 = ((p2 >> 4) & 0x0F0F) | ((p2 & 0x0F0F) << 4);
144 p2 = ((p2 >> 8) & 0x00FF) | ((p2 & 0x00FF) << 8);
145 //fprintf(stderr, "[%s] %04x\n", src - 9, p2);
146 _record_pattern(table, p2, fixed_color);
148 /* V mirror pattern; reverse order of 3-2-3 chunks */
150 int p2 = ((pat & 0xfc00) >> 10) | (pat & 0x03c0) | ((pat & 0x003f) << 10);
151 //fprintf(stderr, "[%s] %04x\n", src - 9, p2);
152 _record_pattern(table, p2, fixed_color);
153 /* H mirror pattern; reverse this bitstring */
154 p2 = ((p2 >> 2) & 0x3333) | ((p2 & 0x3333) << 2);
155 p2 = ((p2 >> 4) & 0x0F0F) | ((p2 & 0x0F0F) << 4);
156 p2 = ((p2 >> 8) & 0x00FF) | ((p2 & 0x00FF) << 8);
157 //fprintf(stderr, "[%s] %04x\n", src - 9, p2);
158 _record_pattern(table, p2, fixed_color);
162 static void __attribute__((constructor))
163 _init_patterns(void)
165 for (int i = 0; i < moggy_patterns_src_n; i++) {
166 int fixed_color = 0;
167 switch (moggy_patterns_src[i][9]) {
168 case 'X': fixed_color = S_BLACK; break;
169 case 'O': fixed_color = S_WHITE; break;
171 _gen_pattern(moggy_patterns, 0, moggy_patterns_src[i], 9, fixed_color);
177 /* Check if we match any pattern centered on given move. */
178 static bool
179 test_pattern_here(struct playout_policy *p, char *hashtable,
180 struct board *b, struct move *m)
182 int pat = 0;
183 int x = coord_x(m->coord, b), y = coord_y(m->coord, b);
184 pat |= (board_atxy(b, x - 1, y - 1) << 14)
185 | (board_atxy(b, x, y - 1) << 12)
186 | (board_atxy(b, x + 1, y - 1) << 10);
187 pat |= (board_atxy(b, x - 1, y) << 8)
188 | (board_atxy(b, x + 1, y) << 6);
189 pat |= (board_atxy(b, x - 1, y + 1) << 4)
190 | (board_atxy(b, x, y + 1) << 2)
191 | (board_atxy(b, x + 1, y + 1));
192 //fprintf(stderr, "(%d,%d) hashtable[%04x] = %d\n", x, y, pat, hashtable[pat]);
193 return (hashtable[pat] & m->color);
196 static void
197 apply_pattern_here(struct playout_policy *p, char *hashtable,
198 struct board *b, struct move *m, struct move_queue *q)
200 if (test_pattern_here(p, hashtable, b, m))
201 q->move[q->moves++] = m->coord;
204 /* Check if we match any pattern around given move (with the other color to play). */
205 static coord_t
206 apply_pattern(struct playout_policy *p, struct board *b, struct move *m, struct move *testmove)
208 //struct moggy_policy *pp = p->data;
209 struct move_queue q;
210 q.moves = 0;
212 /* Suicides do not make any patterns and confuse us. */
213 if (board_at(b, m->coord) == S_NONE || board_at(b, m->coord) == S_OFFBOARD)
214 return pass;
216 // FIXME: Fix assess callers
217 foreach_neighbor(b, m->coord, {
218 struct move m2; m2.coord = c; m2.color = stone_other(m->color);
219 if (board_at(b, c) == S_NONE && board_is_eyelike(b, &c, m->color))
220 apply_pattern_here(p, moggy_patterns, b, &m2, &q);
222 foreach_diag_neighbor(b, m->coord) {
223 struct move m2; m2.coord = c; m2.color = stone_other(m->color);
224 if (board_at(b, c) == S_NONE && board_is_eyelike(b, &c, m->color))
225 apply_pattern_here(p, moggy_patterns, b, &m2, &q);
226 } foreach_diag_neighbor_end;
228 if (PLDEBUGL(5)) {
229 fprintf(stderr, "Pattern candidate moves: ");
230 for (int i = 0; i < q.moves; i++) {
231 fprintf(stderr, "%s ", coord2sstr(q.move[i], b));
233 fprintf(stderr, "\n");
236 if (testmove) {
237 while (q.moves--)
238 if (q.move[q.moves] == testmove->coord) {
239 if (PLDEBUGL(5))
240 fprintf(stderr, "Found queried move.\n");
241 return testmove->coord;
243 return pass;
246 int i = fast_random(q.moves);
247 return q.moves ? q.move[i] : pass;
252 /* Is this ladder breaker friendly for the one who catches ladder. */
253 static bool
254 ladder_catcher(struct board *b, int x, int y, enum stone laddered)
256 enum stone breaker = board_atxy(b, x, y);
257 return breaker == stone_other(laddered) || breaker == S_OFFBOARD;
260 static bool
261 ladder_catches(struct playout_policy *p, struct board *b, coord_t coord, group_t laddered)
263 struct moggy_policy *pp = p->data;
265 /* This is very trivial and gets a lot of corner cases wrong.
266 * We need this to be just very fast. One important point is
267 * that we sometimes might not notice a ladder but if we do,
268 * it should always work; thus we can use this for strong
269 * negative hinting safely. */
270 //fprintf(stderr, "ladder check\n");
272 enum stone lcolor = board_at(b, group_base(laddered));
273 int x = coord_x(coord, b), y = coord_y(coord, b);
275 /* First, special-case first-line "ladders". This is a huge chunk
276 * of ladders we actually meet and want to play. */
277 if (pp->borderladders
278 && neighbor_count_at(b, coord, S_OFFBOARD) == 1
279 && neighbor_count_at(b, coord, lcolor) == 1) {
280 if (PLDEBUGL(5))
281 fprintf(stderr, "border ladder\n");
282 /* Direction along border; xd is horiz. border, yd vertical. */
283 int xd = 0, yd = 0;
284 if (board_atxy(b, x + 1, y) == S_OFFBOARD || board_atxy(b, x - 1, y) == S_OFFBOARD)
285 yd = 1;
286 else
287 xd = 1;
288 /* Direction from the border; -1 is above/left, 1 is below/right. */
289 int dd = (board_atxy(b, x + yd, y + xd) == S_OFFBOARD) ? 1 : -1;
290 if (PLDEBUGL(6))
291 fprintf(stderr, "xd %d yd %d dd %d\n", xd, yd, dd);
292 /* | ? ?
293 * | . O #
294 * | c X #
295 * | . O #
296 * | ? ? */
297 /* This is normally caught, unless we have friends both above
298 * and below... */
299 if (board_atxy(b, x + xd * 2, y + yd * 2) == lcolor
300 && board_atxy(b, x - xd * 2, y - yd * 2) == lcolor)
301 return false;
302 /* ...or can't block where we need because of shortage
303 * of liberties. */
304 int libs1 = board_group_info(b, group_atxy(b, x + xd - yd * dd, y + yd - xd * dd)).libs;
305 int libs2 = board_group_info(b, group_atxy(b, x - xd - yd * dd, y - yd - xd * dd)).libs;
306 if (PLDEBUGL(6))
307 fprintf(stderr, "libs1 %d libs2 %d\n", libs1, libs2);
308 if (libs1 < 2 && libs2 < 2)
309 return false;
310 if (board_atxy(b, x + xd * 2, y + yd * 2) == lcolor && libs1 < 3)
311 return false;
312 if (board_atxy(b, x - xd * 2, y - yd * 2) == lcolor && libs2 < 3)
313 return false;
314 return true;
317 /* Figure out the ladder direction */
318 int xd, yd;
319 xd = board_atxy(b, x + 1, y) == S_NONE ? 1 : board_atxy(b, x - 1, y) == S_NONE ? -1 : 0;
320 yd = board_atxy(b, x, y + 1) == S_NONE ? 1 : board_atxy(b, x, y - 1) == S_NONE ? -1 : 0;
322 /* We do only tight ladders, not loose ladders. Furthermore,
323 * the ladders need to be simple:
324 * . X . . . X
325 * c O X supported . c O unsupported
326 * X # # X O #
329 /* For given (xd,yd), we have two possibilities where to move
330 * next. Consider (-1,1):
331 * n X . n c X
332 * c O X X O #
333 * X # # . X #
335 if (!xd || !yd || !(ladder_catcher(b, x - xd, y, lcolor) ^ ladder_catcher(b, x, y - yd, lcolor))) {
336 /* Silly situation, probably non-simple ladder or suicide. */
337 /* TODO: In case of basic non-simple ladder, play out both variants. */
338 if (PLDEBUGL(5))
339 fprintf(stderr, "non-simple ladder\n");
340 return false;
343 #define ladder_check(xd1_, yd1_, xd2_, yd2_) \
344 if (board_atxy(b, x, y) != S_NONE) { \
345 /* Did we hit a stone when playing out ladder? */ \
346 if (ladder_catcher(b, x, y, lcolor)) \
347 return true; /* ladder works */ \
348 if (board_group_info(b, group_atxy(b, x, y)).lib[0] > 0) \
349 return false; /* friend that's not in atari himself */ \
350 } else { \
351 /* No. So we are at new position. \
352 * We need to check indirect ladder breakers. */ \
353 /* . 2 x . . \
354 * . x o O 1 <- only at O we can check for o at 2 \
355 * x o o x . otherwise x at O would be still deadly \
356 * o o x . . \
357 * We check for o and x at 1, these are vital. \
358 * We check only for o at 2; x at 2 would mean we \
359 * need to fork (one step earlier). */ \
360 enum stone s1 = board_atxy(b, x + (xd1_), y + (yd1_)); \
361 if (s1 == lcolor) return false; \
362 if (s1 == stone_other(lcolor)) return true; \
363 enum stone s2 = board_atxy(b, x + (xd2_), y + (yd2_)); \
364 if (s2 == lcolor) return false; \
366 #define ladder_horiz do { if (PLDEBUGL(6)) fprintf(stderr, "%d,%d horiz step %d\n", x, y, xd); x += xd; ladder_check(xd, 0, -2 * xd, yd); } while (0)
367 #define ladder_vert do { if (PLDEBUGL(6)) fprintf(stderr, "%d,%d vert step %d\n", x, y, yd); y += yd; ladder_check(0, yd, xd, -2 * yd); } while (0)
369 if (ladder_catcher(b, x - xd, y, lcolor))
370 ladder_horiz;
371 do {
372 ladder_vert;
373 ladder_horiz;
374 } while (1);
378 static coord_t
379 group_atari_check(struct playout_policy *p, struct board *b, group_t group)
381 struct moggy_policy *pp = p->data;
382 enum stone color = board_at(b, group_base(group));
383 coord_t lib = board_group_info(b, group).lib[0];
385 assert(color != S_OFFBOARD && color != S_NONE);
386 if (PLDEBUGL(5))
387 fprintf(stderr, "atariiiiiiiii %s of color %d\n", coord2sstr(lib, b), color);
388 assert(board_at(b, lib) == S_NONE);
390 /* Do not suicide... */
391 if (!valid_escape_route(b, color, lib))
392 goto caught;
393 if (PLDEBUGL(6))
394 fprintf(stderr, "...escape route valid\n");
396 /* ...or play out ladders. */
397 if (pp->ladders && ladder_catches(p, b, lib, group)) {
398 goto caught;
400 if (PLDEBUGL(6))
401 fprintf(stderr, "...no ladder\n");
403 return lib;
405 caught:
406 /* There is still hope - can't we capture some neighbor? */
407 foreach_in_group(b, group) {
408 foreach_neighbor(b, c, {
409 if (board_at(b, c) != stone_other(color)
410 || board_group_info(b, group_at(b, c)).libs > 1)
411 continue;
412 if (PLDEBUGL(6))
413 fprintf(stderr, "can capture group %d\n", group_at(b, c));
414 /* If we are saving our group, capture! */
415 if (b->last_move.color == stone_other(color))
416 return board_group_info(b, group_at(b, c)).lib[0];
417 /* If we chase the group, capture it now! */
418 return lib;
420 } foreach_in_group_end;
421 return pass;
424 static coord_t
425 global_atari_check(struct playout_policy *p, struct board *b)
427 if (b->clen == 0)
428 return pass;
430 int g_base = fast_random(b->clen);
431 for (int g = g_base; g < b->clen; g++) {
432 coord_t c = group_atari_check(p, b, group_at(b, group_base(b->c[g])));
433 if (!is_pass(c))
434 return c;
436 for (int g = 0; g < g_base; g++) {
437 coord_t c = group_atari_check(p, b, group_at(b, group_base(b->c[g])));
438 if (!is_pass(c))
439 return c;
441 return pass;
444 static coord_t
445 local_atari_check(struct playout_policy *p, struct board *b, struct move *m, struct move *testmove)
447 struct move_queue q;
448 q.moves = 0;
450 /* Did the opponent play a self-atari? */
451 if (board_group_info(b, group_at(b, m->coord)).libs == 1) {
452 coord_t l = group_atari_check(p, b, group_at(b, m->coord));
453 if (!is_pass(l))
454 q.move[q.moves++] = l;
457 foreach_neighbor(b, m->coord, {
458 group_t g = group_at(b, c);
459 if (!g || board_group_info(b, g).libs != 1)
460 continue;
461 coord_t l = group_atari_check(p, b, g);
462 if (!is_pass(l))
463 q.move[q.moves++] = l;
466 if (PLDEBUGL(5)) {
467 fprintf(stderr, "Local atari candidate moves: ");
468 for (int i = 0; i < q.moves; i++) {
469 fprintf(stderr, "%s ", coord2sstr(q.move[i], b));
471 fprintf(stderr, "\n");
474 if (testmove) {
475 while (q.moves--)
476 if (q.move[q.moves] == testmove->coord) {
477 if (PLDEBUGL(5))
478 fprintf(stderr, "Found queried move.\n");
479 return testmove->coord;
481 return pass;
484 int i = fast_random(q.moves);
485 return q.moves ? q.move[i] : pass;
488 coord_t
489 playout_moggy_choose(struct playout_policy *p, struct board *b, enum stone our_real_color)
491 struct moggy_policy *pp = p->data;
492 coord_t c;
494 if (PLDEBUGL(5))
495 board_print(b, stderr);
497 /* Local checks */
498 if (!is_pass(b->last_move.coord)) {
499 /* Local group in atari? */
500 if (pp->lcapturerate > fast_random(100)) {
501 c = local_atari_check(p, b, &b->last_move, NULL);
502 if (!is_pass(c))
503 return c;
506 /* Check for patterns we know */
507 if (pp->patternrate > fast_random(100)) {
508 c = apply_pattern(p, b, &b->last_move, NULL);
509 if (!is_pass(c))
510 return c;
514 /* Global checks */
516 /* Any groups in atari? */
517 if (pp->capturerate > fast_random(100)) {
518 c = global_atari_check(p, b);
519 if (!is_pass(c))
520 return c;
523 return pass;
526 float
527 playout_moggy_assess(struct playout_policy *p, struct board *b, struct move *m)
529 struct moggy_policy *pp = p->data;
531 if (is_pass(m->coord))
532 return NAN;
534 if (PLDEBUGL(5)) {
535 fprintf(stderr, "ASSESS of %s:\n", coord2sstr(m->coord, b));
536 board_print(b, stderr);
539 /* Are we dealing with atari? */
540 if (pp->lcapturerate > fast_random(100)) {
541 foreach_neighbor(b, m->coord, {
542 struct move m2;
543 m2.coord = c; m2.color = stone_other(m->color);
544 if (local_atari_check(p, b, &m2, m) == m->coord)
545 return 1.0;
548 /* Assess ladders anywhere, local or not. */
549 if (pp->ladderassess) {
550 //fprintf(stderr, "ASSESS %s\n", coord2sstr(m->coord, b));
551 foreach_neighbor(b, m->coord, {
552 if (board_at(b, c) == S_NONE || board_at(b, c) == S_OFFBOARD)
553 continue;
554 group_t g = group_at(b, c);
555 if (board_group_info(b, g).libs != 1)
556 continue;
557 if (ladder_catches(p, b, m->coord, g))
558 return 0.0;
563 /* Pattern check */
564 if (pp->patternrate > fast_random(100)) {
565 if (test_pattern_here(p, moggy_patterns, b, m))
566 return 1.0;
569 return NAN;
573 struct playout_policy *
574 playout_moggy_init(char *arg)
576 struct playout_policy *p = calloc(1, sizeof(*p));
577 struct moggy_policy *pp = calloc(1, sizeof(*pp));
578 p->data = pp;
579 p->choose = playout_moggy_choose;
580 p->assess = playout_moggy_assess;
582 pp->lcapturerate = 75;
583 pp->capturerate = 75;
584 pp->patternrate = 95;
585 pp->ladders = pp->borderladders = true;
586 pp->ladderassess = true;
588 if (arg) {
589 char *optspec, *next = arg;
590 while (*next) {
591 optspec = next;
592 next += strcspn(next, ":");
593 if (*next) { *next++ = 0; } else { *next = 0; }
595 char *optname = optspec;
596 char *optval = strchr(optspec, '=');
597 if (optval) *optval++ = 0;
599 if (!strcasecmp(optname, "lcapturerate") && optval) {
600 pp->lcapturerate = atoi(optval);
601 } else if (!strcasecmp(optname, "capturerate") && optval) {
602 pp->capturerate = atoi(optval);
603 } else if (!strcasecmp(optname, "patternrate") && optval) {
604 pp->patternrate = atoi(optval);
605 } else if (!strcasecmp(optname, "ladders")) {
606 pp->ladders = optval && *optval == '0' ? false : true;
607 } else if (!strcasecmp(optname, "borderladders")) {
608 pp->borderladders = optval && *optval == '0' ? false : true;
609 } else if (!strcasecmp(optname, "ladderassess")) {
610 pp->ladderassess = optval && *optval == '0' ? false : true;
611 } else {
612 fprintf(stderr, "playout-moggy: Invalid policy argument %s or missing value\n", optname);
617 return p;