bd_search.c

filter: Statementstmt 97.5% 197 / 202 Branchbran 84.0% 185 / 220 Conditioncond n/a MC/DCmcdc n/a Subroutinesub n/a Podpod n/a totaltotal 90.5% 382 / 422 CC 0 SCAR 0
CC
0
Cov
0%
CRAP 0
« bd_rules.c ↑ Summary bd_moves.c »
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
if (w) return w; 14315540 0 14315540
57 0 ▶ if (!ready) { bd_weights_default(&DEFAULT); ready = 1; }
Branch: 1 branch
BranchTrueFalseTotal
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
BranchTrueFalseTotal
if ((T->is_corner)(sq)) return 1; 25634225 557670667 583304892
69 557670667 ▶ if (!v->escape_edge) return 0;
Branch: 1 branch
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
while ((T->at)(b, sq) == BD_EMPTY) { 609981481 479852268 1089833749
81 609981481 ▶ if ((T->is_throne)(sq)) {
Branch: 1 branch
BranchTrueFalseTotal
if ((T->is_throne)(sq)) { 33088374 576893107 609981481
82 33088374 ▶ if (v->throne_reentry) out[n++] = sq;
Branch: 1 branch
BranchTrueFalseTotal
if (v->throne_reentry) out[n++] = sq; 0 33088374 33088374
83 33088374 ▶ if (!v->throne_pass) break;
Branch: 1 branch
BranchTrueFalseTotal
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
BranchTrueFalseTotal
if (king < 0) return 0; 0 21835438 21835438
100 109177190 ▶ for (d = 0; d < 4; d++) {
Branch: 1 branch
BranchTrueFalseTotal
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
BranchTrueFalseTotal
for (i = 0; i < n; i++) 123640741 87341752 210982493
103 123640741 ▶ if (is_home(stops[i], v)) one++;
Branch: 1 branch
BranchTrueFalseTotal
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
BranchTrueFalseTotal
if (!b) return 0; 0 14307364 14307364
135 14307364 ▶ if (!v) { (T->variant_default)(&dv); v = &dv; }
Branch: 1 branch
BranchTrueFalseTotal
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
BranchTrueFalseTotal
for (c = 0; c < 4; c++) 57229456 14307364 71536820
141 228917824 ▶ for (i = 0; i < 3; i++)
Branch: 1 branch
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
for (d = 0; d < 4; d++) { 57229456 14307364 71536820
150 57229456 ▶ if ((T->at)(b, king + ORTHO[d]) == BD_ATTACKER) ring++;
Branch: 1 branch
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
if (is_home(stops[i], v)) continue; 904 69512901 69513805
164 347564505 ▶ for (e = 0; e < 4; e++) {
Branch: 1 branch
BranchTrueFalseTotal
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
BranchTrueFalseTotal
for (j = 0; j < m; j++) { 314224756 278051604 592276360
167 314224756 int sq = reach[j];
168 314224756 ▶ if (sq == king) continue;
Branch: 1 branch
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
if (winner < 0) return 0; 23761 232187 255948
260 232187 ▶ return winner == side ? BD_WIN_SCORE - ply : -(BD_WIN_SCORE - ply);
Branch: 1 branch
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
if (outcome != BD_ONGOING) return score_of_outcome(outcome, side, ply); 255948 24397465 24653413
296  
297 24397465 ▶ if (depth <= 0) {
Branch: 1 branch
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
if (n == 0) return 0; 0 2807511 2807511
313 2807511 ▶ if (n > BD_MOVES_MAX) n = BD_MOVES_MAX;
Branch: 1 branch
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
if (e->depth >= depth) { 300260 254947 555207
321 300260 ▶ if (e->flag == TT_EXACT) return e->score;
Branch: 1 branch
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
if (c->stopped) return 0; 7975 24086996 24094971
337 24086996 ▶ if (s > best) { best = s; best_move = list[i]; }
Branch: 1 branch
BranchTrueFalseTotal
if (s > best) { best = s; best_move = list[i]; } 3583963 20503033 24086996
338 24086996 ▶ if (best > alpha) alpha = best;
Branch: 1 branch
BranchTrueFalseTotal
if (best > alpha) alpha = best; 2450933 21636063 24086996
339 24086996 ▶ if (alpha >= beta) {
Branch: 1 branch
BranchTrueFalseTotal
if (alpha >= beta) { 1949906 22137090 24086996
340 1949906 ▶ if (ply < BD_PLY_MAX && c->killer[ply][0] != list[i]) {
Branch: 2 branches
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
if (info) memset(info, 0, sizeof(*info)); 8176 0 8176
384 8176 ▶ if (!game) return 0;
Branch: 1 branch
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
if (c.stopped) break; 3281 558442 561723
417 558442 ▶ if (s > it_best) { it_best = s; it_move = root[i]; }
Branch: 1 branch
BranchTrueFalseTotal
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
BranchTrueFalseTotal
if (it_best > alpha) alpha = it_best; 35481 522961 558442
419 }
420 18719 ▶ if (c.stopped) break;
Branch: 1 branch
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
if (c.nodes >= c.budget) break; 490 11328 11818
430 }
431  
432 8174 ▶ if (info) {
Branch: 1 branch
BranchTrueFalseTotal
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 }
« bd_rules.c ↑ Summary bd_moves.c »