Moggy 3x3: Do not consider pattern moves within eyes
[pachi/json.git] / playout / moggy.c
blobc7e26d50fe3eb9b4b5aa68ec7a268edd35e967b4
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;
19 /* These are relative to patternrate. */
20 int hanerate, cut1rate, cut2rate;
23 #define MQL 64
24 struct move_queue {
25 int moves;
26 coord_t move[MQL];
30 /* Pattern encoding:
31 * X: black; O: white; .: empty; #: edge
32 * x: !black; o: !white; ?: any
34 * extra X: pattern valid only for one side;
35 * middle point ignored. */
37 static char moggy_patterns_src[][11] = {
38 /* hane pattern - enclosing hane */
39 "XOX"
40 "..."
41 "???",
42 /* hane pattern - non-cutting hane */
43 "XO."
44 "..."
45 "?.?",
46 /* hane pattern - magari */
47 "XO?"
48 "X.."
49 "?.?",
50 /* hane pattern - thin hane (SUSPICIOUS) */
51 "XOO"
52 "..."
53 "?.?" "X",
54 /* cut1 pattern (kiri) - unprotected cut */
55 "XO?"
56 "O.o"
57 "?o?",
58 /* cut1 pattern (kiri) - peeped cut */
59 "XO?"
60 "O.X"
61 "???",
62 /* cut2 pattern (de) */
63 "?X?"
64 "O.O"
65 "ooo",
66 /* side pattern - chase */
67 "X.?"
68 "O.?"
69 "##?",
70 /* side pattern - weirdness (SUSPICIOUS) */
71 "?X?"
72 "X.O"
73 "###",
74 /* side pattern - sagari (SUSPICIOUS) */
75 "?XO"
76 "?.?" /* "?.x" ? */
77 "###" "X",
78 /* side pattern - weirdcut (SUSPICIOUS) */
79 "?OX"
80 "?.O"
81 "?##" "X",
82 /* side pattern - cut (SUSPICIOUS) */
83 "?OX"
84 "X.O"
85 "###" "X" /* no "X"? */,
87 #define moggy_patterns_src_n sizeof(moggy_patterns_src) / sizeof(moggy_patterns_src[0])
89 /* Hashtable: 2*8 bits (ignore middle point, 2 bits per intersection) */
90 /* Value: 0: no pattern, 1: black pattern, 2: white pattern, 3: both patterns */
91 static char moggy_patterns[65536];
93 static void
94 _record_pattern(char *table, int pat, int fixed_color)
96 /* Original color assignment */
97 table[pat] = fixed_color ? fixed_color : 3;
99 /* Reverse color assignment - achieved by swapping odd and even bits */
100 pat = ((pat >> 1) & 0x5555) | ((pat & 0x5555) << 1);
101 table[pat] = fixed_color ? 2 - (fixed_color == 2) : 3;
104 static void
105 _gen_pattern(char *table, int pat, char *src, int srclen, int fixed_color)
107 for (; srclen > 0; src++, srclen--) {
108 if (srclen == 5)
109 continue;
110 int patofs = (srclen > 5 ? srclen - 1 : srclen) - 1;
111 switch (*src) {
112 case '?':
113 *src = '.'; _gen_pattern(table, pat, src, srclen, fixed_color);
114 *src = 'X'; _gen_pattern(table, pat, src, srclen, fixed_color);
115 *src = 'O'; _gen_pattern(table, pat, src, srclen, fixed_color);
116 *src = '#'; _gen_pattern(table, pat, src, srclen, fixed_color);
117 *src = '?'; // for future recursions
118 return;
119 case 'x':
120 *src = '.'; _gen_pattern(table, pat, src, srclen, fixed_color);
121 *src = 'O'; _gen_pattern(table, pat, src, srclen, fixed_color);
122 *src = '#'; _gen_pattern(table, pat, src, srclen, fixed_color);
123 *src = 'x'; // for future recursions
124 return;
125 case 'o':
126 *src = '.'; _gen_pattern(table, pat, src, srclen, fixed_color);
127 *src = 'X'; _gen_pattern(table, pat, src, srclen, fixed_color);
128 *src = '#'; _gen_pattern(table, pat, src, srclen, fixed_color);
129 *src = 'o'; // for future recursions
130 return;
131 case '.': /* 0 */ break;
132 case 'X': pat |= S_BLACK << (patofs * 2); break;
133 case 'O': pat |= S_WHITE << (patofs * 2); break;
134 case '#': pat |= S_OFFBOARD << (patofs * 2); break;
138 /* Original pattern */
139 //fprintf(stderr, "[%s] %04x\n", src - 9, pat);
140 _record_pattern(table, pat, fixed_color);
141 /* V/H mirror pattern; reverse order of all 2-bit values */
143 int p2 = pat;
144 p2 = ((p2 >> 2) & 0x3333) | ((p2 & 0x3333) << 2);
145 p2 = ((p2 >> 4) & 0x0F0F) | ((p2 & 0x0F0F) << 4);
146 p2 = ((p2 >> 8) & 0x00FF) | ((p2 & 0x00FF) << 8);
147 //fprintf(stderr, "[%s] %04x\n", src - 9, p2);
148 _record_pattern(table, p2, fixed_color);
150 /* V mirror pattern; reverse order of 3-2-3 chunks */
152 int p2 = ((pat & 0xfc00) >> 10) | (pat & 0x03c0) | ((pat & 0x003f) << 10);
153 //fprintf(stderr, "[%s] %04x\n", src - 9, p2);
154 _record_pattern(table, p2, fixed_color);
155 /* H mirror pattern; reverse this bitstring */
156 p2 = ((p2 >> 2) & 0x3333) | ((p2 & 0x3333) << 2);
157 p2 = ((p2 >> 4) & 0x0F0F) | ((p2 & 0x0F0F) << 4);
158 p2 = ((p2 >> 8) & 0x00FF) | ((p2 & 0x00FF) << 8);
159 //fprintf(stderr, "[%s] %04x\n", src - 9, p2);
160 _record_pattern(table, p2, fixed_color);
164 static void __attribute__((constructor))
165 _init_patterns(void)
167 for (int i = 0; i < moggy_patterns_src_n; i++) {
168 int fixed_color = 0;
169 switch (moggy_patterns_src[i][9]) {
170 case 'X': fixed_color = S_BLACK; break;
171 case 'O': fixed_color = S_WHITE; break;
173 _gen_pattern(moggy_patterns, 0, moggy_patterns_src[i], 9, fixed_color);
179 /* Check if we match any pattern centered on given move. */
180 static bool
181 test_pattern_here(struct playout_policy *p, char *hashtable,
182 struct board *b, struct move *m)
184 int pat = 0;
185 int x = coord_x(m->coord, b), y = coord_y(m->coord, b);
186 pat |= (board_atxy(b, x - 1, y - 1) << 14)
187 | (board_atxy(b, x, y - 1) << 12)
188 | (board_atxy(b, x + 1, y - 1) << 10);
189 pat |= (board_atxy(b, x - 1, y) << 8)
190 | (board_atxy(b, x + 1, y) << 6);
191 pat |= (board_atxy(b, x - 1, y + 1) << 4)
192 | (board_atxy(b, x, y + 1) << 2)
193 | (board_atxy(b, x + 1, y + 1));
194 //fprintf(stderr, "(%d,%d) hashtable[%04x] = %d\n", x, y, pat, hashtable[pat]);
195 return (hashtable[pat] & m->color);
198 static void
199 apply_pattern_here(struct playout_policy *p, char *hashtable,
200 struct board *b, struct move *m, struct move_queue *q)
202 if (test_pattern_here(p, hashtable, b, m))
203 q->move[q->moves++] = m->coord;
206 /* Check if we match any pattern around given move (with the other color to play). */
207 static coord_t
208 apply_pattern(struct playout_policy *p, struct board *b, struct move *m, struct move *testmove)
210 //struct moggy_policy *pp = p->data;
211 struct move_queue q;
212 q.moves = 0;
214 /* Suicides do not make any patterns and confuse us. */
215 if (board_at(b, m->coord) == S_NONE || board_at(b, m->coord) == S_OFFBOARD)
216 return pass;
218 // FIXME: Fix assess callers
219 foreach_neighbor(b, m->coord, {
220 struct move m2; m2.coord = c; m2.color = stone_other(m->color);
221 if (board_at(b, c) == S_NONE && board_is_eyelike(b, &c, m->color))
222 apply_pattern_here(p, moggy_patterns, b, &m2, &q);
224 foreach_diag_neighbor(b, m->coord) {
225 struct move m2; m2.coord = c; m2.color = stone_other(m->color);
226 if (board_at(b, c) == S_NONE && board_is_eyelike(b, &c, m->color))
227 apply_pattern_here(p, moggy_patterns, b, &m2, &q);
228 } foreach_diag_neighbor_end;
230 if (PLDEBUGL(5)) {
231 fprintf(stderr, "Pattern candidate moves: ");
232 for (int i = 0; i < q.moves; i++) {
233 fprintf(stderr, "%s ", coord2sstr(q.move[i], b));
235 fprintf(stderr, "\n");
238 if (testmove) {
239 while (q.moves--)
240 if (q.move[q.moves] == testmove->coord) {
241 if (PLDEBUGL(5))
242 fprintf(stderr, "Found queried move.\n");
243 return testmove->coord;
245 return pass;
248 int i = fast_random(q.moves);
249 return q.moves ? q.move[i] : pass;
254 /* Is this ladder breaker friendly for the one who catches ladder. */
255 static bool
256 ladder_catcher(struct board *b, int x, int y, enum stone laddered)
258 enum stone breaker = board_atxy(b, x, y);
259 return breaker == stone_other(laddered) || breaker == S_OFFBOARD;
262 static bool
263 ladder_catches(struct playout_policy *p, struct board *b, coord_t coord, group_t laddered)
265 struct moggy_policy *pp = p->data;
267 /* This is very trivial and gets a lot of corner cases wrong.
268 * We need this to be just very fast. One important point is
269 * that we sometimes might not notice a ladder but if we do,
270 * it should always work; thus we can use this for strong
271 * negative hinting safely. */
272 //fprintf(stderr, "ladder check\n");
274 enum stone lcolor = board_at(b, group_base(laddered));
275 int x = coord_x(coord, b), y = coord_y(coord, b);
277 /* First, special-case first-line "ladders". This is a huge chunk
278 * of ladders we actually meet and want to play. */
279 if (pp->borderladders
280 && neighbor_count_at(b, coord, S_OFFBOARD) == 1
281 && neighbor_count_at(b, coord, lcolor) == 1) {
282 if (PLDEBUGL(5))
283 fprintf(stderr, "border ladder\n");
284 /* Direction along border; xd is horiz. border, yd vertical. */
285 int xd = 0, yd = 0;
286 if (board_atxy(b, x + 1, y) == S_OFFBOARD || board_atxy(b, x - 1, y) == S_OFFBOARD)
287 yd = 1;
288 else
289 xd = 1;
290 /* Direction from the border; -1 is above/left, 1 is below/right. */
291 int dd = (board_atxy(b, x + yd, y + xd) == S_OFFBOARD) ? 1 : -1;
292 if (PLDEBUGL(6))
293 fprintf(stderr, "xd %d yd %d dd %d\n", xd, yd, dd);
294 /* | ? ?
295 * | . O #
296 * | c X #
297 * | . O #
298 * | ? ? */
299 /* This is normally caught, unless we have friends both above
300 * and below... */
301 if (board_atxy(b, x + xd * 2, y + yd * 2) == lcolor
302 && board_atxy(b, x - xd * 2, y - yd * 2) == lcolor)
303 return false;
304 /* ...or can't block where we need because of shortage
305 * of liberties. */
306 int libs1 = board_group_info(b, group_atxy(b, x + xd - yd * dd, y + yd - xd * dd)).libs;
307 int libs2 = board_group_info(b, group_atxy(b, x - xd - yd * dd, y - yd - xd * dd)).libs;
308 if (PLDEBUGL(6))
309 fprintf(stderr, "libs1 %d libs2 %d\n", libs1, libs2);
310 if (libs1 < 2 && libs2 < 2)
311 return false;
312 if (board_atxy(b, x + xd * 2, y + yd * 2) == lcolor && libs1 < 3)
313 return false;
314 if (board_atxy(b, x - xd * 2, y - yd * 2) == lcolor && libs2 < 3)
315 return false;
316 return true;
319 /* Figure out the ladder direction */
320 int xd, yd;
321 xd = board_atxy(b, x + 1, y) == S_NONE ? 1 : board_atxy(b, x - 1, y) == S_NONE ? -1 : 0;
322 yd = board_atxy(b, x, y + 1) == S_NONE ? 1 : board_atxy(b, x, y - 1) == S_NONE ? -1 : 0;
324 /* We do only tight ladders, not loose ladders. Furthermore,
325 * the ladders need to be simple:
326 * . X . . . X
327 * c O X supported . c O unsupported
328 * X # # X O #
331 /* For given (xd,yd), we have two possibilities where to move
332 * next. Consider (-1,1):
333 * n X . n c X
334 * c O X X O #
335 * X # # . X #
337 if (!xd || !yd || !(ladder_catcher(b, x - xd, y, lcolor) ^ ladder_catcher(b, x, y - yd, lcolor))) {
338 /* Silly situation, probably non-simple ladder or suicide. */
339 /* TODO: In case of basic non-simple ladder, play out both variants. */
340 if (PLDEBUGL(5))
341 fprintf(stderr, "non-simple ladder\n");
342 return false;
345 #define ladder_check(xd1_, yd1_, xd2_, yd2_) \
346 if (board_atxy(b, x, y) != S_NONE) { \
347 /* Did we hit a stone when playing out ladder? */ \
348 if (ladder_catcher(b, x, y, lcolor)) \
349 return true; /* ladder works */ \
350 if (board_group_info(b, group_atxy(b, x, y)).lib[0] > 0) \
351 return false; /* friend that's not in atari himself */ \
352 } else { \
353 /* No. So we are at new position. \
354 * We need to check indirect ladder breakers. */ \
355 /* . 2 x . . \
356 * . x o O 1 <- only at O we can check for o at 2 \
357 * x o o x . otherwise x at O would be still deadly \
358 * o o x . . \
359 * We check for o and x at 1, these are vital. \
360 * We check only for o at 2; x at 2 would mean we \
361 * need to fork (one step earlier). */ \
362 enum stone s1 = board_atxy(b, x + (xd1_), y + (yd1_)); \
363 if (s1 == lcolor) return false; \
364 if (s1 == stone_other(lcolor)) return true; \
365 enum stone s2 = board_atxy(b, x + (xd2_), y + (yd2_)); \
366 if (s2 == lcolor) return false; \
368 #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)
369 #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)
371 if (ladder_catcher(b, x - xd, y, lcolor))
372 ladder_horiz;
373 do {
374 ladder_vert;
375 ladder_horiz;
376 } while (1);
380 static coord_t
381 group_atari_check(struct playout_policy *p, struct board *b, group_t group)
383 struct moggy_policy *pp = p->data;
384 enum stone color = board_at(b, group_base(group));
385 coord_t lib = board_group_info(b, group).lib[0];
387 assert(color != S_OFFBOARD && color != S_NONE);
388 if (PLDEBUGL(5))
389 fprintf(stderr, "atariiiiiiiii %s of color %d\n", coord2sstr(lib, b), color);
390 assert(board_at(b, lib) == S_NONE);
392 /* Do not suicide... */
393 if (!valid_escape_route(b, color, lib))
394 goto caught;
395 if (PLDEBUGL(6))
396 fprintf(stderr, "...escape route valid\n");
398 /* ...or play out ladders. */
399 if (pp->ladders && ladder_catches(p, b, lib, group)) {
400 goto caught;
402 if (PLDEBUGL(6))
403 fprintf(stderr, "...no ladder\n");
405 return lib;
407 caught:
408 /* There is still hope - can't we capture some neighbor? */
409 foreach_in_group(b, group) {
410 foreach_neighbor(b, c, {
411 if (board_at(b, c) != stone_other(color)
412 || board_group_info(b, group_at(b, c)).libs > 1)
413 continue;
414 if (PLDEBUGL(6))
415 fprintf(stderr, "can capture group %d\n", group_at(b, c));
416 /* If we are saving our group, capture! */
417 if (b->last_move.color == stone_other(color))
418 return board_group_info(b, group_at(b, c)).lib[0];
419 /* If we chase the group, capture it now! */
420 return lib;
422 } foreach_in_group_end;
423 return pass;
426 static coord_t
427 global_atari_check(struct playout_policy *p, struct board *b)
429 if (b->clen == 0)
430 return pass;
432 int g_base = fast_random(b->clen);
433 for (int g = g_base; g < b->clen; g++) {
434 coord_t c = group_atari_check(p, b, group_at(b, group_base(b->c[g])));
435 if (!is_pass(c))
436 return c;
438 for (int g = 0; g < g_base; g++) {
439 coord_t c = group_atari_check(p, b, group_at(b, group_base(b->c[g])));
440 if (!is_pass(c))
441 return c;
443 return pass;
446 static coord_t
447 local_atari_check(struct playout_policy *p, struct board *b, struct move *m, struct move *testmove)
449 struct move_queue q;
450 q.moves = 0;
452 /* Did the opponent play a self-atari? */
453 if (board_group_info(b, group_at(b, m->coord)).libs == 1) {
454 coord_t l = group_atari_check(p, b, group_at(b, m->coord));
455 if (!is_pass(l))
456 q.move[q.moves++] = l;
459 foreach_neighbor(b, m->coord, {
460 group_t g = group_at(b, c);
461 if (!g || board_group_info(b, g).libs != 1)
462 continue;
463 coord_t l = group_atari_check(p, b, g);
464 if (!is_pass(l))
465 q.move[q.moves++] = l;
468 if (PLDEBUGL(5)) {
469 fprintf(stderr, "Local atari candidate moves: ");
470 for (int i = 0; i < q.moves; i++) {
471 fprintf(stderr, "%s ", coord2sstr(q.move[i], b));
473 fprintf(stderr, "\n");
476 if (testmove) {
477 while (q.moves--)
478 if (q.move[q.moves] == testmove->coord) {
479 if (PLDEBUGL(5))
480 fprintf(stderr, "Found queried move.\n");
481 return testmove->coord;
483 return pass;
486 int i = fast_random(q.moves);
487 return q.moves ? q.move[i] : pass;
490 coord_t
491 playout_moggy_choose(struct playout_policy *p, struct board *b, enum stone our_real_color)
493 struct moggy_policy *pp = p->data;
494 coord_t c;
496 if (PLDEBUGL(5))
497 board_print(b, stderr);
499 /* Local checks */
500 if (!is_pass(b->last_move.coord)) {
501 /* Local group in atari? */
502 if (pp->lcapturerate > fast_random(100)) {
503 c = local_atari_check(p, b, &b->last_move, NULL);
504 if (!is_pass(c))
505 return c;
508 /* Check for patterns we know */
509 if (pp->patternrate > fast_random(100)) {
510 c = apply_pattern(p, b, &b->last_move, NULL);
511 if (!is_pass(c))
512 return c;
516 /* Global checks */
518 /* Any groups in atari? */
519 if (pp->capturerate > fast_random(100)) {
520 c = global_atari_check(p, b);
521 if (!is_pass(c))
522 return c;
525 return pass;
528 float
529 playout_moggy_assess(struct playout_policy *p, struct board *b, struct move *m)
531 struct moggy_policy *pp = p->data;
533 if (is_pass(m->coord))
534 return NAN;
536 if (PLDEBUGL(5)) {
537 fprintf(stderr, "ASSESS of %s:\n", coord2sstr(m->coord, b));
538 board_print(b, stderr);
541 /* Are we dealing with atari? */
542 if (pp->lcapturerate > fast_random(100)) {
543 foreach_neighbor(b, m->coord, {
544 struct move m2;
545 m2.coord = c; m2.color = stone_other(m->color);
546 if (local_atari_check(p, b, &m2, m) == m->coord)
547 return 1.0;
550 /* Assess ladders anywhere, local or not. */
551 if (pp->ladderassess) {
552 //fprintf(stderr, "ASSESS %s\n", coord2sstr(m->coord, b));
553 foreach_neighbor(b, m->coord, {
554 if (board_at(b, c) == S_NONE || board_at(b, c) == S_OFFBOARD)
555 continue;
556 group_t g = group_at(b, c);
557 if (board_group_info(b, g).libs != 1)
558 continue;
559 if (ladder_catches(p, b, m->coord, g))
560 return 0.0;
565 /* Pattern check */
566 if (pp->patternrate > fast_random(100)) {
567 if (test_pattern_here(p, moggy_patterns, b, m))
568 return 1.0;
571 return NAN;
575 struct playout_policy *
576 playout_moggy_init(char *arg)
578 struct playout_policy *p = calloc(1, sizeof(*p));
579 struct moggy_policy *pp = calloc(1, sizeof(*pp));
580 p->data = pp;
581 p->choose = playout_moggy_choose;
582 p->assess = playout_moggy_assess;
584 pp->lcapturerate = 75;
585 pp->capturerate = 75;
586 pp->patternrate = 75;
587 pp->hanerate = pp->cut1rate = pp->cut2rate = 75;
588 pp->ladders = pp->borderladders = true;
589 pp->ladderassess = true;
591 if (arg) {
592 char *optspec, *next = arg;
593 while (*next) {
594 optspec = next;
595 next += strcspn(next, ":");
596 if (*next) { *next++ = 0; } else { *next = 0; }
598 char *optname = optspec;
599 char *optval = strchr(optspec, '=');
600 if (optval) *optval++ = 0;
602 if (!strcasecmp(optname, "lcapturerate") && optval) {
603 pp->lcapturerate = atoi(optval);
604 } else if (!strcasecmp(optname, "capturerate") && optval) {
605 pp->capturerate = atoi(optval);
606 } else if (!strcasecmp(optname, "patternrate") && optval) {
607 pp->patternrate = atoi(optval);
608 } else if (!strcasecmp(optname, "hanerate") && optval) {
609 pp->hanerate = atoi(optval);
610 } else if (!strcasecmp(optname, "cut1rate") && optval) {
611 pp->cut1rate = atoi(optval);
612 } else if (!strcasecmp(optname, "cut2rate") && optval) {
613 pp->cut2rate = atoi(optval);
614 } else if (!strcasecmp(optname, "ladders")) {
615 pp->ladders = optval && *optval == '0' ? false : true;
616 } else if (!strcasecmp(optname, "borderladders")) {
617 pp->borderladders = optval && *optval == '0' ? false : true;
618 } else if (!strcasecmp(optname, "ladderassess")) {
619 pp->ladderassess = optval && *optval == '0' ? false : true;
620 } else {
621 fprintf(stderr, "playout-moggy: Invalid policy argument %s or missing value\n", optname);
626 return p;