9 #include "tactics/1lib.h"
10 #include "tactics/ladder.h"
14 is_border_ladder(struct board
*b
, coord_t coord
, enum stone lcolor
)
16 int x
= coord_x(coord
, b
), y
= coord_y(coord
, b
);
19 fprintf(stderr
, "border ladder\n");
20 /* Direction along border; xd is horiz. border, yd vertical. */
22 if (board_atxy(b
, x
+ 1, y
) == S_OFFBOARD
|| board_atxy(b
, x
- 1, y
) == S_OFFBOARD
)
26 /* Direction from the border; -1 is above/left, 1 is below/right. */
27 int dd
= (board_atxy(b
, x
+ yd
, y
+ xd
) == S_OFFBOARD
) ? 1 : -1;
29 fprintf(stderr
, "xd %d yd %d dd %d\n", xd
, yd
, dd
);
35 /* This is normally caught, unless we have friends both above
37 if (board_atxy(b
, x
+ xd
* 2, y
+ yd
* 2) == lcolor
38 && board_atxy(b
, x
- xd
* 2, y
- yd
* 2) == lcolor
)
40 /* ...or can't block where we need because of shortage
42 int libs1
= board_group_info(b
, group_atxy(b
, x
+ xd
- yd
* dd
, y
+ yd
- xd
* dd
)).libs
;
43 int libs2
= board_group_info(b
, group_atxy(b
, x
- xd
- yd
* dd
, y
- yd
- xd
* dd
)).libs
;
45 fprintf(stderr
, "libs1 %d libs2 %d\n", libs1
, libs2
);
46 if (libs1
< 2 || libs2
< 2)
48 if (board_atxy(b
, x
+ xd
* 2, y
+ yd
* 2) == lcolor
&& libs1
< 3)
50 if (board_atxy(b
, x
- xd
* 2, y
- yd
* 2) == lcolor
&& libs2
< 3)
56 /* This is a rather expensive ladder reader. It can read out any sequences
57 * where laddered group should be kept at two liberties. The recursion
58 * always makes a "to-be-laddered" move and then considers the chaser's
59 * two alternatives (usually, one of them is trivially refutable). The
60 * function returns true if there is a branch that ends up with laddered
61 * group captured, false if not (i.e. for each branch, laddered group can
62 * gain three liberties). */
65 middle_ladder_walk(struct board
*b
, group_t laddered
, coord_t nextmove
, enum stone lcolor
)
67 assert(board_group_info(b
, laddered
).libs
== 1);
71 fprintf(stderr
, " ladder escape %s\n", coord2sstr(nextmove
, b
));
72 struct move m
= { nextmove
, lcolor
};
73 int res
= board_play(b
, &m
);
74 laddered
= group_at(b
, laddered
);
77 board_print(b
, stderr
);
78 fprintf(stderr
, "%s c %d\n", coord2sstr(laddered
, b
), board_group_info(b
, laddered
).libs
);
81 if (board_group_info(b
, laddered
).libs
== 1) {
83 fprintf(stderr
, "* we can capture now\n");
86 if (board_group_info(b
, laddered
).libs
> 2) {
88 fprintf(stderr
, "* we are free now\n");
92 foreach_neighbor(b
, m
.coord
, {
93 if (board_at(b
, c
) == stone_other(lcolor
) && board_group_info(b
, group_at(b
, c
)).libs
== 1) {
94 /* We can capture one of the ladder stones
96 /* XXX: If we were very lucky, capturing
97 * this stone will not help us escape.
98 * That should be pretty rate. */
100 fprintf(stderr
, "* can capture chaser\n");
105 /* Now, consider alternatives. */
106 int liblist
[2], libs
= 0;
107 for (int i
= 0; i
< 2; i
++) {
108 coord_t ataristone
= board_group_info(b
, laddered
).lib
[i
];
109 coord_t escape
= board_group_info(b
, laddered
).lib
[1 - i
];
110 if (immediate_liberty_count(b
, escape
) > 2 + coord_is_adjecent(ataristone
, escape
, b
)) {
111 /* Too much free space, ignore. */
117 /* Try out the alternatives. */
118 bool is_ladder
= false;
119 for (int i
= 0; !is_ladder
&& i
< libs
; i
++) {
120 struct board
*b2
= b
;
127 coord_t ataristone
= board_group_info(b2
, laddered
).lib
[liblist
[i
]];
128 // coord_t escape = board_group_info(b2, laddered).lib[1 - liblist[i]];
129 struct move m
= { ataristone
, stone_other(lcolor
) };
130 int res
= board_play(b2
, &m
);
131 /* If we just played self-atari, abandon ship. */
132 /* XXX: If we were very lucky, capturing this stone will
133 * not help us escape. That should be pretty rate. */
135 fprintf(stderr
, "(%d=%d) ladder atari %s (%d libs)\n", i
, res
, coord2sstr(ataristone
, b2
), board_group_info(b2
, group_at(b2
, ataristone
)).libs
);
136 if (res
>= 0 && board_group_info(b2
, group_at(b2
, ataristone
)).libs
> 1)
137 is_ladder
= middle_ladder_walk(b2
, laddered
, board_group_info(b2
, laddered
).lib
[0], lcolor
);
140 board_done_noalloc(&b2s
);
144 fprintf(stderr
, "propagating %d\n", is_ladder
);
149 is_middle_ladder(struct board
*b
, coord_t coord
, group_t laddered
, enum stone lcolor
)
151 /* TODO: Remove the redundant parameters. */
152 assert(board_group_info(b
, laddered
).libs
== 1);
153 assert(board_group_info(b
, laddered
).lib
[0] == coord
);
154 assert(board_at(b
, laddered
) == lcolor
);
156 /* If we can move into empty space or do not have enough space
157 * to escape, this is obviously not a ladder. */
158 if (immediate_liberty_count(b
, coord
) != 2) {
160 fprintf(stderr
, "no ladder, wrong free space\n");
164 /* A fair chance for a ladder. Group in atari, with some but limited
165 * space to escape. Time for the expensive stuff - set up a temporary
166 * board and start selective 2-liberty search. */
168 struct move_queue ccq
= { .moves
= 0 };
169 if (can_countercapture(b
, lcolor
, laddered
, lcolor
, &ccq
, 0)) {
170 /* We could escape by countercapturing a group.
172 assert(ccq
.moves
> 0);
173 for (unsigned int i
= 0; i
< ccq
.moves
; i
++) {
176 bool is_ladder
= middle_ladder_walk(&b2
, laddered
, ccq
.move
[i
], lcolor
);
177 board_done_noalloc(&b2
);
185 bool is_ladder
= middle_ladder_walk(&b2
, laddered
, board_group_info(&b2
, laddered
).lib
[0], lcolor
);
186 board_done_noalloc(&b2
);
191 wouldbe_ladder(struct board
*b
, group_t group
, coord_t escapelib
, coord_t chaselib
, enum stone lcolor
)
193 assert(board_group_info(b
, group
).libs
== 2);
194 assert(board_at(b
, group
) == lcolor
);
197 fprintf(stderr
, "would-be ladder check - does %s %s play out chasing move %s?\n",
198 stone2str(lcolor
), coord2sstr(escapelib
, b
), coord2sstr(chaselib
, b
));
200 if (!coord_is_8adjecent(escapelib
, chaselib
, b
)) {
202 fprintf(stderr
, "cannot determine ladder for remote simulated stone\n");
206 if (neighbor_count_at(b
, chaselib
, lcolor
) != 1 || immediate_liberty_count(b
, chaselib
) != 2) {
208 fprintf(stderr
, "overly trivial for a ladder\n");
212 bool is_ladder
= false;
216 struct move m
= { chaselib
, stone_other(lcolor
) };
217 int res
= board_play(&b2
, &m
);
219 is_ladder
= middle_ladder_walk(&b2
, group
, board_group_info(&b2
, group
).lib
[0], lcolor
);
221 board_done_noalloc(&b2
);