1 /* Heuristical playout (and tree prior) policy modelled primarily after
2 * the description of the Mogo engine. */
12 #include "joseki/base.h"
16 #include "playout/moggy.h"
18 #include "tactics/1lib.h"
19 #include "tactics/2lib.h"
20 #include "tactics/ladder.h"
21 #include "tactics/selfatari.h"
22 #include "uct/prior.h"
24 #define PLDEBUGL(n) DEBUGL_(p->debug_level, n)
27 /* In case "seqchoose" move picker is enabled (i.e. no "fullchoose"
28 * parameter passed), we stochastically apply fixed set of decision
29 * rules in given order.
31 * In "fullchoose" mode, we instead build a move queue of variously
32 * tagged candidates, then consider a probability distribution over
33 * them and pick a move from that. */
35 /* Move queue tags. Some may be even undesirable - these moves then
36 * receive a penalty; penalty tags should be used only when it is
37 * certain the move would be considered anyway. */
49 /* Note that the context can be shared by multiple threads! */
52 unsigned int lcapturerate
, atarirate
, capturerate
, patternrate
, korate
, josekirate
;
53 unsigned int selfatarirate
, alwaysccaprate
;
54 unsigned int fillboardtries
;
56 /* Whether to look for patterns around second-to-last move. */
58 /* Whether, when self-atari attempt is detected, to play the other
59 * group's liberty if that is non-self-atari. */
61 /* Whether to always pick from moves capturing all groups in
62 * global_atari_check(). */
65 struct joseki_dict
*jdict
;
66 struct pattern3s patterns
;
68 /* Gamma values for queue tags - correspond to probabilities. */
70 double mq_prob
[MQ_MAX
], tenuki_prob
;
74 static char moggy_patterns_src
[][11] = {
75 /* hane pattern - enclosing hane */
79 /* hane pattern - non-cutting hane */
83 /* hane pattern - magari */
87 /* hane pattern - thin hane */
91 /* generic pattern - katatsuke or diagonal attachment; similar to magari */
95 /* cut1 pattern (kiri) - unprotected cut */
99 /* cut1 pattern (kiri) - peeped cut */
103 /* cut2 pattern (de) */
107 /* cut keima (not in Mogo) */
110 "???", /* o?? has some pathological tsumego cases */
111 /* side pattern - chase */
115 /* side pattern - block side cut */
119 /* side pattern - block side connection */
123 /* side pattern - sagari (SUSPICIOUS) */
125 "x.x" /* Mogo has "x.?" */
126 "###" /* Mogo has "X" */,
127 /* side pattern - throw-in (SUSPICIOUS) */
133 /* side pattern - cut (SUSPICIOUS) */
136 "###" /* Mogo has "X" */,
138 #define moggy_patterns_src_n sizeof(moggy_patterns_src) / sizeof(moggy_patterns_src[0])
141 test_pattern3_here(struct playout_policy
*p
, struct board
*b
, struct move
*m
)
143 struct moggy_policy
*pp
= p
->data
;
144 /* Check if 3x3 pattern is matched by given move... */
145 if (!pattern3_move_here(&pp
->patterns
, b
, m
))
147 /* ...and the move is not obviously stupid. */
148 if (is_bad_selfatari(b
, m
->color
, m
->coord
))
150 /* Ladder moves are stupid. */
151 group_t atari_neighbor
= board_get_atari_neighbor(b
, m
->coord
, m
->color
);
152 if (atari_neighbor
&& is_ladder(b
, m
->coord
, atari_neighbor
))
158 apply_pattern_here(struct playout_policy
*p
, struct board
*b
, coord_t c
, enum stone color
, struct move_queue
*q
)
160 struct move m2
= { .coord
= c
, .color
= color
};
161 if (board_is_valid_move(b
, &m2
) && test_pattern3_here(p
, b
, &m2
))
162 mq_add(q
, c
, 1<<MQ_PAT3
);
165 /* Check if we match any pattern around given move (with the other color to play). */
167 apply_pattern(struct playout_policy
*p
, struct board
*b
, struct move
*m
, struct move
*mm
, struct move_queue
*q
)
169 /* Suicides do not make any patterns and confuse us. */
170 if (board_at(b
, m
->coord
) == S_NONE
|| board_at(b
, m
->coord
) == S_OFFBOARD
)
173 foreach_8neighbor(b
, m
->coord
) {
174 apply_pattern_here(p
, b
, c
, stone_other(m
->color
), q
);
175 } foreach_8neighbor_end
;
177 if (mm
) { /* Second move for pattern searching */
178 foreach_8neighbor(b
, mm
->coord
) {
179 if (coord_is_8adjecent(m
->coord
, c
, b
))
181 apply_pattern_here(p
, b
, c
, stone_other(m
->color
), q
);
182 } foreach_8neighbor_end
;
186 mq_print(q
, b
, "Pattern");
191 joseki_check(struct playout_policy
*p
, struct board
*b
, enum stone to_play
, struct move_queue
*q
)
193 struct moggy_policy
*pp
= p
->data
;
197 for (int i
= 0; i
< 4; i
++) {
198 hash_t h
= b
->qhash
[i
] & joseki_hash_mask
;
199 coord_t
*cc
= pp
->jdict
->patterns
[h
].moves
[to_play
];
201 for (; !is_pass(*cc
); cc
++) {
202 if (coord_quadrant(*cc
, b
) != i
)
204 mq_add(q
, *cc
, 1<<MQ_JOSEKI
);
208 if (q
->moves
> 0 && PLDEBUGL(5))
209 mq_print(q
, b
, "Joseki");
213 global_atari_check(struct playout_policy
*p
, struct board
*b
, enum stone to_play
, struct move_queue
*q
)
218 struct moggy_policy
*pp
= p
->data
;
219 if (pp
->capcheckall
) {
220 for (int g
= 0; g
< b
->clen
; g
++)
221 group_atari_check(pp
->alwaysccaprate
, b
, group_at(b
, group_base(b
->c
[g
])), to_play
, q
, NULL
, 1<<MQ_GATARI
);
223 mq_print(q
, b
, "Global atari");
227 int g_base
= fast_random(b
->clen
);
228 for (int g
= g_base
; g
< b
->clen
; g
++) {
229 group_atari_check(pp
->alwaysccaprate
, b
, group_at(b
, group_base(b
->c
[g
])), to_play
, q
, NULL
, 1<<MQ_GATARI
);
231 /* XXX: Try carrying on. */
233 mq_print(q
, b
, "Global atari");
237 for (int g
= 0; g
< g_base
; g
++) {
238 group_atari_check(pp
->alwaysccaprate
, b
, group_at(b
, group_base(b
->c
[g
])), to_play
, q
, NULL
, 1<<MQ_GATARI
);
240 /* XXX: Try carrying on. */
242 mq_print(q
, b
, "Global atari");
250 local_atari_check(struct playout_policy
*p
, struct board
*b
, struct move
*m
, struct move_queue
*q
)
252 struct moggy_policy
*pp
= p
->data
;
254 /* Did the opponent play a self-atari? */
255 if (board_group_info(b
, group_at(b
, m
->coord
)).libs
== 1) {
256 group_atari_check(pp
->alwaysccaprate
, b
, group_at(b
, m
->coord
), stone_other(m
->color
), q
, NULL
, 1<<MQ_LATARI
);
259 foreach_neighbor(b
, m
->coord
, {
260 group_t g
= group_at(b
, c
);
261 if (!g
|| board_group_info(b
, g
).libs
!= 1)
263 group_atari_check(pp
->alwaysccaprate
, b
, g
, stone_other(m
->color
), q
, NULL
, 1<<MQ_LATARI
);
267 mq_print(q
, b
, "Local atari");
272 local_2lib_check(struct playout_policy
*p
, struct board
*b
, struct move
*m
, struct move_queue
*q
)
274 /* Does the opponent have just two liberties? */
275 if (board_group_info(b
, group_at(b
, m
->coord
)).libs
== 2) {
276 group_2lib_check(b
, group_at(b
, m
->coord
), stone_other(m
->color
), q
, 1<<MQ_L2LIB
);
278 /* We always prefer to take off an enemy chain liberty
279 * before pulling out ourselves. */
280 /* XXX: We aren't guaranteed to return to that group
283 return q
->move
[fast_random(q
->moves
)];
287 /* Then he took a third liberty from neighboring chain? */
288 foreach_neighbor(b
, m
->coord
, {
289 group_t g
= group_at(b
, c
);
290 if (!g
|| board_group_info(b
, g
).libs
!= 2)
292 group_2lib_check(b
, g
, stone_other(m
->color
), q
, 1<<MQ_L2LIB
);
296 mq_print(q
, b
, "Local 2lib");
300 fillboard_check(struct playout_policy
*p
, struct board
*b
)
302 struct moggy_policy
*pp
= p
->data
;
303 unsigned int fbtries
= b
->flen
/ 8;
304 if (pp
->fillboardtries
< fbtries
)
305 fbtries
= pp
->fillboardtries
;
307 for (unsigned int i
= 0; i
< fbtries
; i
++) {
308 coord_t coord
= b
->f
[fast_random(b
->flen
)];
309 if (immediate_liberty_count(b
, coord
) != 4)
311 foreach_diag_neighbor(b
, coord
) {
312 if (board_at(b
, c
) != S_NONE
)
314 } foreach_diag_neighbor_end
;
322 playout_moggy_seqchoose(struct playout_policy
*p
, struct playout_setup
*s
, struct board
*b
, enum stone to_play
)
324 struct moggy_policy
*pp
= p
->data
;
327 board_print(b
, stderr
);
330 if (!is_pass(b
->last_ko
.coord
) && is_pass(b
->ko
.coord
)
331 && b
->moves
- b
->last_ko_age
< pp
->koage
332 && pp
->korate
> fast_random(100)) {
333 if (board_is_valid_play(b
, to_play
, b
->last_ko
.coord
)
334 && !is_bad_selfatari(b
, to_play
, b
->last_ko
.coord
))
335 return b
->last_ko
.coord
;
339 if (!is_pass(b
->last_move
.coord
)) {
340 /* Local group in atari? */
341 if (pp
->lcapturerate
> fast_random(100)) {
342 struct move_queue q
; q
.moves
= 0;
343 local_atari_check(p
, b
, &b
->last_move
, &q
);
348 /* Local group can be PUT in atari? */
349 if (pp
->atarirate
> fast_random(100)) {
350 struct move_queue q
; q
.moves
= 0;
351 local_2lib_check(p
, b
, &b
->last_move
, &q
);
356 /* Check for patterns we know */
357 if (pp
->patternrate
> fast_random(100)) {
358 struct move_queue q
; q
.moves
= 0;
359 apply_pattern(p
, b
, &b
->last_move
,
360 pp
->pattern2
&& b
->last_move2
.coord
>= 0 ? &b
->last_move2
: NULL
,
369 /* Any groups in atari? */
370 if (pp
->capturerate
> fast_random(100)) {
371 struct move_queue q
; q
.moves
= 0;
372 global_atari_check(p
, b
, to_play
, &q
);
378 if (pp
->josekirate
> fast_random(100)) {
379 struct move_queue q
; q
.moves
= 0;
380 joseki_check(p
, b
, to_play
, &q
);
386 if (pp
->fillboardtries
> 0) {
387 coord_t c
= fillboard_check(p
, b
);
395 /* Pick a move from queue q, giving different likelihoods to moves
396 * based on their tags. */
398 mq_tagged_choose(struct playout_policy
*p
, struct board
*b
, enum stone to_play
, struct move_queue
*q
)
400 struct moggy_policy
*pp
= p
->data
;
402 /* First, merge all entries for a move. */
403 /* We use a naive O(N^2) since the average length of the queue
405 for (unsigned int i
= 0; i
< q
->moves
; i
++) {
406 for (unsigned int j
= i
+ 1; j
< q
->moves
; j
++) {
407 if (q
->move
[i
] != q
->move
[j
])
409 q
->tag
[i
] |= q
->tag
[j
];
411 q
->tag
[j
] = q
->tag
[q
->moves
];
412 q
->move
[j
] = q
->move
[q
->moves
];
416 /* Now, construct a probdist. */
419 for (unsigned int i
= 0; i
< q
->moves
; i
++) {
421 assert(q
->tag
[i
] != 0);
422 for (int j
= 0; j
< MQ_MAX
; j
++)
423 if (q
->tag
[i
] & (1<<j
)) {
424 //fprintf(stderr, "%s(%x) %d %f *= %f\n", coord2sstr(q->move[i], b), q->tag[i], j, val, pp->mq_prob[j]);
425 val
*= pp
->mq_prob
[j
];
427 pd
[i
] = double_to_fixp(val
);
430 total
+= double_to_fixp(pp
->tenuki_prob
);
432 /* Finally, pick a move! */
433 fixp_t stab
= fast_irandom(total
);
434 for (unsigned int i
= 0; i
< q
->moves
; i
++) {
435 //fprintf(stderr, "%s(%x) %f (%f/%f)\n", coord2sstr(q->move[i], b), q->tag[i], fixp_to_double(stab), fixp_to_double(pd[i]), fixp_to_double(total));
442 assert(stab
< double_to_fixp(pp
->tenuki_prob
));
447 playout_moggy_fullchoose(struct playout_policy
*p
, struct playout_setup
*s
, struct board
*b
, enum stone to_play
)
449 struct moggy_policy
*pp
= p
->data
;
450 struct move_queue q
; q
.moves
= 0;
453 board_print(b
, stderr
);
456 if (!is_pass(b
->last_ko
.coord
) && is_pass(b
->ko
.coord
)
457 && b
->moves
- b
->last_ko_age
< pp
->koage
) {
458 if (board_is_valid_play(b
, to_play
, b
->last_ko
.coord
)
459 && !is_bad_selfatari(b
, to_play
, b
->last_ko
.coord
))
460 mq_add(&q
, b
->last_ko
.coord
, 1<<MQ_KO
);
464 if (!is_pass(b
->last_move
.coord
)) {
465 /* Local group in atari? */
466 local_atari_check(p
, b
, &b
->last_move
, &q
);
468 /* Local group can be PUT in atari? */
469 local_2lib_check(p
, b
, &b
->last_move
, &q
);
471 /* Check for patterns we know */
472 apply_pattern(p
, b
, &b
->last_move
,
473 pp
->pattern2
&& b
->last_move2
.coord
>= 0 ? &b
->last_move2
: NULL
,
479 /* Any groups in atari? */
480 global_atari_check(p
, b
, to_play
, &q
);
483 joseki_check(p
, b
, to_play
, &q
);
486 /* Average length of the queue is 1.4 move. */
487 printf("MQL %d ", q
.moves
);
488 for (unsigned int i
= 0; i
< q
.moves
; i
++)
489 printf("%s ", coord2sstr(q
.move
[i
], b
));
494 return mq_tagged_choose(p
, b
, to_play
, &q
);
497 if (pp
->fillboardtries
> 0) {
498 coord_t c
= fillboard_check(p
, b
);
508 playout_moggy_assess_group(struct playout_policy
*p
, struct prior_map
*map
, group_t g
, int games
)
510 struct moggy_policy
*pp
= p
->data
;
511 struct board
*b
= map
->b
;
512 struct move_queue q
; q
.moves
= 0;
514 if (board_group_info(b
, g
).libs
> 2)
518 fprintf(stderr
, "ASSESS of group %s:\n", coord2sstr(g
, b
));
519 board_print(b
, stderr
);
522 if (board_group_info(b
, g
).libs
== 2) {
525 group_2lib_check(b
, g
, map
->to_play
, &q
, 0);
527 coord_t coord
= q
.move
[q
.moves
];
529 fprintf(stderr
, "1.0: 2lib %s\n", coord2sstr(coord
, b
));
530 int assess
= games
/ 2;
531 add_prior_value(map
, coord
, 1, assess
);
536 /* This group, sir, is in atari! */
538 coord_t ladder
= pass
;
539 group_atari_check(pp
->alwaysccaprate
, b
, g
, map
->to_play
, &q
, &ladder
, 0);
541 coord_t coord
= q
.move
[q
.moves
];
543 /* _Never_ play here if this move plays out
544 * a caught ladder. */
545 if (coord
== ladder
&& !board_playing_ko_threat(b
)) {
546 /* Note that the opposite is not guarded against;
547 * we do not advise against capturing a laddered
548 * group (but we don't encourage it either). Such
549 * a move can simplify tactical situations if we
551 if (map
->to_play
!= board_at(b
, g
))
553 /* FIXME: We give the malus even if this move
554 * captures another group. */
556 fprintf(stderr
, "0.0: ladder %s\n", coord2sstr(coord
, b
));
557 add_prior_value(map
, coord
, 0, games
);
561 if (!pp
->capturerate
&& !pp
->lcapturerate
)
565 fprintf(stderr
, "1.0: atari %s\n", coord2sstr(coord
, b
));
566 int assess
= games
* 2;
567 add_prior_value(map
, coord
, 1, assess
);
572 playout_moggy_assess_one(struct playout_policy
*p
, struct prior_map
*map
, coord_t coord
, int games
)
574 struct moggy_policy
*pp
= p
->data
;
575 struct board
*b
= map
->b
;
578 fprintf(stderr
, "ASSESS of move %s:\n", coord2sstr(coord
, b
));
579 board_print(b
, stderr
);
582 /* Is this move a self-atari? */
583 if (pp
->selfatarirate
) {
584 if (!board_playing_ko_threat(b
) && is_bad_selfatari(b
, map
->to_play
, coord
)) {
586 fprintf(stderr
, "0.0: self-atari\n");
587 add_prior_value(map
, coord
, 0, games
);
588 if (!pp
->selfatari_other
)
590 /* If we can play on the other liberty of the
591 * endangered group, do! */
592 coord
= selfatari_cousin(b
, map
->to_play
, coord
);
596 fprintf(stderr
, "1.0: self-atari redirect %s\n", coord2sstr(coord
, b
));
597 add_prior_value(map
, coord
, 1.0, games
);
603 if (pp
->patternrate
) {
604 struct move m
= { .color
= map
->to_play
, .coord
= coord
};
605 if (test_pattern3_here(p
, b
, &m
)) {
607 fprintf(stderr
, "1.0: pattern\n");
608 add_prior_value(map
, coord
, 1, games
);
616 playout_moggy_assess(struct playout_policy
*p
, struct prior_map
*map
, int games
)
618 struct moggy_policy
*pp
= p
->data
;
620 /* First, go through all endangered groups. */
621 for (group_t g
= 1; g
< board_size2(map
->b
); g
++)
622 if (group_at(map
->b
, g
) == g
)
623 playout_moggy_assess_group(p
, map
, g
, games
);
625 /* Then, assess individual moves. */
626 if (!pp
->patternrate
&& !pp
->selfatarirate
)
628 foreach_free_point(map
->b
) {
629 if (map
->consider
[c
])
630 playout_moggy_assess_one(p
, map
, c
, games
);
631 } foreach_free_point_end
;
635 playout_moggy_permit(struct playout_policy
*p
, struct board
*b
, struct move
*m
)
637 struct moggy_policy
*pp
= p
->data
;
639 /* The idea is simple for now - never allow self-atari moves.
640 * They suck in general, but this also permits us to actually
641 * handle seki in the playout stage. */
643 if (fast_random(100) >= pp
->selfatarirate
) {
645 fprintf(stderr
, "skipping sar test\n");
648 bool selfatari
= is_bad_selfatari(b
, m
->color
, m
->coord
);
651 fprintf(stderr
, "__ Prohibiting self-atari %s %s\n",
652 stone2str(m
->color
), coord2sstr(m
->coord
, b
));
653 if (pp
->selfatari_other
) {
654 /* Ok, try the other liberty of the atari'd group. */
655 coord_t c
= selfatari_cousin(b
, m
->color
, m
->coord
);
656 if (is_pass(c
)) return false;
658 fprintf(stderr
, "___ Redirecting to other lib %s\n",
669 struct playout_policy
*
670 playout_moggy_init(char *arg
, struct board
*b
, struct joseki_dict
*jdict
)
672 struct playout_policy
*p
= calloc2(1, sizeof(*p
));
673 struct moggy_policy
*pp
= calloc2(1, sizeof(*pp
));
675 p
->choose
= playout_moggy_seqchoose
;
676 p
->assess
= playout_moggy_assess
;
677 p
->permit
= playout_moggy_permit
;
683 pp
->lcapturerate
= pp
->atarirate
= pp
->capturerate
= pp
->patternrate
684 = pp
->selfatarirate
= pp
->josekirate
= -1U;
685 pp
->korate
= 20; pp
->koage
= 4;
686 pp
->alwaysccaprate
= 20;
687 pp
->selfatari_other
= true;
690 double mq_prob_default
[MQ_MAX
] = {
698 memcpy(pp
->mq_prob
, mq_prob_default
, sizeof(pp
->mq_prob
));
701 char *optspec
, *next
= arg
;
704 next
+= strcspn(next
, ":");
705 if (*next
) { *next
++ = 0; } else { *next
= 0; }
707 char *optname
= optspec
;
708 char *optval
= strchr(optspec
, '=');
709 if (optval
) *optval
++ = 0;
711 if (!strcasecmp(optname
, "debug") && optval
) {
712 p
->debug_level
= atoi(optval
);
713 } else if (!strcasecmp(optname
, "lcapturerate") && optval
) {
714 pp
->lcapturerate
= atoi(optval
);
715 } else if (!strcasecmp(optname
, "atarirate") && optval
) {
716 pp
->atarirate
= atoi(optval
);
717 } else if (!strcasecmp(optname
, "capturerate") && optval
) {
718 pp
->capturerate
= atoi(optval
);
719 } else if (!strcasecmp(optname
, "patternrate") && optval
) {
720 pp
->patternrate
= atoi(optval
);
721 } else if (!strcasecmp(optname
, "selfatarirate") && optval
) {
722 pp
->selfatarirate
= atoi(optval
);
723 } else if (!strcasecmp(optname
, "korate") && optval
) {
724 pp
->korate
= atoi(optval
);
725 } else if (!strcasecmp(optname
, "josekirate") && optval
) {
726 pp
->josekirate
= atoi(optval
);
727 } else if (!strcasecmp(optname
, "alwaysccaprate") && optval
) {
728 pp
->alwaysccaprate
= atoi(optval
);
729 } else if (!strcasecmp(optname
, "rate") && optval
) {
731 } else if (!strcasecmp(optname
, "fillboardtries")) {
732 pp
->fillboardtries
= atoi(optval
);
733 } else if (!strcasecmp(optname
, "koage") && optval
) {
734 pp
->koage
= atoi(optval
);
735 } else if (!strcasecmp(optname
, "pattern2")) {
736 pp
->pattern2
= optval
&& *optval
== '0' ? false : true;
737 } else if (!strcasecmp(optname
, "selfatari_other")) {
738 pp
->selfatari_other
= optval
&& *optval
== '0' ? false : true;
739 } else if (!strcasecmp(optname
, "capcheckall")) {
740 pp
->capcheckall
= optval
&& *optval
== '0' ? false : true;
741 } else if (!strcasecmp(optname
, "fullchoose")) {
742 p
->choose
= optval
&& *optval
== '0' ? playout_moggy_seqchoose
: playout_moggy_fullchoose
;
743 } else if (!strcasecmp(optname
, "mqprob") && optval
) {
744 /* KO%LATARI%L2LIB%PAT3%GATARI%JOSEKI */
745 for (int i
= 0; *optval
&& i
< MQ_MAX
; i
++, optval
+= strcspn(optval
, "%")) {
747 pp
->mq_prob
[i
] = atof(optval
);
749 } else if (!strcasecmp(optname
, "tenukiprob") && optval
) {
750 pp
->tenuki_prob
= atof(optval
);
752 fprintf(stderr
, "playout-moggy: Invalid policy argument %s or missing value\n", optname
);
757 if (pp
->lcapturerate
== -1U) pp
->lcapturerate
= rate
;
758 if (pp
->atarirate
== -1U) pp
->atarirate
= rate
;
759 if (pp
->capturerate
== -1U) pp
->capturerate
= rate
;
760 if (pp
->patternrate
== -1U) pp
->patternrate
= rate
;
761 if (pp
->selfatarirate
== -1U) pp
->selfatarirate
= rate
;
762 if (pp
->korate
== -1U) pp
->korate
= rate
;
763 if (pp
->josekirate
== -1U) pp
->josekirate
= rate
;
764 if (pp
->alwaysccaprate
== -1U) pp
->alwaysccaprate
= rate
;
766 pattern3s_init(&pp
->patterns
, moggy_patterns_src
, moggy_patterns_src_n
);