UCB1AMAF: Turn prior_even on, prior_gp off by default
[pachi.git] / playout / moggy.c
blob871ef5e90ab6d40519585ac8e6fdd74a8c08ecd8
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, localassess, 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 static bool
31 cut1_test_cut(struct playout_policy *p, struct board *b, coord_t base, coord_t cut)
33 /* X O ?
34 * O(.)? X is base, (.) is cut
35 * ? ? ? */
36 int x = coord_x(base, b), y = coord_y(base, b);
37 enum stone color = board_at(b, base);
38 int xc = coord_x(cut, b), yc = coord_y(cut, b);
40 if (PLDEBUGL(5))
41 fprintf(stderr, "Probing CUT1 %s -> %s\n", coord2sstr(base, b), coord2sstr(cut, b));
43 /* Kosumi available. Is it cutting? */
44 if (board_atxy(b, x, yc) != stone_other(color)
45 || board_atxy(b, xc, y) != stone_other(color))
46 return false;
48 /* It is! Is the cut protected? */
49 enum stone fix1 = board_atxy(b, xc, yc - (y - yc));
50 enum stone fix2 = board_atxy(b, xc - (x - xc), yc);
51 if (PLDEBUGL(6))
52 fprintf(stderr, "Protection check: %d,%d\n", fix1, fix2);
53 if ((fix1 == stone_other(color) || fix1 == S_OFFBOARD) && fix2 != color)
54 return false;
55 if ((fix2 == stone_other(color) || fix2 == S_OFFBOARD) && fix1 != color)
56 return false;
58 /* Unprotected cut. Feast! */
59 if (PLDEBUGL(6))
60 fprintf(stderr, "Passed.\n");
61 return true;
64 static void
65 cut1_test(struct playout_policy *p, struct board *b, struct move *m, struct move_queue *q)
67 coord_t coord = m->coord;
68 int x = coord_x(coord, b), y = coord_y(coord, b);
69 enum stone color = board_at(b, coord);
71 /* Either last move was cutting threat... */
72 foreach_diag_neighbor(b, coord) {
73 if (board_at(b, c) != S_NONE)
74 continue;
75 /* X O ?
76 * O(.)? X is coord, (.) is c
77 * ? ? ? */
78 if (cut1_test_cut(p, b, coord, c))
79 q->move[q->moves++] = c;
80 } foreach_diag_neighbor_end;
82 /* ...or a cuttable hane. */
83 #define cutbase_test(xb_, yb_) \
84 base = coord_xy_otf(xb_, yb_, b); \
85 if (board_at(b, base) == stone_other(color)) \
86 if (cut1_test_cut(p, b, base, c)) \
87 q->move[q->moves++] = c;
88 foreach_neighbor(b, coord, {
89 if (board_at(b, c) != S_NONE)
90 continue;
91 /* X O ?
92 * O(.)? O is coord, (.) is c
93 * ? ? ? */
94 /* Check for X on both sides of O. */
95 int xc = coord_x(c, b);
96 int yc = coord_y(c, b);
97 coord_t base;
98 /* Either x == xc or y == yc. */
99 cutbase_test(x - (yc - y), y - (xc - x));
100 cutbase_test(x + (yc - y), y + (xc - x));
102 #undef cutbase_test
105 static bool
106 cut2_test_cut(struct playout_policy *p, struct board *b, coord_t base, coord_t cut)
108 /* ? X ?
109 * O(.)O X is base, (.) is cut
110 * ? ? ? */
111 int x = coord_x(base, b), y = coord_y(base, b);
112 enum stone color = board_at(b, base);
113 int xc = coord_x(cut, b), yc = coord_y(cut, b);
115 if (PLDEBUGL(5))
116 fprintf(stderr, "Probing CUT2 %s -> %s\n", coord2sstr(base, b), coord2sstr(cut, b));
118 /* Nobi available. Is it cutting? */
119 if (board_atxy(b, xc - (yc - y), yc - (xc - x)) != stone_other(color)
120 || board_atxy(b, xc + (yc - y), yc + (xc - x)) != stone_other(color))
121 return false;
123 /* It is! Is the cut protected? */
124 enum stone ocolor = stone_other(color);
125 if (x == xc) {
126 if (PLDEBUGL(6))
127 fprintf(stderr, "Protection check - row [%d,%d].\n", xc, yc + (yc - y));
128 if (board_atxy(b, xc - 1, yc + (yc - y)) == ocolor
129 || board_atxy(b, xc, yc + (yc - y)) == ocolor
130 || board_atxy(b, xc + 1, yc + (yc - y)) == ocolor)
131 return false;
132 } else {
133 if (PLDEBUGL(6))
134 fprintf(stderr, "Protection check - column [%d,%d].\n", xc + (xc - x), yc);
135 if (board_atxy(b, xc + (xc - x), yc - 1) == ocolor
136 || board_atxy(b, xc + (xc - x), yc) == ocolor
137 || board_atxy(b, xc + (xc - x), yc + 1) == ocolor)
138 return false;
141 /* Unprotected cut. Feast! */
142 if (PLDEBUGL(6))
143 fprintf(stderr, "Passed.\n");
144 return true;
147 static void
148 cut2_test(struct playout_policy *p, struct board *b, struct move *m, struct move_queue *q)
150 coord_t coord = m->coord;
151 int x = coord_x(coord, b), y = coord_y(coord, b);
152 enum stone color = board_at(b, coord);
154 /* Either last move was cutting threat... */
155 foreach_neighbor(b, coord, {
156 if (board_at(b, c) != S_NONE)
157 continue;
158 /* ? X ?
159 * O(.)O X is coord, (.) is c
160 * ? ? ? */
161 if (cut2_test_cut(p, b, coord, c))
162 q->move[q->moves++] = c;
165 /* ...or a cuttable ikken tobi. */
166 #define cutbase_test(xb_, yb_) \
167 base = coord_xy_otf(xb_, yb_, b); \
168 if (board_at(b, base) == stone_other(color)) \
169 if (cut2_test_cut(p, b, base, c)) \
170 q->move[q->moves++] = c;
171 foreach_neighbor(b, coord, {
172 if (board_at(b, c) != S_NONE)
173 continue;
174 /* ? X ?
175 * O(.)O O is coord, (.) is c
176 * ? ? ? */
177 /* Check for X on both sides of (.). */
178 int xc = coord_x(c, b);
179 int yc = coord_y(c, b);
180 coord_t base;
181 /* Either x == xc or y == yc. */
182 cutbase_test(xc - (yc - y), yc - (xc - x));
183 cutbase_test(xc + (yc - y), yc + (xc - x));
185 #undef cutbase_test
188 /* Check if we match a certain pattern centered on given move. */
189 static coord_t
190 apply_pattern(struct playout_policy *p, struct board *b, struct move *m, struct move *testmove)
192 struct moggy_policy *pp = p->data;
193 struct move_queue q;
194 q.moves = 0;
196 /* Suicides do not make any patterns and confuse us. */
197 if (board_at(b, m->coord) == S_NONE || board_at(b, m->coord) == S_OFFBOARD)
198 return pass;
200 if (pp->hanerate > fast_random(100)) {
201 /* TODO */
204 if (pp->cut1rate > fast_random(100)) {
205 cut1_test(p, b, m, &q);
208 if (pp->cut2rate > fast_random(100)) {
209 cut2_test(p, b, m, &q);
212 if (PLDEBUGL(5)) {
213 fprintf(stderr, "Pattern candidate moves: ");
214 for (int i = 0; i < q.moves; i++) {
215 fprintf(stderr, "%s ", coord2sstr(q.move[i], b));
217 fprintf(stderr, "\n");
220 if (testmove) {
221 while (q.moves--)
222 if (q.move[q.moves] == testmove->coord) {
223 if (PLDEBUGL(5))
224 fprintf(stderr, "Found queried move.\n");
225 return testmove->coord;
227 return pass;
230 int i = fast_random(q.moves);
231 return q.moves ? q.move[i] : pass;
236 /* Is this ladder breaker friendly for the one who catches ladder. */
237 static bool
238 ladder_catcher(struct board *b, int x, int y, enum stone laddered)
240 enum stone breaker = board_atxy(b, x, y);
241 return breaker == stone_other(laddered) || breaker == S_OFFBOARD;
244 static bool
245 ladder_catches(struct playout_policy *p, struct board *b, coord_t coord, group_t laddered)
247 struct moggy_policy *pp = p->data;
249 /* This is very trivial and gets a lot of corner cases wrong.
250 * We need this to be just very fast. One important point is
251 * that we sometimes might not notice a ladder but if we do,
252 * it should always work; thus we can use this for strong
253 * negative hinting safely. */
254 //fprintf(stderr, "ladder check\n");
256 enum stone lcolor = board_at(b, group_base(laddered));
257 int x = coord_x(coord, b), y = coord_y(coord, b);
259 /* First, special-case first-line "ladders". This is a huge chunk
260 * of ladders we actually meet and want to play. */
261 if (pp->borderladders
262 && neighbor_count_at(b, coord, S_OFFBOARD) == 1
263 && neighbor_count_at(b, coord, lcolor) == 1) {
264 if (PLDEBUGL(5))
265 fprintf(stderr, "border ladder\n");
266 /* Direction along border; xd is horiz. border, yd vertical. */
267 int xd = 0, yd = 0;
268 if (board_atxy(b, x + 1, y) == S_OFFBOARD || board_atxy(b, x - 1, y) == S_OFFBOARD)
269 yd = 1;
270 else
271 xd = 1;
272 /* Direction from the border; -1 is above/left, 1 is below/right. */
273 int dd = (board_atxy(b, x + yd, y + xd) == S_OFFBOARD) ? 1 : -1;
274 if (PLDEBUGL(6))
275 fprintf(stderr, "xd %d yd %d dd %d\n", xd, yd, dd);
276 /* | ? ?
277 * | . O #
278 * | c X #
279 * | . O #
280 * | ? ? */
281 /* This is normally caught, unless we have friends both above
282 * and below... */
283 if (board_atxy(b, x + xd * 2, y + yd * 2) == lcolor
284 && board_atxy(b, x - xd * 2, y - yd * 2) == lcolor)
285 return false;
286 /* ...or can't block where we need because of shortage
287 * of liberties. */
288 int libs1 = board_group_info(b, group_atxy(b, x + xd - yd * dd, y + yd - xd * dd)).libs;
289 int libs2 = board_group_info(b, group_atxy(b, x - xd - yd * dd, y - yd - xd * dd)).libs;
290 if (PLDEBUGL(6))
291 fprintf(stderr, "libs1 %d libs2 %d\n", libs1, libs2);
292 if (libs1 < 2 && libs2 < 2)
293 return false;
294 if (board_atxy(b, x + xd * 2, y + yd * 2) == lcolor && libs1 < 3)
295 return false;
296 if (board_atxy(b, x - xd * 2, y - yd * 2) == lcolor && libs2 < 3)
297 return false;
298 return true;
301 /* Figure out the ladder direction */
302 int xd, yd;
303 xd = board_atxy(b, x + 1, y) == S_NONE ? 1 : board_atxy(b, x - 1, y) == S_NONE ? -1 : 0;
304 yd = board_atxy(b, x, y + 1) == S_NONE ? 1 : board_atxy(b, x, y - 1) == S_NONE ? -1 : 0;
306 /* We do only tight ladders, not loose ladders. Furthermore,
307 * the ladders need to be simple:
308 * . X . . . X
309 * c O X supported . c O unsupported
310 * X # # X O #
313 /* For given (xd,yd), we have two possibilities where to move
314 * next. Consider (-1,1):
315 * n X . n c X
316 * c O X X O #
317 * X # # . X #
319 if (!xd || !yd || !(ladder_catcher(b, x - xd, y, lcolor) ^ ladder_catcher(b, x, y - yd, lcolor))) {
320 /* Silly situation, probably non-simple ladder or suicide. */
321 /* TODO: In case of basic non-simple ladder, play out both variants. */
322 if (PLDEBUGL(5))
323 fprintf(stderr, "non-simple ladder\n");
324 return false;
327 #define ladder_check(xd1_, yd1_, xd2_, yd2_) \
328 if (board_atxy(b, x, y) != S_NONE) { \
329 /* Did we hit a stone when playing out ladder? */ \
330 if (ladder_catcher(b, x, y, lcolor)) \
331 return true; /* ladder works */ \
332 if (board_group_info(b, group_atxy(b, x, y)).lib[0] > 0) \
333 return false; /* friend that's not in atari himself */ \
334 } else { \
335 /* No. So we are at new position. \
336 * We need to check indirect ladder breakers. */ \
337 /* . 2 x . . \
338 * . x o O 1 <- only at O we can check for o at 2 \
339 * x o o x . otherwise x at O would be still deadly \
340 * o o x . . \
341 * We check for o and x at 1, these are vital. \
342 * We check only for o at 2; x at 2 would mean we \
343 * need to fork (one step earlier). */ \
344 enum stone s1 = board_atxy(b, x + (xd1_), y + (yd1_)); \
345 if (s1 == lcolor) return false; \
346 if (s1 == stone_other(lcolor)) return true; \
347 enum stone s2 = board_atxy(b, x + (xd2_), y + (yd2_)); \
348 if (s2 == lcolor) return false; \
350 #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)
351 #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)
353 if (ladder_catcher(b, x - xd, y, lcolor))
354 ladder_horiz;
355 do {
356 ladder_vert;
357 ladder_horiz;
358 } while (1);
362 static coord_t
363 group_atari_check(struct playout_policy *p, struct board *b, group_t group)
365 struct moggy_policy *pp = p->data;
366 enum stone color = board_at(b, group_base(group));
367 coord_t lib = board_group_info(b, group).lib[0];
369 assert(color != S_OFFBOARD && color != S_NONE);
370 if (PLDEBUGL(5))
371 fprintf(stderr, "atariiiiiiiii %s of color %d\n", coord2sstr(lib, b), color);
372 assert(board_at(b, lib) == S_NONE);
374 /* Do not suicide... */
375 if (!valid_escape_route(b, color, lib))
376 goto caught;
377 if (PLDEBUGL(6))
378 fprintf(stderr, "...escape route valid\n");
380 /* ...or play out ladders. */
381 if (pp->ladders && ladder_catches(p, b, lib, group)) {
382 goto caught;
384 if (PLDEBUGL(6))
385 fprintf(stderr, "...no ladder\n");
387 return lib;
389 caught:
390 /* There is still hope - can't we capture some neighbor? */
391 foreach_in_group(b, group) {
392 foreach_neighbor(b, c, {
393 if (board_at(b, c) != stone_other(color)
394 || board_group_info(b, group_at(b, c)).libs > 1)
395 continue;
396 if (PLDEBUGL(6))
397 fprintf(stderr, "can capture group %d\n", group_at(b, c));
398 /* If we are saving our group, capture! */
399 if (b->last_move.color == stone_other(color))
400 return board_group_info(b, group_at(b, c)).lib[0];
401 /* If we chase the group, capture it now! */
402 return lib;
404 } foreach_in_group_end;
405 return pass;
408 static coord_t
409 global_atari_check(struct playout_policy *p, struct board *b)
411 if (b->clen == 0)
412 return pass;
414 int g_base = fast_random(b->clen);
415 for (int g = g_base; g < b->clen; g++) {
416 coord_t c = group_atari_check(p, b, group_at(b, group_base(b->c[g])));
417 if (!is_pass(c))
418 return c;
420 for (int g = 0; g < g_base; g++) {
421 coord_t c = group_atari_check(p, b, group_at(b, group_base(b->c[g])));
422 if (!is_pass(c))
423 return c;
425 return pass;
428 static coord_t
429 local_atari_check(struct playout_policy *p, struct board *b, struct move *m, struct move *testmove)
431 struct move_queue q;
432 q.moves = 0;
434 /* Did the opponent play a self-atari? */
435 if (board_group_info(b, group_at(b, m->coord)).libs == 1) {
436 coord_t l = group_atari_check(p, b, group_at(b, m->coord));
437 if (!is_pass(l))
438 q.move[q.moves++] = l;
441 foreach_neighbor(b, m->coord, {
442 group_t g = group_at(b, c);
443 if (!g || board_group_info(b, g).libs != 1)
444 continue;
445 coord_t l = group_atari_check(p, b, g);
446 if (!is_pass(l))
447 q.move[q.moves++] = l;
450 if (PLDEBUGL(5)) {
451 fprintf(stderr, "Local atari candidate moves: ");
452 for (int i = 0; i < q.moves; i++) {
453 fprintf(stderr, "%s ", coord2sstr(q.move[i], b));
455 fprintf(stderr, "\n");
458 if (testmove) {
459 while (q.moves--)
460 if (q.move[q.moves] == testmove->coord) {
461 if (PLDEBUGL(5))
462 fprintf(stderr, "Found queried move.\n");
463 return testmove->coord;
465 return pass;
468 int i = fast_random(q.moves);
469 return q.moves ? q.move[i] : pass;
472 coord_t
473 playout_moggy_choose(struct playout_policy *p, struct board *b, enum stone our_real_color)
475 struct moggy_policy *pp = p->data;
476 coord_t c;
478 if (PLDEBUGL(5))
479 board_print(b, stderr);
481 /* Local checks */
482 if (!is_pass(b->last_move.coord)) {
483 /* Local group in atari? */
484 if (pp->lcapturerate > fast_random(100)) {
485 c = local_atari_check(p, b, &b->last_move, NULL);
486 if (!is_pass(c))
487 return c;
490 /* Check for patterns we know */
491 if (pp->patternrate > fast_random(100)) {
492 c = apply_pattern(p, b, &b->last_move, NULL);
493 if (!is_pass(c))
494 return c;
498 /* Global checks */
500 /* Any groups in atari? */
501 if (pp->capturerate > fast_random(100)) {
502 c = global_atari_check(p, b);
503 if (!is_pass(c))
504 return c;
507 return pass;
510 float
511 playout_moggy_assess(struct playout_policy *p, struct board *b, struct move *m)
513 struct moggy_policy *pp = p->data;
515 if (is_pass(m->coord))
516 return NAN;
518 if (PLDEBUGL(5)) {
519 fprintf(stderr, "ASSESS of %s:\n", coord2sstr(m->coord, b));
520 board_print(b, stderr);
523 /* Are we dealing with atari? */
524 if (pp->lcapturerate > fast_random(100)) {
525 if (pp->localassess && !is_pass(b->last_move.coord)) {
526 if (local_atari_check(p, b, &b->last_move, m) == m->coord)
527 return 1.0;
528 } else {
529 foreach_neighbor(b, m->coord, {
530 struct move m2;
531 m2.coord = c; m2.color = stone_other(m->color);
532 if (local_atari_check(p, b, &m2, m) == m->coord)
533 return 1.0;
537 /* Assess ladders anywhere, local or not. */
538 /* In case we don't localassess, local_atari_check() will
539 * alaready do the job. */
540 if (!pp->localassess && pp->ladderassess) {
541 //fprintf(stderr, "ASSESS %s\n", coord2sstr(m->coord, b));
542 foreach_neighbor(b, m->coord, {
543 if (board_at(b, c) == S_NONE || board_at(b, c) == S_OFFBOARD)
544 continue;
545 group_t g = group_at(b, c);
546 if (board_group_info(b, g).libs != 1)
547 continue;
548 if (ladder_catches(p, b, m->coord, g))
549 return 0.0;
554 /* Pattern check */
555 if (pp->patternrate > fast_random(100)) {
556 if (pp->localassess && !is_pass(b->last_move.coord)) {
557 if (apply_pattern(p, b, &b->last_move, m) == m->coord)
558 return 1.0;
559 } else {
560 foreach_neighbor(b, m->coord, {
561 struct move m2;
562 m2.coord = c; m2.color = stone_other(m->color);
563 if (apply_pattern(p, b, &m2, m) == m->coord)
564 return 1.0;
566 foreach_diag_neighbor(b, m->coord) {
567 struct move m2;
568 m2.coord = c; m2.color = stone_other(m->color);
569 if (apply_pattern(p, b, &m2, m) == m->coord)
570 return 1.0;
571 } foreach_diag_neighbor_end;
575 return NAN;
579 struct playout_policy *
580 playout_moggy_init(char *arg)
582 struct playout_policy *p = calloc(1, sizeof(*p));
583 struct moggy_policy *pp = calloc(1, sizeof(*pp));
584 p->data = pp;
585 p->choose = playout_moggy_choose;
586 p->assess = playout_moggy_assess;
588 pp->lcapturerate = 75;
589 pp->capturerate = 75;
590 pp->patternrate = 75;
591 pp->hanerate = pp->cut1rate = pp->cut2rate = 75;
592 pp->ladders = pp->borderladders = true;
593 pp->ladderassess = true;
595 if (arg) {
596 char *optspec, *next = arg;
597 while (*next) {
598 optspec = next;
599 next += strcspn(next, ":");
600 if (*next) { *next++ = 0; } else { *next = 0; }
602 char *optname = optspec;
603 char *optval = strchr(optspec, '=');
604 if (optval) *optval++ = 0;
606 if (!strcasecmp(optname, "lcapturerate") && optval) {
607 pp->lcapturerate = atoi(optval);
608 } else if (!strcasecmp(optname, "capturerate") && optval) {
609 pp->capturerate = atoi(optval);
610 } else if (!strcasecmp(optname, "patternrate") && optval) {
611 pp->patternrate = atoi(optval);
612 } else if (!strcasecmp(optname, "hanerate") && optval) {
613 pp->hanerate = atoi(optval);
614 } else if (!strcasecmp(optname, "cut1rate") && optval) {
615 pp->cut1rate = atoi(optval);
616 } else if (!strcasecmp(optname, "cut2rate") && optval) {
617 pp->cut2rate = atoi(optval);
618 } else if (!strcasecmp(optname, "ladders")) {
619 pp->ladders = optval && *optval == '0' ? false : true;
620 } else if (!strcasecmp(optname, "borderladders")) {
621 pp->borderladders = optval && *optval == '0' ? false : true;
622 } else if (!strcasecmp(optname, "localassess")) {
623 pp->localassess = optval && *optval == '0' ? false : true;
624 } else if (!strcasecmp(optname, "ladderassess")) {
625 pp->ladderassess = optval && *optval == '0' ? false : true;
626 } else {
627 fprintf(stderr, "playout-moggy: Invalid policy argument %s or missing value\n", optname);
632 return p;