10 #include "playout/moggy.h"
13 #define PLDEBUGL(n) DEBUGL_(p->debug_level, n)
17 bool ladders
, ladderassess
, borderladders
;
18 int lcapturerate
, capturerate
, patternrate
;
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 */
40 /* hane pattern - non-cutting hane */
44 /* hane pattern - magari */
48 /* hane pattern - thin hane (SUSPICIOUS) */
52 /* cut1 pattern (kiri) - unprotected cut */
56 /* cut1 pattern (kiri) - peeped cut */
60 /* cut2 pattern (de) */
64 /* side pattern - chase */
68 /* side pattern - weirdness (SUSPICIOUS) */
72 /* side pattern - sagari (SUSPICIOUS) */
76 /* side pattern - weirdcut (SUSPICIOUS) */
80 /* side pattern - cut (SUSPICIOUS) */
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];
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;
103 _gen_pattern(char *table
, int pat
, char *src
, int srclen
, int fixed_color
)
105 for (; srclen
> 0; src
++, srclen
--) {
108 int patofs
= (srclen
> 5 ? srclen
- 1 : srclen
) - 1;
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
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
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
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 */
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
))
165 for (int i
= 0; i
< moggy_patterns_src_n
; i
++) {
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. */
179 test_pattern_here(struct playout_policy
*p
, char *hashtable
,
180 struct board
*b
, struct move
*m
)
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
);
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). */
206 apply_pattern(struct playout_policy
*p
, struct board
*b
, struct move
*m
, struct move
*testmove
)
208 //struct moggy_policy *pp = p->data;
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
)
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
;
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");
238 if (q
.move
[q
.moves
] == testmove
->coord
) {
240 fprintf(stderr
, "Found queried move.\n");
241 return testmove
->coord
;
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. */
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
;
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) {
281 fprintf(stderr
, "border ladder\n");
282 /* Direction along border; xd is horiz. border, yd vertical. */
284 if (board_atxy(b
, x
+ 1, y
) == S_OFFBOARD
|| board_atxy(b
, x
- 1, y
) == S_OFFBOARD
)
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;
291 fprintf(stderr
, "xd %d yd %d dd %d\n", xd
, yd
, dd
);
297 /* This is normally caught, unless we have friends both above
299 if (board_atxy(b
, x
+ xd
* 2, y
+ yd
* 2) == lcolor
300 && board_atxy(b
, x
- xd
* 2, y
- yd
* 2) == lcolor
)
302 /* ...or can't block where we need because of shortage
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
;
307 fprintf(stderr
, "libs1 %d libs2 %d\n", libs1
, libs2
);
308 if (libs1
< 2 && libs2
< 2)
310 if (board_atxy(b
, x
+ xd
* 2, y
+ yd
* 2) == lcolor
&& libs1
< 3)
312 if (board_atxy(b
, x
- xd
* 2, y
- yd
* 2) == lcolor
&& libs2
< 3)
317 /* Figure out the ladder direction */
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:
325 * c O X supported . c O unsupported
329 /* For given (xd,yd), we have two possibilities where to move
330 * next. Consider (-1,1):
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. */
339 fprintf(stderr
, "non-simple ladder\n");
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 */ \
351 /* No. So we are at new position. \
352 * We need to check indirect ladder breakers. */ \
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 \
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
))
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
);
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
))
394 fprintf(stderr
, "...escape route valid\n");
396 /* ...or play out ladders. */
397 if (pp
->ladders
&& ladder_catches(p
, b
, lib
, group
)) {
401 fprintf(stderr
, "...no ladder\n");
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)
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! */
420 } foreach_in_group_end
;
425 global_atari_check(struct playout_policy
*p
, struct board
*b
)
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
])));
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
])));
445 local_atari_check(struct playout_policy
*p
, struct board
*b
, struct move
*m
, struct move
*testmove
)
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
));
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)
461 coord_t l
= group_atari_check(p
, b
, g
);
463 q
.move
[q
.moves
++] = l
;
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");
476 if (q
.move
[q
.moves
] == testmove
->coord
) {
478 fprintf(stderr
, "Found queried move.\n");
479 return testmove
->coord
;
484 int i
= fast_random(q
.moves
);
485 return q
.moves
? q
.move
[i
] : pass
;
489 playout_moggy_choose(struct playout_policy
*p
, struct board
*b
, enum stone our_real_color
)
491 struct moggy_policy
*pp
= p
->data
;
495 board_print(b
, stderr
);
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
);
506 /* Check for patterns we know */
507 if (pp
->patternrate
> fast_random(100)) {
508 c
= apply_pattern(p
, b
, &b
->last_move
, NULL
);
516 /* Any groups in atari? */
517 if (pp
->capturerate
> fast_random(100)) {
518 c
= global_atari_check(p
, b
);
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
))
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
, {
543 m2
.coord
= c
; m2
.color
= stone_other(m
->color
);
544 if (local_atari_check(p
, b
, &m2
, m
) == m
->coord
)
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
)
554 group_t g
= group_at(b
, c
);
555 if (board_group_info(b
, g
).libs
!= 1)
557 if (ladder_catches(p
, b
, m
->coord
, g
))
564 if (pp
->patternrate
> fast_random(100)) {
565 if (test_pattern_here(p
, moggy_patterns
, b
, m
))
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
));
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;
589 char *optspec
, *next
= arg
;
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;
612 fprintf(stderr
, "playout-moggy: Invalid policy argument %s or missing value\n", optname
);