xq_moves.c

filter: Statementstmt 98.6% 215 / 218 Branchbran 90.9% 211 / 232 Conditioncond n/a MC/DCmcdc n/a Subroutinesub n/a Podpod n/a totaltotal 94.6% 426 / 450 CC 0 SCAR 0
CC
0
Cov
0%
CRAP 0
« xq_judge.c ↑ Summary xq_search.c »
1 /* xq_moves.c - move generation, the attack walk, and perft.
2 *
3 * PERL-FREE, as xq_engine.c is. Phase 03 of plan_xiangqi.
4 *
5 * THE FIVE PREDICATES EACH HAVE A NAME so a test can address one. A generator
6 * written as a single loop with the blocking folded in cannot be tested in
7 * pieces, and four of the five are the rules a reader gets wrong:
8 *
9 * horse_leg the orthogonal step must be empty, either colour blocks
10 * elephant_eye the intervening diagonal point must be empty
11 * cannon_screens exactly one, and only for a capture
12 * soldier_may forward always, sideways only across the river, never back
13 * generals_face the flying general, implemented as an ATTACK
14 *
15 * ONE DEVIATION FROM THE PLAN, and it is a phase boundary rather than a
16 * decision: `attacked` was scoped to phase 04, and it cannot be, because
17 * `gen_legal` filters on "does this leave my own general attacked" and perft
18 * counts LEGAL moves. Generation cannot be finished without it. Phase 04 keeps
19 * `outcome`, `mate_in` and the stalemate loss, which genuinely are its own.
20 */
21  
22 #include <string.h>
23 #include "xq_abi.h"
24  
25 /* xq_engine.c owns the struct; this file reaches it through the same table
26 * every other consumer uses, which keeps the two files honest about the
27 * interface and costs one indirection per call in code that is not the search. */
28 8016698923 static const struct xq_abi *E(void) { return xq_abi_table(); }
29  
30 #define AT(b, pt) ((E())->at((b), (pt)))
31 #define PT(f, r) ((E())->point_of((f), (r)))
32 #define FILE_OF(pt) ((E())->file_of(pt))
33 #define RANK_OF(pt) ((E())->rank_of(pt))
34 #define ONB(pt) ((E())->on_board(pt))
35  
36 static const int ORTHO[4] = { -1, 1, -XQ_STRIDE, XQ_STRIDE };
37 static const int DIAG[4] = { -XQ_STRIDE - 1, -XQ_STRIDE + 1, XQ_STRIDE - 1, XQ_STRIDE + 1 };
38  
39 /* ---- the five predicates ----------------------------------------------------- */
40  
41 /* The horse's eight destinations are eight PAIRS: one orthogonal step, which
42 * must be empty, then one diagonal away from it. The blocker is of either
43 * colour and there are four blocking points for eight destinations.
44 *
45 * THE MISTAKE TO AVOID is testing the blocker against the destination's own
46 * neighbour. Both readings agree for six of the eight and differ for two, which
47 * is the shape of a bug that wins most of its games.
48 */
49 71875563 static int xq_horse_leg(const struct xq_board *b, int from, int to)
50 {
51 71875563 int d = to - from, i;
52 static const int MOVE[8] = {
53 -2 * XQ_STRIDE - 1, -2 * XQ_STRIDE + 1, /* two up, one across */
54 2 * XQ_STRIDE - 1, 2 * XQ_STRIDE + 1, /* two down, one across */
55 -XQ_STRIDE - 2, -XQ_STRIDE + 2, /* one up, two across */
56 XQ_STRIDE - 2, XQ_STRIDE + 2
57 };
58 static const int LEG[8] = {
59 -XQ_STRIDE, -XQ_STRIDE, XQ_STRIDE, XQ_STRIDE, -1, 1, -1, 1
60 };
61 (void) b;
62 300328094 ▶ for (i = 0; i < 8; i++)
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < 8; i++) 300328093 1 300328094
63 300328093 ▶ if (d == MOVE[i]) return from + LEG[i];
Branch: 1 branch
BranchTrueFalseTotal
if (d == MOVE[i]) return from + LEG[i]; 71875562 228452531 300328093
64 1 return -1;
65 }
66  
67 /* "Exactly two points diagonally and may not jump over intervening pieces", and
68 * the intervening point is the eye. Four destinations, four eyes, one each. */
69 2 static int xq_elephant_eye(const struct xq_board *b, int from, int to)
70 {
71 2 int d = to - from, i;
72 (void) b;
73 8 ▶ for (i = 0; i < 4; i++)
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < 4; i++) 8 0 8
74 8 ▶ if (d == 2 * DIAG[i]) return from + DIAG[i];
Branch: 1 branch
BranchTrueFalseTotal
if (d == 2 * DIAG[i]) return from + DIAG[i]; 2 6 8
75 0 return -1;
76 }
77  
78 /* One ray walk answers both halves of the cannon.
79 *
80 * 0 screens, destination empty a move
81 * 0 screens, destination occupied NOT a move: a cannon does not capture
82 * adjacently, and this is the row that
83 * gets written wrong
84 * 1 screen, destination enemy a capture
85 * 1 screen, destination own or empty nothing
86 * 2 or more nothing
87 */
88 7 static int xq_cannon_screens(const struct xq_board *b, int from, int to)
89 {
90 7 int df = FILE_OF(to) - FILE_OF(from);
91 7 int dr = RANK_OF(to) - RANK_OF(from);
92 7 int step, pt, n = 0;
93  
94 7 ▶ if (from == to) return -1;
Branch: 1 branch
BranchTrueFalseTotal
if (from == to) return -1; 0 7 7
95 7 ▶ if (!ONB(from) || !ONB(to)) return -1;
Branch: 2 branches
BranchTrueFalseTotal
if (!ONB(from) || !ONB(to)) return -1; 7 0 7
if (!ONB(from) || !ONB(to)) return -1; 0 7 7
96 7 ▶ if (df != 0 && dr != 0) return -1;
Branch: 2 branches
BranchTrueFalseTotal
if (df != 0 && dr != 0) return -1; 1 6 7
if (df != 0 && dr != 0) return -1; 1 0 1
97 6 ▶ step = (df != 0) ? (df > 0 ? 1 : -1) : (dr > 0 ? XQ_STRIDE : -XQ_STRIDE);
Branch: 3 branches
BranchTrueFalseTotal
step = (df != 0) ? (df > 0 ? 1 : -1) : (dr > 0 ? XQ_STRIDE : -XQ_STRIDE); 0 6 6
step = (df != 0) ? (df > 0 ? 1 : -1) : (dr > 0 ? XQ_STRIDE : -XQ_STRIDE); 0 0 0
step = (df != 0) ? (df > 0 ? 1 : -1) : (dr > 0 ? XQ_STRIDE : -XQ_STRIDE); 6 0 6
98 23 ▶ for (pt = from + step; pt != to; pt += step)
Branch: 1 branch
BranchTrueFalseTotal
for (pt = from + step; pt != to; pt += step) 17 6 23
99 17 ▶ if (AT(b, pt) != XQ_EMPTY) n++;
Branch: 1 branch
BranchTrueFalseTotal
if (AT(b, pt) != XQ_EMPTY) n++; 5 12 17
100 6 return n;
101 }
102  
103 /* One point forward; sideways as well once across the river; NEVER backward and
104 * never promoted. A soldier on the enemy's last rank has only its sideways
105 * moves, which is a rule and not a dead end. */
106 3 static int xq_soldier_may(const struct xq_board *b, int from, int to)
107 {
108 3 int piece = AT(b, from);
109 3 int colour = XQ_COLOUR(piece);
110 3 int d = to - from;
111 3 ▶ int fwd = (colour == XQ_RED) ? XQ_STRIDE : -XQ_STRIDE;
Branch: 1 branch
BranchTrueFalseTotal
int fwd = (colour == XQ_RED) ? XQ_STRIDE : -XQ_STRIDE; 3 0 3
112  
113 3 ▶ if (XQ_KIND(piece) != XQ_SOLDIER) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (XQ_KIND(piece) != XQ_SOLDIER) return 0; 0 3 3
114 3 ▶ if (!ONB(to)) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (!ONB(to)) return 0; 0 3 3
115 3 ▶ if (d == fwd) return 1;
Branch: 1 branch
BranchTrueFalseTotal
if (d == fwd) return 1; 0 3 3
116 3 ▶ if ((d == 1 || d == -1) && (E())->crossed_river(from, colour)) return 1;
Branch: 3 branches
BranchTrueFalseTotal
if ((d == 1 || d == -1) && (E())->crossed_river(from, colour)) return 1; 1 2 3
if ((d == 1 || d == -1) && (E())->crossed_river(from, colour)) return 1; 0 1 1
if ((d == 1 || d == -1) && (E())->crossed_river(from, colour)) return 1; 1 1 2
117 2 return 0;
118 }
119  
120 /* The flying general. The generals may not end a move facing each other down an
121 * open file, and the encyclopaedia's sentence is the one that matters: "creating
122 * this situation in the first place means moving into check, and is therefore
123 * not allowed". So this is not a special case in the generator: gen_legal
124 * refuses any move that leaves it true, in both directions, with no extra
125 * branch, and the flying capture itself is therefore never generated. */
126 74116634 static int xq_generals_face(const struct xq_board *b)
127 {
128 74116634 int rg = (E())->find(b, XQ_RED | XQ_GENERAL);
129 74116634 int bg = (E())->find(b, XQ_BLACK | XQ_GENERAL);
130 int pt;
131  
132 74116634 ▶ if (!rg || !bg) return 0;
Branch: 2 branches
BranchTrueFalseTotal
if (!rg || !bg) return 0; 74116568 66 74116634
if (!rg || !bg) return 0; 2991 74113577 74116568
133 74113577 ▶ if (FILE_OF(rg) != FILE_OF(bg)) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (FILE_OF(rg) != FILE_OF(bg)) return 0; 7254424 66859153 74113577
134 192357927 ▶ for (pt = rg + XQ_STRIDE; pt < bg; pt += XQ_STRIDE)
Branch: 1 branch
BranchTrueFalseTotal
for (pt = rg + XQ_STRIDE; pt < bg; pt += XQ_STRIDE) 192271318 86609 192357927
135 192271318 ▶ if (AT(b, pt) != XQ_EMPTY) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (AT(b, pt) != XQ_EMPTY) return 0; 66772544 125498774 192271318
136 86609 return 1;
137 }
138  
139 /* ---- generation --------------------------------------------------------------
140 *
141 * PSEUDO-LEGAL: every move the piece may make, without asking whether it leaves
142 * its own general attacked. gen_legal filters these.
143 */
144  
145 494180524 static int add(int *out, int n, int from, int to)
146 {
147 494180524 ▶ if (n >= XQ_MAX_MOVES) return n;
Branch: 1 branch
BranchTrueFalseTotal
if (n >= XQ_MAX_MOVES) return n; 0 494180524 494180524
148 494180524 out[n] = (E())->move_make(from, to);
149 494180524 return n + 1;
150 }
151  
152 13495043 static int xq_gen_moves(const struct xq_board *b, int *out)
153 {
154 13495043 int side = (E())->side(b);
155 13495043 int n = 0, f, r, i;
156  
157 148445473 ▶ for (r = 0; r < XQ_RANKS; r++) {
Branch: 1 branch
BranchTrueFalseTotal
for (r = 0; r < XQ_RANKS; r++) { 134950430 13495043 148445473
158 1349504300 ▶ for (f = 0; f < XQ_FILES; f++) {
Branch: 1 branch
BranchTrueFalseTotal
for (f = 0; f < XQ_FILES; f++) { 1214553870 134950430 1349504300
159 1214553870 int from = PT(f, r);
160 1214553870 int piece = AT(b, from);
161 int kind;
162 1214553870 ▶ if (XQ_COLOUR(piece) != side) continue;
Branch: 1 branch
BranchTrueFalseTotal
if (XQ_COLOUR(piece) != side) continue; 1039443683 175110187 1214553870
163 175110187 kind = XQ_KIND(piece);
164  
165 175110187 switch (kind) {
166 13494929 case XQ_GENERAL:
167 67474645 ▶ for (i = 0; i < 4; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < 4; i++) { 53979716 13494929 67474645
168 53979716 int to = from + ORTHO[i];
169 53979716 ▶ if (!(E())->in_palace(to, side)) continue;
Branch: 1 branch
BranchTrueFalseTotal
if (!(E())->in_palace(to, side)) continue; 13248797 40730919 53979716
170 40730919 ▶ if (XQ_COLOUR(AT(b, to)) == side) continue;
Branch: 1 branch
BranchTrueFalseTotal
if (XQ_COLOUR(AT(b, to)) == side) continue; 24628578 16102341 40730919
171 16102341 n = add(out, n, from, to);
172 }
173 13494929 break;
174  
175 26057244 case XQ_ADVISOR:
176 130286220 ▶ for (i = 0; i < 4; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < 4; i++) { 104228976 26057244 130286220
177 104228976 int to = from + DIAG[i];
178 104228976 ▶ if (!(E())->in_palace(to, side)) continue;
Branch: 1 branch
BranchTrueFalseTotal
if (!(E())->in_palace(to, side)) continue; 72307044 31921932 104228976
179 31921932 ▶ if (XQ_COLOUR(AT(b, to)) == side) continue;
Branch: 1 branch
BranchTrueFalseTotal
if (XQ_COLOUR(AT(b, to)) == side) continue; 5087233 26834699 31921932
180 26834699 n = add(out, n, from, to);
181 }
182 26057244 break;
183  
184 25457845 case XQ_ELEPHANT:
185 127289225 ▶ for (i = 0; i < 4; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < 4; i++) { 101831380 25457845 127289225
186 101831380 int to = from + 2 * DIAG[i];
187 101831380 ▶ if (!ONB(to)) continue;
Branch: 1 branch
BranchTrueFalseTotal
if (!ONB(to)) continue; 46717478 55113902 101831380
188 /* never crosses the river: the elephant stays on its own half */
189 55113902 ▶ if ((E())->crossed_river(to, side)) continue;
Branch: 1 branch
BranchTrueFalseTotal
if ((E())->crossed_river(to, side)) continue; 257164 54856738 55113902
190 54856738 ▶ if (AT(b, from + DIAG[i]) != XQ_EMPTY) continue; /* the eye */
Branch: 1 branch
BranchTrueFalseTotal
if (AT(b, from + DIAG[i]) != XQ_EMPTY) continue; /* the eye */ 1429464 53427274 54856738
191 53427274 ▶ if (XQ_COLOUR(AT(b, to)) == side) continue;
Branch: 1 branch
BranchTrueFalseTotal
if (XQ_COLOUR(AT(b, to)) == side) continue; 7765905 45661369 53427274
192 45661369 n = add(out, n, from, to);
193 }
194 25457845 break;
195  
196 19466489 case XQ_HORSE:
197 175198401 ▶ for (i = 0; i < 8; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < 8; i++) { 155731912 19466489 175198401
198 static const int MOVE[8] = {
199 -2 * XQ_STRIDE - 1, -2 * XQ_STRIDE + 1,
200 2 * XQ_STRIDE - 1, 2 * XQ_STRIDE + 1,
201 -XQ_STRIDE - 2, -XQ_STRIDE + 2,
202 XQ_STRIDE - 2, XQ_STRIDE + 2
203 };
204 155731912 int to = from + MOVE[i];
205 int leg;
206 155731912 ▶ if (!ONB(to)) continue;
Branch: 1 branch
BranchTrueFalseTotal
if (!ONB(to)) continue; 84075642 71656270 155731912
207 71656270 leg = xq_horse_leg(b, from, to);
208 71656270 ▶ if (leg < 0 || AT(b, leg) != XQ_EMPTY) continue;
Branch: 2 branches
BranchTrueFalseTotal
if (leg < 0 || AT(b, leg) != XQ_EMPTY) continue; 71656270 0 71656270
if (leg < 0 || AT(b, leg) != XQ_EMPTY) continue; 17246853 54409417 71656270
209 54409417 ▶ if (XQ_COLOUR(AT(b, to)) == side) continue;
Branch: 1 branch
BranchTrueFalseTotal
if (XQ_COLOUR(AT(b, to)) == side) continue; 7711360 46698057 54409417
210 46698057 n = add(out, n, from, to);
211 }
212 19466489 break;
213  
214 23862281 case XQ_CHARIOT:
215 119311405 ▶ for (i = 0; i < 4; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < 4; i++) { 95449124 23862281 119311405
216 int to;
217 189700092 ▶ for (to = from + ORTHO[i]; ONB(to); to += ORTHO[i]) {
Branch: 1 branch
BranchTrueFalseTotal
for (to = from + ORTHO[i]; ONB(to); to += ORTHO[i]) { 142126045 47574047 189700092
218 142126045 int t = AT(b, to);
219 142126045 ▶ if (t == XQ_EMPTY) { n = add(out, n, from, to); continue; }
Branch: 1 branch
BranchTrueFalseTotal
if (t == XQ_EMPTY) { n = add(out, n, from, to); continue; } 94250968 47875077 142126045
220 47875077 ▶ if (XQ_COLOUR(t) != side) n = add(out, n, from, to);
Branch: 1 branch
BranchTrueFalseTotal
if (XQ_COLOUR(t) != side) n = add(out, n, from, to); 8378228 39496849 47875077
221 47875077 break;
222 }
223 }
224 23862281 break;
225  
226 20085978 case XQ_CANNON:
227 100429890 ▶ for (i = 0; i < 4; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < 4; i++) { 80343912 20085978 100429890
228 80343912 int to, seen = 0;
229 380597940 ▶ for (to = from + ORTHO[i]; ONB(to); to += ORTHO[i]) {
Branch: 1 branch
BranchTrueFalseTotal
for (to = from + ORTHO[i]; ONB(to); to += ORTHO[i]) { 320339907 60258033 380597940
230 320339907 int t = AT(b, to);
231 320339907 ▶ if (!seen) {
Branch: 1 branch
BranchTrueFalseTotal
if (!seen) { 248314470 72025437 320339907
232 248314470 ▶ if (t == XQ_EMPTY) { n = add(out, n, from, to); continue; }
Branch: 1 branch
BranchTrueFalseTotal
if (t == XQ_EMPTY) { n = add(out, n, from, to); continue; } 192695469 55619001 248314470
233 55619001 seen = 1; /* the screen; not a capture */
234 55619001 continue;
235 }
236 72025437 ▶ if (t == XQ_EMPTY) continue;
Branch: 1 branch
BranchTrueFalseTotal
if (t == XQ_EMPTY) continue; 51939558 20085879 72025437
237 20085879 ▶ if (XQ_COLOUR(t) != side) n = add(out, n, from, to);
Branch: 1 branch
BranchTrueFalseTotal
if (XQ_COLOUR(t) != side) n = add(out, n, from, to); 12502136 7583743 20085879
238 20085879 break; /* one screen only, ever */
239 }
240 }
241 20085978 break;
242  
243 46685421 case XQ_SOLDIER:
244 {
245 46685421 ▶ int fwd = (side == XQ_RED) ? XQ_STRIDE : -XQ_STRIDE;
Branch: 1 branch
BranchTrueFalseTotal
int fwd = (side == XQ_RED) ? XQ_STRIDE : -XQ_STRIDE; 21384213 25301208 46685421
246 int cand[3];
247 46685421 int c = 0, k;
248 46685421 cand[c++] = from + fwd;
249 46685421 ▶ if ((E())->crossed_river(from, side)) {
Branch: 1 branch
BranchTrueFalseTotal
if ((E())->crossed_river(from, side)) { 2674682 44010739 46685421
250 2674682 cand[c++] = from - 1;
251 2674682 cand[c++] = from + 1;
252 }
253 98720206 ▶ for (k = 0; k < c; k++) {
Branch: 1 branch
BranchTrueFalseTotal
for (k = 0; k < c; k++) { 52034785 46685421 98720206
254 52034785 int to = cand[k];
255 52034785 ▶ if (!ONB(to)) continue;
Branch: 1 branch
BranchTrueFalseTotal
if (!ONB(to)) continue; 99396 51935389 52034785
256 51935389 ▶ if (XQ_COLOUR(AT(b, to)) == side) continue;
Branch: 1 branch
BranchTrueFalseTotal
if (XQ_COLOUR(AT(b, to)) == side) continue; 878132 51057257 51935389
257 51057257 n = add(out, n, from, to);
258 }
259 }
260 46685421 break;
261  
262 0 default:
263 0 break;
264 }
265 }
266 }
267 13495043 return n;
268 }
269  
270 /* ---- the attack walk ---------------------------------------------------------
271 *
272 * Generated BACKWARDS from the point rather than forwards from every piece,
273 * which is what makes the legality filter affordable. Three things here are not
274 * a chess engine's:
275 *
276 * the cannon needs exactly one screen, so the ray walk counts
277 * the horse is blocked, and the leg is checked FROM THE HORSE'S SIDE
278 * the general attacks its orthogonal neighbours inside its own palace
279 */
280 48873579 static int xq_attacked(const struct xq_board *b, int pt, int by)
281 {
282 int i;
283  
284 48873579 ▶ if (!ONB(pt)) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (!ONB(pt)) return 0; 0 48873579 48873579
285  
286 /* chariots and cannons share the ray: the first piece along it can be a
287 * chariot, and the first piece BEYOND that first piece can be a cannon */
288 234032500 ▶ for (i = 0; i < 4; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < 4; i++) { 189054389 44978111 234032500
289 189054389 int s, first = 0, t;
290 577132758 ▶ for (s = pt + ORTHO[i]; ONB(s); s += ORTHO[i]) {
Branch: 1 branch
BranchTrueFalseTotal
for (s = pt + ORTHO[i]; ONB(s); s += ORTHO[i]) { 502732973 74399785 577132758
291 502732973 t = AT(b, s);
292 502732973 ▶ if (t == XQ_EMPTY) continue;
Branch: 1 branch
BranchTrueFalseTotal
if (t == XQ_EMPTY) continue; 259110124 243622849 502732973
293 243622849 ▶ if (!first) {
Branch: 1 branch
BranchTrueFalseTotal
if (!first) { 129758184 113864665 243622849
294 129758184 ▶ if (XQ_COLOUR(t) == by && XQ_KIND(t) == XQ_CHARIOT) return 1;
Branch: 2 branches
BranchTrueFalseTotal
if (XQ_COLOUR(t) == by && XQ_KIND(t) == XQ_CHARIOT) return 1; 11244630 118513554 129758184
if (XQ_COLOUR(t) == by && XQ_KIND(t) == XQ_CHARIOT) return 1; 789922 10454708 11244630
295 /* A general one step away, and THE TARGET must be in that
296 * general's palace, not merely the general itself. A general
297 * cannot leave its palace, so it cannot capture outside one;
298 * testing the general's own square instead said that a general
299 * on d2 attacked c2, which made an enemy piece there look
300 * defended when it was not.
301 *
302 * PERFT CANNOT SEE THIS, which is why it survived phase 03: the
303 * only point `attacked` is asked about during a legality filter
304 * is a general, and a general is always inside its own palace.
305 * Phase 05's `protected_at` would have inherited it. */
306 128968262 ▶ if (XQ_COLOUR(t) == by && XQ_KIND(t) == XQ_GENERAL
Branch: 2 branches
BranchTrueFalseTotal
if (XQ_COLOUR(t) == by && XQ_KIND(t) == XQ_GENERAL 10454708 118513554 128968262
if (XQ_COLOUR(t) == by && XQ_KIND(t) == XQ_GENERAL 520 10454188 10454708
307 520 ▶ && s == pt + ORTHO[i] && (E())->in_palace(pt, by)) return 1;
Branch: 2 branches
BranchTrueFalseTotal
&& s == pt + ORTHO[i] && (E())->in_palace(pt, by)) return 1; 19 501 520
&& s == pt + ORTHO[i] && (E())->in_palace(pt, by)) return 1; 17 2 19
308 128968245 first = 1;
309 128968245 continue;
310 }
311 113864665 ▶ if (XQ_COLOUR(t) == by && XQ_KIND(t) == XQ_CANNON) return 1;
Branch: 2 branches
BranchTrueFalseTotal
if (XQ_COLOUR(t) == by && XQ_KIND(t) == XQ_CANNON) return 1; 31955715 81908950 113864665
if (XQ_COLOUR(t) == by && XQ_KIND(t) == XQ_CANNON) return 1; 3105529 28850186 31955715
312 110759136 break;
313 }
314 }
315  
316 /* horses: eight origins, each with its leg tested from the horse's side */
317 {
318 static const int MOVE[8] = {
319 -2 * XQ_STRIDE - 1, -2 * XQ_STRIDE + 1,
320 2 * XQ_STRIDE - 1, 2 * XQ_STRIDE + 1,
321 -XQ_STRIDE - 2, -XQ_STRIDE + 2,
322 XQ_STRIDE - 2, XQ_STRIDE + 2
323 };
324 404166907 ▶ for (i = 0; i < 8; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < 8; i++) { 359330122 44836785 404166907
325 359330122 int from = pt - MOVE[i];
326 int t, leg;
327 359330122 ▶ if (!ONB(from)) continue;
Branch: 1 branch
BranchTrueFalseTotal
if (!ONB(from)) continue; 168202859 191127263 359330122
328 191127263 t = AT(b, from);
329 191127263 ▶ if (XQ_COLOUR(t) != by || XQ_KIND(t) != XQ_HORSE) continue;
Branch: 2 branches
BranchTrueFalseTotal
if (XQ_COLOUR(t) != by || XQ_KIND(t) != XQ_HORSE) continue; 1923040 189204223 191127263
if (XQ_COLOUR(t) != by || XQ_KIND(t) != XQ_HORSE) continue; 1703752 219288 1923040
330 219288 leg = xq_horse_leg(b, from, pt);
331 219288 ▶ if (leg >= 0 && AT(b, leg) == XQ_EMPTY) return 1;
Branch: 2 branches
BranchTrueFalseTotal
if (leg >= 0 && AT(b, leg) == XQ_EMPTY) return 1; 219288 0 219288
if (leg >= 0 && AT(b, leg) == XQ_EMPTY) return 1; 141326 77962 219288
332 }
333 }
334  
335 /* elephants and advisors capture too, and a legality filter that forgets
336 * them lets a general walk onto a defended point */
337 224183457 ▶ for (i = 0; i < 4; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < 4; i++) { 179346834 44836623 224183457
338 179346834 int from = pt - 2 * DIAG[i];
339 int t;
340 179346834 ▶ if (ONB(from)) {
Branch: 1 branch
BranchTrueFalseTotal
if (ONB(from)) { 89813697 89533137 179346834
341 89813697 t = AT(b, from);
342 89813697 ▶ if (XQ_COLOUR(t) == by && XQ_KIND(t) == XQ_ELEPHANT
Branch: 2 branches
BranchTrueFalseTotal
if (XQ_COLOUR(t) == by && XQ_KIND(t) == XQ_ELEPHANT 3419266 86394431 89813697
if (XQ_COLOUR(t) == by && XQ_KIND(t) == XQ_ELEPHANT 2184 3417082 3419266
343 2184 ▶ && AT(b, from + DIAG[i]) == XQ_EMPTY
Branch: 1 branch
BranchTrueFalseTotal
&& AT(b, from + DIAG[i]) == XQ_EMPTY 1937 247 2184
344 1937 ▶ && !(E())->crossed_river(pt, by)) return 1;
Branch: 1 branch
BranchTrueFalseTotal
&& !(E())->crossed_river(pt, by)) return 1; 161 1776 1937
345 }
346 179346673 from = pt - DIAG[i];
347 179346673 ▶ if (ONB(from)) {
Branch: 1 branch
BranchTrueFalseTotal
if (ONB(from)) { 100975152 78371521 179346673
348 100975152 t = AT(b, from);
349 100975152 ▶ if (XQ_COLOUR(t) == by && XQ_KIND(t) == XQ_ADVISOR
Branch: 2 branches
BranchTrueFalseTotal
if (XQ_COLOUR(t) == by && XQ_KIND(t) == XQ_ADVISOR 1466756 99508396 100975152
if (XQ_COLOUR(t) == by && XQ_KIND(t) == XQ_ADVISOR 2 1466754 1466756
350 2 ▶ && (E())->in_palace(from, by) && (E())->in_palace(pt, by)) return 1;
Branch: 2 branches
BranchTrueFalseTotal
&& (E())->in_palace(from, by) && (E())->in_palace(pt, by)) return 1; 2 0 2
&& (E())->in_palace(from, by) && (E())->in_palace(pt, by)) return 1; 1 1 2
351 }
352 }
353  
354 /* soldiers: one behind, and one to each side once it is across the river */
355 {
356 44836623 ▶ int back = (by == XQ_RED) ? -XQ_STRIDE : XQ_STRIDE;
Branch: 1 branch
BranchTrueFalseTotal
int back = (by == XQ_RED) ? -XQ_STRIDE : XQ_STRIDE; 25165724 19670899 44836623
357 44836623 int from = pt + back, t;
358 44836623 ▶ if (ONB(from)) {
Branch: 1 branch
BranchTrueFalseTotal
if (ONB(from)) { 44836475 148 44836623
359 44836475 t = AT(b, from);
360 44836475 ▶ if (XQ_COLOUR(t) == by && XQ_KIND(t) == XQ_SOLDIER) return 1;
Branch: 2 branches
BranchTrueFalseTotal
if (XQ_COLOUR(t) == by && XQ_KIND(t) == XQ_SOLDIER) return 1; 448639 44387836 44836475
if (XQ_COLOUR(t) == by && XQ_KIND(t) == XQ_SOLDIER) return 1; 25317 423322 448639
361 }
362 134370505 ▶ for (i = -1; i <= 1; i += 2) {
Branch: 1 branch
BranchTrueFalseTotal
for (i = -1; i <= 1; i += 2) { 89591170 44779335 134370505
363 89591170 from = pt + i;
364 89591170 ▶ if (!ONB(from)) continue;
Branch: 1 branch
BranchTrueFalseTotal
if (!ONB(from)) continue; 34328 89556842 89591170
365 89556842 t = AT(b, from);
366 89556842 ▶ if (XQ_COLOUR(t) == by && XQ_KIND(t) == XQ_SOLDIER
Branch: 2 branches
BranchTrueFalseTotal
if (XQ_COLOUR(t) == by && XQ_KIND(t) == XQ_SOLDIER 930827 88626015 89556842
if (XQ_COLOUR(t) == by && XQ_KIND(t) == XQ_SOLDIER 33174 897653 930827
367 33174 ▶ && (E())->crossed_river(from, by)) return 1;
Branch: 1 branch
BranchTrueFalseTotal
&& (E())->crossed_river(from, by)) return 1; 31971 1203 33174
368 }
369 }
370  
371 44779335 return 0;
372 }
373  
374 /* IN CHECK INCLUDES THE FLYING GENERAL, and `attacked` deliberately does not.
375 *
376 * `attacked` answers "could a piece of that colour capture this point", which is
377 * a question about pieces and is what the perft ladder validates. Facing
378 * generals are a question about the two generals only, so folding it into the
379 * general walk would make `attacked` answer differently for one point than for
380 * every other, which is a worse interface.
381 *
382 * It matters here and nowhere else: after a LEGAL move the generals never face,
383 * so perft never asks. A position built by hand or read from a FEN can have them
384 * facing, and without this a mated general reads as STALEMATED, which phase 04
385 * will turn into the right result by the wrong route. Found by building a mate
386 * fixture for t/04 and being told it was not check. */
387 48847920 static int xq_in_check(const struct xq_board *b, int colour)
388 {
389 48847920 int g = (E())->find(b, colour | XQ_GENERAL);
390 48847920 ▶ if (!g) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (!g) return 0; 2782 48845138 48847920
391 48845138 ▶ if (xq_generals_face(b)) return 1;
Branch: 1 branch
BranchTrueFalseTotal
if (xq_generals_face(b)) return 1; 86605 48758533 48845138
392 48758533 ▶ return xq_attacked(b, g, XQ_OTHER(colour));
Branch: 1 branch
BranchTrueFalseTotal
return xq_attacked(b, g, XQ_OTHER(colour)); 21316353 27442180 48758533
393 }
394  
395 /* A move is legal when it leaves your own general unattacked AND does not leave
396 * the two generals facing each other. The second clause is the flying general
397 * and it is why that rule costs nothing anywhere else. */
398 800510 static int xq_gen_legal(struct xq_board *b, int *out)
399 {
400 int buf[XQ_MAX_MOVES];
401 800510 int n = xq_gen_moves(b, buf);
402 800510 int side = (E())->side(b);
403 800510 int i, k = 0;
404  
405 29552537 ▶ for (i = 0; i < n; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < n; i++) { 28752027 800510 29552537
406 struct xq_undo u;
407 28752027 (E())->do_move(b, buf[i], &u);
408 28752027 ▶ if (!xq_in_check(b, side) && !xq_generals_face(b)) out[k++] = buf[i];
Branch: 2 branches
BranchTrueFalseTotal
if (!xq_in_check(b, side) && !xq_generals_face(b)) out[k++] = buf[i]; 25271486 3480541 28752027
if (!xq_in_check(b, side) && !xq_generals_face(b)) out[k++] = buf[i]; 25271486 0 25271486
409 28752027 (E())->undo_move(b, &u);
410 }
411 800510 return k;
412 }
413  
414 /* ---- perft --------------------------------------------------------------------
415 *
416 * In C because depth 4 is 3.29 million nodes and depth 5 is 133 million: a Perl
417 * loop over do_move and undo_move would take the afternoon. The oracle is
418 * external either way, which is the point: this counts, the wiki says what the
419 * count should be.
420 *
421 * NODES, CHECKS AND CAPTURES ARE ABOUT THE LEAF PLY. Of the 44 moves at depth 1,
422 * two are captures and none gives check, which is what the published table says.
423 *
424 * MATES ARE NOT, AND THAT COST AN HOUR. They are counted at the NODE whose side
425 * to move is mated, which is one ply EARLIER than the move that delivered the
426 * mate. So a mate delivered by the third move is counted by perft(4) and not by
427 * perft(3).
428 *
429 * The first version here counted a mate at the move that delivered it, which is
430 * the reading the column name invites, and it produced a table that agreed with
431 * the source on nodes, checks and captures at EVERY depth of every position and
432 * disagreed on mates at every depth by exactly one ply: 23, 1537 and 41673 all
433 * appeared one row too early. Three columns matching exactly is what said the
434 * generator was right and the accounting was ours; a single-column ladder would
435 * have read as a bug in the rules and sent somebody into the cannon code.
436 */
437 360547 static void perft_go(struct xq_board *b, int depth, struct xq_perft *out)
438 {
439 int moves[XQ_MAX_MOVES];
440 360547 int n = xq_gen_legal(b, moves);
441 360547 int side = (E())->side(b);
442 360547 ▶ int them = XQ_OTHER(side);
Branch: 1 branch
BranchTrueFalseTotal
int them = XQ_OTHER(side); 18634 341913 360547
443 int i;
444  
445 /* No legal move: the side to move is mated if it is in check, and
446 * stalemated if it is not, which phase 04 will make a loss as well. Either
447 * way this node has no descendants and contributes no nodes.
448 *
449 * THE MATE IS COUNTED ONLY AT THE LEAF PLY, which is `depth == 1`. Counting
450 * it at every depth accumulates the shallower plies' mates into the deeper
451 * rows: position 2 at depth 5 then reads 1560, which is the true 1537 plus
452 * the 23 that belong to depth 4. That version PASSED THE WHOLE t/ SUITE,
453 * because the positions run there have no mates above the leaf ply, and only
454 * xt/perft-deep.t found it. */
455 360547 ▶ if (n == 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (n == 0) { 340 360207 360547
456 340 ▶ if (depth == 1 && xq_in_check(b, side)) out->mates++;
Branch: 2 branches
BranchTrueFalseTotal
if (depth == 1 && xq_in_check(b, side)) out->mates++; 338 2 340
if (depth == 1 && xq_in_check(b, side)) out->mates++; 337 1 338
457 349959 return;
458 }
459  
460 360207 ▶ if (depth == 1) {
Branch: 1 branch
BranchTrueFalseTotal
if (depth == 1) { 349619 10588 360207
461 12292124 ▶ for (i = 0; i < n; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < n; i++) { 11942505 349619 12292124
462 struct xq_undo u;
463 11942505 int captured = (E())->do_move(b, moves[i], &u);
464 11942505 out->nodes++;
465 11942505 ▶ if (captured != XQ_EMPTY) out->captures++;
Branch: 1 branch
BranchTrueFalseTotal
if (captured != XQ_EMPTY) out->captures++; 436791 11505714 11942505
466 11942505 ▶ if (xq_in_check(b, them)) out->checks++;
Branch: 1 branch
BranchTrueFalseTotal
if (xq_in_check(b, them)) out->checks++; 192334 11750171 11942505
467 11942505 (E())->undo_move(b, &u);
468 }
469 349619 return;
470 }
471 371081 ▶ for (i = 0; i < n; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < n; i++) { 360493 10588 371081
472 struct xq_undo u;
473 360493 (E())->do_move(b, moves[i], &u);
474 360493 perft_go(b, depth - 1, out);
475 360493 (E())->undo_move(b, &u);
476 }
477 }
478  
479 54 static void xq_perft(struct xq_board *b, int depth, struct xq_perft *out)
480 {
481 54 out->nodes = out->checks = out->captures = out->mates = 0;
482 54 ▶ if (depth < 1) { out->nodes = 1; return; }
Branch: 1 branch
BranchTrueFalseTotal
if (depth < 1) { out->nodes = 1; return; } 0 54 54
483 54 perft_go(b, depth, out);
484 }
485  
486 /* ---- installed into the table by xq_engine.c --------------------------------- */
487  
488 void xq_moves_install(struct xq_abi *t);
489  
490 24 void xq_moves_install(struct xq_abi *t)
491 {
492 24 t->horse_leg = xq_horse_leg;
493 24 t->elephant_eye = xq_elephant_eye;
494 24 t->cannon_screens = xq_cannon_screens;
495 24 t->soldier_may = xq_soldier_may;
496 24 t->generals_face = xq_generals_face;
497 24 t->gen_moves = xq_gen_moves;
498 24 t->gen_legal = xq_gen_legal;
499 24 t->attacked = xq_attacked;
500 24 t->in_check = xq_in_check;
501 24 t->perft = xq_perft;
502 24 }
« xq_judge.c ↑ Summary xq_search.c »