| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| for (rank = 0; rank < e->rows(b); rank++) { |
101963417 |
18575442 |
120538859 |
|
| 121 |
1003377902 |
▶ | for (file = 0; file < e->cols(b); file++) { |
Branch: 1 branch
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| for (i = 0; i < n; i++) |
142071468 |
27582027 |
169653495 |
|
| 126 |
142071468 |
▶ | if (tmp[i].kind != FN_PAIKA) return 1; |
Branch: 1 branch
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| for (rank = 0; rank < e->rows(b); rank++) { |
66828293 |
13374889 |
80203182 |
|
| 142 |
667799948 |
▶ | for (file = 0; file < e->cols(b); file++) { |
Branch: 1 branch
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| for (i = 0; i < n; i++) { |
98687724 |
25063772 |
123751496 |
|
| 147 |
98687724 |
▶ | if (must && tmp[i].kind == FN_PAIKA) continue; |
Branch: 2 branches
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| if (AT(b, to) != FN_EMPTY) return FN_WHY_OCCUPIED; |
1864 |
9708942 |
9710806 |
|
| 189 |
9708942 |
▶ | if (kind != FN_PAIKA) { |
Branch: 1 branch
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| || 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| if (u) memset(u, 0, sizeof(*u)); |
15125215 |
0 |
15125215 |
|
| 212 |
15125215 |
▶ | if (!s) return -1; |
Branch: 1 branch
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| if (n < 0) n = 0; |
0 |
15125215 |
15125215 |
|
| 217 |
15125215 |
▶ | if (n > FN_LINE_MAX) n = FN_LINE_MAX; |
Branch: 1 branch
| Branch | True | False | Total |
| if (n > FN_LINE_MAX) n = FN_LINE_MAX; |
0 |
15125215 |
15125215 |
|
| 218 |
15125215 |
▶ | if (u) { |
Branch: 1 branch
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| if (depth == 1) return (unsigned long long) n; |
1523 |
300 |
1823 |
|
| 260 |
2114 |
▶ | for (i = 0; i < n; i++) { |
Branch: 1 branch
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| for (i = 0; i < n; i++) { |
15791039 |
3004983 |
18796022 |
|
| 312 |
15791039 |
▶ | if (tmp[i].kind == FN_PAIKA) continue; |
Branch: 1 branch
| Branch | True | False | Total |
| if (tmp[i].kind == FN_PAIKA) continue; |
13254116 |
2536923 |
15791039 |
|
| 313 |
2536923 |
▶ | if (tmp[i].dir == last) continue; |
Branch: 1 branch
| Branch | True | False | Total |
| if (tmp[i].dir == last) continue; |
62706 |
2474217 |
2536923 |
|
| 314 |
2474217 |
▶ | if (e->chain_seen(b, tmp[i].to)) continue; |
Branch: 1 branch
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| if (e->chain_seen(b, to)) return FN_WHY_REVISIT; |
249 |
643391 |
643640 |
|
| 351 |
643391 |
▶ | if (kind == FN_PAIKA) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (kind == FN_PAIKA) { |
201 |
643190 |
643391 |
|
| 352 |
201 |
▶ | if (fn_step_build(b, from, dir, FN_APPROACH, &either) |
Branch: 1 branch
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| || 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| if (u) memset(u, 0, sizeof(*u)); |
77679 |
0 |
77679 |
|
| 413 |
77679 |
▶ | if (e->chain_at(b) < 0) return 0; |
Branch: 1 branch
| Branch | True | False | Total |
| if (e->chain_at(b) < 0) return 0; |
1 |
77678 |
77679 |
|
| 414 |
77678 |
▶ | if (u) { |
Branch: 1 branch
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| for (i = 0; i < n; i++) { |
4740588 |
1023937 |
5764525 |
|
| 458 |
4740588 |
▶ | if (w->cap && w->found >= w->cap) return; |
Branch: 2 branches
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| while (i-- > 0) fn_play_undo(b, &undo[i]); |
2589418 |
2358647 |
4948065 |
|
| 523 |
2358647 |
▶ | return ok ? m->n : -1; |
Branch: 1 branch
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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 |
| } |