bd_moves.c

filter: Statementstmt 99.0% 211 / 213 Branchbran 87.3% 194 / 222 Conditioncond n/a MC/DCmcdc n/a Subroutinesub n/a Podpod n/a totaltotal 93.1% 405 / 435 CC 0 SCAR 0
CC
0
Cov
0%
CRAP 0
« bd_search.c ↑ Summary bd_engine.c »
1 /* bd_moves.c - where a piece may go, what it captures, and two perfts.
2 *
3 * PERL-FREE, as bd_engine.c is.
4 *
5 * THE RULES THIS FILE IMPLEMENTS, quoted from the source the distribution
6 * names in its documentation:
7 *
8 * 4. "Pieces move any distance orthogonally, not landing on nor jumping over
9 * other pieces on the board."
10 * 5. "No piece may land on the central square, not even the king once he has
11 * left it. Only the king may land on the corner squares."
12 *
13 * and one decision the source leaves open: a piece may SLIDE ACROSS the empty
14 * throne and may not stop on it. Rule 4 forbids jumping pieces and rule 5
15 * forbids landing; neither says the empty square blocks. bd_variant.throne_pass
16 * turns that off.
17 *
18 * TWO PERFTS. `relocate` moves a piece and passes the turn, and perft_slides
19 * counts that capture-free game; `do_move` captures as well, and perft counts
20 * that one. Two ladders, so that a wrong number says which half is wrong.
21 *
22 * THE CAPTURE RULES, from the same source:
23 *
24 * 6. "A piece other than the king is captured when it is surrounded
25 * orthogonally on two opposite squares by enemies. The king can take part
26 * in captures in partnership with a defender."
27 * 7. "A piece may also be captured between an enemy and the empty central
28 * square or a corner square."
29 * 8. "When in the central square, the king is captured by surrounding him on
30 * four orthogonal sides with attackers."
31 * 9. "When standing beside the central square, the king may be captured by
32 * surrounding him on the remaining three sides with attackers."
33 * 10. "Elsewhere on the board, the king is captured as other pieces. This
34 * includes beside the corners, where he can be captured between an
35 * attacker and the corner as in rule 7."
36 *
37 * and three decisions where the source is silent or brief:
38 *
39 * - ONLY THE PIECE THAT MOVED CAPTURES. A piece may stand between two
40 * enemies unharmed if neither of them just moved to make it so. The search
41 * therefore goes outward from the square moved to and nowhere else.
42 * - EVERY ENEMY THE MOVE CLOSES ON IS TAKEN, up to three, each judged on the
43 * board as it stands after the move and before anything is removed.
44 * - THE KING CAPTURES like any piece of his side, as the piece that moves or
45 * as the piece that waits.
46 */
47  
48  
49 #include <string.h>
50 #include "bd_abi.h"
51  
52 /* bd_engine.c owns the struct; this file reaches it through the same table
53 * every other consumer uses, which keeps the two files honest about the
54 * interface. */
55 48754015855 static const struct bd_abi *E(void) { return bd_abi_table(); }
56  
57 #define AT(b, sq) ((E())->at((b), (sq)))
58  
59 /* left, right, down, up: the order the move list is written in */
60 static const int ORTHO[4] = { -1, 1, -BD_STRIDE, BD_STRIDE };
61  
62 /* ---- the rule set ------------------------------------------------------------ */
63  
64 1757706 static void bd_variant_default(struct bd_variant *v)
65 {
66 1757706 ▶ if (!v) return;
Branch: 1 branch
BranchTrueFalseTotal
if (!v) return; 0 1757706 1757706
67 1757706 memset(v, 0, sizeof(*v));
68 1757706 v->throne_pass = 1;
69 1757706 v->repeat = BD_REPEAT_DEFAULT;
70 1757706 v->ply_cap = BD_PLY_CAP_DEFAULT;
71 }
72  
73 310311064 static const struct bd_variant *variant_or_default(const struct bd_variant *v)
74 {
75 static struct bd_variant DEFAULT;
76 static int ready = 0;
77 310311064 ▶ if (v) return v;
Branch: 1 branch
BranchTrueFalseTotal
if (v) return v; 310311064 0 310311064
78 0 ▶ if (!ready) { bd_variant_default(&DEFAULT); ready = 1; }
Branch: 1 branch
BranchTrueFalseTotal
if (!ready) { bd_variant_default(&DEFAULT); ready = 1; } 0 0 0
79 0 return &DEFAULT;
80 }
81  
82 /* ---- a move ------------------------------------------------------------------ */
83  
84 5553206822 static int bd_move_make(int from, int to) { return (from & 0x7F) | ((to & 0x7F) << 7); }
85 433887267 static int bd_move_from(int mv) { return mv & 0x7F; }
86 432271088 static int bd_move_to(int mv) { return (mv >> 7) & 0x7F; }
87  
88 /* ---- rule 5: who may STOP where ------------------------------------------------
89 *
90 * The one place that knows. The square is empty when this is asked.
91 */
92 5958810590 static int may_land(int piece, int sq, const struct bd_variant *v)
93 {
94 5958810590 ▶ if ((E())->is_throne(sq)) return piece == BD_KING && v->throne_reentry;
Branch: 3 branches
BranchTrueFalseTotal
if ((E())->is_throne(sq)) return piece == BD_KING && v->throne_reentry; 104967274 5853843316 5958810590
if ((E())->is_throne(sq)) return piece == BD_KING && v->throne_reentry; 12463073 92504201 104967274
if ((E())->is_throne(sq)) return piece == BD_KING && v->throne_reentry; 1025237 11437836 12463073
95 5853843316 ▶ if ((E())->is_corner(sq)) return piece == BD_KING;
Branch: 1 branch
BranchTrueFalseTotal
if ((E())->is_corner(sq)) return piece == BD_KING; 353657127 5500186189 5853843316
96 5500186189 return 1;
97 }
98  
99 /* ---- generation ----------------------------------------------------------------
100 *
101 * A slide walks while the cell is BD_EMPTY. The ring reads BD_BORDER and a
102 * piece reads as itself, so both end the walk with no bounds test. An empty
103 * throne does not end it unless the rule set says so; it is only refused as a
104 * place to stop.
105 */
106 152402267 static int bd_gen_moves(const struct bd_board *b, const struct bd_variant *v, int *out, int max)
107 {
108 152402267 int side = (E())->side(b);
109 152402267 int rank, file, d, n = 0;
110 152402267 v = variant_or_default(v);
111  
112 1219218136 ▶ for (rank = 0; rank < BD_SIZE; rank++) {
Branch: 1 branch
BranchTrueFalseTotal
for (rank = 0; rank < BD_SIZE; rank++) { 1066815869 152402267 1219218136
113 8534526952 ▶ for (file = 0; file < BD_SIZE; file++) {
Branch: 1 branch
BranchTrueFalseTotal
for (file = 0; file < BD_SIZE; file++) { 7467711083 1066815869 8534526952
114 7467711083 int from = (E())->square_of(file, rank);
115 7467711083 int piece = AT(b, from);
116 7467711083 ▶ if (!BD_IS_PIECE(piece) || (E())->side_of(piece) != side) continue;
Branch: 3 branches
BranchTrueFalseTotal
if (!BD_IS_PIECE(piece) || (E())->side_of(piece) != side) continue; 2215071673 5252639410 7467711083
if (!BD_IS_PIECE(piece) || (E())->side_of(piece) != side) continue; 2215071673 0 2215071673
if (!BD_IS_PIECE(piece) || (E())->side_of(piece) != side) continue; 1015216034 1199855639 2215071673
117 5999278195 ▶ for (d = 0; d < 4; d++) {
Branch: 1 branch
BranchTrueFalseTotal
for (d = 0; d < 4; d++) { 4799422556 1199855639 5999278195
118 4799422556 int sq = from + ORTHO[d];
119 10749561126 ▶ while (AT(b, sq) == BD_EMPTY) {
Branch: 1 branch
BranchTrueFalseTotal
while (AT(b, sq) == BD_EMPTY) { 5958617490 4790943636 10749561126
120 5958617490 ▶ if (may_land(piece, sq, v)) {
Branch: 1 branch
BranchTrueFalseTotal
if (may_land(piece, sq, v)) { 5559914751 398702739 5958617490
121 5559914751 ▶ if (out && n < max) out[n] = bd_move_make(from, sq);
Branch: 2 branches
BranchTrueFalseTotal
if (out && n < max) out[n] = bd_move_make(from, sq); 5551730683 8184068 5559914751
if (out && n < max) out[n] = bd_move_make(from, sq); 5551730683 0 5551730683
122 5559914751 n++;
123 }
124 5958617490 ▶ if ((E())->is_throne(sq) && !v->throne_pass) break;
Branch: 2 branches
BranchTrueFalseTotal
if ((E())->is_throne(sq) && !v->throne_pass) break; 104966706 5853650784 5958617490
if ((E())->is_throne(sq) && !v->throne_pass) break; 8478920 96487786 104966706
125 5950138570 sq += ORTHO[d];
126 }
127 }
128 }
129 }
130 152402267 return n;
131 }
132  
133 /* Generation and a search of the list. NOT a second implementation of the
134 * rules: why_not below is that, by necessity, and a test holds the two
135 * together. */
136 345121 static int bd_is_legal(const struct bd_board *b, const struct bd_variant *v, int mv)
137 {
138 int list[BD_MOVES_MAX];
139 345121 int n = bd_gen_moves(b, v, list, BD_MOVES_MAX), i;
140 345121 ▶ if (n > BD_MOVES_MAX) n = BD_MOVES_MAX;
Branch: 1 branch
BranchTrueFalseTotal
if (n > BD_MOVES_MAX) n = BD_MOVES_MAX; 0 345121 345121
141 7029982 ▶ for (i = 0; i < n; i++)
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < n; i++) 6935117 94865 7029982
142 6935117 ▶ if (list[i] == mv) return 1;
Branch: 1 branch
BranchTrueFalseTotal
if (list[i] == mv) return 1; 250256 6684861 6935117
143 94865 return 0;
144 }
145  
146 /* The reason a person is shown. It walks the line itself, so that it can say
147 * WHAT was wrong and not only that something was. */
148 1380159 static int bd_why_not(const struct bd_board *b, const struct bd_variant *v, int from, int to)
149 {
150 int piece, step, sq, ff, fr, tf, tr;
151 1380159 v = variant_or_default(v);
152  
153 1380159 ▶ if (!(E())->on_board(from) || !(E())->on_board(to)) return BD_WHY_OFF_BOARD;
Branch: 2 branches
BranchTrueFalseTotal
if (!(E())->on_board(from) || !(E())->on_board(to)) return BD_WHY_OFF_BOARD; 1380157 2 1380159
if (!(E())->on_board(from) || !(E())->on_board(to)) return BD_WHY_OFF_BOARD; 1 1380156 1380157
154 1380156 piece = AT(b, from);
155 1380156 ▶ if (!BD_IS_PIECE(piece)) return BD_WHY_NO_PIECE;
Branch: 2 branches
BranchTrueFalseTotal
if (!BD_IS_PIECE(piece)) return BD_WHY_NO_PIECE; 831530 548626 1380156
if (!BD_IS_PIECE(piece)) return BD_WHY_NO_PIECE; 0 831530 831530
156 831530 ▶ if ((E())->side_of(piece) != (E())->side(b)) return BD_WHY_NOT_YOURS;
Branch: 1 branch
BranchTrueFalseTotal
if ((E())->side_of(piece) != (E())->side(b)) return BD_WHY_NOT_YOURS; 328734 502796 831530
157 502796 ▶ if (from == to) return BD_WHY_NO_MOVE;
Branch: 1 branch
BranchTrueFalseTotal
if (from == to) return BD_WHY_NO_MOVE; 6638 496158 502796
158  
159 496158 ff = (E())->file_of(from); fr = (E())->rank_of(from);
160 496158 tf = (E())->file_of(to); tr = (E())->rank_of(to);
161 496158 ▶ if (ff != tf && fr != tr) return BD_WHY_NOT_A_LINE;
Branch: 2 branches
BranchTrueFalseTotal
if (ff != tf && fr != tr) return BD_WHY_NOT_A_LINE; 367559 128599 496158
if (ff != tf && fr != tr) return BD_WHY_NOT_A_LINE; 238865 128694 367559
162  
163 257293 ▶ if (fr == tr) step = (tf > ff) ? 1 : -1;
Branch: 2 branches
BranchTrueFalseTotal
if (fr == tr) step = (tf > ff) ? 1 : -1; 128694 128599 257293
if (fr == tr) step = (tf > ff) ? 1 : -1; 64219 64475 128694
164 128599 ▶ else step = (tr > fr) ? BD_STRIDE : -BD_STRIDE;
Branch: 1 branch
BranchTrueFalseTotal
else step = (tr > fr) ? BD_STRIDE : -BD_STRIDE; 64493 64106 128599
165  
166 480216 ▶ for (sq = from + step; sq != to; sq += step) {
Branch: 1 branch
BranchTrueFalseTotal
for (sq = from + step; sq != to; sq += step) { 267637 212579 480216
167 267637 ▶ if (AT(b, sq) != BD_EMPTY) return BD_WHY_BLOCKED;
Branch: 1 branch
BranchTrueFalseTotal
if (AT(b, sq) != BD_EMPTY) return BD_WHY_BLOCKED; 44094 223543 267637
168 223543 ▶ if ((E())->is_throne(sq) && !v->throne_pass) return BD_WHY_THRONE;
Branch: 2 branches
BranchTrueFalseTotal
if ((E())->is_throne(sq) && !v->throne_pass) return BD_WHY_THRONE; 9882 213661 223543
if ((E())->is_throne(sq) && !v->throne_pass) return BD_WHY_THRONE; 620 9262 9882
169 }
170 212579 ▶ if (AT(b, to) != BD_EMPTY) return BD_WHY_BLOCKED;
Branch: 1 branch
BranchTrueFalseTotal
if (AT(b, to) != BD_EMPTY) return BD_WHY_BLOCKED; 19479 193100 212579
171 193100 ▶ if (!may_land(piece, to, v))
Branch: 1 branch
BranchTrueFalseTotal
if (!may_land(piece, to, v)) 1299 191801 193100
172 1299 ▶ return (E())->is_throne(to) ? BD_WHY_THRONE : BD_WHY_CORNER;
Branch: 1 branch
BranchTrueFalseTotal
return (E())->is_throne(to) ? BD_WHY_THRONE : BD_WHY_CORNER; 349 950 1299
173 191801 return BD_WHY_OK;
174 }
175  
176 /* ---- relocate ------------------------------------------------------------------ */
177  
178 97512990 static void bd_relocate(struct bd_board *b, int mv)
179 {
180 97512990 int from = bd_move_from(mv), to = bd_move_to(mv);
181 int piece;
182 97512990 ▶ if (!(E())->on_board(from) || !(E())->on_board(to)) return;
Branch: 2 branches
BranchTrueFalseTotal
if (!(E())->on_board(from) || !(E())->on_board(to)) return; 97512989 1 97512990
if (!(E())->on_board(from) || !(E())->on_board(to)) return; 0 97512989 97512989
183 97512989 piece = AT(b, from);
184 97512989 (E())->lift(b, from);
185 97512989 (E())->put(b, to, piece);
186 97512989 (E())->set_side(b, BD_OTHER((E())->side(b)));
187 }
188  
189 /* ---- perft, slides only --------------------------------------------------------
190 *
191 * The last ply is counted and not played: the number of leaves under a node
192 * one ply from the bottom is the length of its move list.
193 *
194 * A move is taken back by hand here because nothing is ever captured: put the
195 * piece where it was and give the turn back. The key comes back with it, being
196 * an xor each way.
197 */
198 97517255 static unsigned long long perft_go(struct bd_board *b, const struct bd_variant *v, int depth)
199 {
200 int list[BD_MOVES_MAX];
201 97517255 int n = bd_gen_moves(b, v, list, BD_MOVES_MAX), i;
202 97517255 unsigned long long total = 0;
203  
204 97517255 ▶ if (depth <= 1) return (unsigned long long) n;
Branch: 1 branch
BranchTrueFalseTotal
if (depth <= 1) return (unsigned long long) n; 94150262 3366993 97517255
205 3366993 ▶ if (n > BD_MOVES_MAX) n = BD_MOVES_MAX;
Branch: 1 branch
BranchTrueFalseTotal
if (n > BD_MOVES_MAX) n = BD_MOVES_MAX; 0 3366993 3366993
206 100879112 ▶ for (i = 0; i < n; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < n; i++) { 97512119 3366993 100879112
207 97512119 int from = bd_move_from(list[i]), to = bd_move_to(list[i]);
208 97512119 int piece = AT(b, from);
209 97512119 int side = (E())->side(b);
210 97512119 bd_relocate(b, list[i]);
211 97512119 total += perft_go(b, v, depth - 1);
212 97512119 (E())->lift(b, to);
213 97512119 (E())->put(b, from, piece);
214 97512119 (E())->set_side(b, side);
215 }
216 3366993 return total;
217 }
218  
219 5138 static unsigned long long bd_perft_slides(struct bd_board *b, const struct bd_variant *v, int depth)
220 {
221 5138 ▶ if (!b) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (!b) return 0; 0 5138 5138
222 5138 ▶ if (depth <= 0) return 1;
Branch: 1 branch
BranchTrueFalseTotal
if (depth <= 0) return 1; 2 5136 5138
223 5136 return perft_go(b, variant_or_default(v), depth);
224 }
225  
226 /* ---- capture -------------------------------------------------------------------
227 *
228 * THE ONE PREDICATE. A piece is judged as a piece wherever it stands, the
229 * throne and the corners included: the king on his throne is an enemy of the
230 * attackers because he is the king, and a friend of the defenders for the same
231 * reason. Only an EMPTY marked square is hostile in its own right, and it is
232 * hostile to both sides ("A piece may also be captured...").
233 *
234 * The ring is not hostile. Nothing in the rules captures against the edge, and
235 * that is what lets a walk two cells out from the moved piece read the border
236 * and carry on.
237 */
238 31233184 static int bd_hostile_to(const struct bd_board *b, int sq, int side)
239 {
240 31233184 int cell = AT(b, sq);
241 31233184 ▶ if (BD_IS_PIECE(cell)) return (E())->side_of(cell) != side;
Branch: 2 branches
BranchTrueFalseTotal
if (BD_IS_PIECE(cell)) return (E())->side_of(cell) != side; 12677919 18555265 31233184
if (BD_IS_PIECE(cell)) return (E())->side_of(cell) != side; 6962932 5714987 12677919
242 24270252 ▶ if (cell != BD_EMPTY) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (cell != BD_EMPTY) return 0; 5714987 18555265 24270252
243 18555265 ▶ if ((E())->is_corner(sq)) return 1;
Branch: 1 branch
BranchTrueFalseTotal
if ((E())->is_corner(sq)) return 1; 940560 17614705 18555265
244 17614705 ▶ if ((E())->is_throne(sq)) return 1;
Branch: 1 branch
BranchTrueFalseTotal
if ((E())->is_throne(sq)) return 1; 488881 17125824 17614705
245 17125824 return 0;
246 }
247  
248 /* The king stands on `king` and an attacker has just arrived at king - step.
249 * Three places, and three rules.
250 *
251 * On the throne and beside it the king is judged on his whole neighbourhood
252 * and not on the line through the piece that moved. That piece is one of the
253 * neighbours by construction, so the mover is still what closes the capture.
254 */
255 5033751 static int king_falls(const struct bd_board *b, const struct bd_variant *v, int king, int step)
256 {
257 int d;
258  
259 5033751 ▶ if (v->king_everywhere_two)
Branch: 1 branch
BranchTrueFalseTotal
if (v->king_everywhere_two) 1022237 4011514 5033751
260 1022237 return bd_hostile_to(b, king + step, BD_DEFENDERS);
261  
262 4011514 ▶ if (v->king_strong) {
Branch: 1 branch
BranchTrueFalseTotal
if (v->king_strong) { 1024486 2987028 4011514
263 /* every side closed: by an attacker or by the empty throne. The edge
264 * closes nothing, so a king on it cannot be taken; and since every
265 * square next to a corner is on the edge, a corner never gets to
266 * count and is not asked about. */
267 1337168 ▶ for (d = 0; d < 4; d++) {
Branch: 1 branch
BranchTrueFalseTotal
for (d = 0; d < 4; d++) { 1336889 279 1337168
268 1336889 int sq = king + ORTHO[d];
269 1336889 int cell = AT(b, sq);
270 1336889 ▶ if (cell == BD_ATTACKER) continue;
Branch: 1 branch
BranchTrueFalseTotal
if (cell == BD_ATTACKER) continue; 306081 1030808 1336889
271 1030808 ▶ if (cell == BD_EMPTY && (E())->is_throne(sq)) continue;
Branch: 2 branches
BranchTrueFalseTotal
if (cell == BD_EMPTY && (E())->is_throne(sq)) continue; 535445 495363 1030808
if (cell == BD_EMPTY && (E())->is_throne(sq)) continue; 6601 528844 535445
272 1024207 return 0;
273 }
274 279 return 1;
275 }
276  
277 2987028 ▶ if ((E())->is_throne(king)) {
Branch: 1 branch
BranchTrueFalseTotal
if ((E())->is_throne(king)) { 364904 2622124 2987028
278 502396 ▶ for (d = 0; d < 4; d++)
Branch: 1 branch
BranchTrueFalseTotal
for (d = 0; d < 4; d++) 502149 247 502396
279 502149 ▶ if (AT(b, king + ORTHO[d]) != BD_ATTACKER) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (AT(b, king + ORTHO[d]) != BD_ATTACKER) return 0; 364657 137492 502149
280 247 return 1;
281 }
282  
283 2622124 ▶ if ((E())->beside_throne(king)) {
Branch: 1 branch
BranchTrueFalseTotal
if ((E())->beside_throne(king)) { 428737 2193387 2622124
284 /* "the remaining three sides": the fourth is the throne. In play it is
285 * empty, the king being the only piece that ever stands there. A
286 * DEFENDER on it, which only a hand-built board has, is a friend at
287 * his side and he is not surrounded. */
288 808123 ▶ for (d = 0; d < 4; d++) {
Branch: 1 branch
BranchTrueFalseTotal
for (d = 0; d < 4; d++) { 801625 6498 808123
289 801625 int sq = king + ORTHO[d];
290 801625 int cell = AT(b, sq);
291 801625 ▶ if ((E())->is_throne(sq)) {
Branch: 1 branch
BranchTrueFalseTotal
if ((E())->is_throne(sq)) { 110359 691266 801625
292 110359 ▶ if (BD_IS_PIECE(cell) && (E())->side_of(cell) == BD_DEFENDERS) return 0;
Branch: 3 branches
BranchTrueFalseTotal
if (BD_IS_PIECE(cell) && (E())->side_of(cell) == BD_DEFENDERS) return 0; 11522 98837 110359
if (BD_IS_PIECE(cell) && (E())->side_of(cell) == BD_DEFENDERS) return 0; 11522 0 11522
if (BD_IS_PIECE(cell) && (E())->side_of(cell) == BD_DEFENDERS) return 0; 5746 5776 11522
293 }
294 691266 ▶ else if (cell != BD_ATTACKER) return 0;
Branch: 1 branch
BranchTrueFalseTotal
else if (cell != BD_ATTACKER) return 0; 416493 274773 691266
295 }
296 6498 return 1;
297 }
298  
299 2193387 return bd_hostile_to(b, king + step, BD_DEFENDERS);
300 }
301  
302 78260696 static int bd_captures_at(const struct bd_board *b, const struct bd_variant *v, int to, int *out)
303 {
304 78260696 int mover = AT(b, to);
305 78260696 int side, d, n = 0;
306 78260696 v = variant_or_default(v);
307 78260696 ▶ if (!BD_IS_PIECE(mover)) return 0;
Branch: 2 branches
BranchTrueFalseTotal
if (!BD_IS_PIECE(mover)) return 0; 78260695 1 78260696
if (!BD_IS_PIECE(mover)) return 0; 0 78260695 78260695
308 78260695 side = (E())->side_of(mover);
309  
310 391303475 ▶ for (d = 0; d < 4; d++) {
Branch: 1 branch
BranchTrueFalseTotal
for (d = 0; d < 4; d++) { 313042780 78260695 391303475
311 313042780 int sq = to + ORTHO[d];
312 313042780 int victim = AT(b, sq);
313 int taken;
314 313042780 ▶ if (!BD_IS_PIECE(victim) || (E())->side_of(victim) == side) continue;
Branch: 3 branches
BranchTrueFalseTotal
if (!BD_IS_PIECE(victim) || (E())->side_of(victim) == side) continue; 89976712 223066068 313042780
if (!BD_IS_PIECE(victim) || (E())->side_of(victim) == side) continue; 55994642 33982070 89976712
if (!BD_IS_PIECE(victim) || (E())->side_of(victim) == side) continue; 22943417 33051225 55994642
315 33051225 ▶ if (victim == BD_KING) taken = king_falls(b, v, sq, ORTHO[d]);
Branch: 1 branch
BranchTrueFalseTotal
if (victim == BD_KING) taken = king_falls(b, v, sq, ORTHO[d]); 5033751 28017474 33051225
316 28017474 else taken = bd_hostile_to(b, sq + ORTHO[d], (E())->side_of(victim));
317 33051225 ▶ if (taken) {
Branch: 1 branch
BranchTrueFalseTotal
if (taken) { 4770987 28280238 33051225
318 4770987 ▶ if (out) out[n] = sq;
Branch: 1 branch
BranchTrueFalseTotal
if (out) out[n] = sq; 4770987 0 4770987
319 4770987 n++;
320 }
321 }
322 78260695 return n;
323 }
324  
325 10807 static int on_edge(int sq)
326 {
327 10807 int f = (E())->file_of(sq), r = (E())->rank_of(sq);
328 10807 ▶ return f == 0 || r == 0 || f == BD_SIZE - 1 || r == BD_SIZE - 1;
Branch: 4 branches
BranchTrueFalseTotal
return f == 0 || r == 0 || f == BD_SIZE - 1 || r == BD_SIZE - 1; 10126 681 10807
return f == 0 || r == 0 || f == BD_SIZE - 1 || r == BD_SIZE - 1; 9483 643 10126
return f == 0 || r == 0 || f == BD_SIZE - 1 || r == BD_SIZE - 1; 8902 581 9483
return f == 0 || r == 0 || f == BD_SIZE - 1 || r == BD_SIZE - 1; 613 8289 8902
329 }
330  
331 /* COLLECT, THEN REMOVE. Every capture is decided on the board as it stands
332 * after the move and before any piece leaves it, so the order they leave in
333 * cannot matter. A test removes them in every order to show that it does not.
334 */
335 78257988 static int bd_do_move(struct bd_board *b, const struct bd_variant *v, int mv, struct bd_undo *u)
336 {
337 78257988 int from = bd_move_from(mv), to = bd_move_to(mv);
338 int taken[BD_CAPTURES_MAX];
339 78257988 int piece, n, i, flags = 0;
340 78257988 v = variant_or_default(v);
341  
342 78257988 ▶ if (u) {
Branch: 1 branch
BranchTrueFalseTotal
if (u) { 78257988 0 78257988
343 78257988 memset(u, 0, sizeof(*u));
344 78257988 u->side = (E())->side(b);
345 78257988 u->key = (E())->key(b);
346 }
347 78257988 ▶ if (!(E())->on_board(from) || !(E())->on_board(to)) return 0;
Branch: 2 branches
BranchTrueFalseTotal
if (!(E())->on_board(from) || !(E())->on_board(to)) return 0; 78257987 1 78257988
if (!(E())->on_board(from) || !(E())->on_board(to)) return 0; 0 78257987 78257987
348 78257987 piece = AT(b, from);
349 78257987 ▶ if (!BD_IS_PIECE(piece) || AT(b, to) != BD_EMPTY) return 0;
Branch: 3 branches
BranchTrueFalseTotal
if (!BD_IS_PIECE(piece) || AT(b, to) != BD_EMPTY) return 0; 78257986 1 78257987
if (!BD_IS_PIECE(piece) || AT(b, to) != BD_EMPTY) return 0; 78257986 0 78257986
if (!BD_IS_PIECE(piece) || AT(b, to) != BD_EMPTY) return 0; 1 78257985 78257986
350  
351 78257985 (E())->lift(b, from);
352 78257985 (E())->put(b, to, piece);
353  
354 78257985 n = bd_captures_at(b, v, to, taken);
355 83026057 ▶ for (i = 0; i < n; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < n; i++) { 4768072 78257985 83026057
356 4768072 int gone = AT(b, taken[i]);
357 4768072 ▶ if (gone == BD_KING) flags |= BD_KING_TAKEN;
Branch: 1 branch
BranchTrueFalseTotal
if (gone == BD_KING) flags |= BD_KING_TAKEN; 363659 4404413 4768072
358 4768072 ▶ if (u) { u->square[i] = taken[i]; u->piece[i] = gone; }
Branch: 1 branch
BranchTrueFalseTotal
if (u) { u->square[i] = taken[i]; u->piece[i] = gone; } 4768072 0 4768072
359 }
360 83026057 ▶ for (i = 0; i < n; i++) (E())->lift(b, taken[i]);
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < n; i++) (E())->lift(b, taken[i]); 4768072 78257985 83026057
361 78257985 ▶ if (n) flags |= BD_DID_CAPTURE;
Branch: 1 branch
BranchTrueFalseTotal
if (n) flags |= BD_DID_CAPTURE; 4700576 73557409 78257985
362  
363 78257985 ▶ if (piece == BD_KING && ((E())->is_corner(to) || (v->escape_edge && on_edge(to))))
Branch: 4 branches
BranchTrueFalseTotal
if (piece == BD_KING && ((E())->is_corner(to) || (v->escape_edge && on_edge(to)))) 8913573 69344412 78257985
if (piece == BD_KING && ((E())->is_corner(to) || (v->escape_edge && on_edge(to)))) 8119537 794036 8913573
if (piece == BD_KING && ((E())->is_corner(to) || (v->escape_edge && on_edge(to)))) 10807 8108730 8119537
if (piece == BD_KING && ((E())->is_corner(to) || (v->escape_edge && on_edge(to)))) 2518 8289 10807
364 796554 flags |= BD_KING_HOME;
365  
366 78257985 (E())->set_side(b, BD_OTHER((E())->side(b)));
367  
368 78257985 ▶ if (u) { u->mv = mv; u->flags = flags; u->n = n; }
Branch: 1 branch
BranchTrueFalseTotal
if (u) { u->mv = mv; u->flags = flags; u->n = n; } 78257985 0 78257985
369 78257985 return flags;
370 }
371  
372 /* Puts every piece back and the turn with it. The key returns by the same
373 * xors that moved it, and a test holds it to the key that was saved. */
374 76164112 static void bd_undo_move(struct bd_board *b, const struct bd_undo *u)
375 {
376 int from, to, piece, i;
377 76164112 ▶ if (!u || u->mv == 0) return;
Branch: 2 branches
BranchTrueFalseTotal
if (!u || u->mv == 0) return; 76164112 0 76164112
if (!u || u->mv == 0) return; 1 76164111 76164112
378 76164111 from = bd_move_from(u->mv);
379 76164111 to = bd_move_to(u->mv);
380 76164111 piece = AT(b, to);
381 76164111 (E())->lift(b, to);
382 76164111 (E())->put(b, from, piece);
383 80822614 ▶ for (i = 0; i < u->n && i < BD_CAPTURES_MAX; i++)
Branch: 2 branches
BranchTrueFalseTotal
for (i = 0; i < u->n && i < BD_CAPTURES_MAX; i++) 4658503 76164111 80822614
for (i = 0; i < u->n && i < BD_CAPTURES_MAX; i++) 4658503 0 4658503
384 4658503 (E())->put(b, u->square[i], u->piece[i]);
385 76164111 (E())->set_side(b, u->side);
386 }
387  
388 /* do_move on a copy, so that the board asked about is never touched, not even
389 * for the length of the call. */
390 1867782 static int bd_preview(const struct bd_board *b, const struct bd_variant *v, int mv, int *out, int *flags)
391 {
392 1867782 struct bd_board *c = (E())->board_copy(b);
393 struct bd_undo u;
394 int i, n;
395 1867782 ▶ if (flags) *flags = 0;
Branch: 1 branch
BranchTrueFalseTotal
if (flags) *flags = 0; 1867782 0 1867782
396 1867782 ▶ if (!c) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (!c) return 0; 0 1867782 1867782
397 1867782 bd_do_move(c, v, mv, &u);
398 1867782 (E())->board_drop(c);
399 1867782 n = u.n;
400 1966803 ▶ for (i = 0; i < n && out; i++) out[i] = u.square[i];
Branch: 2 branches
BranchTrueFalseTotal
for (i = 0; i < n && out; i++) out[i] = u.square[i]; 99021 1867782 1966803
for (i = 0; i < n && out; i++) out[i] = u.square[i]; 99021 0 99021
401 1867782 ▶ if (flags) *flags = u.flags;
Branch: 1 branch
BranchTrueFalseTotal
if (flags) *flags = u.flags; 1867782 0 1867782
402 1867782 return n;
403 }
404  
405 /* ---- perft, with captures -------------------------------------------------------
406 *
407 * The same shape as perft_slides: the last ply is counted and not played.
408 * NOTHING ENDS THE WALK. A king may be taken and the count goes on through
409 * what his side has left, which is what the reference implementation it is
410 * compared with does too.
411 */
412 51334814 static unsigned long long perft_full(struct bd_board *b, const struct bd_variant *v, int depth)
413 {
414 int list[BD_MOVES_MAX];
415 51334814 int n = bd_gen_moves(b, v, list, BD_MOVES_MAX), i;
416 51334814 unsigned long long total = 0;
417  
418 51334814 ▶ if (depth <= 1) return (unsigned long long) n;
Branch: 1 branch
BranchTrueFalseTotal
if (depth <= 1) return (unsigned long long) n; 49562129 1772685 51334814
419 1772685 ▶ if (n > BD_MOVES_MAX) n = BD_MOVES_MAX;
Branch: 1 branch
BranchTrueFalseTotal
if (n > BD_MOVES_MAX) n = BD_MOVES_MAX; 0 1772685 1772685
420 53102681 ▶ for (i = 0; i < n; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < n; i++) { 51329996 1772685 53102681
421 struct bd_undo u;
422 51329996 bd_do_move(b, v, list[i], &u);
423 51329996 total += perft_full(b, v, depth - 1);
424 51329996 bd_undo_move(b, &u);
425 }
426 1772685 return total;
427 }
428  
429 4818 static unsigned long long bd_perft(struct bd_board *b, const struct bd_variant *v, int depth)
430 {
431 4818 ▶ if (!b) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (!b) return 0; 0 4818 4818
432 4818 ▶ if (depth <= 0) return 1;
Branch: 1 branch
BranchTrueFalseTotal
if (depth <= 0) return 1; 0 4818 4818
433 4818 return perft_full(b, variant_or_default(v), depth);
434 }
435  
436 /* ---- installed into the table by bd_engine.c ---------------------------------- */
437  
438 void bd_moves_install(struct bd_abi *t);
439  
440 59 void bd_moves_install(struct bd_abi *t)
441 {
442 59 t->variant_default = bd_variant_default;
443 59 t->move_make = bd_move_make;
444 59 t->move_from = bd_move_from;
445 59 t->move_to = bd_move_to;
446 59 t->gen_moves = bd_gen_moves;
447 59 t->is_legal = bd_is_legal;
448 59 t->why_not = bd_why_not;
449 59 t->relocate = bd_relocate;
450 59 t->perft_slides = bd_perft_slides;
451  
452 59 t->hostile_to = bd_hostile_to;
453 59 t->captures_at = bd_captures_at;
454 59 t->do_move = bd_do_move;
455 59 t->undo_move = bd_undo_move;
456 59 t->preview = bd_preview;
457 59 t->perft = bd_perft;
458 59 }
« bd_search.c ↑ Summary bd_engine.c »