| 1 |
|
| /* bd_search.c - choosing a move: an evaluation, and a search bounded in nodes. |
| 2 |
|
| * |
| 3 |
|
| * PERL-FREE, as the other bd_*.c files are. |
| 4 |
|
| * |
| 5 |
|
| * INTEGER ONLY. A score is an int and nothing here is a float, so the same |
| 6 |
|
| * position, budget and seed give the same move on every machine and every |
| 7 |
|
| * compiler. |
| 8 |
|
| * |
| 9 |
|
| * THE SEARCH NEVER READS A CLOCK. Its budget is a count of nodes, asked about |
| 10 |
|
| * every 1,024 of them, and the move it returns is the best move of the last |
| 11 |
|
| * iteration that FINISHED. A loaded machine therefore plays the move an idle |
| 12 |
|
| * one plays, and a game against it can be played again. |
| 13 |
|
| * |
| 14 |
|
| * THE SEARCH KNOWS HOW A GAME ENDS. It plays its moves into a copy of the game, |
| 15 |
|
| * so a line that repeats a position for the last time the rule set allows, or |
| 16 |
|
| * runs into the ply cap, is scored as the draw it is. A search that did not |
| 17 |
|
| * would walk into drawn positions believing it was winning them. |
| 18 |
|
| * |
| 19 |
|
| * It is a plain negamax with alpha-beta, deepened one ply at a time, with a |
| 20 |
|
| * table of positions already searched and the previous iteration's best move |
| 21 |
|
| * tried first. Nothing here is clever, and the reason is the use it is put to: |
| 22 |
|
| * the second thing this file is for, after choosing a move, is measuring |
| 23 |
|
| * whether the two sides of this game win about as often as each other. |
| 24 |
|
| */ |
| 25 |
|
| |
| 26 |
|
| #include <stdlib.h> |
| 27 |
|
| #include <string.h> |
| 28 |
|
| #include "bd_abi.h" |
| 29 |
|
| |
| 30 |
|
| static const struct bd_abi *T = NULL; |
| 31 |
|
| |
| 32 |
|
| /* ---- the weights --------------------------------------------------------------- |
| 33 |
|
| * |
| 34 |
|
| * The evaluation is scored FOR THE ATTACKERS and negated for the defenders. |
| 35 |
|
| * Every term is one int in one struct, so a measurement can vary one and leave |
| 36 |
|
| * the rest. |
| 37 |
|
| */ |
| 38 |
|
| |
| 39 |
12696 |
| static void bd_weights_default(struct bd_weights *w) |
| 40 |
|
| { |
| 41 |
12696 |
▶ | if (!w) return; |
Branch: 1 branch
| Branch | True | False | Total |
| if (!w) return; |
0 |
12696 |
12696 |
|
| 42 |
12696 |
| memset(w, 0, sizeof(*w)); |
| 43 |
12696 |
| w->attacker = 100; |
| 44 |
12696 |
| w->defender = 160; |
| 45 |
12696 |
| w->lane_one = 450; |
| 46 |
12696 |
| w->lane_two = 70; |
| 47 |
12696 |
| w->freedom = 4; |
| 48 |
12696 |
| w->corner_guard = 14; |
| 49 |
12696 |
| w->ring = 22; |
| 50 |
|
| } |
| 51 |
|
| |
| 52 |
14315540 |
| static const struct bd_weights *weights_or_default(const struct bd_weights *w) |
| 53 |
|
| { |
| 54 |
|
| static struct bd_weights DEFAULT; |
| 55 |
|
| static int ready = 0; |
| 56 |
14315540 |
▶ | if (w) return w; |
Branch: 1 branch
| Branch | True | False | Total |
| if (w) return w; |
14315540 |
0 |
14315540 |
|
| 57 |
0 |
▶ | if (!ready) { bd_weights_default(&DEFAULT); ready = 1; } |
Branch: 1 branch
| Branch | True | False | Total |
| if (!ready) { bd_weights_default(&DEFAULT); ready = 1; } |
0 |
0 |
0 |
|
| 58 |
0 |
| return &DEFAULT; |
| 59 |
|
| } |
| 60 |
|
| |
| 61 |
|
| /* ---- the evaluation ------------------------------------------------------------- */ |
| 62 |
|
| |
| 63 |
|
| static const int ORTHO[4] = { -1, 1, -BD_STRIDE, BD_STRIDE }; |
| 64 |
|
| |
| 65 |
583304892 |
| static int is_home(int sq, const struct bd_variant *v) |
| 66 |
|
| { |
| 67 |
|
| int f, r; |
| 68 |
583304892 |
▶ | if ((T->is_corner)(sq)) return 1; |
Branch: 1 branch
| Branch | True | False | Total |
| if ((T->is_corner)(sq)) return 1; |
25634225 |
557670667 |
583304892 |
|
| 69 |
557670667 |
▶ | if (!v->escape_edge) return 0; |
Branch: 1 branch
| Branch | True | False | Total |
| if (!v->escape_edge) return 0; |
557670667 |
0 |
557670667 |
|
| 70 |
0 |
| f = (T->file_of)(sq); |
| 71 |
0 |
| r = (T->rank_of)(sq); |
| 72 |
0 |
▶ | 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; |
0 |
0 |
0 |
| return f == 0 || r == 0 || f == BD_SIZE - 1 || r == BD_SIZE - 1; |
0 |
0 |
0 |
| return f == 0 || r == 0 || f == BD_SIZE - 1 || r == BD_SIZE - 1; |
0 |
0 |
0 |
| return f == 0 || r == 0 || f == BD_SIZE - 1 || r == BD_SIZE - 1; |
0 |
0 |
0 |
|
| 73 |
|
| } |
| 74 |
|
| |
| 75 |
|
| /* Where the king could stop if he moved in direction `d` from `from`, written |
| 76 |
|
| * into `out`. The same walk the move generator makes, for one piece. */ |
| 77 |
479852268 |
| static int king_slide(const struct bd_board *b, const struct bd_variant *v, int from, int d, int *out) |
| 78 |
|
| { |
| 79 |
479852268 |
| int sq = from + d, n = 0; |
| 80 |
1089833749 |
▶ | while ((T->at)(b, sq) == BD_EMPTY) { |
Branch: 1 branch
| Branch | True | False | Total |
| while ((T->at)(b, sq) == BD_EMPTY) { |
609981481 |
479852268 |
1089833749 |
|
| 81 |
609981481 |
▶ | if ((T->is_throne)(sq)) { |
Branch: 1 branch
| Branch | True | False | Total |
| if ((T->is_throne)(sq)) { |
33088374 |
576893107 |
609981481 |
|
| 82 |
33088374 |
▶ | if (v->throne_reentry) out[n++] = sq; |
Branch: 1 branch
| Branch | True | False | Total |
| if (v->throne_reentry) out[n++] = sq; |
0 |
33088374 |
33088374 |
|
| 83 |
33088374 |
▶ | if (!v->throne_pass) break; |
Branch: 1 branch
| Branch | True | False | Total |
| if (!v->throne_pass) break; |
0 |
33088374 |
33088374 |
|
| 84 |
|
| } |
| 85 |
576893107 |
| else out[n++] = sq; |
| 86 |
609981481 |
| sq += d; |
| 87 |
|
| } |
| 88 |
479852268 |
| return n; |
| 89 |
|
| } |
| 90 |
|
| |
| 91 |
|
| /* How many squares the king wins on can he reach in ONE move. The whole of the |
| 92 |
|
| * tactics of this game hangs on this number: with the defenders to move and it |
| 93 |
|
| * above zero the game is won, and with the attackers to move it is a threat |
| 94 |
|
| * that must be answered now. */ |
| 95 |
21835438 |
| static int king_lanes(const struct bd_board *b, const struct bd_variant *v) |
| 96 |
|
| { |
| 97 |
21835438 |
| int king = (T->king_square)(b), d, i, n, one = 0; |
| 98 |
|
| int stops[BD_SIZE]; |
| 99 |
21835438 |
▶ | if (king < 0) return 0; |
Branch: 1 branch
| Branch | True | False | Total |
| if (king < 0) return 0; |
0 |
21835438 |
21835438 |
|
| 100 |
109177190 |
▶ | for (d = 0; d < 4; d++) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (d = 0; d < 4; d++) { |
87341752 |
21835438 |
109177190 |
|
| 101 |
87341752 |
| n = king_slide(b, v, king, ORTHO[d], stops); |
| 102 |
210982493 |
▶ | for (i = 0; i < n; i++) |
Branch: 1 branch
| Branch | True | False | Total |
| for (i = 0; i < n; i++) |
123640741 |
87341752 |
210982493 |
|
| 103 |
123640741 |
▶ | if (is_home(stops[i], v)) one++; |
Branch: 1 branch
| Branch | True | False | Total |
| if (is_home(stops[i], v)) one++; |
9448355 |
114192386 |
123640741 |
|
| 104 |
|
| } |
| 105 |
21835438 |
| return one; |
| 106 |
|
| } |
| 107 |
|
| |
| 108 |
|
| /* THE SEVEN TERMS. |
| 109 |
|
| * |
| 110 |
|
| * material attackers left, and defenders left, each with its own weight |
| 111 |
|
| * lane_one squares the king wins on that he can reach in ONE move |
| 112 |
|
| * lane_two such squares he can reach in two and not in one |
| 113 |
|
| * freedom how many squares the king can move to at all |
| 114 |
|
| * corner_guard attackers on the three squares that close a corner |
| 115 |
|
| * ring attackers standing next to the king |
| 116 |
|
| * |
| 117 |
|
| * The first two lanes are what the game is about: a king with a line to a |
| 118 |
|
| * corner has won unless it is closed at once, and a king with two has won. |
| 119 |
|
| */ |
| 120 |
14307364 |
| static int bd_evaluate(const struct bd_board *b, const struct bd_variant *v, const struct bd_weights *w) |
| 121 |
|
| { |
| 122 |
|
| static const int GUARD[4][3][2] = { |
| 123 |
|
| { { 0, 2 }, { 1, 1 }, { 2, 0 } }, |
| 124 |
|
| { { 6, 2 }, { 5, 1 }, { 4, 0 } }, |
| 125 |
|
| { { 0, 4 }, { 1, 5 }, { 2, 6 } }, |
| 126 |
|
| { { 6, 4 }, { 5, 5 }, { 4, 6 } } |
| 127 |
|
| }; |
| 128 |
|
| struct bd_variant dv; |
| 129 |
|
| int score, king, d, e, i, c; |
| 130 |
14307364 |
| int one = 0, two = 0, freedom = 0, ring = 0, guards = 0; |
| 131 |
|
| int home_one[BD_CELLS]; |
| 132 |
|
| int stops[BD_SIZE], n; |
| 133 |
|
| |
| 134 |
14307364 |
▶ | if (!b) return 0; |
Branch: 1 branch
| Branch | True | False | Total |
| if (!b) return 0; |
0 |
14307364 |
14307364 |
|
| 135 |
14307364 |
▶ | if (!v) { (T->variant_default)(&dv); v = &dv; } |
Branch: 1 branch
| Branch | True | False | Total |
| if (!v) { (T->variant_default)(&dv); v = &dv; } |
0 |
14307364 |
14307364 |
|
| 136 |
14307364 |
| w = weights_or_default(w); |
| 137 |
|
| |
| 138 |
14307364 |
| score = w->attacker * (T->count)(b, BD_ATTACKER) - w->defender * (T->count)(b, BD_DEFENDER); |
| 139 |
|
| |
| 140 |
71536820 |
▶ | for (c = 0; c < 4; c++) |
Branch: 1 branch
| Branch | True | False | Total |
| for (c = 0; c < 4; c++) |
57229456 |
14307364 |
71536820 |
|
| 141 |
228917824 |
▶ | for (i = 0; i < 3; i++) |
Branch: 1 branch
| Branch | True | False | Total |
| for (i = 0; i < 3; i++) |
171688368 |
57229456 |
228917824 |
|
| 142 |
171688368 |
▶ | if ((T->at)(b, (T->square_of)(GUARD[c][i][0], GUARD[c][i][1])) == BD_ATTACKER) guards++; |
Branch: 1 branch
| Branch | True | False | Total |
| if ((T->at)(b, (T->square_of)(GUARD[c][i][0], GUARD[c][i][1])) == BD_ATTACKER) guards++; |
23989065 |
147699303 |
171688368 |
|
| 143 |
14307364 |
| score += w->corner_guard * guards; |
| 144 |
|
| |
| 145 |
14307364 |
| king = (T->king_square)(b); |
| 146 |
14307364 |
▶ | if (king < 0) return score; |
Branch: 1 branch
| Branch | True | False | Total |
| if (king < 0) return score; |
0 |
14307364 |
14307364 |
|
| 147 |
|
| |
| 148 |
14307364 |
| memset(home_one, 0, sizeof(home_one)); |
| 149 |
71536820 |
▶ | for (d = 0; d < 4; d++) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (d = 0; d < 4; d++) { |
57229456 |
14307364 |
71536820 |
|
| 150 |
57229456 |
▶ | if ((T->at)(b, king + ORTHO[d]) == BD_ATTACKER) ring++; |
Branch: 1 branch
| Branch | True | False | Total |
| if ((T->at)(b, king + ORTHO[d]) == BD_ATTACKER) ring++; |
7299266 |
49930190 |
57229456 |
|
| 151 |
57229456 |
| n = king_slide(b, v, king, ORTHO[d], stops); |
| 152 |
57229456 |
| freedom += n; |
| 153 |
126743261 |
▶ | for (i = 0; i < n; i++) |
Branch: 1 branch
| Branch | True | False | Total |
| for (i = 0; i < n; i++) |
69513805 |
57229456 |
126743261 |
|
| 154 |
69513805 |
▶ | if (is_home(stops[i], v) && !home_one[stops[i]]) { home_one[stops[i]] = 1; one++; } |
Branch: 2 branches
| Branch | True | False | Total |
| if (is_home(stops[i], v) && !home_one[stops[i]]) { home_one[stops[i]] = 1; one++; } |
904 |
69512901 |
69513805 |
| if (is_home(stops[i], v) && !home_one[stops[i]]) { home_one[stops[i]] = 1; one++; } |
904 |
0 |
904 |
|
| 155 |
|
| } |
| 156 |
|
| { |
| 157 |
|
| int home_two[BD_CELLS]; |
| 158 |
14307364 |
| memset(home_two, 0, sizeof(home_two)); |
| 159 |
71536820 |
▶ | for (d = 0; d < 4; d++) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (d = 0; d < 4; d++) { |
57229456 |
14307364 |
71536820 |
|
| 160 |
57229456 |
| n = king_slide(b, v, king, ORTHO[d], stops); |
| 161 |
126743261 |
▶ | for (i = 0; i < n; i++) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (i = 0; i < n; i++) { |
69513805 |
57229456 |
126743261 |
|
| 162 |
|
| int reach[BD_SIZE], m, j; |
| 163 |
69513805 |
▶ | if (is_home(stops[i], v)) continue; |
Branch: 1 branch
| Branch | True | False | Total |
| if (is_home(stops[i], v)) continue; |
904 |
69512901 |
69513805 |
|
| 164 |
347564505 |
▶ | for (e = 0; e < 4; e++) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (e = 0; e < 4; e++) { |
278051604 |
69512901 |
347564505 |
|
| 165 |
278051604 |
| m = king_slide(b, v, stops[i], ORTHO[e], reach); |
| 166 |
592276360 |
▶ | for (j = 0; j < m; j++) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (j = 0; j < m; j++) { |
314224756 |
278051604 |
592276360 |
|
| 167 |
314224756 |
| int sq = reach[j]; |
| 168 |
314224756 |
▶ | if (sq == king) continue; |
Branch: 1 branch
| Branch | True | False | Total |
| if (sq == king) continue; |
0 |
314224756 |
314224756 |
|
| 169 |
314224756 |
▶ | if (is_home(sq, v) && !home_one[sq] && !home_two[sq]) { home_two[sq] = 1; two++; } |
Branch: 3 branches
| Branch | True | False | Total |
| if (is_home(sq, v) && !home_one[sq] && !home_two[sq]) { home_two[sq] = 1; two++; } |
16043334 |
298181422 |
314224756 |
| if (is_home(sq, v) && !home_one[sq] && !home_two[sq]) { home_two[sq] = 1; two++; } |
16042264 |
1070 |
16043334 |
| if (is_home(sq, v) && !home_one[sq] && !home_two[sq]) { home_two[sq] = 1; two++; } |
14555007 |
1487257 |
16042264 |
|
| 170 |
|
| } |
| 171 |
|
| } |
| 172 |
|
| } |
| 173 |
|
| } |
| 174 |
|
| } |
| 175 |
|
| |
| 176 |
14307364 |
| score += w->ring * ring; |
| 177 |
14307364 |
| score -= w->lane_one * one; |
| 178 |
14307364 |
| score -= w->lane_two * two; |
| 179 |
14307364 |
| score -= w->freedom * freedom; |
| 180 |
14307364 |
| return score; |
| 181 |
|
| } |
| 182 |
|
| |
| 183 |
|
| /* ---- the table of positions already searched ------------------------------------ */ |
| 184 |
|
| |
| 185 |
|
| #define TT_EXACT 0 |
| 186 |
|
| #define TT_LOWER 1 |
| 187 |
|
| #define TT_UPPER 2 |
| 188 |
|
| |
| 189 |
|
| struct tt_entry { |
| 190 |
|
| unsigned long long key; |
| 191 |
|
| int move; |
| 192 |
|
| int score; |
| 193 |
|
| short depth; |
| 194 |
|
| unsigned char flag; |
| 195 |
|
| unsigned char used; |
| 196 |
|
| }; |
| 197 |
|
| |
| 198 |
|
| #define BD_INF (BD_WIN_SCORE + 1000) |
| 199 |
|
| |
| 200 |
|
| /* how deep one line may run, the extension included */ |
| 201 |
|
| #define BD_PLY_MAX 96 |
| 202 |
|
| |
| 203 |
|
| struct ctx { |
| 204 |
|
| struct bd_game *g; |
| 205 |
|
| struct bd_variant v; |
| 206 |
|
| const struct bd_weights *w; |
| 207 |
|
| unsigned long long nodes, budget, seed; |
| 208 |
|
| int may_stop; |
| 209 |
|
| int stopped; |
| 210 |
|
| struct tt_entry *tt; |
| 211 |
|
| size_t mask; |
| 212 |
|
| int killer[BD_PLY_MAX][2]; |
| 213 |
|
| }; |
| 214 |
|
| |
| 215 |
|
| |
| 216 |
|
| /* The order moves are tried in: the move the table remembers, the king going |
| 217 |
|
| * home, a move that cut this depth off a moment ago in another line, moves |
| 218 |
|
| * that land beside an enemy, the king's other moves, the rest. It |
| 219 |
|
| * changes how many nodes a search costs and never which move a search to a |
| 220 |
|
| * fixed depth returns, apart from the choice among moves of equal score, which |
| 221 |
|
| * `salt` settles and a test holds to that. */ |
| 222 |
635001 |
| static unsigned long long mix(unsigned long long z) |
| 223 |
|
| { |
| 224 |
635001 |
| z += 0x9E3779B97F4A7C15ULL; |
| 225 |
635001 |
| z = (z ^ (z >> 30)) * 0xBF58476D1CE4E5B9ULL; |
| 226 |
635001 |
| z = (z ^ (z >> 27)) * 0x94D049BB133111EBULL; |
| 227 |
635001 |
| return z ^ (z >> 31); |
| 228 |
|
| } |
| 229 |
|
| |
| 230 |
2535522 |
| static void order_moves(const struct ctx *c, const struct bd_board *b, int *list, int n, int first, unsigned long long salt, int ply) |
| 231 |
|
| { |
| 232 |
|
| int key[BD_MOVES_MAX]; |
| 233 |
2535522 |
| int i, j, side = (T->side)(b); |
| 234 |
|
| |
| 235 |
83958836 |
▶ | for (i = 0; i < n; i++) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (i = 0; i < n; i++) { |
81423314 |
2535522 |
83958836 |
|
| 236 |
81423314 |
| int from = (T->move_from)(list[i]), to = (T->move_to)(list[i]); |
| 237 |
81423314 |
| int piece = (T->at)(b, from); |
| 238 |
81423314 |
| int k = 0, d; |
| 239 |
81423314 |
▶ | if (list[i] == first) k += 100000; |
Branch: 1 branch
| Branch | True | False | Total |
| if (list[i] == first) k += 100000; |
275044 |
81148270 |
81423314 |
|
| 240 |
81423314 |
▶ | if (ply >= 0 && ply < BD_PLY_MAX && (list[i] == c->killer[ply][0] || list[i] == c->killer[ply][1])) k += 20000; |
Branch: 4 branches
| Branch | True | False | Total |
| if (ply >= 0 && ply < BD_PLY_MAX && (list[i] == c->killer[ply][0] || list[i] == c->killer[ply][1])) k += 20000; |
80788313 |
635001 |
81423314 |
| if (ply >= 0 && ply < BD_PLY_MAX && (list[i] == c->killer[ply][0] || list[i] == c->killer[ply][1])) k += 20000; |
80788313 |
0 |
80788313 |
| if (ply >= 0 && ply < BD_PLY_MAX && (list[i] == c->killer[ply][0] || list[i] == c->killer[ply][1])) k += 20000; |
78745840 |
2042473 |
80788313 |
| if (ply >= 0 && ply < BD_PLY_MAX && (list[i] == c->killer[ply][0] || list[i] == c->killer[ply][1])) k += 20000; |
1601231 |
77144609 |
78745840 |
|
| 241 |
81423314 |
▶ | if (piece == BD_KING) k += is_home(to, &c->v) ? 50000 : 300; |
Branch: 2 branches
| Branch | True | False | Total |
| if (piece == BD_KING) k += is_home(to, &c->v) ? 50000 : 300; |
6411785 |
75011529 |
81423314 |
| if (piece == BD_KING) k += is_home(to, &c->v) ? 50000 : 300; |
140728 |
6271057 |
6411785 |
|
| 242 |
336465505 |
▶ | for (d = 0; d < 4; d++) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (d = 0; d < 4; d++) { |
282304896 |
54160609 |
336465505 |
|
| 243 |
282304896 |
| int beside = (T->at)(b, to + ORTHO[d]); |
| 244 |
282304896 |
▶ | if (BD_IS_PIECE(beside) && (T->side_of)(beside) != side) { k += 1000; break; } |
Branch: 3 branches
| Branch | True | False | Total |
| if (BD_IS_PIECE(beside) && (T->side_of)(beside) != side) { k += 1000; break; } |
107494896 |
174810000 |
282304896 |
| if (BD_IS_PIECE(beside) && (T->side_of)(beside) != side) { k += 1000; break; } |
78752085 |
28742811 |
107494896 |
| if (BD_IS_PIECE(beside) && (T->side_of)(beside) != side) { k += 1000; break; } |
27262705 |
51489380 |
78752085 |
|
| 245 |
|
| } |
| 246 |
81423314 |
▶ | if (salt) k += (int) (mix(salt ^ ((unsigned long long) list[i] * 0x100000001B3ULL)) & 0xFF); |
Branch: 1 branch
| Branch | True | False | Total |
| if (salt) k += (int) (mix(salt ^ ((unsigned long long) list[i] * 0x100000001B3ULL)) & 0xFF); |
635001 |
80788313 |
81423314 |
|
| 247 |
81423314 |
| key[i] = k; |
| 248 |
|
| } |
| 249 |
81423314 |
▶ | for (i = 1; i < n; i++) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (i = 1; i < n; i++) { |
78887792 |
2535522 |
81423314 |
|
| 250 |
78887792 |
| int m = list[i], k = key[i]; |
| 251 |
387769994 |
▶ | for (j = i - 1; j >= 0 && key[j] < k; j--) { list[j + 1] = list[j]; key[j + 1] = key[j]; } |
Branch: 2 branches
| Branch | True | False | Total |
| for (j = i - 1; j >= 0 && key[j] < k; j--) { list[j + 1] = list[j]; key[j + 1] = key[j]; } |
383538407 |
4231587 |
387769994 |
| for (j = i - 1; j >= 0 && key[j] < k; j--) { list[j + 1] = list[j]; key[j + 1] = key[j]; } |
308882202 |
74656205 |
383538407 |
|
| 252 |
78887792 |
| list[j + 1] = m; key[j + 1] = k; |
| 253 |
|
| } |
| 254 |
2535522 |
| } |
| 255 |
|
| |
| 256 |
255948 |
| static int score_of_outcome(int outcome, int side, int ply) |
| 257 |
|
| { |
| 258 |
255948 |
| int winner = (T->winner_of)(outcome); |
| 259 |
255948 |
▶ | if (winner < 0) return 0; |
Branch: 1 branch
| Branch | True | False | Total |
| if (winner < 0) return 0; |
23761 |
232187 |
255948 |
|
| 260 |
232187 |
▶ | return winner == side ? BD_WIN_SCORE - ply : -(BD_WIN_SCORE - ply); |
Branch: 1 branch
| Branch | True | False | Total |
| return winner == side ? BD_WIN_SCORE - ply : -(BD_WIN_SCORE - ply); |
0 |
232187 |
232187 |
|
| 261 |
|
| } |
| 262 |
|
| |
| 263 |
|
| /* THE EXTENSION. A search that stops at a fixed depth stops, as often as not, |
| 264 |
|
| * with the king one move from a corner, and scores that as a quiet position. |
| 265 |
|
| * So at the horizon the king's lanes are counted first: |
| 266 |
|
| * |
| 267 |
|
| * the defenders to move with a lane open he walks out: a win, and exact |
| 268 |
|
| * the attackers to move with a lane open they must answer it NOW, so the |
| 269 |
|
| * line is searched one ply further |
| 270 |
|
| * |
| 271 |
|
| * IT CANNOT RUN AWAY, and needs no counter to stop it. The one extra ply is |
| 272 |
|
| * the attackers', and at the end of it the defenders are to move, where the |
| 273 |
|
| * search never extends: it returns a win if the lane is still open and the |
| 274 |
|
| * evaluation if it is not. Because the extension depends on the position alone |
| 275 |
|
| * and not on how the line got there, a position is worth the same by every |
| 276 |
|
| * road, which is what lets the table of positions be trusted. |
| 277 |
|
| * |
| 278 |
|
| * Without it the attackers of this file lost every game they played in |
| 279 |
|
| * eight moves, to combinations one ply past where they were looking. */ |
| 280 |
24656694 |
| static int negamax(struct ctx *c, int depth, int alpha, int beta, int ply) |
| 281 |
|
| { |
| 282 |
24656694 |
| const struct bd_board *b = (T->game_board)(c->g); |
| 283 |
|
| int list[BD_MOVES_MAX]; |
| 284 |
24656694 |
| int n, i, best = -BD_INF, best_move = 0, first = 0, alpha0 = alpha; |
| 285 |
24656694 |
| int side = (T->side)(b); |
| 286 |
|
| int outcome; |
| 287 |
|
| unsigned long long key; |
| 288 |
24656694 |
| struct tt_entry *e = NULL; |
| 289 |
|
| |
| 290 |
24656694 |
| c->nodes++; |
| 291 |
24656694 |
▶ | if (c->may_stop && (c->nodes & 1023ULL) == 0 && c->nodes >= c->budget) c->stopped = 1; |
Branch: 3 branches
| Branch | True | False | Total |
| if (c->may_stop && (c->nodes & 1023ULL) == 0 && c->nodes >= c->budget) c->stopped = 1; |
24292943 |
363751 |
24656694 |
| if (c->may_stop && (c->nodes & 1023ULL) == 0 && c->nodes >= c->budget) c->stopped = 1; |
23162 |
24269781 |
24292943 |
| if (c->may_stop && (c->nodes & 1023ULL) == 0 && c->nodes >= c->budget) c->stopped = 1; |
3281 |
19881 |
23162 |
|
| 292 |
24656694 |
▶ | if (c->stopped) return 0; |
Branch: 1 branch
| Branch | True | False | Total |
| if (c->stopped) return 0; |
3281 |
24653413 |
24656694 |
|
| 293 |
|
| |
| 294 |
24653413 |
| outcome = (T->game_outcome)(c->g); |
| 295 |
24653413 |
▶ | if (outcome != BD_ONGOING) return score_of_outcome(outcome, side, ply); |
Branch: 1 branch
| Branch | True | False | Total |
| if (outcome != BD_ONGOING) return score_of_outcome(outcome, side, ply); |
255948 |
24397465 |
24653413 |
|
| 296 |
|
| |
| 297 |
24397465 |
▶ | if (depth <= 0) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (depth <= 0) { |
21835438 |
2562027 |
24397465 |
|
| 298 |
21835438 |
| int lanes = king_lanes(b, &c->v); |
| 299 |
21835438 |
▶ | if (lanes && side == BD_DEFENDERS) return BD_WIN_SCORE - ply - 1; |
Branch: 2 branches
| Branch | True | False | Total |
| if (lanes && side == BD_DEFENDERS) return BD_WIN_SCORE - ply - 1; |
7532590 |
14302848 |
21835438 |
| if (lanes && side == BD_DEFENDERS) return BD_WIN_SCORE - ply - 1; |
7287106 |
245484 |
7532590 |
|
| 300 |
14548332 |
▶ | if (lanes && ply < BD_PLY_MAX - 2) { |
Branch: 2 branches
| Branch | True | False | Total |
| if (lanes && ply < BD_PLY_MAX - 2) { |
245484 |
14302848 |
14548332 |
| if (lanes && ply < BD_PLY_MAX - 2) { |
245484 |
0 |
245484 |
|
| 301 |
245484 |
| depth = 1; |
| 302 |
|
| } |
| 303 |
|
| else { |
| 304 |
14302848 |
| int s = bd_evaluate(b, &c->v, c->w); |
| 305 |
14302848 |
▶ | return side == BD_ATTACKERS ? s : -s; |
Branch: 1 branch
| Branch | True | False | Total |
| return side == BD_ATTACKERS ? s : -s; |
10194841 |
4108007 |
14302848 |
|
| 306 |
|
| } |
| 307 |
|
| } |
| 308 |
|
| |
| 309 |
|
| /* game_push left "can the side to move, move?" unasked, so it is asked |
| 310 |
|
| * here, by the list this node needs anyway */ |
| 311 |
2807511 |
| n = (T->gen_moves)(b, &c->v, list, BD_MOVES_MAX); |
| 312 |
2807511 |
▶ | if (n == 0) return 0; |
Branch: 1 branch
| Branch | True | False | Total |
| if (n == 0) return 0; |
0 |
2807511 |
2807511 |
|
| 313 |
2807511 |
▶ | 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 |
2807511 |
2807511 |
|
| 314 |
|
| |
| 315 |
2807511 |
| key = (T->key)(b); |
| 316 |
2807511 |
▶ | if (c->tt) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (c->tt) { |
2807511 |
0 |
2807511 |
|
| 317 |
2807511 |
| e = &c->tt[(size_t) key & c->mask]; |
| 318 |
2807511 |
▶ | if (e->used && e->key == key) { |
Branch: 2 branches
| Branch | True | False | Total |
| if (e->used && e->key == key) { |
628961 |
2178550 |
2807511 |
| if (e->used && e->key == key) { |
555207 |
73754 |
628961 |
|
| 319 |
555207 |
| first = e->move; |
| 320 |
555207 |
▶ | if (e->depth >= depth) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (e->depth >= depth) { |
300260 |
254947 |
555207 |
|
| 321 |
300260 |
▶ | if (e->flag == TT_EXACT) return e->score; |
Branch: 1 branch
| Branch | True | False | Total |
| if (e->flag == TT_EXACT) return e->score; |
6931 |
293329 |
300260 |
|
| 322 |
293329 |
▶ | if (e->flag == TT_LOWER && e->score > alpha) alpha = e->score; |
Branch: 2 branches
| Branch | True | False | Total |
| if (e->flag == TT_LOWER && e->score > alpha) alpha = e->score; |
287445 |
5884 |
293329 |
| if (e->flag == TT_LOWER && e->score > alpha) alpha = e->score; |
286446 |
999 |
287445 |
|
| 323 |
293329 |
▶ | if (e->flag == TT_UPPER && e->score < beta) beta = e->score; |
Branch: 2 branches
| Branch | True | False | Total |
| if (e->flag == TT_UPPER && e->score < beta) beta = e->score; |
5884 |
287445 |
293329 |
| if (e->flag == TT_UPPER && e->score < beta) beta = e->score; |
5307 |
577 |
5884 |
|
| 324 |
293329 |
▶ | if (alpha >= beta) return e->score; |
Branch: 1 branch
| Branch | True | False | Total |
| if (alpha >= beta) return e->score; |
283777 |
9552 |
293329 |
|
| 325 |
|
| } |
| 326 |
|
| } |
| 327 |
|
| } |
| 328 |
|
| |
| 329 |
2516803 |
| order_moves(c, b, list, n, first, 0, ply); |
| 330 |
|
| |
| 331 |
24653893 |
▶ | for (i = 0; i < n; i++) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (i = 0; i < n; i++) { |
24094971 |
558922 |
24653893 |
|
| 332 |
|
| int s; |
| 333 |
24094971 |
| (T->game_push)(c->g, list[i], NULL); |
| 334 |
24094971 |
| s = -negamax(c, depth - 1, -beta, -alpha, ply + 1); |
| 335 |
24094971 |
| (T->game_undo)(c->g); |
| 336 |
24094971 |
▶ | if (c->stopped) return 0; |
Branch: 1 branch
| Branch | True | False | Total |
| if (c->stopped) return 0; |
7975 |
24086996 |
24094971 |
|
| 337 |
24086996 |
▶ | if (s > best) { best = s; best_move = list[i]; } |
Branch: 1 branch
| Branch | True | False | Total |
| if (s > best) { best = s; best_move = list[i]; } |
3583963 |
20503033 |
24086996 |
|
| 338 |
24086996 |
▶ | if (best > alpha) alpha = best; |
Branch: 1 branch
| Branch | True | False | Total |
| if (best > alpha) alpha = best; |
2450933 |
21636063 |
24086996 |
|
| 339 |
24086996 |
▶ | if (alpha >= beta) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (alpha >= beta) { |
1949906 |
22137090 |
24086996 |
|
| 340 |
1949906 |
▶ | if (ply < BD_PLY_MAX && c->killer[ply][0] != list[i]) { |
Branch: 2 branches
| Branch | True | False | Total |
| if (ply < BD_PLY_MAX && c->killer[ply][0] != list[i]) { |
1949906 |
0 |
1949906 |
| if (ply < BD_PLY_MAX && c->killer[ply][0] != list[i]) { |
546502 |
1403404 |
1949906 |
|
| 341 |
546502 |
| c->killer[ply][1] = c->killer[ply][0]; |
| 342 |
546502 |
| c->killer[ply][0] = list[i]; |
| 343 |
|
| } |
| 344 |
1949906 |
| break; |
| 345 |
|
| } |
| 346 |
|
| } |
| 347 |
|
| |
| 348 |
|
| /* A score that is a win or a loss carries the distance from the ROOT, which |
| 349 |
|
| * is the wrong distance for the same position met by another road, so those |
| 350 |
|
| * are left out of the table. */ |
| 351 |
2508828 |
▶ | if (e && best > -(BD_WIN_SCORE - 1000) && best < BD_WIN_SCORE - 1000) { |
Branch: 3 branches
| Branch | True | False | Total |
| if (e && best > -(BD_WIN_SCORE - 1000) && best < BD_WIN_SCORE - 1000) { |
2508828 |
0 |
2508828 |
| if (e && best > -(BD_WIN_SCORE - 1000) && best < BD_WIN_SCORE - 1000) { |
2312043 |
196785 |
2508828 |
| if (e && best > -(BD_WIN_SCORE - 1000) && best < BD_WIN_SCORE - 1000) { |
1935811 |
376232 |
2312043 |
|
| 352 |
1935811 |
| e->used = 1; |
| 353 |
1935811 |
| e->key = key; |
| 354 |
1935811 |
| e->move = best_move; |
| 355 |
1935811 |
| e->score = best; |
| 356 |
1935811 |
| e->depth = (short) depth; |
| 357 |
1935811 |
▶ | e->flag = (unsigned char) (best <= alpha0 ? TT_UPPER : best >= beta ? TT_LOWER : TT_EXACT); |
Branch: 2 branches
| Branch | True | False | Total |
| e->flag = (unsigned char) (best <= alpha0 ? TT_UPPER : best >= beta ? TT_LOWER : TT_EXACT); |
1682521 |
253290 |
1935811 |
| e->flag = (unsigned char) (best <= alpha0 ? TT_UPPER : best >= beta ? TT_LOWER : TT_EXACT); |
1572436 |
110085 |
1682521 |
|
| 358 |
|
| } |
| 359 |
2508828 |
| return best; |
| 360 |
|
| } |
| 361 |
|
| |
| 362 |
|
| #define BD_DEPTH_MAX 60 |
| 363 |
|
| |
| 364 |
|
| /* THE MOVE RETURNED IS THE BEST OF THE LAST ITERATION THAT FINISHED. An |
| 365 |
|
| * iteration cut short by the budget has looked at some of the moves and not |
| 366 |
|
| * others, and its "best so far" is the best of an arbitrary subset. |
| 367 |
|
| * |
| 368 |
|
| * The first iteration is never cut short, so there is always a move to |
| 369 |
|
| * return; it costs one node a legal move and a budget smaller than that is |
| 370 |
|
| * simply exceeded by it. |
| 371 |
|
| * |
| 372 |
|
| * `seed` settles the choice among root moves of equal score, and nothing else. |
| 373 |
|
| */ |
| 374 |
8176 |
| static int bd_search(const struct bd_game *game, const struct bd_weights *w, |
| 375 |
|
| unsigned long long budget, unsigned long long seed, int max_depth, |
| 376 |
|
| struct bd_search_info *info) |
| 377 |
|
| { |
| 378 |
|
| struct ctx c; |
| 379 |
|
| int root[BD_MOVES_MAX]; |
| 380 |
8176 |
| int n, depth, i, best_move = 0, best_score = 0, done = 0; |
| 381 |
8176 |
| size_t size = 1024; |
| 382 |
|
| |
| 383 |
8176 |
▶ | if (info) memset(info, 0, sizeof(*info)); |
Branch: 1 branch
| Branch | True | False | Total |
| if (info) memset(info, 0, sizeof(*info)); |
8176 |
0 |
8176 |
|
| 384 |
8176 |
▶ | if (!game) return 0; |
Branch: 1 branch
| Branch | True | False | Total |
| if (!game) return 0; |
0 |
8176 |
8176 |
|
| 385 |
|
| |
| 386 |
8176 |
| memset(&c, 0, sizeof(c)); |
| 387 |
8176 |
| c.g = (T->game_copy)(game); |
| 388 |
8176 |
▶ | if (!c.g) return 0; |
Branch: 1 branch
| Branch | True | False | Total |
| if (!c.g) return 0; |
0 |
8176 |
8176 |
|
| 389 |
8176 |
| (T->game_variant)(c.g, &c.v); |
| 390 |
8176 |
| c.w = weights_or_default(w); |
| 391 |
8176 |
| c.budget = budget; |
| 392 |
8176 |
▶ | c.seed = seed ? seed : 1; |
Branch: 1 branch
| Branch | True | False | Total |
| c.seed = seed ? seed : 1; |
8175 |
1 |
8176 |
|
| 393 |
|
| |
| 394 |
8176 |
| n = (T->game_moves)(c.g, root, BD_MOVES_MAX); |
| 395 |
8176 |
▶ | if (n <= 0) { (T->game_drop)(c.g); return 0; } |
Branch: 1 branch
| Branch | True | False | Total |
| if (n <= 0) { (T->game_drop)(c.g); return 0; } |
2 |
8174 |
8176 |
|
| 396 |
8174 |
▶ | 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 |
8174 |
8174 |
|
| 397 |
|
| |
| 398 |
29773 |
▶ | while (size < budget && size < ((size_t) 1 << 20)) size <<= 1; |
Branch: 2 branches
| Branch | True | False | Total |
| while (size < budget && size < ((size_t) 1 << 20)) size <<= 1; |
23193 |
6580 |
29773 |
| while (size < budget && size < ((size_t) 1 << 20)) size <<= 1; |
21599 |
1594 |
23193 |
|
| 399 |
8174 |
| c.tt = (struct tt_entry *) calloc(size, sizeof(struct tt_entry)); |
| 400 |
8174 |
| c.mask = size - 1; |
| 401 |
|
| |
| 402 |
8174 |
▶ | if (max_depth <= 0 || max_depth > BD_DEPTH_MAX) max_depth = BD_DEPTH_MAX; |
Branch: 2 branches
| Branch | True | False | Total |
| if (max_depth <= 0 || max_depth > BD_DEPTH_MAX) max_depth = BD_DEPTH_MAX; |
1594 |
6580 |
8174 |
| if (max_depth <= 0 || max_depth > BD_DEPTH_MAX) max_depth = BD_DEPTH_MAX; |
0 |
1594 |
1594 |
|
| 403 |
|
| |
| 404 |
19502 |
▶ | for (depth = 1; depth <= max_depth; depth++) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (depth = 1; depth <= max_depth; depth++) { |
18719 |
783 |
19502 |
|
| 405 |
18719 |
| int alpha = -BD_INF, beta = BD_INF, it_best = -BD_INF, it_move = 0; |
| 406 |
18719 |
| const struct bd_board *b = (T->game_board)(c.g); |
| 407 |
|
| |
| 408 |
18719 |
| c.may_stop = depth > 1; |
| 409 |
18719 |
| order_moves(&c, b, root, n, best_move, c.seed, -1); |
| 410 |
|
| |
| 411 |
577161 |
▶ | for (i = 0; i < n; i++) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (i = 0; i < n; i++) { |
561723 |
15438 |
577161 |
|
| 412 |
|
| int s; |
| 413 |
561723 |
| (T->game_push)(c.g, root[i], NULL); |
| 414 |
561723 |
| s = -negamax(&c, depth - 1, -beta, -alpha, 1); |
| 415 |
561723 |
| (T->game_undo)(c.g); |
| 416 |
561723 |
▶ | if (c.stopped) break; |
Branch: 1 branch
| Branch | True | False | Total |
| if (c.stopped) break; |
3281 |
558442 |
561723 |
|
| 417 |
558442 |
▶ | if (s > it_best) { it_best = s; it_move = root[i]; } |
Branch: 1 branch
| Branch | True | False | Total |
| if (s > it_best) { it_best = s; it_move = root[i]; } |
35481 |
522961 |
558442 |
|
| 418 |
558442 |
▶ | if (it_best > alpha) alpha = it_best; |
Branch: 1 branch
| Branch | True | False | Total |
| if (it_best > alpha) alpha = it_best; |
35481 |
522961 |
558442 |
|
| 419 |
|
| } |
| 420 |
18719 |
▶ | if (c.stopped) break; |
Branch: 1 branch
| Branch | True | False | Total |
| if (c.stopped) break; |
3281 |
15438 |
18719 |
|
| 421 |
|
| |
| 422 |
15438 |
| best_move = it_move; |
| 423 |
15438 |
| best_score = it_best; |
| 424 |
15438 |
| done = depth; |
| 425 |
|
| |
| 426 |
|
| /* a win or a loss that is forced has been seen to its end, and looking |
| 427 |
|
| * further would only find the same thing more slowly */ |
| 428 |
15438 |
▶ | if (best_score > BD_WIN_SCORE - 1000 || best_score < -(BD_WIN_SCORE - 1000)) break; |
Branch: 2 branches
| Branch | True | False | Total |
| if (best_score > BD_WIN_SCORE - 1000 || best_score < -(BD_WIN_SCORE - 1000)) break; |
12544 |
2894 |
15438 |
| if (best_score > BD_WIN_SCORE - 1000 || best_score < -(BD_WIN_SCORE - 1000)) break; |
11818 |
726 |
12544 |
|
| 429 |
11818 |
▶ | if (c.nodes >= c.budget) break; |
Branch: 1 branch
| Branch | True | False | Total |
| if (c.nodes >= c.budget) break; |
490 |
11328 |
11818 |
|
| 430 |
|
| } |
| 431 |
|
| |
| 432 |
8174 |
▶ | if (info) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (info) { |
8174 |
0 |
8174 |
|
| 433 |
8174 |
| info->nodes = c.nodes; |
| 434 |
8174 |
| info->depth = done; |
| 435 |
8174 |
| info->score = best_score; |
| 436 |
8174 |
| info->stopped = c.stopped; |
| 437 |
|
| } |
| 438 |
8174 |
| free(c.tt); |
| 439 |
8174 |
| (T->game_drop)(c.g); |
| 440 |
8174 |
| return best_move; |
| 441 |
|
| } |
| 442 |
|
| |
| 443 |
|
| /* ---- installed into the table by bd_engine.c -------------------------------------- */ |
| 444 |
|
| |
| 445 |
|
| void bd_search_install(struct bd_abi *t); |
| 446 |
|
| |
| 447 |
59 |
| void bd_search_install(struct bd_abi *t) |
| 448 |
|
| { |
| 449 |
59 |
| T = t; |
| 450 |
59 |
| t->weights_default = bd_weights_default; |
| 451 |
59 |
| t->evaluate = bd_evaluate; |
| 452 |
59 |
| t->search = bd_search; |
| 453 |
59 |
| } |