Moggy: Move ladder_catches() to common tactics.* code
[pachi/json.git] / playout / moggy.c
bloba45e5ccca28c163c848fa6c1e7f63c1faf519893
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 "mq.h"
10 #include "pattern3.h"
11 #include "playout.h"
12 #include "playout/moggy.h"
13 #include "random.h"
14 #include "tactics.h"
15 #include "uct/prior.h"
17 #define PLDEBUGL(n) DEBUGL_(p->debug_level, n)
20 /* Note that the context can be shared by multiple threads! */
22 struct moggy_policy {
23 bool ladders, ladderassess, borderladders, assess_local;
24 int lcapturerate, atarirate, capturerate, patternrate;
25 int selfatarirate;
26 int fillboardtries;
27 /* Whether to look for patterns around second-to-last move. */
28 bool pattern2;
30 struct pattern3s patterns;
34 static char moggy_patterns_src[][11] = {
35 /* hane pattern - enclosing hane */
36 "XOX"
37 "..."
38 "???",
39 /* hane pattern - non-cutting hane */
40 "XO."
41 "..."
42 "?.?",
43 /* hane pattern - magari */
44 "XO?"
45 "X.."
46 "x.?",
47 /* hane pattern - thin hane */
48 "XOO"
49 "..."
50 "?.?" "X",
51 /* generic pattern - katatsuke or diagonal attachment; similar to magari */
52 ".O."
53 "X.."
54 "...",
55 /* cut1 pattern (kiri) - unprotected cut */
56 "XO?"
57 "O.o"
58 "?o?",
59 /* cut1 pattern (kiri) - peeped cut */
60 "XO?"
61 "O.X"
62 "???",
63 /* cut2 pattern (de) */
64 "?X?"
65 "O.O"
66 "ooo",
67 /* cut keima (not in Mogo) */
68 "OX?"
69 "o.O"
70 "???", /* o?? has some pathological tsumego cases */
71 /* side pattern - chase */
72 "X.?"
73 "O.?"
74 "##?",
75 /* side pattern - weirdness (SUSPICIOUS) */
76 "?X?"
77 "X.O"
78 "###",
79 /* side pattern - sagari (SUSPICIOUS) */
80 "?XO"
81 "x.x" /* Mogo has "x.?" */
82 "###" /* Mogo has "X" */,
83 /* side pattern - throw-in (SUSPICIOUS) */
84 #if 0
85 "?OX"
86 "o.O"
87 "?##" "X",
88 #endif
89 /* side pattern - cut (SUSPICIOUS) */
90 "?OX"
91 "X.O"
92 "###" /* Mogo has "X" */,
94 #define moggy_patterns_src_n sizeof(moggy_patterns_src) / sizeof(moggy_patterns_src[0])
97 static void
98 apply_pattern_here(struct playout_policy *p,
99 struct board *b, struct move *m, struct move_queue *q)
101 struct moggy_policy *pp = p->data;
102 if (test_pattern3_here(&pp->patterns, b, m))
103 mq_add(q, m->coord);
106 /* Check if we match any pattern around given move (with the other color to play). */
107 static coord_t
108 apply_pattern(struct playout_policy *p, struct board *b, struct move *m, struct move *mm)
110 struct move_queue q;
111 q.moves = 0;
113 /* Suicides do not make any patterns and confuse us. */
114 if (board_at(b, m->coord) == S_NONE || board_at(b, m->coord) == S_OFFBOARD)
115 return pass;
117 foreach_neighbor(b, m->coord, {
118 struct move m2; m2.coord = c; m2.color = stone_other(m->color);
119 if (board_is_valid_move(b, &m2))
120 apply_pattern_here(p, b, &m2, &q);
122 foreach_diag_neighbor(b, m->coord) {
123 struct move m2; m2.coord = c; m2.color = stone_other(m->color);
124 if (board_is_valid_move(b, &m2))
125 apply_pattern_here(p, b, &m2, &q);
126 } foreach_diag_neighbor_end;
128 if (mm) { /* Second move for pattern searching */
129 foreach_neighbor(b, mm->coord, {
130 if (coord_is_8adjecent(m->coord, c, b))
131 continue;
132 struct move m2; m2.coord = c; m2.color = stone_other(m->color);
133 if (board_is_valid_move(b, &m2))
134 apply_pattern_here(p, b, &m2, &q);
136 foreach_diag_neighbor(b, mm->coord) {
137 if (coord_is_8adjecent(m->coord, c, b))
138 continue;
139 struct move m2; m2.coord = c; m2.color = stone_other(m->color);
140 if (board_is_valid_move(b, &m2))
141 apply_pattern_here(p, b, &m2, &q);
142 } foreach_diag_neighbor_end;
145 if (PLDEBUGL(5))
146 mq_print(&q, b, "Pattern");
148 return mq_pick(&q);
153 static coord_t
154 can_be_captured(struct playout_policy *p, struct board *b, enum stone capturer, coord_t c, enum stone to_play)
156 if (board_at(b, c) != stone_other(capturer)
157 || board_group_info(b, group_at(b, c)).libs > 1)
158 return pass;
160 coord_t capture = board_group_info(b, group_at(b, c)).lib[0];
161 if (PLDEBUGL(6))
162 fprintf(stderr, "can capture group %d (%s)?\n",
163 group_at(b, c), coord2sstr(capture, b));
164 struct move m; m.color = to_play; m.coord = capture;
165 /* Does that move even make sense? */
166 if (!board_is_valid_move(b, &m))
167 return pass;
168 /* Make sure capturing the group will actually
169 * do us any good. */
170 else if (is_bad_selfatari(b, to_play, capture))
171 return pass;
173 return capture;
176 static bool
177 can_be_rescued(struct playout_policy *p, struct board *b, group_t group, enum stone color, coord_t lib)
179 /* Does playing on the liberty rescue the group? */
180 if (!is_bad_selfatari(b, color, lib))
181 return true;
183 /* Then, maybe we can capture one of our neighbors? */
184 foreach_in_group(b, group) {
185 foreach_neighbor(b, c, {
186 if (!is_pass(can_be_captured(p, b, color, c, color)))
187 return true;
189 } foreach_in_group_end;
190 return false;
193 static void
194 group_atari_check(struct playout_policy *p, struct board *b, group_t group, enum stone to_play, struct move_queue *q, coord_t *ladder)
196 struct moggy_policy *pp = p->data;
197 int qmoves_prev = q->moves;
199 /* We don't use @to_play almost anywhere since any moves here are good
200 * for both defender and attacker. */
202 enum stone color = board_at(b, group_base(group));
203 coord_t lib = board_group_info(b, group).lib[0];
205 assert(color != S_OFFBOARD && color != S_NONE);
206 if (PLDEBUGL(5))
207 fprintf(stderr, "[%s] atariiiiiiiii %s of color %d\n", coord2sstr(group, b), coord2sstr(lib, b), color);
208 assert(board_at(b, lib) == S_NONE);
210 /* Do not bother with kos. */
211 if (group_is_onestone(b, group)
212 && neighbor_count_at(b, lib, color) + neighbor_count_at(b, lib, S_OFFBOARD) == 4)
213 return;
215 /* Can we capture some neighbor? */
216 foreach_in_group(b, group) {
217 foreach_neighbor(b, c, {
218 coord_t capture = can_be_captured(p, b, color, c, to_play);
219 if (is_pass(capture))
220 continue;
222 mq_add(q, capture);
223 mq_nodup(q);
225 } foreach_in_group_end;
227 struct move m; m.color = to_play; m.coord = lib;
228 if (!board_is_valid_move(b, &m))
229 return;
231 /* Do not suicide... */
232 if (is_bad_selfatari(b, to_play, lib))
233 return;
234 /* Do not remove group that cannot be saved by the opponent. */
235 if (to_play != color && !can_be_rescued(p, b, group, color, lib))
236 return;
237 if (PLDEBUGL(6))
238 fprintf(stderr, "...escape route valid\n");
240 /* ...or play out ladders. */
241 if (ladder_catches(b, lib, group, pp->borderladders, pp->ladders)) {
242 /* Sometimes we want to keep the ladder move in the
243 * queue in order to discourage it. */
244 if (!ladder)
245 return;
246 else
247 *ladder = lib;
249 if (PLDEBUGL(6))
250 fprintf(stderr, "...no ladder\n");
252 if (to_play != color) {
253 /* We are the attacker! In that case, throw away the moves
254 * that defend our groups, since we can capture the culprit. */
255 q->moves = qmoves_prev;
258 mq_add(q, lib);
259 mq_nodup(q);
262 static coord_t
263 global_atari_check(struct playout_policy *p, struct board *b, enum stone to_play)
265 struct move_queue q;
266 q.moves = 0;
268 if (b->clen == 0)
269 return pass;
271 int g_base = fast_random(b->clen);
272 for (int g = g_base; g < b->clen; g++) {
273 group_atari_check(p, b, group_at(b, group_base(b->c[g])), to_play, &q, NULL);
274 if (q.moves > 0)
275 return mq_pick(&q);
277 for (int g = 0; g < g_base; g++) {
278 group_atari_check(p, b, group_at(b, group_base(b->c[g])), to_play, &q, NULL);
279 if (q.moves > 0)
280 return mq_pick(&q);
282 return pass;
285 static coord_t
286 local_atari_check(struct playout_policy *p, struct board *b, struct move *m)
288 struct move_queue q;
289 q.moves = 0;
291 /* Did the opponent play a self-atari? */
292 if (board_group_info(b, group_at(b, m->coord)).libs == 1) {
293 group_atari_check(p, b, group_at(b, m->coord), stone_other(m->color), &q, NULL);
296 foreach_neighbor(b, m->coord, {
297 group_t g = group_at(b, c);
298 if (!g || board_group_info(b, g).libs != 1)
299 continue;
300 group_atari_check(p, b, g, stone_other(m->color), &q, NULL);
303 if (PLDEBUGL(5))
304 mq_print(&q, b, "Local atari");
306 return mq_pick(&q);
309 static bool
310 miai_2lib(struct board *b, group_t group, enum stone color)
312 bool can_connect = false, can_pull_out = false;
313 /* We have miai if we can either connect on both libs,
314 * or connect on one lib and escape on another. (Just
315 * having two escape routes can be risky.) */
316 foreach_neighbor(b, board_group_info(b, group).lib[0], {
317 enum stone cc = board_at(b, c);
318 if (cc == S_NONE && cc != board_group_info(b, group).lib[1]) {
319 can_pull_out = true;
320 } else if (cc != color) {
321 continue;
324 group_t cg = group_at(b, c);
325 if (cg && cg != group && board_group_info(b, cg).libs > 1)
326 can_connect = true;
328 foreach_neighbor(b, board_group_info(b, group).lib[1], {
329 enum stone cc = board_at(b, c);
330 if (cc == S_NONE && cc != board_group_info(b, group).lib[0] && can_connect) {
331 return true;
332 } else if (cc != color) {
333 continue;
336 group_t cg = group_at(b, c);
337 if (cg && cg != group && board_group_info(b, cg).libs > 1)
338 return (can_connect || can_pull_out);
340 return false;
343 static void
344 group_2lib_check(struct playout_policy *p, struct board *b, group_t group, enum stone to_play, struct move_queue *q)
346 enum stone color = board_at(b, group_base(group));
347 assert(color != S_OFFBOARD && color != S_NONE);
349 if (PLDEBUGL(5))
350 fprintf(stderr, "[%s] 2lib check of color %d\n",
351 coord2sstr(group, b), color);
353 /* Do not try to atari groups that cannot be harmed. */
354 if (miai_2lib(b, group, color))
355 return;
357 for (int i = 0; i < 2; i++) {
358 coord_t lib = board_group_info(b, group).lib[i];
359 assert(board_at(b, lib) == S_NONE);
360 struct move m; m.color = to_play; m.coord = lib;
361 if (!board_is_valid_move(b, &m))
362 continue;
364 /* Don't play at the spot if it is extremely short
365 * of liberties... */
366 /* XXX: This looks harmful, could significantly
367 * prefer atari to throwin:
369 * XXXOOOOOXX
370 * .OO.....OX
371 * XXXOOOOOOX */
372 #if 0
373 if (neighbor_count_at(b, lib, stone_other(color)) + immediate_liberty_count(b, lib) < 2)
374 continue;
375 #endif
377 /* If the owner can't play at the spot, we don't want
378 * to bother either. */
379 if (is_bad_selfatari(b, color, lib))
380 continue;
382 /* Of course we don't want to play bad selfatari
383 * ourselves, if we are the attacker... */
384 if (to_play != color && is_bad_selfatari(b, to_play, lib))
385 continue;
387 /* Tasty! Crispy! Good! */
388 mq_add(q, lib);
392 static coord_t
393 local_2lib_check(struct playout_policy *p, struct board *b, struct move *m)
395 struct move_queue q;
396 q.moves = 0;
398 /* Does the opponent have just two liberties? */
399 if (board_group_info(b, group_at(b, m->coord)).libs == 2) {
400 group_2lib_check(p, b, group_at(b, m->coord), stone_other(m->color), &q);
401 #if 0
402 /* We always prefer to take off an enemy chain liberty
403 * before pulling out ourselves. */
404 /* XXX: We aren't guaranteed to return to that group
405 * later. */
406 if (q.moves)
407 return q.move[fast_random(q.moves)];
408 #endif
411 /* Then he took a third liberty from neighboring chain? */
412 foreach_neighbor(b, m->coord, {
413 group_t g = group_at(b, c);
414 if (!g || board_group_info(b, g).libs != 2)
415 continue;
416 group_2lib_check(p, b, g, stone_other(m->color), &q);
419 if (PLDEBUGL(5))
420 mq_print(&q, b, "Local 2lib");
422 return mq_pick(&q);
425 coord_t
426 playout_moggy_choose(struct playout_policy *p, struct board *b, enum stone to_play)
428 struct moggy_policy *pp = p->data;
429 coord_t c;
431 if (PLDEBUGL(5))
432 board_print(b, stderr);
434 /* Local checks */
435 if (!is_pass(b->last_move.coord)) {
436 /* Local group in atari? */
437 if (pp->lcapturerate > fast_random(100)) {
438 c = local_atari_check(p, b, &b->last_move);
439 if (!is_pass(c))
440 return c;
443 /* Local group can be PUT in atari? */
444 if (pp->atarirate > fast_random(100)) {
445 c = local_2lib_check(p, b, &b->last_move);
446 if (!is_pass(c))
447 return c;
450 /* Check for patterns we know */
451 if (pp->patternrate > fast_random(100)) {
452 c = apply_pattern(p, b, &b->last_move,
453 pp->pattern2 && b->last_move2.coord >= 0 ? &b->last_move2 : NULL);
454 if (!is_pass(c))
455 return c;
459 /* Global checks */
461 /* Any groups in atari? */
462 if (pp->capturerate > fast_random(100)) {
463 c = global_atari_check(p, b, to_play);
464 if (!is_pass(c))
465 return c;
468 /* Fill board */
469 int fbtries = b->flen / 8;
470 for (int i = 0; i < (fbtries < pp->fillboardtries ? fbtries : pp->fillboardtries); i++) {
471 coord_t coord = b->f[fast_random(b->flen)];
472 if (is_pass(coord) || immediate_liberty_count(b, coord) != 4)
473 continue;
474 foreach_diag_neighbor(b, coord) {
475 if (board_at(b, c) != S_NONE)
476 goto next_try;
477 } foreach_diag_neighbor_end;
478 return coord;
479 next_try:;
482 return pass;
486 static int
487 assess_local_bonus(struct playout_policy *p, struct board *board, coord_t a, coord_t b, int games)
489 struct moggy_policy *pp = p->data;
490 if (!pp->assess_local)
491 return games;
493 int dx = abs(coord_x(a, board) - coord_x(b, board));
494 int dy = abs(coord_y(a, board) - coord_y(b, board));
495 /* adjecent move, directly or diagonally? */
496 if (dx + dy <= 1 + (dx && dy))
497 return games;
498 else
499 return games / 2;
502 void
503 playout_moggy_assess_group(struct playout_policy *p, struct prior_map *map, group_t g, int games)
505 struct moggy_policy *pp = p->data;
506 struct board *b = map->b;
507 struct move_queue q; q.moves = 0;
509 if (board_group_info(b, g).libs > 2)
510 return;
512 if (PLDEBUGL(5)) {
513 fprintf(stderr, "ASSESS of group %s:\n", coord2sstr(g, b));
514 board_print(b, stderr);
517 if (board_group_info(b, g).libs == 2) {
518 if (!pp->atarirate)
519 return;
520 group_2lib_check(p, b, g, map->to_play, &q);
521 while (q.moves--) {
522 coord_t coord = q.move[q.moves];
523 if (PLDEBUGL(5))
524 fprintf(stderr, "1.0: 2lib %s\n", coord2sstr(coord, b));
525 int assess = assess_local_bonus(p, b, b->last_move.coord, coord, games) / 2;
526 add_prior_value(map, coord, assess, assess);
528 return;
531 /* This group, sir, is in atari! */
533 if (!pp->capturerate && !pp->lcapturerate && !pp->ladderassess)
534 return;
536 coord_t ladder = pass;
537 group_atari_check(p, b, g, map->to_play, &q, &ladder);
538 while (q.moves--) {
539 coord_t coord = q.move[q.moves];
541 /* _Never_ play here if this move plays out
542 * a caught ladder. */
543 if (coord == ladder) {
544 /* Note that the opposite is not guarded against;
545 * we do not advise against capturing a laddered
546 * group (but we don't encourage it either). Such
547 * a move can simplify tactical situations if we
548 * can afford it. */
549 if (!pp->ladderassess || map->to_play != board_at(b, g))
550 continue;
551 /* FIXME: We give the malus even if this move
552 * captures another group. */
553 if (PLDEBUGL(5))
554 fprintf(stderr, "0.0: ladder %s\n", coord2sstr(coord, b));
555 add_prior_value(map, coord, -games, games);
556 continue;
559 if (!pp->capturerate && !pp->lcapturerate)
560 continue;
562 if (PLDEBUGL(5))
563 fprintf(stderr, "1.0: atari %s\n", coord2sstr(coord, b));
564 int assess = assess_local_bonus(p, b, b->last_move.coord, coord, games) * 2;
565 add_prior_value(map, coord, assess, assess);
570 playout_moggy_assess_one(struct playout_policy *p, struct prior_map *map, coord_t coord, int games)
572 struct moggy_policy *pp = p->data;
573 struct board *b = map->b;
575 if (PLDEBUGL(5)) {
576 fprintf(stderr, "ASSESS of move %s:\n", coord2sstr(coord, b));
577 board_print(b, stderr);
580 /* Is this move a self-atari? */
581 if (pp->selfatarirate) {
582 if (is_bad_selfatari(b, map->to_play, coord)) {
583 if (PLDEBUGL(5))
584 fprintf(stderr, "0.0: self-atari\n");
585 return -games;
589 /* Pattern check */
590 if (pp->patternrate) {
591 struct move m = { .color = map->to_play, .coord = coord };
592 if (test_pattern3_here(&pp->patterns, b, &m)) {
593 if (PLDEBUGL(5))
594 fprintf(stderr, "1.0: pattern\n");
595 return assess_local_bonus(p, b, b->last_move.coord, coord, games);
599 return 0;
602 void
603 playout_moggy_assess(struct playout_policy *p, struct prior_map *map, int games)
605 struct moggy_policy *pp = p->data;
607 /* First, go through all endangered groups. */
608 if (pp->lcapturerate || pp->capturerate || pp->atarirate || pp->ladderassess)
609 for (group_t g = 1; g < board_size2(map->b); g++)
610 if (group_at(map->b, g) == g)
611 playout_moggy_assess_group(p, map, g, games);
613 /* Then, assess individual moves. */
614 if (!pp->patternrate && !pp->selfatarirate)
615 return;
616 foreach_point(map->b) {
617 if (!map->consider[c])
618 continue;
619 int assess = playout_moggy_assess_one(p, map, c, games);
620 if (!assess)
621 continue;
622 add_prior_value(map, c, assess, abs(assess));
623 } foreach_point_end;
626 bool
627 playout_moggy_permit(struct playout_policy *p, struct board *b, struct move *m)
629 struct moggy_policy *pp = p->data;
631 /* The idea is simple for now - never allow self-atari moves.
632 * They suck in general, but this also permits us to actually
633 * handle seki in the playout stage. */
635 if (fast_random(100) >= pp->selfatarirate) {
636 if (PLDEBUGL(5))
637 fprintf(stderr, "skipping sar test\n");
638 return true;
640 bool selfatari = is_bad_selfatari(b, m->color, m->coord);
641 if (PLDEBUGL(5) && selfatari)
642 fprintf(stderr, "__ Prohibiting self-atari %s %s\n",
643 stone2str(m->color), coord2sstr(m->coord, b));
644 return !selfatari;
648 struct playout_policy *
649 playout_moggy_init(char *arg)
651 struct playout_policy *p = calloc(1, sizeof(*p));
652 struct moggy_policy *pp = calloc(1, sizeof(*pp));
653 p->data = pp;
654 p->choose = playout_moggy_choose;
655 p->assess = playout_moggy_assess;
656 p->permit = playout_moggy_permit;
658 int rate = 90;
660 pp->lcapturerate = pp->atarirate = pp->capturerate = pp->patternrate = pp->selfatarirate = -1;
661 pp->ladders = pp->borderladders = true;
662 pp->ladderassess = true;
664 if (arg) {
665 char *optspec, *next = arg;
666 while (*next) {
667 optspec = next;
668 next += strcspn(next, ":");
669 if (*next) { *next++ = 0; } else { *next = 0; }
671 char *optname = optspec;
672 char *optval = strchr(optspec, '=');
673 if (optval) *optval++ = 0;
675 if (!strcasecmp(optname, "lcapturerate") && optval) {
676 pp->lcapturerate = atoi(optval);
677 } else if (!strcasecmp(optname, "atarirate") && optval) {
678 pp->atarirate = atoi(optval);
679 } else if (!strcasecmp(optname, "capturerate") && optval) {
680 pp->capturerate = atoi(optval);
681 } else if (!strcasecmp(optname, "patternrate") && optval) {
682 pp->patternrate = atoi(optval);
683 } else if (!strcasecmp(optname, "selfatarirate") && optval) {
684 pp->selfatarirate = atoi(optval);
685 } else if (!strcasecmp(optname, "rate") && optval) {
686 rate = atoi(optval);
687 } else if (!strcasecmp(optname, "fillboardtries")) {
688 pp->fillboardtries = atoi(optval);
689 } else if (!strcasecmp(optname, "ladders")) {
690 pp->ladders = optval && *optval == '0' ? false : true;
691 } else if (!strcasecmp(optname, "borderladders")) {
692 pp->borderladders = optval && *optval == '0' ? false : true;
693 } else if (!strcasecmp(optname, "ladderassess")) {
694 pp->ladderassess = optval && *optval == '0' ? false : true;
695 } else if (!strcasecmp(optname, "assess_local")) {
696 pp->assess_local = optval && *optval == '0' ? false : true;
697 } else if (!strcasecmp(optname, "pattern2")) {
698 pp->pattern2 = optval && *optval == '0' ? false : true;
699 } else {
700 fprintf(stderr, "playout-moggy: Invalid policy argument %s or missing value\n", optname);
701 exit(1);
705 if (pp->lcapturerate == -1) pp->lcapturerate = rate;
706 if (pp->atarirate == -1) pp->atarirate = rate;
707 if (pp->capturerate == -1) pp->capturerate = rate;
708 if (pp->patternrate == -1) pp->patternrate = rate;
709 if (pp->selfatarirate == -1) pp->selfatarirate = rate;
711 pattern3s_init(&pp->patterns, moggy_patterns_src, moggy_patterns_src_n);
713 return p;