| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| if (v) return v; |
310311064 |
0 |
310311064 |
|
| 78 |
0 |
▶ | if (!ready) { bd_variant_default(&DEFAULT); ready = 1; } |
Branch: 1 branch
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| for (rank = 0; rank < BD_SIZE; rank++) { |
1066815869 |
152402267 |
1219218136 |
|
| 113 |
8534526952 |
▶ | for (file = 0; file < BD_SIZE; file++) { |
Branch: 1 branch
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| while (AT(b, sq) == BD_EMPTY) { |
5958617490 |
4790943636 |
10749561126 |
|
| 120 |
5958617490 |
▶ | if (may_land(piece, sq, v)) { |
Branch: 1 branch
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| if (n > BD_MOVES_MAX) n = BD_MOVES_MAX; |
0 |
345121 |
345121 |
|
| 141 |
7029982 |
▶ | for (i = 0; i < n; i++) |
Branch: 1 branch
| Branch | True | False | Total |
| for (i = 0; i < n; i++) |
6935117 |
94865 |
7029982 |
|
| 142 |
6935117 |
▶ | if (list[i] == mv) return 1; |
Branch: 1 branch
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| if (AT(b, to) != BD_EMPTY) return BD_WHY_BLOCKED; |
19479 |
193100 |
212579 |
|
| 171 |
193100 |
▶ | if (!may_land(piece, to, v)) |
Branch: 1 branch
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| if (n > BD_MOVES_MAX) n = BD_MOVES_MAX; |
0 |
3366993 |
3366993 |
|
| 206 |
100879112 |
▶ | for (i = 0; i < n; i++) { |
Branch: 1 branch
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| if (!b) return 0; |
0 |
5138 |
5138 |
|
| 222 |
5138 |
▶ | if (depth <= 0) return 1; |
Branch: 1 branch
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| if (cell != BD_EMPTY) return 0; |
5714987 |
18555265 |
24270252 |
|
| 243 |
18555265 |
▶ | if ((E())->is_corner(sq)) return 1; |
Branch: 1 branch
| Branch | True | False | Total |
| if ((E())->is_corner(sq)) return 1; |
940560 |
17614705 |
18555265 |
|
| 244 |
17614705 |
▶ | if ((E())->is_throne(sq)) return 1; |
Branch: 1 branch
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| if (cell == BD_ATTACKER) continue; |
306081 |
1030808 |
1336889 |
|
| 271 |
1030808 |
▶ | if (cell == BD_EMPTY && (E())->is_throne(sq)) continue; |
Branch: 2 branches
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| if ((E())->is_throne(king)) { |
364904 |
2622124 |
2987028 |
|
| 278 |
502396 |
▶ | for (d = 0; d < 4; d++) |
Branch: 1 branch
| Branch | True | False | Total |
| for (d = 0; d < 4; d++) |
502149 |
247 |
502396 |
|
| 279 |
502149 |
▶ | if (AT(b, king + ORTHO[d]) != BD_ATTACKER) return 0; |
Branch: 1 branch
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| if (taken) { |
4770987 |
28280238 |
33051225 |
|
| 318 |
4770987 |
▶ | if (out) out[n] = sq; |
Branch: 1 branch
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| if (flags) *flags = 0; |
1867782 |
0 |
1867782 |
|
| 396 |
1867782 |
▶ | if (!c) return 0; |
Branch: 1 branch
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| if (n > BD_MOVES_MAX) n = BD_MOVES_MAX; |
0 |
1772685 |
1772685 |
|
| 420 |
53102681 |
▶ | for (i = 0; i < n; i++) { |
Branch: 1 branch
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| if (!b) return 0; |
0 |
4818 |
4818 |
|
| 432 |
4818 |
▶ | if (depth <= 0) return 1; |
Branch: 1 branch
| Branch | True | False | Total |
| 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 |
| } |