uct/uct.c: Print backtrace when deleting invalid node
[pachi.git] / playout / moggy.c
blob1037888e560066748f3f9977ee6f194e3347562b
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 return pass;
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 return pass;
384 if (PLDEBUGL(6))
385 fprintf(stderr, "...no ladder\n");
387 return lib;
390 static coord_t
391 global_atari_check(struct playout_policy *p, struct board *b)
393 if (b->clen == 0)
394 return pass;
396 int g_base = fast_random(b->clen);
397 for (int g = g_base; g < b->clen; g++) {
398 coord_t c = group_atari_check(p, b, group_at(b, group_base(b->c[g])));
399 if (!is_pass(c))
400 return c;
402 for (int g = 0; g < g_base; g++) {
403 coord_t c = group_atari_check(p, b, group_at(b, group_base(b->c[g])));
404 if (!is_pass(c))
405 return c;
407 return pass;
410 static coord_t
411 local_atari_check(struct playout_policy *p, struct board *b, struct move *m, struct move *testmove)
413 struct move_queue q;
414 q.moves = 0;
416 /* Did the opponent play a self-atari? */
417 if (board_group_info(b, group_at(b, m->coord)).libs == 1) {
418 coord_t l = group_atari_check(p, b, group_at(b, m->coord));
419 if (!is_pass(l))
420 q.move[q.moves++] = l;
423 foreach_neighbor(b, m->coord, {
424 group_t g = group_at(b, c);
425 if (!g || board_group_info(b, g).libs != 1)
426 continue;
427 coord_t l = group_atari_check(p, b, g);
428 if (!is_pass(l))
429 q.move[q.moves++] = l;
432 if (PLDEBUGL(5)) {
433 fprintf(stderr, "Local atari candidate moves: ");
434 for (int i = 0; i < q.moves; i++) {
435 fprintf(stderr, "%s ", coord2sstr(q.move[i], b));
437 fprintf(stderr, "\n");
440 if (testmove) {
441 while (q.moves--)
442 if (q.move[q.moves] == testmove->coord) {
443 if (PLDEBUGL(5))
444 fprintf(stderr, "Found queried move.\n");
445 return testmove->coord;
447 return pass;
450 int i = fast_random(q.moves);
451 return q.moves ? q.move[i] : pass;
454 coord_t
455 playout_moggy_choose(struct playout_policy *p, struct board *b, enum stone our_real_color)
457 struct moggy_policy *pp = p->data;
458 coord_t c;
460 if (PLDEBUGL(5))
461 board_print(b, stderr);
463 /* Local checks */
464 if (!is_pass(b->last_move.coord)) {
465 /* Local group in atari? */
466 if (pp->lcapturerate > fast_random(100)) {
467 c = local_atari_check(p, b, &b->last_move, NULL);
468 if (!is_pass(c))
469 return c;
472 /* Check for patterns we know */
473 if (pp->patternrate > fast_random(100)) {
474 c = apply_pattern(p, b, &b->last_move, NULL);
475 if (!is_pass(c))
476 return c;
480 /* Global checks */
482 /* Any groups in atari? */
483 if (pp->capturerate > fast_random(100)) {
484 c = global_atari_check(p, b);
485 if (!is_pass(c))
486 return c;
489 return pass;
492 float
493 playout_moggy_assess(struct playout_policy *p, struct board *b, struct move *m)
495 struct moggy_policy *pp = p->data;
497 if (is_pass(m->coord))
498 return NAN;
500 if (PLDEBUGL(5))
501 board_print(b, stderr);
503 /* Are we dealing with atari? */
504 if (pp->lcapturerate > fast_random(100)) {
505 /* Assess ladders anywhere, local or not. */
506 if (pp->ladderassess) {
507 //fprintf(stderr, "ASSESS %s\n", coord2sstr(m->coord, b));
508 foreach_neighbor(b, m->coord, {
509 if (board_at(b, c) == S_NONE || board_at(b, c) == S_OFFBOARD)
510 continue;
511 group_t g = group_at(b, c);
512 if (board_group_info(b, g).libs != 1)
513 continue;
514 if (ladder_catches(p, b, m->coord, g))
515 return 0.0;
518 if (pp->localassess) {
519 if (local_atari_check(p, b, &b->last_move, m) == m->coord)
520 return 1.0;
521 } else {
522 foreach_neighbor(b, m->coord, {
523 struct move m2;
524 m2.coord = c; m2.color = stone_other(m->color);
525 if (local_atari_check(p, b, &m2, m) == m->coord)
526 return 1.0;
531 /* Pattern check */
532 if (pp->patternrate > fast_random(100)) {
533 if (pp->localassess) {
534 if (apply_pattern(p, b, &b->last_move, m) == m->coord)
535 return 1.0;
536 } else {
537 foreach_neighbor(b, m->coord, {
538 struct move m2;
539 m2.coord = c; m2.color = stone_other(m->color);
540 if (apply_pattern(p, b, &m2, m) == m->coord)
541 return 1.0;
543 foreach_diag_neighbor(b, m->coord) {
544 struct move m2;
545 m2.coord = c; m2.color = stone_other(m->color);
546 if (apply_pattern(p, b, &m2, m) == m->coord)
547 return 1.0;
548 } foreach_diag_neighbor_end;
552 return NAN;
556 struct playout_policy *
557 playout_moggy_init(char *arg)
559 struct playout_policy *p = calloc(1, sizeof(*p));
560 struct moggy_policy *pp = calloc(1, sizeof(*pp));
561 p->data = pp;
562 p->choose = playout_moggy_choose;
563 p->assess = playout_moggy_assess;
565 pp->lcapturerate = 75;
566 pp->capturerate = 75;
567 pp->patternrate = 75;
568 pp->hanerate = pp->cut1rate = pp->cut2rate = 75;
570 if (arg) {
571 char *optspec, *next = arg;
572 while (*next) {
573 optspec = next;
574 next += strcspn(next, ":");
575 if (*next) { *next++ = 0; } else { *next = 0; }
577 char *optname = optspec;
578 char *optval = strchr(optspec, '=');
579 if (optval) *optval++ = 0;
581 if (!strcasecmp(optname, "lcapturerate") && optval) {
582 pp->lcapturerate = atoi(optval);
583 } else if (!strcasecmp(optname, "capturerate") && optval) {
584 pp->capturerate = atoi(optval);
585 } else if (!strcasecmp(optname, "ladders")) {
586 pp->ladders = true;
587 } else if (!strcasecmp(optname, "patternrate") && optval) {
588 pp->patternrate = atoi(optval);
589 } else if (!strcasecmp(optname, "hanerate") && optval) {
590 pp->hanerate = atoi(optval);
591 } else if (!strcasecmp(optname, "cut1rate") && optval) {
592 pp->cut1rate = atoi(optval);
593 } else if (!strcasecmp(optname, "cut2rate") && optval) {
594 pp->cut2rate = atoi(optval);
595 } else if (!strcasecmp(optname, "localassess")) {
596 pp->localassess = true;
597 } else if (!strcasecmp(optname, "ladderassess")) {
598 pp->ladderassess = true;
599 } else if (!strcasecmp(optname, "borderladders")) {
600 pp->borderladders = true;
601 } else {
602 fprintf(stderr, "playout-moggy: Invalid policy argument %s or missing value\n", optname);
607 return p;