fn_moves.c

filter: Statementstmt 100% 316 / 316 Branchbran 83.6% 251 / 300 Conditioncond n/a MC/DCmcdc n/a Subroutinesub n/a Podpod n/a totaltotal 92.0% 567 / 616 CC 0 SCAR 0
CC
0
Cov
0%
CRAP 0
« fn_rules.c ↑ Summary fn_search.c »
1 /* fn_moves.c - one stone, one step: where it may go and what it takes; and
2 * then the chain of steps that is a whole move.
3 *
4 * PERL-FREE, as fn_engine.c is.
5 *
6 * THE RULES THIS FILE IMPLEMENTS, quoted from the sources the distribution
7 * names in its documentation:
8 *
9 * "A paika move consists of moving one stone along a line to an adjacent
10 * intersection."
11 * "Capturing moves are obligatory and have to be played in preference to
12 * paika moves." And: "If any capturing moves are possible anywhere on the
13 * board, then a capturing move must be made. If multiple captures are
14 * possible, you can choose which to do."
15 * Approach: "moving the capturing stone to a point adjacent to an opponent's
16 * stone, which must be on the continuation of the capturing stone's
17 * movement line."
18 * Withdrawal: "the capturing stone moves from a point adjacent to the
19 * opponent's stone, away from the stone along the continuation of the line
20 * between them."
21 * "All opponent pieces in line beyond that stone (as long as there is no
22 * interruption by an empty point or an own stone) are captured as well."
23 * "It is not allowed to capture by approach and withdrawal at the same time
24 * ... the player has to choose".
25 *
26 * and two readings where the sources are brief:
27 *
28 * - A STEP THAT COULD TAKE, TAKES. Capture is obligatory, so there is no
29 * moving there and declining: a step is a paika only when it takes
30 * nothing by either method.
31 * - THE OBLIGATION IS GLOBAL AND THE CHOICE IS FREE. If any stone can take,
32 * no stone may make a paika; but which capture is made is the mover's,
33 * and the largest has no priority.
34 *
35 * THE LINE IS READ OUTWARD FROM THE STEP. Nothing here scans the board for
36 * lines: an approach looks at the point beyond `to`, a withdrawal at the point
37 * behind `from`, and each walks on from there.
38 */
39  
40 #include <string.h>
41 #include "fn_abi.h"
42  
43 /* fn_engine.c owns the struct; this file reaches it through the same table
44 * every other consumer uses, which keeps the two files honest about the
45 * interface. */
46 3623658887 static const struct fn_abi *E(void) { return fn_abi_table(); }
47  
48 #define AT(b, sq) ((E())->at((b), (sq)))
49 #define NEXT(b, sq, dir) ((E())->next((b), (sq), (dir)))
50  
51 /* A stone has at most eight ways to go and each is at most two entries. */
52 #define STONE_STEPS_MAX 16
53  
54 /* ---- the line ------------------------------------------------------------------
55 *
56 * The enemy stones from `start` onward in `dir`, nearest first, until the
57 * line breaks. `start` may be -1, which is the edge and an empty line.
58 *
59 * A diagonal walk never has to ask whether it may go on: every point on a
60 * diagonal is a strong point, so NEXT answers -1 only at the edge.
61 */
62 543702303 static int line_from(const struct fn_board *b, int start, int dir, int foe, int *out)
63 {
64 543702303 int n = 0, sq = start;
65 562323252 ▶ while (sq >= 0 && n < FN_LINE_MAX && AT(b, sq) == foe) {
Branch: 3 branches
BranchTrueFalseTotal
while (sq >= 0 && n < FN_LINE_MAX && AT(b, sq) == foe) { 441926324 120396928 562323252
while (sq >= 0 && n < FN_LINE_MAX && AT(b, sq) == foe) { 441926324 0 441926324
while (sq >= 0 && n < FN_LINE_MAX && AT(b, sq) == foe) { 18620949 423305375 441926324
66 18620949 out[n++] = sq;
67 18620949 sq = NEXT(b, sq, dir);
68 }
69 543702303 return n;
70 }
71  
72 273261702 static void step_fill(struct fn_step *s, int from, int to, int dir, int kind, const int *taken, int n)
73 {
74 int i;
75 273261702 s->from = from;
76 273261702 s->to = to;
77 273261702 s->dir = dir;
78 273261702 s->kind = kind;
79 273261702 s->taken_n = n;
80 2186093616 ▶ for (i = 0; i < FN_LINE_MAX; i++) s->taken[i] = i < n ? taken[i] : 0;
Branch: 2 branches
BranchTrueFalseTotal
for (i = 0; i < FN_LINE_MAX; i++) s->taken[i] = i < n ? taken[i] : 0; 18600190 1894231724 1912831914
for (i = 0; i < FN_LINE_MAX; i++) s->taken[i] = i < n ? taken[i] : 0; 1912831914 273261702 2186093616
81 273261702 }
82  
83 /* The steps of one stone, judging nothing but the geometry. Returns how many
84 * there are and writes at most `max`. */
85 58785601 static int fn_steps_of(const struct fn_board *b, int sq, struct fn_step *out, int max)
86 {
87 58785601 int stone = AT(b, sq);
88 58785601 int foe, dir, n = 0;
89 58785601 ▶ if (!FN_IS_STONE(stone)) return 0;
Branch: 2 branches
BranchTrueFalseTotal
if (!FN_IS_STONE(stone)) return 0; 27752282 31033319 58785601
if (!FN_IS_STONE(stone)) return 0; 0 27752282 27752282
90 58785601 foe = FN_OTHER(stone);
91 529070409 ▶ for (dir = 0; dir < FN_DIRS; dir++) {
Branch: 1 branch
BranchTrueFalseTotal
for (dir = 0; dir < FN_DIRS; dir++) { 470284808 58785601 529070409
92 int ahead[FN_LINE_MAX], behind[FN_LINE_MAX];
93 int a, w;
94 470284808 int to = NEXT(b, sq, dir);
95 470284808 ▶ if (to < 0 || AT(b, to) != FN_EMPTY) continue;
Branch: 2 branches
BranchTrueFalseTotal
if (to < 0 || AT(b, to) != FN_EMPTY) continue; 298673643 171611165 470284808
if (to < 0 || AT(b, to) != FN_EMPTY) continue; 36178483 262495160 298673643
96 262495160 a = line_from(b, NEXT(b, to, dir), dir, foe, ahead);
97 262495160 w = line_from(b, NEXT(b, sq, (dir + 4) % FN_DIRS), (dir + 4) % FN_DIRS, foe, behind);
98 262495160 ▶ if (a) {
Branch: 1 branch
BranchTrueFalseTotal
if (a) { 7866216 254628944 262495160
99 7866216 ▶ if (out && n < max) step_fill(&out[n], sq, to, dir, FN_APPROACH, ahead, a);
Branch: 2 branches
BranchTrueFalseTotal
if (out && n < max) step_fill(&out[n], sq, to, dir, FN_APPROACH, ahead, a); 7866216 0 7866216
if (out && n < max) step_fill(&out[n], sq, to, dir, FN_APPROACH, ahead, a); 7866216 0 7866216
100 7866216 n++;
101 }
102 262495160 ▶ if (w) {
Branch: 1 branch
BranchTrueFalseTotal
if (w) { 4749396 257745764 262495160
103 4749396 ▶ if (out && n < max) step_fill(&out[n], sq, to, dir, FN_WITHDRAWAL, behind, w);
Branch: 2 branches
BranchTrueFalseTotal
if (out && n < max) step_fill(&out[n], sq, to, dir, FN_WITHDRAWAL, behind, w); 4749396 0 4749396
if (out && n < max) step_fill(&out[n], sq, to, dir, FN_WITHDRAWAL, behind, w); 4749396 0 4749396
104 4749396 n++;
105 }
106 262495160 ▶ if (!a && !w) {
Branch: 2 branches
BranchTrueFalseTotal
if (!a && !w) { 254628944 7866216 262495160
if (!a && !w) { 250286858 4342086 254628944
107 250286858 ▶ if (out && n < max) step_fill(&out[n], sq, to, dir, FN_PAIKA, ahead, 0);
Branch: 2 branches
BranchTrueFalseTotal
if (out && n < max) step_fill(&out[n], sq, to, dir, FN_PAIKA, ahead, 0); 250286858 0 250286858
if (out && n < max) step_fill(&out[n], sq, to, dir, FN_PAIKA, ahead, 0); 250286858 0 250286858
108 250286858 n++;
109 }
110 }
111 58785601 return n;
112 }
113  
114 21710256 static int fn_can_capture(const struct fn_board *b, int side)
115 {
116 21710256 const struct fn_abi *e = E();
117 struct fn_step tmp[STONE_STEPS_MAX];
118 int rank, file, i, n;
119 21710256 ▶ if (!FN_IS_STONE(side)) return 0;
Branch: 2 branches
BranchTrueFalseTotal
if (!FN_IS_STONE(side)) return 0; 11146098 10564158 21710256
if (!FN_IS_STONE(side)) return 0; 1 11146097 11146098
120 120538859 ▶ for (rank = 0; rank < e->rows(b); rank++) {
Branch: 1 branch
BranchTrueFalseTotal
for (rank = 0; rank < e->rows(b); rank++) { 101963417 18575442 120538859
121 1003377902 ▶ for (file = 0; file < e->cols(b); file++) {
Branch: 1 branch
BranchTrueFalseTotal
for (file = 0; file < e->cols(b); file++) { 904549298 98828604 1003377902
122 904549298 int sq = e->square_of(file, rank);
123 904549298 ▶ if (AT(b, sq) != side) continue;
Branch: 1 branch
BranchTrueFalseTotal
if (AT(b, sq) != side) continue; 873832458 30716840 904549298
124 30716840 n = fn_steps_of(b, sq, tmp, STONE_STEPS_MAX);
125 169653495 ▶ for (i = 0; i < n; i++)
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < n; i++) 142071468 27582027 169653495
126 142071468 ▶ if (tmp[i].kind != FN_PAIKA) return 1;
Branch: 1 branch
BranchTrueFalseTotal
if (tmp[i].kind != FN_PAIKA) return 1; 3134813 138936655 142071468
127 }
128 }
129 18575442 return 0;
130 }
131  
132 /* THE OBLIGATION. Every step of every stone is found first; if one of them
133 * takes, the paikas are dropped from the list, wherever they stand. */
134 13374889 static int fn_gen_steps(const struct fn_board *b, struct fn_step *out, int max)
135 {
136 13374889 const struct fn_abi *e = E();
137 struct fn_step tmp[STONE_STEPS_MAX];
138 13374889 int side = e->side(b);
139 13374889 int must = fn_can_capture(b, side);
140 13374889 int rank, file, i, n, found = 0;
141 80203182 ▶ for (rank = 0; rank < e->rows(b); rank++) {
Branch: 1 branch
BranchTrueFalseTotal
for (rank = 0; rank < e->rows(b); rank++) { 66828293 13374889 80203182
142 667799948 ▶ for (file = 0; file < e->cols(b); file++) {
Branch: 1 branch
BranchTrueFalseTotal
for (file = 0; file < e->cols(b); file++) { 600971655 66828293 667799948
143 600971655 int sq = e->square_of(file, rank);
144 600971655 ▶ if (AT(b, sq) != side) continue;
Branch: 1 branch
BranchTrueFalseTotal
if (AT(b, sq) != side) continue; 575907883 25063772 600971655
145 25063772 n = fn_steps_of(b, sq, tmp, STONE_STEPS_MAX);
146 123751496 ▶ for (i = 0; i < n; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < n; i++) { 98687724 25063772 123751496
147 98687724 ▶ if (must && tmp[i].kind == FN_PAIKA) continue;
Branch: 2 branches
BranchTrueFalseTotal
if (must && tmp[i].kind == FN_PAIKA) continue; 35840308 62847416 98687724
if (must && tmp[i].kind == FN_PAIKA) continue; 29189299 6651009 35840308
148 69498425 ▶ if (out && found < max) out[found] = tmp[i];
Branch: 2 branches
BranchTrueFalseTotal
if (out && found < max) out[found] = tmp[i]; 31300013 38198412 69498425
if (out && found < max) out[found] = tmp[i]; 31300013 0 31300013
149 69498425 found++;
150 }
151 }
152 }
153 13374889 return found;
154 }
155  
156 27049242 static int fn_step_build(const struct fn_board *b, int from, int dir, int kind, struct fn_step *out)
157 {
158 int ahead[FN_LINE_MAX];
159 27049242 int stone, to, n = 0;
160 27049242 ▶ if (dir < 0 || dir >= FN_DIRS) return 0;
Branch: 2 branches
BranchTrueFalseTotal
if (dir < 0 || dir >= FN_DIRS) return 0; 27049242 0 27049242
if (dir < 0 || dir >= FN_DIRS) return 0; 1 27049241 27049242
161 27049241 ▶ if (kind != FN_PAIKA && kind != FN_APPROACH && kind != FN_WITHDRAWAL) return 0;
Branch: 3 branches
BranchTrueFalseTotal
if (kind != FN_PAIKA && kind != FN_APPROACH && kind != FN_WITHDRAWAL) return 0; 18711984 8337257 27049241
if (kind != FN_PAIKA && kind != FN_APPROACH && kind != FN_WITHDRAWAL) return 0; 9104439 9607545 18711984
if (kind != FN_PAIKA && kind != FN_APPROACH && kind != FN_WITHDRAWAL) return 0; 1 9104438 9104439
162 27049240 stone = AT(b, from);
163 27049240 ▶ if (!FN_IS_STONE(stone)) return 0;
Branch: 2 branches
BranchTrueFalseTotal
if (!FN_IS_STONE(stone)) return 0; 11524163 15525077 27049240
if (!FN_IS_STONE(stone)) return 0; 3 11524160 11524163
164 27049237 to = NEXT(b, from, dir);
165 27049237 ▶ if (to < 0 || AT(b, to) != FN_EMPTY) return 0;
Branch: 2 branches
BranchTrueFalseTotal
if (to < 0 || AT(b, to) != FN_EMPTY) return 0; 27049235 2 27049237
if (to < 0 || AT(b, to) != FN_EMPTY) return 0; 1 27049234 27049235
166 27049234 ▶ if (kind == FN_APPROACH)
Branch: 1 branch
BranchTrueFalseTotal
if (kind == FN_APPROACH) 9607545 17441689 27049234
167 9607545 n = line_from(b, NEXT(b, to, dir), dir, FN_OTHER(stone), ahead);
168 17441689 ▶ else if (kind == FN_WITHDRAWAL)
Branch: 1 branch
BranchTrueFalseTotal
else if (kind == FN_WITHDRAWAL) 9104438 8337251 17441689
169 9104438 n = line_from(b, NEXT(b, from, (dir + 4) % FN_DIRS), (dir + 4) % FN_DIRS, FN_OTHER(stone), ahead);
170 27049234 ▶ if (kind != FN_PAIKA && !n) return 0;
Branch: 2 branches
BranchTrueFalseTotal
if (kind != FN_PAIKA && !n) return 0; 18711983 8337251 27049234
if (kind != FN_PAIKA && !n) return 0; 16673629 2038354 18711983
171 10375605 ▶ if (out) step_fill(out, from, to, dir, kind, ahead, n);
Branch: 1 branch
BranchTrueFalseTotal
if (out) step_fill(out, from, to, dir, kind, ahead, n); 10359232 16373 10375605
172 10375605 return 1;
173 }
174  
175 9775284 static int fn_step_why(const struct fn_board *b, int from, int dir, int kind, struct fn_step *out)
176 {
177 9775284 const struct fn_abi *e = E();
178 struct fn_step either;
179 int stone, to, takes;
180 9775284 ▶ if (!e->on_board(b, from)) return FN_WHY_OFF_BOARD;
Branch: 1 branch
BranchTrueFalseTotal
if (!e->on_board(b, from)) return FN_WHY_OFF_BOARD; 1 9775283 9775284
181 9775283 ▶ if (dir < 0 || dir >= FN_DIRS) return FN_WHY_BAD_STEP;
Branch: 2 branches
BranchTrueFalseTotal
if (dir < 0 || dir >= FN_DIRS) return FN_WHY_BAD_STEP; 9775283 0 9775283
if (dir < 0 || dir >= FN_DIRS) return FN_WHY_BAD_STEP; 1 9775282 9775283
182 9775282 ▶ if (kind != FN_PAIKA && kind != FN_APPROACH && kind != FN_WITHDRAWAL) return FN_WHY_BAD_STEP;
Branch: 3 branches
BranchTrueFalseTotal
if (kind != FN_PAIKA && kind != FN_APPROACH && kind != FN_WITHDRAWAL) return FN_WHY_BAD_STEP; 1417490 8357792 9775282
if (kind != FN_PAIKA && kind != FN_APPROACH && kind != FN_WITHDRAWAL) return FN_WHY_BAD_STEP; 492166 925324 1417490
if (kind != FN_PAIKA && kind != FN_APPROACH && kind != FN_WITHDRAWAL) return FN_WHY_BAD_STEP; 1 492165 492166
183 9775281 stone = AT(b, from);
184 9775281 ▶ if (!FN_IS_STONE(stone)) return FN_WHY_NO_STONE;
Branch: 2 branches
BranchTrueFalseTotal
if (!FN_IS_STONE(stone)) return FN_WHY_NO_STONE; 4269237 5506044 9775281
if (!FN_IS_STONE(stone)) return FN_WHY_NO_STONE; 49828 4219409 4269237
185 9725453 ▶ if (stone != e->side(b)) return FN_WHY_NOT_YOURS;
Branch: 1 branch
BranchTrueFalseTotal
if (stone != e->side(b)) return FN_WHY_NOT_YOURS; 10591 9714862 9725453
186 9714862 to = NEXT(b, from, dir);
187 9714862 ▶ if (to < 0) return FN_WHY_NO_LINE;
Branch: 1 branch
BranchTrueFalseTotal
if (to < 0) return FN_WHY_NO_LINE; 4056 9710806 9714862
188 9710806 ▶ if (AT(b, to) != FN_EMPTY) return FN_WHY_OCCUPIED;
Branch: 1 branch
BranchTrueFalseTotal
if (AT(b, to) != FN_EMPTY) return FN_WHY_OCCUPIED; 1864 9708942 9710806
189 9708942 ▶ if (kind != FN_PAIKA) {
Branch: 1 branch
BranchTrueFalseTotal
if (kind != FN_PAIKA) { 1373267 8335675 9708942
190 1373267 ▶ if (!fn_step_build(b, from, dir, kind, out)) return FN_WHY_TAKES_NOTHING;
Branch: 1 branch
BranchTrueFalseTotal
if (!fn_step_build(b, from, dir, kind, out)) return FN_WHY_TAKES_NOTHING; 2262 1371005 1373267
191 1371005 return FN_WHY_OK;
192 }
193 8335675 takes = fn_step_build(b, from, dir, FN_APPROACH, &either)
194 8335675 ▶ || fn_step_build(b, from, dir, FN_WITHDRAWAL, &either);
Branch: 2 branches
BranchTrueFalseTotal
|| fn_step_build(b, from, dir, FN_WITHDRAWAL, &either); 8335492 183 8335675
|| fn_step_build(b, from, dir, FN_WITHDRAWAL, &either); 134 8335358 8335492
195 8335675 ▶ if (takes) return FN_WHY_NOT_A_PAIKA;
Branch: 1 branch
BranchTrueFalseTotal
if (takes) return FN_WHY_NOT_A_PAIKA; 317 8335358 8335675
196 8335358 ▶ if (fn_can_capture(b, stone)) return FN_WHY_MUST_CAPTURE;
Branch: 1 branch
BranchTrueFalseTotal
if (fn_can_capture(b, stone)) return FN_WHY_MUST_CAPTURE; 921 8334437 8335358
197 8334437 fn_step_build(b, from, dir, FN_PAIKA, out);
198 8334437 return FN_WHY_OK;
199 }
200  
201 /* ---- do and undo ----------------------------------------------------------------
202 *
203 * do_step takes the step at its word about what is taken, and records what
204 * actually stood on each point so that undo puts back exactly that.
205 */
206  
207 15125215 static int fn_do_step(struct fn_board *b, const struct fn_step *s, struct fn_undo *u)
208 {
209 15125215 const struct fn_abi *e = E();
210 15125215 int stone, i, n, removed = 0;
211 15125215 ▶ if (u) memset(u, 0, sizeof(*u));
Branch: 1 branch
BranchTrueFalseTotal
if (u) memset(u, 0, sizeof(*u)); 15125215 0 15125215
212 15125215 ▶ if (!s) return -1;
Branch: 1 branch
BranchTrueFalseTotal
if (!s) return -1; 0 15125215 15125215
213 15125215 stone = AT(b, s->from);
214 15125215 ▶ if (!FN_IS_STONE(stone) || AT(b, s->to) != FN_EMPTY) return -1;
Branch: 3 branches
BranchTrueFalseTotal
if (!FN_IS_STONE(stone) || AT(b, s->to) != FN_EMPTY) return -1; 6670480 8454735 15125215
if (!FN_IS_STONE(stone) || AT(b, s->to) != FN_EMPTY) return -1; 6670480 0 6670480
if (!FN_IS_STONE(stone) || AT(b, s->to) != FN_EMPTY) return -1; 0 15125215 15125215
215 15125215 n = s->taken_n;
216 15125215 ▶ if (n < 0) n = 0;
Branch: 1 branch
BranchTrueFalseTotal
if (n < 0) n = 0; 0 15125215 15125215
217 15125215 ▶ if (n > FN_LINE_MAX) n = FN_LINE_MAX;
Branch: 1 branch
BranchTrueFalseTotal
if (n > FN_LINE_MAX) n = FN_LINE_MAX; 0 15125215 15125215
218 15125215 ▶ if (u) {
Branch: 1 branch
BranchTrueFalseTotal
if (u) { 15125215 0 15125215
219 15125215 u->step = *s;
220 15125215 u->step.taken_n = n;
221 15125215 u->did = 1;
222 15125215 u->stone = stone;
223 15125215 u->side = e->side(b);
224 15125215 u->key = e->key(b);
225 }
226 15125215 e->lift(b, s->from);
227 15125215 e->put(b, s->to, stone);
228 18348474 ▶ for (i = 0; i < n; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < n; i++) { 3223259 15125215 18348474
229 3223259 int was = AT(b, s->taken[i]);
230 3223259 ▶ if (u) u->was[i] = FN_IS_STONE(was) ? was : FN_EMPTY;
Branch: 3 branches
BranchTrueFalseTotal
if (u) u->was[i] = FN_IS_STONE(was) ? was : FN_EMPTY; 3223259 0 3223259
if (u) u->was[i] = FN_IS_STONE(was) ? was : FN_EMPTY; 1704826 1518433 3223259
if (u) u->was[i] = FN_IS_STONE(was) ? was : FN_EMPTY; 1704826 0 1704826
231 3223259 ▶ if (!FN_IS_STONE(was)) continue;
Branch: 2 branches
BranchTrueFalseTotal
if (!FN_IS_STONE(was)) continue; 1704826 1518433 3223259
if (!FN_IS_STONE(was)) continue; 0 1704826 1704826
232 3223259 e->lift(b, s->taken[i]);
233 3223259 removed++;
234 }
235 15125215 e->set_side(b, FN_OTHER(e->side(b)));
236 15125215 return removed;
237 }
238  
239 15048039 static void fn_undo_step(struct fn_board *b, const struct fn_undo *u)
240 {
241 15048039 const struct fn_abi *e = E();
242 int i;
243 15048039 ▶ if (!u || !u->did) return;
Branch: 2 branches
BranchTrueFalseTotal
if (!u || !u->did) return; 15048039 0 15048039
if (!u || !u->did) return; 0 15048039 15048039
244 15048039 e->set_side(b, u->side);
245 18193400 ▶ for (i = 0; i < u->step.taken_n; i++)
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < u->step.taken_n; i++) 3145361 15048039 18193400
246 3145361 ▶ if (FN_IS_STONE(u->was[i])) e->put(b, u->step.taken[i], u->was[i]);
Branch: 2 branches
BranchTrueFalseTotal
if (FN_IS_STONE(u->was[i])) e->put(b, u->step.taken[i], u->was[i]); 1665218 1480143 3145361
if (FN_IS_STONE(u->was[i])) e->put(b, u->step.taken[i], u->was[i]); 1665218 0 1665218
247 15048039 e->lift(b, u->step.to);
248 15048039 e->put(b, u->step.from, u->stone);
249 }
250  
251 1824 static unsigned long long fn_perft_steps(struct fn_board *b, int depth)
252 {
253 struct fn_step list[FN_STEPS_MAX];
254 struct fn_undo u;
255 1824 unsigned long long total = 0;
256 int n, i;
257 1824 ▶ if (depth <= 0) return 1;
Branch: 1 branch
BranchTrueFalseTotal
if (depth <= 0) return 1; 1 1823 1824
258 1823 n = fn_gen_steps(b, list, FN_STEPS_MAX);
259 1823 ▶ if (depth == 1) return (unsigned long long) n;
Branch: 1 branch
BranchTrueFalseTotal
if (depth == 1) return (unsigned long long) n; 1523 300 1823
260 2114 ▶ for (i = 0; i < n; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < n; i++) { 1814 300 2114
261 1814 fn_do_step(b, &list[i], &u);
262 1814 total += fn_perft_steps(b, depth - 1);
263 1814 fn_undo_step(b, &u);
264 }
265 300 return total;
266 }
267  
268 /* ---- the chain, version 3 ---------------------------------------------------------
269 *
270 * THE RULES, quoted from the same sources:
271 *
272 * "it is allowed to continue capturing with the same piece ... (Even if a
273 * move consists of multiple movements of one single piece it still counts
274 * as a single move.)"
275 * "the player may stop capturing after any number of opponent pieces are
276 * captured."
277 * "It is not allowed to make a capturing move in the same direction as the
278 * capturing move directly before ... A player is allowed to play a
279 * capturing sequence two times into the same direction if a capturing
280 * movement in another direction is done in between. The last movement
281 * direction of the capturing move in the previous turn ... does not
282 * influence possible capturing directions in the current turn."
283 * "The current capturing piece is not allowed to arrive on the same
284 * intersection twice during a capturing sequence." The source's own
285 * example refuses a return to the point the chain STARTED from.
286 * "you must keep moving the same piece"
287 *
288 * and one reading: every step of a chain after the first must take. A stone
289 * that has taken may stop; it may not then make a paika.
290 *
291 * THE DIRECTION RULE LOOKS BACK ONE STEP AND NO FURTHER, and nothing of a
292 * chain outlives it: closing clears all three fields.
293 */
294  
295 4199294 static unsigned long long bit_of(int sq)
296 {
297 4199294 int bit = (E())->point_bit(sq);
298 4199294 ▶ return bit < 0 ? 0 : (1ULL << bit);
Branch: 1 branch
BranchTrueFalseTotal
return bit < 0 ? 0 : (1ULL << bit); 4199294 0 4199294
299 }
300  
301 /* The steps that may follow in an open chain. */
302 3004983 static int chain_steps(const struct fn_board *b, struct fn_step *out, int max)
303 {
304 3004983 const struct fn_abi *e = E();
305 struct fn_step tmp[STONE_STEPS_MAX];
306 3004983 int at = e->chain_at(b);
307 3004983 int last = e->chain_dir(b);
308 3004983 int i, n, found = 0;
309 3004983 ▶ if (at < 0) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (at < 0) return 0; 0 3004983 3004983
310 3004983 n = fn_steps_of(b, at, tmp, STONE_STEPS_MAX);
311 18796022 ▶ for (i = 0; i < n; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < n; i++) { 15791039 3004983 18796022
312 15791039 ▶ if (tmp[i].kind == FN_PAIKA) continue;
Branch: 1 branch
BranchTrueFalseTotal
if (tmp[i].kind == FN_PAIKA) continue; 13254116 2536923 15791039
313 2536923 ▶ if (tmp[i].dir == last) continue;
Branch: 1 branch
BranchTrueFalseTotal
if (tmp[i].dir == last) continue; 62706 2474217 2536923
314 2474217 ▶ if (e->chain_seen(b, tmp[i].to)) continue;
Branch: 1 branch
BranchTrueFalseTotal
if (e->chain_seen(b, tmp[i].to)) continue; 414187 2060030 2474217
315 2060030 ▶ if (out && found < max) out[found] = tmp[i];
Branch: 2 branches
BranchTrueFalseTotal
if (out && found < max) out[found] = tmp[i]; 703669 1356361 2060030
if (out && found < max) out[found] = tmp[i]; 703669 0 703669
316 2060030 found++;
317 }
318 3004983 return found;
319 }
320  
321 12845339 static int fn_play_steps(const struct fn_board *b, struct fn_step *out, int max)
322 {
323 12845339 ▶ if ((E())->chain_at(b) >= 0) return chain_steps(b, out, max);
Branch: 1 branch
BranchTrueFalseTotal
if ((E())->chain_at(b) >= 0) return chain_steps(b, out, max); 402910 12442429 12845339
324 12442429 return fn_gen_steps(b, out, max);
325 }
326  
327 74806 static int fn_can_stop(const struct fn_board *b)
328 {
329 74806 return (E())->chain_at(b) >= 0;
330 }
331  
332 10426710 static int fn_play_why(const struct fn_board *b, int from, int dir, int kind, struct fn_step *out)
333 {
334 10426710 const struct fn_abi *e = E();
335 struct fn_step either;
336 10426710 int at = e->chain_at(b);
337 int stone, to;
338 10426710 ▶ if (at < 0) return fn_step_why(b, from, dir, kind, out);
Branch: 1 branch
BranchTrueFalseTotal
if (at < 0) return fn_step_why(b, from, dir, kind, out); 9710454 716256 10426710
339 716256 ▶ if (!e->on_board(b, from)) return FN_WHY_OFF_BOARD;
Branch: 1 branch
BranchTrueFalseTotal
if (!e->on_board(b, from)) return FN_WHY_OFF_BOARD; 0 716256 716256
340 716256 ▶ if (dir < 0 || dir >= FN_DIRS) return FN_WHY_BAD_STEP;
Branch: 2 branches
BranchTrueFalseTotal
if (dir < 0 || dir >= FN_DIRS) return FN_WHY_BAD_STEP; 716256 0 716256
if (dir < 0 || dir >= FN_DIRS) return FN_WHY_BAD_STEP; 0 716256 716256
341 716256 ▶ if (kind != FN_PAIKA && kind != FN_APPROACH && kind != FN_WITHDRAWAL) return FN_WHY_BAD_STEP;
Branch: 3 branches
BranchTrueFalseTotal
if (kind != FN_PAIKA && kind != FN_APPROACH && kind != FN_WITHDRAWAL) return FN_WHY_BAD_STEP; 691770 24486 716256
if (kind != FN_PAIKA && kind != FN_APPROACH && kind != FN_WITHDRAWAL) return FN_WHY_BAD_STEP; 312349 379421 691770
if (kind != FN_PAIKA && kind != FN_APPROACH && kind != FN_WITHDRAWAL) return FN_WHY_BAD_STEP; 0 312349 312349
342 716256 stone = AT(b, from);
343 716256 ▶ if (!FN_IS_STONE(stone)) return FN_WHY_NO_STONE;
Branch: 2 branches
BranchTrueFalseTotal
if (!FN_IS_STONE(stone)) return FN_WHY_NO_STONE; 310743 405513 716256
if (!FN_IS_STONE(stone)) return FN_WHY_NO_STONE; 39481 271262 310743
344 676775 ▶ if (stone != e->side(b)) return FN_WHY_NOT_YOURS;
Branch: 1 branch
BranchTrueFalseTotal
if (stone != e->side(b)) return FN_WHY_NOT_YOURS; 20521 656254 676775
345 656254 ▶ if (from != at) return FN_WHY_NOT_THE_STONE;
Branch: 1 branch
BranchTrueFalseTotal
if (from != at) return FN_WHY_NOT_THE_STONE; 11810 644444 656254
346 644444 to = NEXT(b, from, dir);
347 644444 ▶ if (to < 0) return FN_WHY_NO_LINE;
Branch: 1 branch
BranchTrueFalseTotal
if (to < 0) return FN_WHY_NO_LINE; 277 644167 644444
348 644167 ▶ if (AT(b, to) != FN_EMPTY) return FN_WHY_OCCUPIED;
Branch: 1 branch
BranchTrueFalseTotal
if (AT(b, to) != FN_EMPTY) return FN_WHY_OCCUPIED; 348 643819 644167
349 643819 ▶ if (dir == e->chain_dir(b)) return FN_WHY_SAME_DIRECTION;
Branch: 1 branch
BranchTrueFalseTotal
if (dir == e->chain_dir(b)) return FN_WHY_SAME_DIRECTION; 179 643640 643819
350 643640 ▶ if (e->chain_seen(b, to)) return FN_WHY_REVISIT;
Branch: 1 branch
BranchTrueFalseTotal
if (e->chain_seen(b, to)) return FN_WHY_REVISIT; 249 643391 643640
351 643391 ▶ if (kind == FN_PAIKA) {
Branch: 1 branch
BranchTrueFalseTotal
if (kind == FN_PAIKA) { 201 643190 643391
352 201 ▶ if (fn_step_build(b, from, dir, FN_APPROACH, &either)
Branch: 1 branch
BranchTrueFalseTotal
if (fn_step_build(b, from, dir, FN_APPROACH, &either) 134 67 201
353 201 ▶ || fn_step_build(b, from, dir, FN_WITHDRAWAL, &either)) return FN_WHY_NOT_A_PAIKA;
Branch: 1 branch
BranchTrueFalseTotal
|| fn_step_build(b, from, dir, FN_WITHDRAWAL, &either)) return FN_WHY_NOT_A_PAIKA; 37 97 134
354 97 return FN_WHY_PAIKA_IN_CHAIN;
355 }
356 643190 ▶ if (!fn_step_build(b, from, dir, kind, out)) return FN_WHY_TAKES_NOTHING;
Branch: 1 branch
BranchTrueFalseTotal
if (!fn_step_build(b, from, dir, kind, out)) return FN_WHY_TAKES_NOTHING; 285 642905 643190
357 642905 return FN_WHY_OK;
358 }
359  
360 77678 static void undo_keep_chain(const struct fn_board *b, struct fn_undo *u, int stop)
361 {
362 77678 const struct fn_abi *e = E();
363 77678 ▶ if (!u) return;
Branch: 1 branch
BranchTrueFalseTotal
if (!u) return; 0 77678 77678
364 77678 u->reserved[FN_UNDO_PLAYED] = 1;
365 77678 u->reserved[FN_UNDO_AT] = e->chain_at(b);
366 77678 u->reserved[FN_UNDO_DIR] = e->chain_dir(b);
367 77678 u->reserved[FN_UNDO_STOP] = stop;
368 77678 u->reserved64[FN_UNDO_SEEN] = e->chain_mask(b);
369 }
370  
371 15118388 static int fn_play_step(struct fn_board *b, const struct fn_step *s, struct fn_undo *u)
372 {
373 15118388 const struct fn_abi *e = E();
374 struct fn_undo local;
375 unsigned long long seen;
376 int mover, was_open, removed;
377 15118388 ▶ if (!u) u = &local;
Branch: 1 branch
BranchTrueFalseTotal
if (!u) u = &local; 0 15118388 15118388
378 15118388 mover = e->side(b);
379 15118388 was_open = e->chain_at(b) >= 0;
380 15118388 seen = e->chain_mask(b);
381 {
382 /* the chain as it was, before do_step clears the record */
383 15118388 int at = e->chain_at(b), dir = e->chain_dir(b);
384 15118388 removed = fn_do_step(b, s, u);
385 15118388 ▶ if (removed < 0) return -1;
Branch: 1 branch
BranchTrueFalseTotal
if (removed < 0) return -1; 0 15118388 15118388
386 15118388 u->reserved[FN_UNDO_PLAYED] = 1;
387 15118388 u->reserved[FN_UNDO_AT] = at;
388 15118388 u->reserved[FN_UNDO_DIR] = dir;
389 15118388 u->reserved[FN_UNDO_STOP] = 0;
390 15118388 u->reserved64[FN_UNDO_SEEN] = seen;
391 }
392 15118388 ▶ if (removed == 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (removed == 0) { 12615252 2503136 15118388
393 /* a paika: do_step has passed the turn, and no chain survives one */
394 12615252 e->chain_set(b, -1, -1, 0);
395 12615252 return 0;
396 }
397 /* it took: the turn stays with the mover and the chain is on this stone */
398 2503136 e->set_side(b, mover);
399 2503136 ▶ if (!was_open) seen = bit_of(s->from);
Branch: 1 branch
BranchTrueFalseTotal
if (!was_open) seen = bit_of(s->from); 1696158 806978 2503136
400 2503136 seen |= bit_of(s->to);
401 2503136 e->chain_set(b, s->to, s->dir, seen);
402 2503136 ▶ if (chain_steps(b, NULL, 0) == 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (chain_steps(b, NULL, 0) == 0) { 1684480 818656 2503136
403 1684480 e->chain_set(b, -1, -1, 0);
404 1684480 e->set_side(b, FN_OTHER(mover));
405 }
406 2503136 return removed;
407 }
408  
409 77679 static int fn_play_stop(struct fn_board *b, struct fn_undo *u)
410 {
411 77679 const struct fn_abi *e = E();
412 77679 ▶ if (u) memset(u, 0, sizeof(*u));
Branch: 1 branch
BranchTrueFalseTotal
if (u) memset(u, 0, sizeof(*u)); 77679 0 77679
413 77679 ▶ if (e->chain_at(b) < 0) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (e->chain_at(b) < 0) return 0; 1 77678 77679
414 77678 ▶ if (u) {
Branch: 1 branch
BranchTrueFalseTotal
if (u) { 77678 0 77678
415 77678 u->did = 1;
416 77678 u->side = e->side(b);
417 77678 u->key = e->key(b);
418 }
419 77678 undo_keep_chain(b, u, 1);
420 77678 e->chain_set(b, -1, -1, 0);
421 77678 e->set_side(b, FN_OTHER(e->side(b)));
422 77678 return 1;
423 }
424  
425 15115230 static void fn_play_undo(struct fn_board *b, const struct fn_undo *u)
426 {
427 15115230 const struct fn_abi *e = E();
428 15115230 ▶ if (!u || !u->did) return;
Branch: 2 branches
BranchTrueFalseTotal
if (!u || !u->did) return; 15115230 0 15115230
if (!u || !u->did) return; 0 15115230 15115230
429 15115230 ▶ if (u->reserved[FN_UNDO_STOP]) e->set_side(b, u->side);
Branch: 1 branch
BranchTrueFalseTotal
if (u->reserved[FN_UNDO_STOP]) e->set_side(b, u->side); 74011 15041219 15115230
430 15041219 else fn_undo_step(b, u);
431 15115230 e->chain_set(b, u->reserved[FN_UNDO_AT], u->reserved[FN_UNDO_DIR], u->reserved64[FN_UNDO_SEEN]);
432 }
433  
434 /* ---- whole moves -------------------------------------------------------------------
435 *
436 * A walk of the step tree, depth first. A move ends after every step: a paika
437 * is a move, a step that closed its own chain is a move, and a step that left
438 * the chain open is a move too, because the mover may stop there. So every
439 * node of the tree below the root is one move, and a chain's shorter
440 * beginnings are met before its longer ones.
441 */
442  
443 struct walk {
444 struct fn_move cur;
445 struct fn_move *out;
446 int max;
447 unsigned long long found;
448 unsigned long long cap;
449 };
450  
451 1023956 static void walk_from(struct fn_board *b, struct walk *w, struct fn_step *list, int n)
452 {
453 1023956 const struct fn_abi *e = E();
454 struct fn_step next[STONE_STEPS_MAX];
455 struct fn_undo u;
456 int i, m;
457 5764525 ▶ for (i = 0; i < n; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < n; i++) { 4740588 1023937 5764525
458 4740588 ▶ if (w->cap && w->found >= w->cap) return;
Branch: 2 branches
BranchTrueFalseTotal
if (w->cap && w->found >= w->cap) return; 4718815 21773 4740588
if (w->cap && w->found >= w->cap) return; 19 4718796 4718815
459 4740569 ▶ if (w->cur.n >= FN_CHAIN_MAX) return;
Branch: 1 branch
BranchTrueFalseTotal
if (w->cur.n >= FN_CHAIN_MAX) return; 0 4740569 4740569
460 4740569 ▶ if (w->cur.n == 0) w->cur.from = list[i].from;
Branch: 1 branch
BranchTrueFalseTotal
if (w->cur.n == 0) w->cur.from = list[i].from; 4597515 143054 4740569
461 4740569 w->cur.dir[w->cur.n] = (unsigned char) list[i].dir;
462 4740569 w->cur.kind[w->cur.n] = (unsigned char) list[i].kind;
463 4740569 w->cur.n++;
464 4740569 w->cur.taken += list[i].taken_n;
465 4740569 fn_play_step(b, &list[i], &u);
466 4740569 ▶ if (w->out && w->found < (unsigned long long) w->max) w->out[w->found] = w->cur;
Branch: 2 branches
BranchTrueFalseTotal
if (w->out && w->found < (unsigned long long) w->max) w->out[w->found] = w->cur; 2358647 2381922 4740569
if (w->out && w->found < (unsigned long long) w->max) w->out[w->found] = w->cur; 2358647 0 2358647
467 4740569 w->found++;
468 4740569 ▶ if (e->chain_at(b) >= 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (e->chain_at(b) >= 0) { 98937 4641632 4740569
469 98937 m = chain_steps(b, next, STONE_STEPS_MAX);
470 98937 walk_from(b, w, next, m);
471 }
472 4740569 fn_play_undo(b, &u);
473 4740569 w->cur.taken -= list[i].taken_n;
474 4740569 w->cur.n--;
475 }
476 }
477  
478 925019 static unsigned long long walk_moves(struct fn_board *b, struct fn_move *out, int max, unsigned long long cap)
479 {
480 struct fn_step list[FN_STEPS_MAX];
481 struct walk w;
482 int n;
483 925019 memset(&w, 0, sizeof(w));
484 925019 w.out = out;
485 925019 w.max = max;
486 925019 w.cap = cap;
487 925019 ▶ if ((E())->chain_at(b) >= 0) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if ((E())->chain_at(b) >= 0) return 0; 0 925019 925019
488 925019 n = fn_gen_steps(b, list, FN_STEPS_MAX);
489 925019 walk_from(b, &w, list, n);
490 925019 return w.found;
491 }
492  
493 462727 static unsigned long long fn_count_moves(struct fn_board *b, unsigned long long cap)
494 {
495 462727 return walk_moves(b, NULL, 0, cap);
496 }
497  
498 /* THE WALK STOPS ONE PAST `max`. A position can have more whole moves than
499 * anyone will wait for, so "how many there are" is answered only as far as
500 * the caller's buffer plus one: enough to know the buffer was short, and no
501 * further. count_moves is the call that counts. */
502 462292 static int fn_gen_moves(struct fn_board *b, struct fn_move *out, int max)
503 {
504 462292 ▶ if (max < 0) max = 0;
Branch: 1 branch
BranchTrueFalseTotal
if (max < 0) max = 0; 0 462292 462292
505 462292 return (int) walk_moves(b, out, max, (unsigned long long) max + 1ULL);
506 }
507  
508 2358647 static int fn_move_steps(struct fn_board *b, const struct fn_move *m, struct fn_step *out)
509 {
510 2358647 const struct fn_abi *e = E();
511 struct fn_undo undo[FN_CHAIN_MAX];
512 struct fn_step s;
513 2358647 int at, i, ok = 1;
514 2358647 ▶ if (!m || m->n < 1 || m->n > FN_CHAIN_MAX || e->chain_at(b) >= 0) return -1;
Branch: 4 branches
BranchTrueFalseTotal
if (!m || m->n < 1 || m->n > FN_CHAIN_MAX || e->chain_at(b) >= 0) return -1; 2358647 0 2358647
if (!m || m->n < 1 || m->n > FN_CHAIN_MAX || e->chain_at(b) >= 0) return -1; 2358647 0 2358647
if (!m || m->n < 1 || m->n > FN_CHAIN_MAX || e->chain_at(b) >= 0) return -1; 2358647 0 2358647
if (!m || m->n < 1 || m->n > FN_CHAIN_MAX || e->chain_at(b) >= 0) return -1; 0 2358647 2358647
515 2358647 at = m->from;
516 4948065 ▶ for (i = 0; i < m->n; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < m->n; i++) { 2589418 2358647 4948065
517 2589418 ▶ if (fn_play_why(b, at, m->dir[i], m->kind[i], &s) != FN_WHY_OK) { ok = 0; break; }
Branch: 1 branch
BranchTrueFalseTotal
if (fn_play_why(b, at, m->dir[i], m->kind[i], &s) != FN_WHY_OK) { ok = 0; break; } 0 2589418 2589418
518 2589418 ▶ if (out) out[i] = s;
Branch: 1 branch
BranchTrueFalseTotal
if (out) out[i] = s; 2589418 0 2589418
519 2589418 fn_play_step(b, &s, &undo[i]);
520 2589418 at = s.to;
521 }
522 4948065 ▶ while (i-- > 0) fn_play_undo(b, &undo[i]);
Branch: 1 branch
BranchTrueFalseTotal
while (i-- > 0) fn_play_undo(b, &undo[i]); 2589418 2358647 4948065
523 2358647 ▶ return ok ? m->n : -1;
Branch: 1 branch
BranchTrueFalseTotal
return ok ? m->n : -1; 2358647 0 2358647
524 }
525  
526 35677 static unsigned long long fn_perft_moves(struct fn_board *b, int depth)
527 {
528 35677 const struct fn_abi *e = E();
529 struct fn_step list[FN_STEPS_MAX];
530 struct fn_undo u, stop;
531 35677 unsigned long long total = 0;
532 int n, i;
533 35677 ▶ if (depth <= 0) return 1;
Branch: 1 branch
BranchTrueFalseTotal
if (depth <= 0) return 1; 22834 12843 35677
534 12843 n = fn_play_steps(b, list, FN_STEPS_MAX);
535 36866 ▶ for (i = 0; i < n; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < n; i++) { 24023 12843 36866
536 24023 fn_play_step(b, &list[i], &u);
537 24023 ▶ if (e->chain_at(b) >= 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (e->chain_at(b) >= 0) { 11636 12387 24023
538 /* the mover may stop here, which ends this move ... */
539 11636 fn_play_stop(b, &stop);
540 11636 total += fn_perft_moves(b, depth - 1);
541 11636 fn_play_undo(b, &stop);
542 /* ... or go on, which is still this move */
543 11636 total += fn_perft_moves(b, depth);
544 }
545 else {
546 12387 total += fn_perft_moves(b, depth - 1);
547 }
548 24023 fn_play_undo(b, &u);
549 }
550 12843 return total;
551 }
552  
553 /* ---- installed into the table by fn_engine.c ---------------------------------- */
554  
555 void fn_moves_install(struct fn_abi *t);
556  
557 43 void fn_moves_install(struct fn_abi *t)
558 {
559 43 t->gen_steps = fn_gen_steps;
560 43 t->steps_of = fn_steps_of;
561 43 t->can_capture = fn_can_capture;
562 43 t->step_why = fn_step_why;
563 43 t->step_build = fn_step_build;
564 43 t->do_step = fn_do_step;
565 43 t->undo_step = fn_undo_step;
566 43 t->perft_steps = fn_perft_steps;
567  
568 43 t->play_steps = fn_play_steps;
569 43 t->can_stop = fn_can_stop;
570 43 t->play_why = fn_play_why;
571 43 t->play_step = fn_play_step;
572 43 t->play_stop = fn_play_stop;
573 43 t->play_undo = fn_play_undo;
574 43 t->count_moves = fn_count_moves;
575 43 t->gen_moves = fn_gen_moves;
576 43 t->move_steps = fn_move_steps;
577 43 t->perft_moves = fn_perft_moves;
578 43 }
« fn_rules.c ↑ Summary fn_search.c »