Merge branch 'master' into win2
[pachi/nmclean.git] / tactics / ladder.c
blob48f0a76e7f6f2b6daa2f2b54eee8cdbcaa87a5a4
1 #include <assert.h>
2 #include <stdio.h>
3 #include <stdlib.h>
5 #define DEBUG
6 #include "board.h"
7 #include "debug.h"
8 #include "tactics/ladder.h"
11 /* Is this ladder breaker friendly for the one who catches ladder. */
12 static bool
13 ladder_catcher(struct board *b, int x, int y, enum stone laddered)
15 enum stone breaker = board_atxy(b, x, y);
16 return breaker == stone_other(laddered) || breaker == S_OFFBOARD;
19 bool
20 is_border_ladder(struct board *b, coord_t coord, enum stone lcolor)
22 int x = coord_x(coord, b), y = coord_y(coord, b);
24 if (DEBUGL(5))
25 fprintf(stderr, "border ladder\n");
26 /* Direction along border; xd is horiz. border, yd vertical. */
27 int xd = 0, yd = 0;
28 if (board_atxy(b, x + 1, y) == S_OFFBOARD || board_atxy(b, x - 1, y) == S_OFFBOARD)
29 yd = 1;
30 else
31 xd = 1;
32 /* Direction from the border; -1 is above/left, 1 is below/right. */
33 int dd = (board_atxy(b, x + yd, y + xd) == S_OFFBOARD) ? 1 : -1;
34 if (DEBUGL(6))
35 fprintf(stderr, "xd %d yd %d dd %d\n", xd, yd, dd);
36 /* | ? ?
37 * | . O #
38 * | c X #
39 * | . O #
40 * | ? ? */
41 /* This is normally caught, unless we have friends both above
42 * and below... */
43 if (board_atxy(b, x + xd * 2, y + yd * 2) == lcolor
44 && board_atxy(b, x - xd * 2, y - yd * 2) == lcolor)
45 return false;
46 /* ...or can't block where we need because of shortage
47 * of liberties. */
48 int libs1 = board_group_info(b, group_atxy(b, x + xd - yd * dd, y + yd - xd * dd)).libs;
49 int libs2 = board_group_info(b, group_atxy(b, x - xd - yd * dd, y - yd - xd * dd)).libs;
50 if (DEBUGL(6))
51 fprintf(stderr, "libs1 %d libs2 %d\n", libs1, libs2);
52 if (libs1 < 2 && libs2 < 2)
53 return false;
54 if (board_atxy(b, x + xd * 2, y + yd * 2) == lcolor && libs1 < 3)
55 return false;
56 if (board_atxy(b, x - xd * 2, y - yd * 2) == lcolor && libs2 < 3)
57 return false;
58 return true;
62 /* This is very trivial and gets a lot of corner cases wrong.
63 * We need this to be just very fast. One important point is
64 * that we sometimes might not notice a ladder but if we do,
65 * it should always work; thus we can use this for strong
66 * negative hinting safely. */
68 static bool
69 middle_ladder_walk(struct board *b, enum stone lcolor, int x, int y, int xd, int yd)
71 #define ladder_check(xd1_, yd1_, xd2_, yd2_, xd3_, yd3_) \
72 if (board_atxy(b, x, y) != S_NONE) { \
73 /* Did we hit a stone when playing out ladder? */ \
74 if (ladder_catcher(b, x, y, lcolor)) \
75 return true; /* ladder works */ \
76 if (board_group_info(b, group_atxy(b, x, y)).lib[0] > 0) \
77 return false; /* friend that's not in atari himself */ \
78 } else { \
79 /* No. So we are at new position. \
80 * We need to check indirect ladder breakers. */ \
81 /* . 2 x 3 . \
82 * . x o O 1 <- only at O we can check for o at 2 \
83 * x o o x . otherwise x at O would be still deadly \
84 * o o x . . \
85 * We check for o and x at 1, these are vital. \
86 * We check only for o at 2; x at 2 would mean we \
87 * need to fork (one step earlier). */ \
88 coord_t c = coord_xy(b, x, y); \
89 coord_t c1 = coord_xy(b, x + (xd1_), y + (yd1_)); \
90 enum stone s1 = board_at(b, c1); \
91 if (s1 == lcolor) return false; \
92 if (s1 == stone_other(lcolor)) { \
93 /* One more thing - if the position at 3 is \
94 * friendly and safe, we escaped anyway! */ \
95 coord_t c3 = coord_xy(b, x + (xd3_), y + (yd3_)); \
96 return board_at(b, c3) != lcolor \
97 || board_group_info(b, group_at(b, c3)).libs < 2; \
98 } \
99 enum stone s2 = board_atxy(b, x + (xd2_), y + (yd2_)); \
100 if (s2 == lcolor) return false; \
101 /* Then, can X actually "play" 1 in the ladder? Of course,
102 * if we had already hit the edge, no need. */ \
103 if (neighbor_count_at(b, c, S_OFFBOARD) == 0 \
104 && neighbor_count_at(b, c1, lcolor) + neighbor_count_at(b, c1, S_OFFBOARD) >= 2) \
105 return false; /* It would be self-atari! */ \
107 #define ladder_horiz do { if (DEBUGL(6)) fprintf(stderr, "%d,%d horiz step (%d,%d)\n", x, y, xd, yd); x += xd; ladder_check(xd, 0, -2 * xd, yd, 0, yd); } while (0)
108 #define ladder_vert do { if (DEBUGL(6)) fprintf(stderr, "%d,%d vert step of (%d,%d)\n", x, y, xd, yd); y += yd; ladder_check(0, yd, xd, -2 * yd, xd, 0); } while (0)
110 if (ladder_catcher(b, x - xd, y, lcolor))
111 ladder_horiz;
112 do {
113 ladder_vert;
114 ladder_horiz;
115 } while (1);
118 bool
119 is_middle_ladder(struct board *b, coord_t coord, enum stone lcolor)
121 int x = coord_x(coord, b), y = coord_y(coord, b);
123 /* Figure out the ladder direction */
124 int xd, yd;
125 xd = board_atxy(b, x + 1, y) == S_NONE ? 1 : board_atxy(b, x - 1, y) == S_NONE ? -1 : 0;
126 yd = board_atxy(b, x, y + 1) == S_NONE ? 1 : board_atxy(b, x, y - 1) == S_NONE ? -1 : 0;
128 if (!xd || !yd) {
129 if (DEBUGL(5))
130 fprintf(stderr, "no ladder, too little space; self-atari?\n");
131 return false;
134 /* For given (xd,yd), we have two possibilities where to move
135 * next. Consider (-1,-1):
136 * n X . n c X
137 * c O X X O #
138 * X # # . X #
140 bool horiz_first = ladder_catcher(b, x, y - yd, lcolor); // left case
141 bool vert_first = ladder_catcher(b, x - xd, y, lcolor); // right case
143 /* We don't have to look at the other 'X' in the position - if it
144 * wouldn't be there, the group wouldn't be in atari. */
146 /* We do only tight ladders, not loose ladders. Furthermore,
147 * the ladders need to be simple:
148 * . X . . . X
149 * c O X supported . c O unsupported
150 * X # # X O #
152 assert(!(horiz_first && vert_first));
153 if (!horiz_first && !vert_first) {
154 /* TODO: In case of basic non-simple ladder, play out both variants. */
155 if (DEBUGL(5))
156 fprintf(stderr, "non-simple ladder\n");
157 return false;
160 /* We do that below for further moves, but now initially - check
161 * that at 'c', we aren't putting any of the catching stones
162 * in atari. */
163 #if 1 // this might be broken?
164 #define check_catcher_danger(b, x_, y_) do { \
165 if (board_atxy(b, (x_), (y_)) != S_OFFBOARD \
166 && board_group_info(b, group_atxy(b, (x_), (y_))).libs <= 2) { \
167 if (DEBUGL(5)) \
168 fprintf(stderr, "ladder failed - atari at the beginning\n"); \
169 return false; \
170 } } while (0)
172 if (horiz_first) {
173 check_catcher_danger(b, x, y - yd);
174 check_catcher_danger(b, x - xd, y + yd);
175 } else {
176 check_catcher_danger(b, x - xd, y);
177 check_catcher_danger(b, x + xd, y - yd);
179 #undef check_catcher_danger
180 #endif
182 return middle_ladder_walk(b, lcolor, x, y, xd, yd);
185 bool
186 wouldbe_ladder(struct board *b, coord_t escapelib, coord_t chaselib, enum stone lcolor)
188 if (DEBUGL(6))
189 fprintf(stderr, "would-be ladder check - does %s %s play out chasing move %s?\n",
190 stone2str(lcolor), coord2sstr(escapelib, b), coord2sstr(chaselib, b));
192 if (!coord_is_8adjecent(escapelib, chaselib, b)) {
193 if (DEBUGL(5))
194 fprintf(stderr, "cannot determine ladder for remote simulated stone\n");
195 return false;
198 if (neighbor_count_at(b, chaselib, lcolor) != 1 || immediate_liberty_count(b, chaselib) != 2) {
199 if (DEBUGL(5))
200 fprintf(stderr, "overly trivial for a ladder\n");
201 return false;
204 int x = coord_x(escapelib, b), y = coord_y(escapelib, b);
205 int cx = coord_x(chaselib, b), cy = coord_y(chaselib, b);
207 /* Figure out the ladder direction */
208 int xd, yd;
209 xd = board_atxy(b, x + 1, y) == S_NONE ? 1 : board_atxy(b, x - 1, y) == S_NONE ? -1 : 0;
210 yd = board_atxy(b, x, y + 1) == S_NONE ? 1 : board_atxy(b, x, y - 1) == S_NONE ? -1 : 0;
212 if (board_atxy(b, x + 1, y) == board_atxy(b, x - 1, y)
213 || board_atxy(b, x, y + 1) == board_atxy(b, x, y - 1)) {
214 if (DEBUGL(5))
215 fprintf(stderr, "no ladder, distorted space\n");
216 return false;
219 /* The ladder may be
220 * . c . . e X
221 * e O X or c O X
222 * X X X . X X */
223 bool horiz_first = cx + xd == x;
224 bool vert_first = cy + yd == y;
225 //fprintf(stderr, "esc %d,%d chase %d,%d xd %d yd %d\n", x,y, cx,cy, xd, yd);
226 if (horiz_first == vert_first) {
227 /* TODO: In case of basic non-simple ladder, play out both variants. */
228 if (DEBUGL(5))
229 fprintf(stderr, "non-simple ladder\n");
230 return false;
233 /* We skip the atari check, obviously. */
234 return middle_ladder_walk(b, lcolor, x, y, xd, yd);