10 #include "playout/moggy.h"
13 #define PLDEBUGL(n) DEBUGL_(p->debug_level, n)
17 bool ladders
, ladderassess
, borderladders
;
18 int lcapturerate
, capturerate
, patternrate
;
19 /* These are relative to patternrate. */
20 int hanerate
, cut1rate
, cut2rate
;
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 mogo_patterns_src
[][11] = {
38 /* hane pattern - enclosing hane */
42 /* hane pattern - non-cutting hane */
46 /* hane pattern - magari */
50 /* hane pattern - thin hane (SUSPICIOUS) */
54 /* cut1 pattern (kiri) - unprotected cut */
58 /* cut1 pattern (kiri) - peeped cut */
62 /* cut2 pattern (de) */
66 /* side pattern - chase */
70 /* side pattern - weirdness (SUSPICIOUS) */
74 /* side pattern - sagari (SUSPICIOUS) */
78 /* side pattern - weirdcut (SUSPICIOUS) */
82 /* side pattern - cut (SUSPICIOUS) */
85 "###" "X" /* no "X"? */,
87 #define mogo_patterns_src_n sizeof(mogo_patterns_src) / sizeof(mogo_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 mogo_patterns
[65536];
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;
105 _gen_pattern(char *table
, int pat
, char *src
, int srclen
, int fixed_color
)
107 for (; srclen
> 0; src
++, srclen
--) {
110 int patofs
= (srclen
> 5 ? srclen
- 1 : srclen
) - 1;
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
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
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
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 */
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
))
167 for (int i
= 0; i
< mogo_patterns_src_n
; i
++) {
169 switch (mogo_patterns_src
[i
][9]) {
170 case 'X': fixed_color
= S_BLACK
; break;
171 case 'O': fixed_color
= S_WHITE
; break;
173 _gen_pattern(mogo_patterns
, 0, mogo_patterns_src
[i
], 9, fixed_color
);
179 /* Check if we match any pattern centered on given move. */
181 test_pattern_here(struct playout_policy
*p
, char *hashtable
,
182 struct board
*b
, struct move
*m
)
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
);
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). */
208 apply_pattern(struct playout_policy
*p
, struct board
*b
, struct move
*m
, struct move
*testmove
)
210 //struct moggy_policy *pp = p->data;
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
)
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
)
222 apply_pattern_here(p
, mogo_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
)
227 apply_pattern_here(p
, mogo_patterns
, b
, &m2
, &q
);
228 } foreach_diag_neighbor_end
;
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");
240 if (q
.move
[q
.moves
] == testmove
->coord
) {
242 fprintf(stderr
, "Found queried move.\n");
243 return testmove
->coord
;
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. */
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
;
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) {
283 fprintf(stderr
, "border ladder\n");
284 /* Direction along border; xd is horiz. border, yd vertical. */
286 if (board_atxy(b
, x
+ 1, y
) == S_OFFBOARD
|| board_atxy(b
, x
- 1, y
) == S_OFFBOARD
)
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;
293 fprintf(stderr
, "xd %d yd %d dd %d\n", xd
, yd
, dd
);
299 /* This is normally caught, unless we have friends both above
301 if (board_atxy(b
, x
+ xd
* 2, y
+ yd
* 2) == lcolor
302 && board_atxy(b
, x
- xd
* 2, y
- yd
* 2) == lcolor
)
304 /* ...or can't block where we need because of shortage
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
;
309 fprintf(stderr
, "libs1 %d libs2 %d\n", libs1
, libs2
);
310 if (libs1
< 2 && libs2
< 2)
312 if (board_atxy(b
, x
+ xd
* 2, y
+ yd
* 2) == lcolor
&& libs1
< 3)
314 if (board_atxy(b
, x
- xd
* 2, y
- yd
* 2) == lcolor
&& libs2
< 3)
319 /* Figure out the ladder direction */
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:
327 * c O X supported . c O unsupported
331 /* For given (xd,yd), we have two possibilities where to move
332 * next. Consider (-1,1):
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. */
341 fprintf(stderr
, "non-simple ladder\n");
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 */ \
353 /* No. So we are at new position. \
354 * We need to check indirect ladder breakers. */ \
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 \
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
))
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
);
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
))
396 fprintf(stderr
, "...escape route valid\n");
398 /* ...or play out ladders. */
399 if (pp
->ladders
&& ladder_catches(p
, b
, lib
, group
)) {
403 fprintf(stderr
, "...no ladder\n");
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)
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! */
422 } foreach_in_group_end
;
427 global_atari_check(struct playout_policy
*p
, struct board
*b
)
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
])));
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
])));
447 local_atari_check(struct playout_policy
*p
, struct board
*b
, struct move
*m
, struct move
*testmove
)
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
));
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)
463 coord_t l
= group_atari_check(p
, b
, g
);
465 q
.move
[q
.moves
++] = l
;
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");
478 if (q
.move
[q
.moves
] == testmove
->coord
) {
480 fprintf(stderr
, "Found queried move.\n");
481 return testmove
->coord
;
486 int i
= fast_random(q
.moves
);
487 return q
.moves
? q
.move
[i
] : pass
;
491 playout_moggy_choose(struct playout_policy
*p
, struct board
*b
, enum stone our_real_color
)
493 struct moggy_policy
*pp
= p
->data
;
497 board_print(b
, stderr
);
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
);
508 /* Check for patterns we know */
509 if (pp
->patternrate
> fast_random(100)) {
510 c
= apply_pattern(p
, b
, &b
->last_move
, NULL
);
518 /* Any groups in atari? */
519 if (pp
->capturerate
> fast_random(100)) {
520 c
= global_atari_check(p
, b
);
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
))
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
, {
545 m2
.coord
= c
; m2
.color
= stone_other(m
->color
);
546 if (local_atari_check(p
, b
, &m2
, m
) == m
->coord
)
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
)
556 group_t g
= group_at(b
, c
);
557 if (board_group_info(b
, g
).libs
!= 1)
559 if (ladder_catches(p
, b
, m
->coord
, g
))
566 if (pp
->patternrate
> fast_random(100)) {
567 if (test_pattern_here(p
, mogo_patterns
, b
, m
))
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
));
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;
592 char *optspec
, *next
= arg
;
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;
621 fprintf(stderr
, "playout-moggy: Invalid policy argument %s or missing value\n", optname
);