| 1 |
|
| /* xq_engine.c - the xiangqi board, and nothing that judges a move. |
| 2 |
|
| * |
| 3 |
|
| * PERL-FREE by design: see include/xq_abi.h. This file compiles into the XS, |
| 4 |
|
| * into a plain program, or to wasm, and knows nothing about any of them. |
| 5 |
|
| * |
| 6 |
|
| * PHASE 02 SCOPE. The board, the padded index, put and lift, do and undo, the |
| 7 |
|
| * zobrist key, and FEN in and out. No move generation, no legality, no check. |
| 8 |
|
| * Those are phases 03 and 04 and they append to the table. |
| 9 |
|
| */ |
| 10 |
|
| |
| 11 |
|
| #include <stdlib.h> |
| 12 |
|
| #include <string.h> |
| 13 |
|
| #include "xq_abi.h" |
| 14 |
|
| |
| 15 |
|
| /* ---- the position --------------------------------------------------------- |
| 16 |
|
| * |
| 17 |
|
| * A flat 132-cell array with a sentinel ring, the side to move, and a key |
| 18 |
|
| * maintained incrementally. No pointers, so a copy is a struct assignment and |
| 19 |
|
| * two boards never share anything. |
| 20 |
|
| */ |
| 21 |
|
| |
| 22 |
|
| struct xq_board { |
| 23 |
|
| unsigned char cell[XQ_CELLS]; |
| 24 |
|
| int side; |
| 25 |
|
| unsigned long long key; |
| 26 |
|
| }; |
| 27 |
|
| |
| 28 |
|
| /* ---- the zobrist table ----------------------------------------------------- |
| 29 |
|
| * |
| 30 |
|
| * DERIVED, NOT COMMITTED, and the difference is worth a paragraph because the |
| 31 |
|
| * plan asked for a committed table of constants. |
| 32 |
|
| * |
| 33 |
|
| * What the requirement actually is: two workers in a pool must agree about |
| 34 |
|
| * whether a position has been seen, so the table must not come from rand() or |
| 35 |
|
| * from anything that varies per process. A fixed function of a fixed seed |
| 36 |
|
| * satisfies that exactly as a committed array does, in four lines instead of |
| 37 |
|
| * four thousand, and it cannot suffer the transcription error a hand-pasted |
| 38 |
|
| * array can. splitmix64 is used rather than a hand-rolled mixer because it is |
| 39 |
|
| * published, has no weak seeds, and passes the usual test batteries. |
| 40 |
|
| * |
| 41 |
|
| * The consequence to keep in mind: CHANGING THIS GENERATOR CHANGES EVERY KEY. |
| 42 |
|
| * Nothing persists a key across versions today, and if anything ever does, this |
| 43 |
|
| * is the line that breaks it. t/03-key.t pins four values so the change is |
| 44 |
|
| * caught by a red test rather than by a silent disagreement between a stored |
| 45 |
|
| * key and a live one. |
| 46 |
|
| */ |
| 47 |
|
| |
| 48 |
|
| static unsigned long long ZOB[XQ_BORDER + 1][XQ_CELLS]; |
| 49 |
|
| static unsigned long long ZOB_SIDE; |
| 50 |
|
| static int ZOB_READY = 0; |
| 51 |
|
| |
| 52 |
104568 |
| static unsigned long long splitmix64(unsigned long long *state) |
| 53 |
|
| { |
| 54 |
|
| unsigned long long z; |
| 55 |
104568 |
| *state += 0x9E3779B97F4A7C15ULL; |
| 56 |
104568 |
| z = *state; |
| 57 |
104568 |
| z = (z ^ (z >> 30)) * 0xBF58476D1CE4E5B9ULL; |
| 58 |
104568 |
| z = (z ^ (z >> 27)) * 0x94D049BB133111EBULL; |
| 59 |
104568 |
| return z ^ (z >> 31); |
| 60 |
|
| } |
| 61 |
|
| |
| 62 |
99361983 |
| static void zob_init(void) |
| 63 |
|
| { |
| 64 |
99361983 |
| unsigned long long s = 0x7869616E67716921ULL; /* "xiangqi!" */ |
| 65 |
|
| int p, c; |
| 66 |
99361983 |
▶ | if (ZOB_READY) return; |
Branch: 1 branch
| Branch | True | False | Total |
| if (ZOB_READY) return; |
99361959 |
24 |
99361983 |
|
| 67 |
816 |
▶ | for (p = 0; p <= XQ_BORDER; p++) |
Branch: 1 branch
| Branch | True | False | Total |
| for (p = 0; p <= XQ_BORDER; p++) |
792 |
24 |
816 |
|
| 68 |
105336 |
▶ | for (c = 0; c < XQ_CELLS; c++) |
Branch: 1 branch
| Branch | True | False | Total |
| for (c = 0; c < XQ_CELLS; c++) |
104544 |
792 |
105336 |
|
| 69 |
104544 |
| ZOB[p][c] = splitmix64(&s); |
| 70 |
24 |
| ZOB_SIDE = splitmix64(&s); |
| 71 |
24 |
| ZOB_READY = 1; |
| 72 |
|
| } |
| 73 |
|
| |
| 74 |
|
| /* The key covers the pieces, their points, and the side to move, and NOTHING |
| 75 |
|
| * else. There is no castling, no en passant and no halfmove clock in this game, |
| 76 |
|
| * so a position repeating is a position repeating, which is what phase 06's |
| 77 |
|
| * loop detector needs it to mean. */ |
| 78 |
99361556 |
| static unsigned long long zob_of(int piece, int pt) |
| 79 |
|
| { |
| 80 |
99361556 |
| zob_init(); |
| 81 |
99361556 |
▶ | if (piece <= 0 || piece > XQ_BORDER) return 0; |
Branch: 2 branches
| Branch | True | False | Total |
| if (piece <= 0 || piece > XQ_BORDER) return 0; |
99361556 |
0 |
99361556 |
| if (piece <= 0 || piece > XQ_BORDER) return 0; |
0 |
99361556 |
99361556 |
|
| 82 |
99361556 |
▶ | if (pt < 0 || pt >= XQ_CELLS) return 0; |
Branch: 2 branches
| Branch | True | False | Total |
| if (pt < 0 || pt >= XQ_CELLS) return 0; |
99361556 |
0 |
99361556 |
| if (pt < 0 || pt >= XQ_CELLS) return 0; |
0 |
99361556 |
99361556 |
|
| 83 |
99361556 |
| return ZOB[piece][pt]; |
| 84 |
|
| } |
| 85 |
|
| |
| 86 |
|
| /* ---- geometry -------------------------------------------------------------- */ |
| 87 |
|
| |
| 88 |
3 |
| static int xq_stride(void) { return XQ_STRIDE; } |
| 89 |
|
| |
| 90 |
1214634728 |
| static int xq_point_of(int file, int rank) |
| 91 |
|
| { |
| 92 |
1214634728 |
▶ | if (file < 0 || file >= XQ_FILES || rank < 0 || rank >= XQ_RANKS) return -1; |
Branch: 4 branches
| Branch | True | False | Total |
| if (file < 0 || file >= XQ_FILES || rank < 0 || rank >= XQ_RANKS) return -1; |
1214634728 |
0 |
1214634728 |
| if (file < 0 || file >= XQ_FILES || rank < 0 || rank >= XQ_RANKS) return -1; |
1214634728 |
0 |
1214634728 |
| if (file < 0 || file >= XQ_FILES || rank < 0 || rank >= XQ_RANKS) return -1; |
1214634728 |
0 |
1214634728 |
| if (file < 0 || file >= XQ_FILES || rank < 0 || rank >= XQ_RANKS) return -1; |
0 |
1214634728 |
1214634728 |
|
| 93 |
1214634728 |
| return (rank + 1) * XQ_STRIDE + (file + 1); |
| 94 |
|
| } |
| 95 |
|
| |
| 96 |
6176117009 |
| static int xq_on_board(int pt) |
| 97 |
|
| { |
| 98 |
|
| int f, r; |
| 99 |
6176117009 |
▶ | if (pt < 0 || pt >= XQ_CELLS) return 0; |
Branch: 2 branches
| Branch | True | False | Total |
| if (pt < 0 || pt >= XQ_CELLS) return 0; |
6068162518 |
107954491 |
6176117009 |
| if (pt < 0 || pt >= XQ_CELLS) return 0; |
121950655 |
5946211863 |
6068162518 |
|
| 100 |
5946211863 |
| f = pt % XQ_STRIDE; |
| 101 |
5946211863 |
| r = pt / XQ_STRIDE; |
| 102 |
5946211863 |
▶ | return f >= 1 && f <= XQ_FILES && r >= 1 && r <= XQ_RANKS; |
Branch: 4 branches
| Branch | True | False | Total |
| return f >= 1 && f <= XQ_FILES && r >= 1 && r <= XQ_RANKS; |
5646708501 |
299503362 |
5946211863 |
| return f >= 1 && f <= XQ_FILES && r >= 1 && r <= XQ_RANKS; |
5345275742 |
301432759 |
5646708501 |
| return f >= 1 && f <= XQ_FILES && r >= 1 && r <= XQ_RANKS; |
4978229154 |
367046588 |
5345275742 |
| return f >= 1 && f <= XQ_FILES && r >= 1 && r <= XQ_RANKS; |
4572452295 |
405776859 |
4978229154 |
|
| 103 |
|
| } |
| 104 |
|
| |
| 105 |
435238529 |
| static int xq_file_of(int pt) |
| 106 |
|
| { |
| 107 |
435238529 |
▶ | if (!xq_on_board(pt)) return -1; |
Branch: 1 branch
| Branch | True | False | Total |
| if (!xq_on_board(pt)) return -1; |
60601329 |
374637200 |
435238529 |
|
| 108 |
374637200 |
| return (pt % XQ_STRIDE) - 1; |
| 109 |
|
| } |
| 110 |
|
| |
| 111 |
367897274 |
| static int xq_rank_of(int pt) |
| 112 |
|
| { |
| 113 |
367897274 |
▶ | if (!xq_on_board(pt)) return -1; |
Branch: 1 branch
| Branch | True | False | Total |
| if (!xq_on_board(pt)) return -1; |
60601329 |
307295945 |
367897274 |
|
| 114 |
307295945 |
| return (pt / XQ_STRIDE) - 1; |
| 115 |
|
| } |
| 116 |
|
| |
| 117 |
|
| /* The palace is files d to f and the three ranks at that side's own end. Nine |
| 118 |
|
| * points each, and the general and the advisor never leave them. */ |
| 119 |
158208997 |
| static int xq_in_palace(int pt, int colour) |
| 120 |
|
| { |
| 121 |
158208997 |
| int f = xq_file_of(pt), r = xq_rank_of(pt); |
| 122 |
158208997 |
▶ | if (f < 3 || f > 5) return 0; |
Branch: 2 branches
| Branch | True | False | Total |
| if (f < 3 || f > 5) return 0; |
85711324 |
72497673 |
158208997 |
| if (f < 3 || f > 5) return 0; |
12806538 |
72904786 |
85711324 |
|
| 123 |
72904786 |
▶ | if (colour == XQ_RED) return r >= 0 && r <= 2; |
Branch: 3 branches
| Branch | True | False | Total |
| if (colour == XQ_RED) return r >= 0 && r <= 2; |
36933943 |
35970843 |
72904786 |
| if (colour == XQ_RED) return r >= 0 && r <= 2; |
36933943 |
0 |
36933943 |
| if (colour == XQ_RED) return r >= 0 && r <= 2; |
36857088 |
76855 |
36933943 |
|
| 124 |
35970843 |
▶ | if (colour == XQ_BLACK) return r >= 7 && r <= 9; |
Branch: 3 branches
| Branch | True | False | Total |
| if (colour == XQ_BLACK) return r >= 7 && r <= 9; |
35970843 |
0 |
35970843 |
| if (colour == XQ_BLACK) return r >= 7 && r <= 9; |
35795810 |
175033 |
35970843 |
| if (colour == XQ_BLACK) return r >= 7 && r <= 9; |
35795810 |
0 |
35795810 |
|
| 125 |
0 |
| return 0; |
| 126 |
|
| } |
| 127 |
|
| |
| 128 |
|
| /* Red advances up the ranks and Black down them, so "across the river" is rank |
| 129 |
|
| * 5 or more for Red and rank 4 or less for Black. Forty-five points each. */ |
| 130 |
207642190 |
| static int xq_crossed_river(int pt, int colour) |
| 131 |
|
| { |
| 132 |
207642190 |
| int r = xq_rank_of(pt); |
| 133 |
207642190 |
▶ | if (r < 0) return 0; |
Branch: 1 branch
| Branch | True | False | Total |
| if (r < 0) return 0; |
0 |
207642190 |
207642190 |
|
| 134 |
207642190 |
▶ | if (colour == XQ_RED) return r >= 5; |
Branch: 1 branch
| Branch | True | False | Total |
| if (colour == XQ_RED) return r >= 5; |
101231117 |
106411073 |
207642190 |
|
| 135 |
106411073 |
▶ | if (colour == XQ_BLACK) return r <= 4; |
Branch: 1 branch
| Branch | True | False | Total |
| if (colour == XQ_BLACK) return r <= 4; |
106411073 |
0 |
106411073 |
|
| 136 |
0 |
| return 0; |
| 137 |
|
| } |
| 138 |
|
| |
| 139 |
|
| /* ---- the board ------------------------------------------------------------- */ |
| 140 |
|
| |
| 141 |
403 |
| static void board_blank(struct xq_board *b) |
| 142 |
|
| { |
| 143 |
|
| int f, r; |
| 144 |
403 |
| memset(b, 0, sizeof(*b)); |
| 145 |
403 |
| memset(b->cell, XQ_BORDER, sizeof(b->cell)); |
| 146 |
4433 |
▶ | for (r = 0; r < XQ_RANKS; r++) |
Branch: 1 branch
| Branch | True | False | Total |
| for (r = 0; r < XQ_RANKS; r++) |
4030 |
403 |
4433 |
|
| 147 |
40300 |
▶ | for (f = 0; f < XQ_FILES; f++) |
Branch: 1 branch
| Branch | True | False | Total |
| for (f = 0; f < XQ_FILES; f++) |
36270 |
4030 |
40300 |
|
| 148 |
36270 |
| b->cell[xq_point_of(f, r)] = XQ_EMPTY; |
| 149 |
403 |
| b->side = XQ_RED; |
| 150 |
403 |
| b->key = 0; |
| 151 |
403 |
| } |
| 152 |
|
| |
| 153 |
403 |
| static struct xq_board *xq_board_empty(void) |
| 154 |
|
| { |
| 155 |
|
| struct xq_board *b; |
| 156 |
403 |
| zob_init(); |
| 157 |
403 |
| b = (struct xq_board *) malloc(sizeof(struct xq_board)); |
| 158 |
403 |
▶ | if (!b) return NULL; |
Branch: 1 branch
| Branch | True | False | Total |
| if (!b) return NULL; |
0 |
403 |
403 |
|
| 159 |
403 |
| board_blank(b); |
| 160 |
403 |
| return b; |
| 161 |
|
| } |
| 162 |
|
| |
| 163 |
|
| /* put and lift MAINTAIN THE KEY and judge nothing else. A caller may stack |
| 164 |
|
| * three generals on three points or leave a side without one; that is what the |
| 165 |
|
| * structure primitives are for and it is how a test builds a position. */ |
| 166 |
94517704 |
| static void xq_put(struct xq_board *b, int pt, int piece) |
| 167 |
|
| { |
| 168 |
|
| int old; |
| 169 |
94517704 |
▶ | if (!xq_on_board(pt)) return; |
Branch: 1 branch
| Branch | True | False | Total |
| if (!xq_on_board(pt)) return; |
0 |
94517704 |
94517704 |
|
| 170 |
94517704 |
| old = b->cell[pt]; |
| 171 |
94517704 |
▶ | if (old != XQ_EMPTY) b->key ^= zob_of(old, pt); |
Branch: 1 branch
| Branch | True | False | Total |
| if (old != XQ_EMPTY) b->key ^= zob_of(old, pt); |
52098480 |
42419224 |
94517704 |
|
| 172 |
94517704 |
| b->cell[pt] = (unsigned char) piece; |
| 173 |
94517704 |
▶ | if (piece != XQ_EMPTY) b->key ^= zob_of(piece, pt); |
Branch: 1 branch
| Branch | True | False | Total |
| if (piece != XQ_EMPTY) b->key ^= zob_of(piece, pt); |
47263070 |
47254634 |
94517704 |
|
| 174 |
|
| } |
| 175 |
|
| |
| 176 |
47250810 |
| static void xq_lift(struct xq_board *b, int pt) |
| 177 |
|
| { |
| 178 |
47250810 |
| xq_put(b, pt, XQ_EMPTY); |
| 179 |
47250810 |
| } |
| 180 |
|
| |
| 181 |
5283734219 |
| static int xq_at(const struct xq_board *b, int pt) |
| 182 |
|
| { |
| 183 |
5283734219 |
▶ | if (pt < 0 || pt >= XQ_CELLS) return XQ_BORDER; |
Branch: 2 branches
| Branch | True | False | Total |
| if (pt < 0 || pt >= XQ_CELLS) return XQ_BORDER; |
5283734219 |
0 |
5283734219 |
| if (pt < 0 || pt >= XQ_CELLS) return XQ_BORDER; |
0 |
5283734219 |
5283734219 |
|
| 184 |
5283734219 |
| return b->cell[pt]; |
| 185 |
|
| } |
| 186 |
|
| |
| 187 |
32729627 |
| static int xq_side(const struct xq_board *b) { return b->side; } |
| 188 |
|
| |
| 189 |
62140973 |
| static void xq_set_side(struct xq_board *b, int colour) |
| 190 |
|
| { |
| 191 |
62140973 |
▶ | if (colour != XQ_RED && colour != XQ_BLACK) return; |
Branch: 2 branches
| Branch | True | False | Total |
| if (colour != XQ_RED && colour != XQ_BLACK) return; |
16424890 |
45716083 |
62140973 |
| if (colour != XQ_RED && colour != XQ_BLACK) return; |
0 |
16424890 |
16424890 |
|
| 192 |
62140973 |
▶ | if (b->side == colour) return; |
Branch: 1 branch
| Branch | True | False | Total |
| if (b->side == colour) return; |
4957187 |
57183786 |
62140973 |
|
| 193 |
57183786 |
| b->side = colour; |
| 194 |
57183786 |
| b->key ^= ZOB_SIDE; |
| 195 |
|
| } |
| 196 |
|
| |
| 197 |
6 |
| static int xq_count(const struct xq_board *b, int piece) |
| 198 |
|
| { |
| 199 |
6 |
| int pt, n = 0; |
| 200 |
798 |
▶ | for (pt = 0; pt < XQ_CELLS; pt++) |
Branch: 1 branch
| Branch | True | False | Total |
| for (pt = 0; pt < XQ_CELLS; pt++) |
792 |
6 |
798 |
|
| 201 |
792 |
▶ | if (b->cell[pt] == piece && xq_on_board(pt)) n++; |
Branch: 2 branches
| Branch | True | False | Total |
| if (b->cell[pt] == piece && xq_on_board(pt)) n++; |
13 |
779 |
792 |
| if (b->cell[pt] == piece && xq_on_board(pt)) n++; |
13 |
0 |
13 |
|
| 202 |
6 |
| return n; |
| 203 |
|
| } |
| 204 |
|
| |
| 205 |
206995808 |
| static int xq_find(const struct xq_board *b, int piece) |
| 206 |
|
| { |
| 207 |
|
| int pt; |
| 208 |
13930036939 |
▶ | for (pt = 0; pt < XQ_CELLS; pt++) |
Branch: 1 branch
| Branch | True | False | Total |
| for (pt = 0; pt < XQ_CELLS; pt++) |
13930031100 |
5839 |
13930036939 |
|
| 209 |
13930031100 |
▶ | if (b->cell[pt] == piece && xq_on_board(pt)) return pt; |
Branch: 2 branches
| Branch | True | False | Total |
| if (b->cell[pt] == piece && xq_on_board(pt)) return pt; |
206989969 |
13723041131 |
13930031100 |
| if (b->cell[pt] == piece && xq_on_board(pt)) return pt; |
206989969 |
0 |
206989969 |
|
| 210 |
5839 |
| return 0; |
| 211 |
|
| } |
| 212 |
|
| |
| 213 |
|
| /* The opening position, from the Asian Rules chapter 1 section 1. Rank 0 is |
| 214 |
|
| * Red's back rank. */ |
| 215 |
|
| static const int BACK[XQ_FILES] = { |
| 216 |
|
| XQ_CHARIOT, XQ_HORSE, XQ_ELEPHANT, XQ_ADVISOR, XQ_GENERAL, |
| 217 |
|
| XQ_ADVISOR, XQ_ELEPHANT, XQ_HORSE, XQ_CHARIOT |
| 218 |
|
| }; |
| 219 |
|
| |
| 220 |
184 |
| static struct xq_board *xq_board_new(void) |
| 221 |
|
| { |
| 222 |
184 |
| struct xq_board *b = xq_board_empty(); |
| 223 |
|
| int f; |
| 224 |
184 |
▶ | if (!b) return NULL; |
Branch: 1 branch
| Branch | True | False | Total |
| if (!b) return NULL; |
0 |
184 |
184 |
|
| 225 |
1840 |
▶ | for (f = 0; f < XQ_FILES; f++) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (f = 0; f < XQ_FILES; f++) { |
1656 |
184 |
1840 |
|
| 226 |
1656 |
| xq_put(b, xq_point_of(f, 0), (int) (XQ_RED | BACK[f])); |
| 227 |
1656 |
| xq_put(b, xq_point_of(f, 9), (int) (XQ_BLACK | BACK[f])); |
| 228 |
|
| } |
| 229 |
184 |
| xq_put(b, xq_point_of(1, 2), XQ_RED | XQ_CANNON); |
| 230 |
184 |
| xq_put(b, xq_point_of(7, 2), XQ_RED | XQ_CANNON); |
| 231 |
184 |
| xq_put(b, xq_point_of(1, 7), XQ_BLACK | XQ_CANNON); |
| 232 |
184 |
| xq_put(b, xq_point_of(7, 7), XQ_BLACK | XQ_CANNON); |
| 233 |
1104 |
▶ | for (f = 0; f < XQ_FILES; f += 2) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (f = 0; f < XQ_FILES; f += 2) { |
920 |
184 |
1104 |
|
| 234 |
920 |
| xq_put(b, xq_point_of(f, 3), XQ_RED | XQ_SOLDIER); |
| 235 |
920 |
| xq_put(b, xq_point_of(f, 6), XQ_BLACK | XQ_SOLDIER); |
| 236 |
|
| } |
| 237 |
184 |
| return b; |
| 238 |
|
| } |
| 239 |
|
| |
| 240 |
441 |
| static struct xq_board *xq_board_copy(const struct xq_board *b) |
| 241 |
|
| { |
| 242 |
441 |
| struct xq_board *n = (struct xq_board *) malloc(sizeof(struct xq_board)); |
| 243 |
441 |
▶ | if (!n) return NULL; |
Branch: 1 branch
| Branch | True | False | Total |
| if (!n) return NULL; |
0 |
441 |
441 |
|
| 244 |
441 |
| *n = *b; |
| 245 |
441 |
| return n; |
| 246 |
|
| } |
| 247 |
|
| |
| 248 |
844 |
| static void xq_board_drop(struct xq_board *b) { free(b); } |
| 249 |
|
| |
| 250 |
|
| /* ---- moves ------------------------------------------------------------------ |
| 251 |
|
| * |
| 252 |
|
| * from and to each fit in eight bits (a point is 0 to 131), so a move is packed |
| 253 |
|
| * into sixteen and the upper bits are left for the flags phases 03 and beyond |
| 254 |
|
| * will want. Nothing outside the header unpacks one by hand. |
| 255 |
|
| */ |
| 256 |
|
| |
| 257 |
494180984 |
| static int xq_move_make(int from, int to) { return (from & 0xFF) | ((to & 0xFF) << 8); } |
| 258 |
193606487 |
| static int xq_move_from(int mv) { return mv & 0xFF; } |
| 259 |
246101851 |
| static int xq_move_to(int mv) { return (mv >> 8) & 0xFF; } |
| 260 |
|
| |
| 261 |
|
| /* NOT A RULES CALL. It moves whatever is on `from` to `to`, captures whatever |
| 262 |
|
| * was there, flips the side and maintains the key. Whether the move was legal |
| 263 |
|
| * is phase 03's question and this function never asks it. */ |
| 264 |
47246553 |
| static int xq_do_move(struct xq_board *b, int mv, struct xq_undo *u) |
| 265 |
|
| { |
| 266 |
47246553 |
| int from = xq_move_from(mv), to = xq_move_to(mv); |
| 267 |
|
| int piece, captured; |
| 268 |
|
| |
| 269 |
47246553 |
▶ | if (!xq_on_board(from) || !xq_on_board(to)) { |
Branch: 2 branches
| Branch | True | False | Total |
| if (!xq_on_board(from) || !xq_on_board(to)) { |
47246553 |
0 |
47246553 |
| if (!xq_on_board(from) || !xq_on_board(to)) { |
0 |
47246553 |
47246553 |
|
| 270 |
0 |
▶ | if (u) { u->mv = 0; u->captured = XQ_EMPTY; u->side = b->side; u->key = b->key; } |
Branch: 1 branch
| Branch | True | False | Total |
| if (u) { u->mv = 0; u->captured = XQ_EMPTY; u->side = b->side; u->key = b->key; } |
0 |
0 |
0 |
|
| 271 |
0 |
| return XQ_EMPTY; |
| 272 |
|
| } |
| 273 |
47246553 |
| piece = b->cell[from]; |
| 274 |
47246553 |
| captured = b->cell[to]; |
| 275 |
|
| |
| 276 |
47246553 |
▶ | if (u) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (u) { |
47246553 |
0 |
47246553 |
|
| 277 |
47246553 |
| u->mv = mv; |
| 278 |
47246553 |
| u->captured = captured; |
| 279 |
47246553 |
| u->side = b->side; |
| 280 |
47246553 |
| u->key = b->key; |
| 281 |
|
| } |
| 282 |
47246553 |
| xq_lift(b, from); |
| 283 |
47246553 |
| xq_put(b, to, piece); |
| 284 |
47246553 |
▶ | xq_set_side(b, XQ_OTHER(b->side)); |
Branch: 1 branch
| Branch | True | False | Total |
| xq_set_side(b, XQ_OTHER(b->side)); |
9253707 |
37992846 |
47246553 |
|
| 285 |
47246553 |
| return captured; |
| 286 |
|
| } |
| 287 |
|
| |
| 288 |
|
| /* Restores the position EXACTLY, key included, by putting the key back rather |
| 289 |
|
| * than by xor-ing the same values again. The two are equal when nothing else |
| 290 |
|
| * touched the board, and only one of them stays true if anything did. */ |
| 291 |
47242782 |
| static void xq_undo_move(struct xq_board *b, const struct xq_undo *u) |
| 292 |
|
| { |
| 293 |
|
| int from, to; |
| 294 |
47242782 |
▶ | if (!u || u->mv == 0) return; |
Branch: 2 branches
| Branch | True | False | Total |
| if (!u || u->mv == 0) return; |
47242782 |
0 |
47242782 |
| if (!u || u->mv == 0) return; |
0 |
47242782 |
47242782 |
|
| 295 |
47242782 |
| from = xq_move_from(u->mv); |
| 296 |
47242782 |
| to = xq_move_to(u->mv); |
| 297 |
47242782 |
| b->cell[from] = b->cell[to]; |
| 298 |
47242782 |
| b->cell[to] = (unsigned char) u->captured; |
| 299 |
47242782 |
| b->side = u->side; |
| 300 |
47242782 |
| b->key = u->key; |
| 301 |
|
| } |
| 302 |
|
| |
| 303 |
2808765 |
| static unsigned long long xq_key(const struct xq_board *b) { return b->key; } |
| 304 |
|
| |
| 305 |
|
| /* ---- FEN -------------------------------------------------------------------- |
| 306 |
|
| * |
| 307 |
|
| * THE READER TAKES BOTH LETTER CONVENTIONS AND THE WRITER EMITS h/e. |
| 308 |
|
| * |
| 309 |
|
| * The same opening position is published both ways by the same author: the |
| 310 |
|
| * Chess Programming Wiki's Chinese Chess perft page spells the horse h and the |
| 311 |
|
| * elephant e, and Maksim Korzh's TalkChess post of the same table spells them n |
| 312 |
|
| * and b after chess's knight and bishop. A reader that takes one convention |
| 313 |
|
| * cannot load half the oracles there are, and the failure is the bad kind: the |
| 314 |
|
| * position does not parse, the test skips, and the suite is green. |
| 315 |
|
| */ |
| 316 |
|
| |
| 317 |
1131 |
| static int letter_piece(char c) |
| 318 |
|
| { |
| 319 |
1131 |
▶ | int colour = (c >= 'a' && c <= 'z') ? XQ_BLACK : XQ_RED; |
Branch: 2 branches
| Branch | True | False | Total |
| int colour = (c >= 'a' && c <= 'z') ? XQ_BLACK : XQ_RED; |
584 |
547 |
1131 |
| int colour = (c >= 'a' && c <= 'z') ? XQ_BLACK : XQ_RED; |
584 |
0 |
584 |
|
| 320 |
1131 |
▶ | char u = (c >= 'a' && c <= 'z') ? (char) (c - 'a' + 'A') : c; |
Branch: 2 branches
| Branch | True | False | Total |
| char u = (c >= 'a' && c <= 'z') ? (char) (c - 'a' + 'A') : c; |
584 |
547 |
1131 |
| char u = (c >= 'a' && c <= 'z') ? (char) (c - 'a' + 'A') : c; |
584 |
0 |
584 |
|
| 321 |
1131 |
| switch (u) { |
| 322 |
120 |
| case 'K': return colour | XQ_GENERAL; |
| 323 |
166 |
| case 'A': return colour | XQ_ADVISOR; |
| 324 |
148 |
| case 'E': case 'B': return colour | XQ_ELEPHANT; |
| 325 |
139 |
| case 'R': return colour | XQ_CHARIOT; |
| 326 |
143 |
| case 'H': case 'N': return colour | XQ_HORSE; |
| 327 |
137 |
| case 'C': return colour | XQ_CANNON; |
| 328 |
273 |
| case 'P': return colour | XQ_SOLDIER; |
| 329 |
5 |
| default: return -1; |
| 330 |
|
| } |
| 331 |
|
| } |
| 332 |
|
| |
| 333 |
1096 |
| static char piece_letter(int piece) |
| 334 |
|
| { |
| 335 |
|
| static const char up[8] = { '.', 'K', 'A', 'E', 'R', 'H', 'C', 'P' }; |
| 336 |
1096 |
| char c = up[XQ_KIND(piece)]; |
| 337 |
1096 |
▶ | if (XQ_COLOUR(piece) == XQ_BLACK) c = (char) (c - 'A' + 'a'); |
Branch: 1 branch
| Branch | True | False | Total |
| if (XQ_COLOUR(piece) == XQ_BLACK) c = (char) (c - 'A' + 'a'); |
542 |
554 |
1096 |
|
| 338 |
1096 |
| return c; |
| 339 |
|
| } |
| 340 |
|
| |
| 341 |
69 |
| static struct xq_board *xq_board_of_fen(const char *fen, int *err) |
| 342 |
|
| { |
| 343 |
|
| struct xq_board *b; |
| 344 |
69 |
| int rank = XQ_RANKS - 1, file = 0; |
| 345 |
69 |
| const char *s = fen; |
| 346 |
|
| size_t n; |
| 347 |
|
| |
| 348 |
69 |
▶ | if (err) *err = XQ_OK; |
Branch: 1 branch
| Branch | True | False | Total |
| if (err) *err = XQ_OK; |
69 |
0 |
69 |
|
| 349 |
69 |
▶ | if (!fen) { if (err) *err = XQ_FEN_NULL; return NULL; } |
Branch: 2 branches
| Branch | True | False | Total |
| if (!fen) { if (err) *err = XQ_FEN_NULL; return NULL; } |
0 |
69 |
69 |
| if (!fen) { if (err) *err = XQ_FEN_NULL; return NULL; } |
0 |
0 |
0 |
|
| 350 |
69 |
| n = strlen(fen); |
| 351 |
69 |
▶ | if (n == 0) { if (err) *err = XQ_FEN_NULL; return NULL; } |
Branch: 2 branches
| Branch | True | False | Total |
| if (n == 0) { if (err) *err = XQ_FEN_NULL; return NULL; } |
1 |
68 |
69 |
| if (n == 0) { if (err) *err = XQ_FEN_NULL; return NULL; } |
1 |
0 |
1 |
|
| 352 |
68 |
▶ | if (n >= XQ_FEN_MAX) { if (err) *err = XQ_FEN_LONG; return NULL; } |
Branch: 2 branches
| Branch | True | False | Total |
| if (n >= XQ_FEN_MAX) { if (err) *err = XQ_FEN_LONG; return NULL; } |
1 |
67 |
68 |
| if (n >= XQ_FEN_MAX) { if (err) *err = XQ_FEN_LONG; return NULL; } |
1 |
0 |
1 |
|
| 353 |
|
| |
| 354 |
67 |
| b = xq_board_empty(); |
| 355 |
67 |
▶ | if (!b) { if (err) *err = XQ_FEN_NULL; return NULL; } |
Branch: 2 branches
| Branch | True | False | Total |
| if (!b) { if (err) *err = XQ_FEN_NULL; return NULL; } |
0 |
67 |
67 |
| if (!b) { if (err) *err = XQ_FEN_NULL; return NULL; } |
0 |
0 |
0 |
|
| 356 |
|
| |
| 357 |
2767 |
▶ | for (; *s && *s != ' '; s++) { |
Branch: 2 branches
| Branch | True | False | Total |
| for (; *s && *s != ' '; s++) { |
2764 |
3 |
2767 |
| for (; *s && *s != ' '; s++) { |
2708 |
56 |
2764 |
|
| 358 |
2708 |
▶ | if (*s == '/') { |
Branch: 1 branch
| Branch | True | False | Total |
| if (*s == '/') { |
534 |
2174 |
2708 |
|
| 359 |
534 |
▶ | if (file != XQ_FILES) { if (err) *err = XQ_FEN_WIDTH; xq_board_drop(b); return NULL; } |
Branch: 2 branches
| Branch | True | False | Total |
| if (file != XQ_FILES) { if (err) *err = XQ_FEN_WIDTH; xq_board_drop(b); return NULL; } |
1 |
533 |
534 |
| if (file != XQ_FILES) { if (err) *err = XQ_FEN_WIDTH; xq_board_drop(b); return NULL; } |
1 |
0 |
1 |
|
| 360 |
533 |
▶ | if (rank == 0) { if (err) *err = XQ_FEN_ROWS; xq_board_drop(b); return NULL; } |
Branch: 2 branches
| Branch | True | False | Total |
| if (rank == 0) { if (err) *err = XQ_FEN_ROWS; xq_board_drop(b); return NULL; } |
1 |
532 |
533 |
| if (rank == 0) { if (err) *err = XQ_FEN_ROWS; xq_board_drop(b); return NULL; } |
1 |
0 |
1 |
|
| 361 |
532 |
| rank--; file = 0; |
| 362 |
532 |
| continue; |
| 363 |
|
| } |
| 364 |
2174 |
▶ | if (*s >= '1' && *s <= '9') { |
Branch: 2 branches
| Branch | True | False | Total |
| if (*s >= '1' && *s <= '9') { |
2174 |
0 |
2174 |
| if (*s >= '1' && *s <= '9') { |
1043 |
1131 |
2174 |
|
| 365 |
1043 |
| file += *s - '0'; |
| 366 |
1043 |
▶ | if (file > XQ_FILES) { if (err) *err = XQ_FEN_WIDTH; xq_board_drop(b); return NULL; } |
Branch: 2 branches
| Branch | True | False | Total |
| if (file > XQ_FILES) { if (err) *err = XQ_FEN_WIDTH; xq_board_drop(b); return NULL; } |
0 |
1043 |
1043 |
| if (file > XQ_FILES) { if (err) *err = XQ_FEN_WIDTH; xq_board_drop(b); return NULL; } |
0 |
0 |
0 |
|
| 367 |
1043 |
| continue; |
| 368 |
|
| } |
| 369 |
|
| { |
| 370 |
1131 |
| int piece = letter_piece(*s); |
| 371 |
1131 |
▶ | if (piece < 0) { if (err) *err = XQ_FEN_LETTER; xq_board_drop(b); return NULL; } |
Branch: 2 branches
| Branch | True | False | Total |
| if (piece < 0) { if (err) *err = XQ_FEN_LETTER; xq_board_drop(b); return NULL; } |
5 |
1126 |
1131 |
| if (piece < 0) { if (err) *err = XQ_FEN_LETTER; xq_board_drop(b); return NULL; } |
5 |
0 |
5 |
|
| 372 |
1126 |
▶ | if (file >= XQ_FILES) { if (err) *err = XQ_FEN_WIDTH; xq_board_drop(b); return NULL; } |
Branch: 2 branches
| Branch | True | False | Total |
| if (file >= XQ_FILES) { if (err) *err = XQ_FEN_WIDTH; xq_board_drop(b); return NULL; } |
1 |
1125 |
1126 |
| if (file >= XQ_FILES) { if (err) *err = XQ_FEN_WIDTH; xq_board_drop(b); return NULL; } |
1 |
0 |
1 |
|
| 373 |
1125 |
| xq_put(b, xq_point_of(file, rank), piece); |
| 374 |
1125 |
| file++; |
| 375 |
|
| } |
| 376 |
|
| } |
| 377 |
59 |
▶ | if (rank != 0 || file != XQ_FILES) { |
Branch: 2 branches
| Branch | True | False | Total |
| if (rank != 0 || file != XQ_FILES) { |
57 |
2 |
59 |
| if (rank != 0 || file != XQ_FILES) { |
0 |
57 |
57 |
|
| 378 |
2 |
▶ | if (err) *err = (rank != 0) ? XQ_FEN_ROWS : XQ_FEN_WIDTH; |
Branch: 2 branches
| Branch | True | False | Total |
| if (err) *err = (rank != 0) ? XQ_FEN_ROWS : XQ_FEN_WIDTH; |
2 |
0 |
2 |
| if (err) *err = (rank != 0) ? XQ_FEN_ROWS : XQ_FEN_WIDTH; |
2 |
0 |
2 |
|
| 379 |
2 |
| xq_board_drop(b); |
| 380 |
2 |
| return NULL; |
| 381 |
|
| } |
| 382 |
|
| |
| 383 |
|
| /* the side field. w and r both mean Red: the perft sources write w, and |
| 384 |
|
| * much of the xiangqi world writes r. Anything else is a refusal rather |
| 385 |
|
| * than a silent default, because defaulting here would make a typo into a |
| 386 |
|
| * position with the wrong player to move, which is a different position. */ |
| 387 |
113 |
▶ | while (*s == ' ') s++; |
Branch: 1 branch
| Branch | True | False | Total |
| while (*s == ' ') s++; |
56 |
57 |
113 |
|
| 388 |
57 |
▶ | if (*s) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (*s) { |
56 |
1 |
57 |
|
| 389 |
56 |
▶ | if (*s == 'w' || *s == 'W' || *s == 'r' || *s == 'R') xq_set_side(b, XQ_RED); |
Branch: 4 branches
| Branch | True | False | Total |
| if (*s == 'w' || *s == 'W' || *s == 'r' || *s == 'R') xq_set_side(b, XQ_RED); |
12 |
44 |
56 |
| if (*s == 'w' || *s == 'W' || *s == 'r' || *s == 'R') xq_set_side(b, XQ_RED); |
12 |
0 |
12 |
| if (*s == 'w' || *s == 'W' || *s == 'r' || *s == 'R') xq_set_side(b, XQ_RED); |
11 |
1 |
12 |
| if (*s == 'w' || *s == 'W' || *s == 'r' || *s == 'R') xq_set_side(b, XQ_RED); |
0 |
11 |
11 |
|
| 390 |
11 |
▶ | else if (*s == 'b' || *s == 'B') xq_set_side(b, XQ_BLACK); |
Branch: 2 branches
| Branch | True | False | Total |
| else if (*s == 'b' || *s == 'B') xq_set_side(b, XQ_BLACK); |
1 |
10 |
11 |
| else if (*s == 'b' || *s == 'B') xq_set_side(b, XQ_BLACK); |
0 |
1 |
1 |
|
| 391 |
1 |
▶ | else { if (err) *err = XQ_FEN_SIDE; xq_board_drop(b); return NULL; } |
Branch: 1 branch
| Branch | True | False | Total |
| else { if (err) *err = XQ_FEN_SIDE; xq_board_drop(b); return NULL; } |
1 |
0 |
1 |
|
| 392 |
|
| } |
| 393 |
|
| /* every field after the side is ignored: this game has no castling, no en |
| 394 |
|
| * passant, and the two clocks are the caller's business */ |
| 395 |
56 |
| return b; |
| 396 |
|
| } |
| 397 |
|
| |
| 398 |
39 |
| static int xq_to_fen(const struct xq_board *b, char *buf, int len) |
| 399 |
|
| { |
| 400 |
39 |
| int rank, file, i = 0, run; |
| 401 |
39 |
▶ | if (!buf || len < XQ_FEN_MAX) return -1; |
Branch: 2 branches
| Branch | True | False | Total |
| if (!buf || len < XQ_FEN_MAX) return -1; |
39 |
0 |
39 |
| if (!buf || len < XQ_FEN_MAX) return -1; |
0 |
39 |
39 |
|
| 402 |
429 |
▶ | for (rank = XQ_RANKS - 1; rank >= 0; rank--) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (rank = XQ_RANKS - 1; rank >= 0; rank--) { |
390 |
39 |
429 |
|
| 403 |
390 |
| run = 0; |
| 404 |
3900 |
▶ | for (file = 0; file < XQ_FILES; file++) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (file = 0; file < XQ_FILES; file++) { |
3510 |
390 |
3900 |
|
| 405 |
3510 |
| int piece = b->cell[xq_point_of(file, rank)]; |
| 406 |
3510 |
▶ | if (piece == XQ_EMPTY) { run++; continue; } |
Branch: 1 branch
| Branch | True | False | Total |
| if (piece == XQ_EMPTY) { run++; continue; } |
2414 |
1096 |
3510 |
|
| 407 |
1096 |
▶ | if (run) { buf[i++] = (char) ('0' + run); run = 0; } |
Branch: 1 branch
| Branch | True | False | Total |
| if (run) { buf[i++] = (char) ('0' + run); run = 0; } |
446 |
650 |
1096 |
|
| 408 |
1096 |
| buf[i++] = piece_letter(piece); |
| 409 |
|
| } |
| 410 |
390 |
▶ | if (run) buf[i++] = (char) ('0' + run); |
Branch: 1 branch
| Branch | True | False | Total |
| if (run) buf[i++] = (char) ('0' + run); |
268 |
122 |
390 |
|
| 411 |
390 |
▶ | if (rank) buf[i++] = '/'; |
Branch: 1 branch
| Branch | True | False | Total |
| if (rank) buf[i++] = '/'; |
351 |
39 |
390 |
|
| 412 |
|
| } |
| 413 |
39 |
| buf[i++] = ' '; |
| 414 |
39 |
▶ | buf[i++] = (b->side == XQ_BLACK) ? 'b' : 'w'; |
Branch: 1 branch
| Branch | True | False | Total |
| buf[i++] = (b->side == XQ_BLACK) ? 'b' : 'w'; |
8 |
31 |
39 |
|
| 415 |
39 |
| buf[i++] = ' '; buf[i++] = '-'; |
| 416 |
39 |
| buf[i++] = ' '; buf[i++] = '-'; |
| 417 |
39 |
| buf[i++] = ' '; buf[i++] = '0'; |
| 418 |
39 |
| buf[i++] = ' '; buf[i++] = '1'; |
| 419 |
39 |
| buf[i] = '\0'; |
| 420 |
39 |
| return i; |
| 421 |
|
| } |
| 422 |
|
| |
| 423 |
|
| /* ---- the table -------------------------------------------------------------- */ |
| 424 |
|
| |
| 425 |
|
| static struct xq_abi XQ_TABLE; |
| 426 |
|
| static int XQ_TABLE_READY = 0; |
| 427 |
|
| |
| 428 |
|
| /* Phase 03 lives in xq_moves.c and installs itself into the table here. |
| 429 |
|
| * |
| 430 |
|
| * The two files call into each other and it terminates: xq_abi_table sets |
| 431 |
|
| * XQ_TABLE_READY before calling the installer, and xq_moves.c only ever reaches |
| 432 |
|
| * xq_abi_table from inside a function the installer has already been handed. |
| 433 |
|
| * Game::Go's search does the same dance and its comment says the same thing. */ |
| 434 |
|
| void xq_moves_install(struct xq_abi *t); |
| 435 |
|
| void xq_mate_install(struct xq_abi *t); |
| 436 |
|
| void xq_judge_install(struct xq_abi *t); |
| 437 |
|
| void xq_judge2_install(struct xq_abi *t); |
| 438 |
|
| void xq_search_install(struct xq_abi *t); |
| 439 |
|
| |
| 440 |
13375993954 |
| const struct xq_abi *xq_abi_table(void) |
| 441 |
|
| { |
| 442 |
13375993954 |
▶ | if (!XQ_TABLE_READY) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (!XQ_TABLE_READY) { |
24 |
13375993930 |
13375993954 |
|
| 443 |
24 |
| zob_init(); |
| 444 |
24 |
| XQ_TABLE.abi_version = XQ_ABI_VERSION; |
| 445 |
|
| |
| 446 |
24 |
| XQ_TABLE.board_new = xq_board_new; |
| 447 |
24 |
| XQ_TABLE.board_empty = xq_board_empty; |
| 448 |
24 |
| XQ_TABLE.board_of_fen = xq_board_of_fen; |
| 449 |
24 |
| XQ_TABLE.board_copy = xq_board_copy; |
| 450 |
24 |
| XQ_TABLE.board_drop = xq_board_drop; |
| 451 |
|
| |
| 452 |
24 |
| XQ_TABLE.at = xq_at; |
| 453 |
24 |
| XQ_TABLE.put = xq_put; |
| 454 |
24 |
| XQ_TABLE.lift = xq_lift; |
| 455 |
24 |
| XQ_TABLE.side = xq_side; |
| 456 |
24 |
| XQ_TABLE.set_side = xq_set_side; |
| 457 |
24 |
| XQ_TABLE.count = xq_count; |
| 458 |
24 |
| XQ_TABLE.find = xq_find; |
| 459 |
|
| |
| 460 |
24 |
| XQ_TABLE.move_make = xq_move_make; |
| 461 |
24 |
| XQ_TABLE.move_from = xq_move_from; |
| 462 |
24 |
| XQ_TABLE.move_to = xq_move_to; |
| 463 |
24 |
| XQ_TABLE.do_move = xq_do_move; |
| 464 |
24 |
| XQ_TABLE.undo_move = xq_undo_move; |
| 465 |
|
| |
| 466 |
24 |
| XQ_TABLE.key = xq_key; |
| 467 |
24 |
| XQ_TABLE.to_fen = xq_to_fen; |
| 468 |
24 |
| XQ_TABLE.zobrist = zob_of; |
| 469 |
|
| |
| 470 |
24 |
| XQ_TABLE.point_of = xq_point_of; |
| 471 |
24 |
| XQ_TABLE.file_of = xq_file_of; |
| 472 |
24 |
| XQ_TABLE.rank_of = xq_rank_of; |
| 473 |
24 |
| XQ_TABLE.on_board = xq_on_board; |
| 474 |
24 |
| XQ_TABLE.in_palace = xq_in_palace; |
| 475 |
24 |
| XQ_TABLE.crossed_river = xq_crossed_river; |
| 476 |
24 |
| XQ_TABLE.stride = xq_stride; |
| 477 |
|
| |
| 478 |
24 |
| XQ_TABLE_READY = 1; /* before the installer, or it recurses */ |
| 479 |
24 |
| xq_moves_install(&XQ_TABLE); |
| 480 |
24 |
| xq_mate_install(&XQ_TABLE); |
| 481 |
24 |
| xq_judge_install(&XQ_TABLE); |
| 482 |
24 |
| xq_judge2_install(&XQ_TABLE); |
| 483 |
24 |
| xq_search_install(&XQ_TABLE); |
| 484 |
|
| } |
| 485 |
13375993954 |
| return &XQ_TABLE; |
| 486 |
|
| } |