xq_search.c

filter: Statementstmt 100% 183 / 183 Branchbran 90.9% 160 / 176 Conditioncond n/a MC/DCmcdc n/a Subroutinesub n/a Podpod n/a totaltotal 95.5% 343 / 359 CC 0 SCAR 0
CC
0
Cov
0%
CRAP 0
« xq_moves.c ↑ Summary xq_mate.c »
1 /* xq_search.c - the evaluation and the search. Phase 09 of plan_xiangqi.
2 *
3 * PERL-FREE, as the rest of the engine is.
4 *
5 * ---- FAIL-SOFT, AND THE REASON IS ONE PARAGRAPH --------------------------------
6 *
7 * Game::Oware shipped fail-HARD alpha-beta feeding a tie-break and its bot got
8 * STRICTLY WORSE WITH DEPTH: `_alphabeta` returned `$alpha`, so every child that
9 * failed low came back exactly equal to the best score, the root drew uniformly
10 * from that pool, and deeper search raised alpha sooner and so clamped more
11 * children. More search produced more randomness. Level 2 lost 0-10 to level 1
12 * before anybody suspected the search rather than the evaluation, and what ruled
13 * the evaluation out was sweeping every weight to zero and seeing no change.
14 *
15 * So: fail-soft, and a full window at the root. This is at the top of the file
16 * because the bug is invisible in any single game and looks exactly like a bad
17 * evaluation.
18 *
19 * ---- BOUNDED IN WORK, NEVER IN TIME (D6) ----------------------------------------
20 *
21 * The site plays the bot inside the move transaction. A search bounded by
22 * seconds makes the length of a database transaction a property of how loaded
23 * the box is, and makes a bot game unreplayable, because a loaded machine would
24 * choose a different move from an idle one and the site's whole verification
25 * story goes with it.
26 *
27 * The budget is tested every 1024 nodes. NO alarm, NO ualarm, NO signals:
28 * Chess::Plisco uses them and therefore needs a watcher class on the site to
29 * stop a search at all. This one stops itself, which is why the site's adapter
30 * has no Watcher.pm and says so.
31 *
32 * Spent through ITERATIVE DEEPENING, so running out always leaves a complete
33 * search at a shallower depth rather than half of a deeper one.
34 *
35 * ---- LEGALITY IS LAZY, AND THAT IS WHERE THE SPEED IS ----------------------------
36 *
37 * The first version of this file called `gen_legal` at every node and searched
38 * 90,000 nodes a second, while perft over the same generator runs at 2.26 MILLION.
39 * The difference was not the evaluation, which was measured at 4 microseconds
40 * against a node cost of 11: it was that `gen_legal` plays and unplays all forty
41 * moves to filter them, and a node that takes a beta cutoff on its second move
42 * had paid for thirty-eight it never looked at.
43 *
44 * So the search generates PSEUDO-LEGAL moves and tests legality inside the loop,
45 * after `do_move`, on the moves it actually searches. The test is the same one
46 * `gen_legal` uses and is not a second opinion: own general not attacked, and the
47 * two generals not facing.
48 *
49 * The cost of this is that a node does not know whether it has NO legal move
50 * until the loop ends, so the mate and stalemate score moved to the bottom of the
51 * loop. At a horizon node, where the loop does not run at all, a side that is IN
52 * CHECK is still tested exactly, because `in_check` is a tenth of a microsecond
53 * and a missed mate is the one error the search may not make. A horizon
54 * STALEMATE, which is a loss in this game, is scored as an evaluation instead:
55 * the next iteration of the deepening sees it as an ordinary node and rules on
56 * it, and buying it one iteration earlier would cost a full filter at every leaf.
57 */
58  
59 #include <stdlib.h>
60 #include <string.h>
61 #include "xq_abi.h"
62  
63 5354793132 static const struct xq_abi *E(void) { return xq_abi_table(); }
64  
65 #define AT(b, pt) ((E())->at((b), (pt)))
66  
67 /* ---- the evaluation, four terms, integers only (D5) ----------------------------
68 *
69 * In centi-soldiers. `value_of` is phase 05's table and is used rather than a
70 * second one here, because `is_exchange` needs the same numbers and two tables
71 * would drift.
72 *
73 * THE VALUES, and their source: the conventional table every xiangqi primer
74 * gives, chariot 9, cannon 4.5, horse 4, advisor and elephant 2, soldier 1 and 2
75 * once across the river. Wikipedia's own endgame section qualifies it in ways
76 * the flat numbers cannot: three soldiers on the seventh rank are about a
77 * chariot, "in the opening and the middlegame ... the cannon is stronger since
78 * platforms are plentiful and the horse is often blocked", and five soldiers on
79 * the tenth rank cannot force mate at all. A phase-tapered table is the obvious
80 * later improvement and this is not it.
81 */
82  
83 #define MOBILITY_WEIGHT 2
84 #define ADVANCE_WEIGHT 4
85 #define OPEN_FILE_PENALTY 30
86 #define HOME_GUARD_BONUS 6
87  
88 /* =head2 material
89 *
90 * The term that dominates, and the only one that is not a heuristic. A soldier
91 * doubles once it is across the river, which is the one positional fact the
92 * material term carries itself because it is a rule rather than a judgement.
93 */
94 4957087 static int term_material(const struct xq_board *b, int side)
95 {
96 4957087 int pt, score = 0;
97 659292571 ▶ for (pt = 0; pt < XQ_CELLS; pt++) {
Branch: 1 branch
BranchTrueFalseTotal
for (pt = 0; pt < XQ_CELLS; pt++) { 654335484 4957087 659292571
98 int p, v;
99 654335484 ▶ if (!(E())->on_board(pt)) continue;
Branch: 1 branch
BranchTrueFalseTotal
if (!(E())->on_board(pt)) continue; 208197654 446137830 654335484
100 446137830 p = AT(b, pt);
101 446137830 ▶ if (!XQ_IS_PIECE(p)) continue;
Branch: 2 branches
BranchTrueFalseTotal
if (!XQ_IS_PIECE(p)) continue; 128798169 317339661 446137830
if (!XQ_IS_PIECE(p)) continue; 0 128798169 128798169
102 128798169 v = (E())->value_of(p);
103 128798169 ▶ if (XQ_KIND(p) == XQ_SOLDIER && (E())->crossed_river(pt, XQ_COLOUR(p)))
Branch: 2 branches
BranchTrueFalseTotal
if (XQ_KIND(p) == XQ_SOLDIER && (E())->crossed_river(pt, XQ_COLOUR(p))) 33908993 94889176 128798169
if (XQ_KIND(p) == XQ_SOLDIER && (E())->crossed_river(pt, XQ_COLOUR(p))) 2037611 31871382 33908993
104 2037611 v *= 2;
105 128798169 ▶ score += (XQ_COLOUR(p) == side) ? v : -v;
Branch: 1 branch
BranchTrueFalseTotal
score += (XQ_COLOUR(p) == side) ? v : -v; 64297496 64500673 128798169
106 }
107 4957087 return score;
108 }
109  
110 /* =head2 mobility
111 *
112 * Doing more work in this game than in chess, and that is why it is here at all.
113 * A horse with three legs blocked is worth nearly nothing and the material term
114 * cannot see it; a cannon with no screen in front of it is a chariot that cannot
115 * take. Counted as pseudo-legal moves, because the legality filter costs a do
116 * and an undo per move and the difference is noise at this weight.
117 */
118 4957087 static int term_mobility(struct xq_board *b, int side)
119 {
120 int buf[XQ_MAX_MOVES];
121 4957087 int keep = (E())->side(b);
122 int mine, theirs;
123  
124 4957087 (E())->set_side(b, side);
125 4957087 mine = (E())->gen_moves(b, buf);
126 4957087 ▶ (E())->set_side(b, XQ_OTHER(side));
Branch: 1 branch
BranchTrueFalseTotal
(E())->set_side(b, XQ_OTHER(side)); 2754376 2202711 4957087
127 4957087 theirs = (E())->gen_moves(b, buf);
128 4957087 (E())->set_side(b, keep);
129 4957087 return (mine - theirs) * MOBILITY_WEIGHT;
130 }
131  
132 /* =head2 the general's safety
133 *
134 * The palace's own term, and THE OPEN FILE IS THE ONE TO GET RIGHT because of
135 * the flying general: a general on a file with nothing in front of it is a
136 * general that can be answered by the enemy general alone, and every chariot and
137 * cannon on that file is worth more than its square suggests.
138 *
139 * Its advisors and elephants still at home are the other half, because they are
140 * the only pieces that can defend inside the palace at all.
141 */
142 9914174 static int term_general(const struct xq_board *b, int side)
143 {
144 9914174 int g = (E())->find(b, side | XQ_GENERAL);
145 9914174 int score = 0, pt, file, open = 1;
146  
147 9914174 ▶ if (!g) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (!g) return 0; 0 9914174 9914174
148 9914174 file = (E())->file_of(g);
149  
150 1318585142 ▶ for (pt = 0; pt < XQ_CELLS; pt++) {
Branch: 1 branch
BranchTrueFalseTotal
for (pt = 0; pt < XQ_CELLS; pt++) { 1308670968 9914174 1318585142
151 int p;
152 1308670968 ▶ if (!(E())->on_board(pt)) continue;
Branch: 1 branch
BranchTrueFalseTotal
if (!(E())->on_board(pt)) continue; 416395308 892275660 1308670968
153 892275660 p = AT(b, pt);
154 892275660 ▶ if (XQ_COLOUR(p) != side) continue;
Branch: 1 branch
BranchTrueFalseTotal
if (XQ_COLOUR(p) != side) continue; 763477491 128798169 892275660
155 128798169 ▶ if ((XQ_KIND(p) == XQ_ADVISOR || XQ_KIND(p) == XQ_ELEPHANT)
Branch: 2 branches
BranchTrueFalseTotal
if ((XQ_KIND(p) == XQ_ADVISOR || XQ_KIND(p) == XQ_ELEPHANT) 109649959 19148210 128798169
if ((XQ_KIND(p) == XQ_ADVISOR || XQ_KIND(p) == XQ_ELEPHANT) 18841053 90808906 109649959
156 37989263 ▶ && !(E())->crossed_river(pt, side))
Branch: 1 branch
BranchTrueFalseTotal
&& !(E())->crossed_river(pt, side)) 37989263 0 37989263
157 37989263 score += HOME_GUARD_BONUS;
158 128798169 ▶ if (pt != g && (E())->file_of(pt) == file) open = 0;
Branch: 2 branches
BranchTrueFalseTotal
if (pt != g && (E())->file_of(pt) == file) open = 0; 118883995 9914174 128798169
if (pt != g && (E())->file_of(pt) == file) open = 0; 9943239 108940756 118883995
159 }
160 9914174 ▶ if (open) score -= OPEN_FILE_PENALTY;
Branch: 1 branch
BranchTrueFalseTotal
if (open) score -= OPEN_FILE_PENALTY; 2601662 7312512 9914174
161 9914174 return score;
162 }
163  
164 /* =head2 soldier advance
165 *
166 * Counted BEYOND the crossing only, because the crossing itself is already in
167 * the material term and counting it twice would make a soldier stepping over
168 * the river look like winning a piece.
169 */
170 4957087 static int term_advance(const struct xq_board *b, int side)
171 {
172 4957087 int pt, score = 0;
173 659292571 ▶ for (pt = 0; pt < XQ_CELLS; pt++) {
Branch: 1 branch
BranchTrueFalseTotal
for (pt = 0; pt < XQ_CELLS; pt++) { 654335484 4957087 659292571
174 int p, r;
175 654335484 ▶ if (!(E())->on_board(pt)) continue;
Branch: 1 branch
BranchTrueFalseTotal
if (!(E())->on_board(pt)) continue; 208197654 446137830 654335484
176 446137830 p = AT(b, pt);
177 446137830 ▶ if (XQ_KIND(p) != XQ_SOLDIER) continue;
Branch: 1 branch
BranchTrueFalseTotal
if (XQ_KIND(p) != XQ_SOLDIER) continue; 412228837 33908993 446137830
178 33908993 ▶ if (!(E())->crossed_river(pt, XQ_COLOUR(p))) continue;
Branch: 1 branch
BranchTrueFalseTotal
if (!(E())->crossed_river(pt, XQ_COLOUR(p))) continue; 31871382 2037611 33908993
179 2037611 r = (E())->rank_of(pt);
180 2037611 ▶ r = (XQ_COLOUR(p) == XQ_RED) ? r - 5 : 4 - r;
Branch: 1 branch
BranchTrueFalseTotal
r = (XQ_COLOUR(p) == XQ_RED) ? r - 5 : 4 - r; 29602 2008009 2037611
181 2037611 ▶ score += (XQ_COLOUR(p) == side) ? r * ADVANCE_WEIGHT : -r * ADVANCE_WEIGHT;
Branch: 1 branch
BranchTrueFalseTotal
score += (XQ_COLOUR(p) == side) ? r * ADVANCE_WEIGHT : -r * ADVANCE_WEIGHT; 818462 1219149 2037611
182 }
183 4957087 return score;
184 }
185  
186 4957087 static int xq_evaluate(struct xq_board *b)
187 {
188 4957087 int side = (E())->side(b);
189 4957087 return term_material(b, side)
190 4957087 + term_mobility(b, side)
191 4957087 ▶ + term_general(b, side) - term_general(b, XQ_OTHER(side))
Branch: 1 branch
BranchTrueFalseTotal
+ term_general(b, side) - term_general(b, XQ_OTHER(side)) 2754376 2202711 4957087
192 4957087 + term_advance(b, side);
193 }
194  
195 /* ---- the transposition table ------------------------------------------------------
196 *
197 * ALLOCATED PER SEARCH AND FREED AFTER IT. Chess/Bot.pm measured Plisco's at
198 * about 2.5 times its megabytes in RSS, which on a pre-forked web worker is the
199 * kind of thing that is paid once per worker and never given back.
200 */
201 #define TT_BITS 16
202 #define TT_SIZE (1 << TT_BITS)
203  
204 #define TT_EXACT 1
205 #define TT_LOWER 2
206 #define TT_UPPER 3
207  
208 struct tt_entry {
209 unsigned long long key;
210 int move;
211 short score;
212 signed char depth;
213 unsigned char flag;
214 };
215  
216 struct search {
217 unsigned long long nodes;
218 unsigned long long budget;
219 int stopped;
220 struct tt_entry *tt;
221 unsigned int seed;
222 };
223  
224 /* ---- move ordering ------------------------------------------------------------------
225 *
226 * The transposition move first, then captures by what they take. No killers and
227 * no history in this version, deliberately: they are cheap to add later and
228 * their ABSENCE is easy to measure, where their presence hides how much the rest
229 * of the ordering is doing.
230 */
231 2773532 static void order(struct xq_board *b, int *moves, int n, int tt_move)
232 {
233 int score[XQ_MAX_MOVES];
234 int i, j;
235 101554533 ▶ for (i = 0; i < n; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < n; i++) { 98781001 2773532 101554533
236 98781001 int victim = AT(b, (E())->move_to(moves[i]));
237 98781001 int mover = AT(b, (E())->move_from(moves[i]));
238 98781001 score[i] = (moves[i] == tt_move) ? 1000000
239 201978081 ▶ : XQ_IS_PIECE(victim)
Branch: 2 branches
BranchTrueFalseTotal
: XQ_IS_PIECE(victim) 98717472 63529 98781001
: XQ_IS_PIECE(victim) 4479608 0 4479608
240 4479608 ? 1000 + (E())->value_of(victim) - (E())->value_of(mover) / 10
241 103197080 ▶ : 0;
Branch: 1 branch
BranchTrueFalseTotal
: 0; 4479608 94237864 98717472
242 }
243 98781001 ▶ for (i = 1; i < n; i++) { /* insertion sort: n is small and it is stable */
Branch: 1 branch
BranchTrueFalseTotal
for (i = 1; i < n; i++) { /* insertion sort: n is small and it is stable */ 96007469 2773532 98781001
244 96007469 int m = moves[i], sc = score[i];
245 182664984 ▶ for (j = i - 1; j >= 0 && score[j] < sc; j--) {
Branch: 2 branches
BranchTrueFalseTotal
for (j = i - 1; j >= 0 && score[j] < sc; j--) { 179716520 2948464 182664984
for (j = i - 1; j >= 0 && score[j] < sc; j--) { 86657515 93059005 179716520
246 86657515 moves[j + 1] = moves[j];
247 86657515 score[j + 1] = score[j];
248 }
249 96007469 moves[j + 1] = m;
250 96007469 score[j + 1] = sc;
251 }
252 2773532 }
253  
254 /* The legality test, AFTER a move has been played, for the side that played it.
255 * It is `gen_legal`'s own test and not a second opinion: if these two ever
256 * disagreed the search would search moves the facade refuses, and the bot would
257 * offer the site a move the site rejects.
258 *
259 * AND IT IS ONE CALL, NOT TWO. This read `!in_check(b, us) && !generals_face(b)`
260 * for most of phase 09, mirroring `gen_legal` line for line, and the second half
261 * was DEAD: `in_check` already carries the flying-general rule, and returns true
262 * for BOTH sides when the two generals see each other down an open file. Note that
263 * `attacked` does not, which is why the redundancy was not obvious from reading it.
264 *
265 * Found by a mutation that dropped the second call and which NOTHING caught, at
266 * which point the question stopped being "where is the missing test" and became
267 * "is this a mutation at all". It was not. Proved by measurement and not by
268 * argument: with the call and without it, a 400,000-node search explores
269 * 400,384 nodes either way, reaches the same depth, returns the same move, and
270 * twenty self-played moves are identical. Removing it is 5.5% faster, which at one
271 * call per searched node is worth having.
272 *
273 * `gen_legal` in xq_moves.c keeps its explicit call. It is the perft path and the
274 * oracle runs through it, so it is not being touched for 5.5% on a different
275 * function. */
276 5758772 static int legal_after(struct xq_board *b, int us)
277 {
278 5758772 return !(E())->in_check(b, us);
279 }
280  
281 /* THE ROOT LIST IS SHUFFLED BY THE SEED, ONCE, BEFORE ANYTHING IS SEARCHED.
282 *
283 * This is the whole tie-break. Only a STRICT improvement takes the move at the
284 * root, so the move that wins is the first one to reach the best score, and a
285 * random starting order makes "first to reach it" a uniform draw among the moves
286 * that genuinely tie. It costs no nodes at all, where scoring every root move
287 * exactly costs a ply.
288 *
289 * THE SEAT IS IN THE SEED and the caller puts it there. Without it both bots in a
290 * bot-versus-bot game shuffle identically, open identically every time, and a
291 * soak measures nothing: Game::Goofspiel shipped exactly that.
292 *
293 * splitmix32 rather than rand(): the engine is deterministic given its seed, and
294 * a bot game that cannot be replayed move for move breaks the site's whole
295 * verification story.
296 */
297 526 static void shuffle(int *moves, int n, unsigned int seed)
298 {
299 int i;
300 526 ▶ unsigned int x = seed ? seed : 0x9E3779B9u;
Branch: 1 branch
BranchTrueFalseTotal
unsigned int x = seed ? seed : 0x9E3779B9u; 496 30 526
301 18890 ▶ for (i = n - 1; i > 0; i--) {
Branch: 1 branch
BranchTrueFalseTotal
for (i = n - 1; i > 0; i--) { 18364 526 18890
302 unsigned int z;
303 int j, t;
304 18364 x += 0x9E3779B9u;
305 18364 z = x;
306 18364 z = (z ^ (z >> 16)) * 0x21F0AAADu;
307 18364 z = (z ^ (z >> 15)) * 0x735A2D97u;
308 18364 z = z ^ (z >> 15);
309 18364 j = (int) (z % (unsigned int) (i + 1));
310 18364 t = moves[i]; moves[i] = moves[j]; moves[j] = t;
311 }
312 526 }
313  
314 /* THE BUDGET CHECK IS NEVER DISABLED, NOT EVEN FOR THE FIRST ITERATION, and that
315 * is a fact learned the hard way. `quiesce` is bounded by NOTHING ELSE: it
316 * searches captures, and captures do reduce material, but the branching is wide
317 * enough that a tactical position explodes. An attempt to guarantee that the
318 * first iteration always completes, by gating this check off until the root had
319 * one full iteration in hand, HUNG THE SEARCH on the opening position. A budget
320 * that can be switched off is not a budget. */
321 7762090 static int spent(struct search *s)
322 {
323 7762090 ▶ if (s->stopped) return 1;
Branch: 1 branch
BranchTrueFalseTotal
if (s->stopped) return 1; 0 7762090 7762090
324 7762090 ▶ if ((s->nodes & 1023) == 0 && s->nodes >= s->budget) s->stopped = 1;
Branch: 2 branches
BranchTrueFalseTotal
if ((s->nodes & 1023) == 0 && s->nodes >= s->budget) s->stopped = 1; 7576 7754514 7762090
if ((s->nodes & 1023) == 0 && s->nodes >= s->budget) s->stopped = 1; 506 7070 7576
325 7762090 return s->stopped;
326 }
327  
328 /* ---- quiescence ---------------------------------------------------------------------
329 *
330 * Captures only. Without it the search hands back a score taken in the middle of
331 * an exchange, which in this game is worse than in chess: a cannon's capture
332 * arrives from a distance and over a screen, so a quiet-looking position is
333 * routinely one move from losing a chariot.
334 */
335 4956433 static int quiesce(struct xq_board *b, struct search *s, int alpha, int beta)
336 {
337 int moves[XQ_MAX_MOVES];
338 4956433 int n, i, best, us = (E())->side(b);
339  
340 4956433 s->nodes++;
341 4956433 ▶ if (spent(s)) return xq_evaluate(b);
Branch: 1 branch
BranchTrueFalseTotal
if (spent(s)) return xq_evaluate(b); 355 4956078 4956433
342  
343 4956078 best = xq_evaluate(b);
344 4956078 ▶ if (best >= beta) return best;
Branch: 1 branch
BranchTrueFalseTotal
if (best >= beta) return best; 2549759 2406319 4956078
345 2406319 ▶ if (best > alpha) alpha = best;
Branch: 1 branch
BranchTrueFalseTotal
if (best > alpha) alpha = best; 316571 2089748 2406319
346  
347 2406319 n = (E())->gen_moves(b, moves);
348 2406319 order(b, moves, n, 0);
349 51537623 ▶ for (i = 0; i < n; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < n; i++) { 50094270 1443353 51537623
350 struct xq_undo u;
351 int score;
352 50094270 ▶ if (!XQ_IS_PIECE(AT(b, (E())->move_to(moves[i])))) continue; /* captures only */
Branch: 2 branches
BranchTrueFalseTotal
if (!XQ_IS_PIECE(AT(b, (E())->move_to(moves[i])))) continue; /* captures only */ 2703689 47390581 50094270
if (!XQ_IS_PIECE(AT(b, (E())->move_to(moves[i])))) continue; /* captures only */ 0 2703689 2703689
353 2703689 (E())->do_move(b, moves[i], &u);
354 2703689 ▶ if (legal_after(b, us)) {
Branch: 1 branch
BranchTrueFalseTotal
if (legal_after(b, us)) { 2570958 132731 2703689
355 2570958 score = -quiesce(b, s, -beta, -alpha);
356 2570958 (E())->undo_move(b, &u);
357 2570958 ▶ if (s->stopped) return best;
Branch: 1 branch
BranchTrueFalseTotal
if (s->stopped) return best; 496 2570462 2570958
358 2570462 ▶ if (score > best) best = score;
Branch: 1 branch
BranchTrueFalseTotal
if (score > best) best = score; 1708623 861839 2570462
359 2570462 ▶ if (best > alpha) alpha = best;
Branch: 1 branch
BranchTrueFalseTotal
if (best > alpha) alpha = best; 1115943 1454519 2570462
360 2570462 ▶ if (alpha >= beta) break;
Branch: 1 branch
BranchTrueFalseTotal
if (alpha >= beta) break; 962470 1607992 2570462
361 }
362 132731 else (E())->undo_move(b, &u);
363 }
364 2405823 return best;
365 }
366  
367 /* ---- the search ------------------------------------------------------------------- */
368  
369 2805657 static int alphabeta(struct xq_board *b, struct search *s,
370 int depth, int alpha, int beta, int ply)
371 {
372 int moves[XQ_MAX_MOVES];
373 2805657 int n, i, best = -XQ_MATE_SCORE * 2, tt_move = 0;
374 2805657 int alpha0 = alpha, played = 0, us = (E())->side(b);
375 2805657 unsigned long long key = (E())->key(b);
376 2805657 struct tt_entry *e = &s->tt[key & (TT_SIZE - 1)];
377  
378 2805657 s->nodes++;
379 2805657 ▶ if (spent(s)) return xq_evaluate(b);
Branch: 1 branch
BranchTrueFalseTotal
if (spent(s)) return xq_evaluate(b); 151 2805506 2805657
380  
381 2805506 ▶ if (e->key == key) {
Branch: 1 branch
BranchTrueFalseTotal
if (e->key == key) { 114779 2690727 2805506
382 114779 tt_move = e->move;
383 114779 ▶ if (e->depth >= depth) {
Branch: 1 branch
BranchTrueFalseTotal
if (e->depth >= depth) { 53629 61150 114779
384 53629 ▶ if (e->flag == TT_EXACT) return e->score;
Branch: 1 branch
BranchTrueFalseTotal
if (e->flag == TT_EXACT) return e->score; 615 53014 53629
385 53014 ▶ 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; 51452 1562 53014
if (e->flag == TT_LOWER && e->score > alpha) alpha = e->score; 51231 221 51452
386 53014 ▶ 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; 1562 51452 53014
if (e->flag == TT_UPPER && e->score < beta) beta = e->score; 1339 223 1562
387 53014 ▶ if (alpha >= beta) return e->score;
Branch: 1 branch
BranchTrueFalseTotal
if (alpha >= beta) return e->score; 51803 1211 53014
388 }
389 }
390  
391 /* At the horizon the loop below never runs, so a mate would go unseen. A side
392 * IN CHECK is therefore tested exactly, which costs a tenth of a microsecond
393 * for the test and a full filter only on the nodes that are actually in
394 * check. See the head of this file for the stalemate that is not tested. */
395 2753088 ▶ if (depth <= 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (depth <= 0) { 2387616 365472 2753088
396 2387616 ▶ if ((E())->in_check(b, us)) {
Branch: 1 branch
BranchTrueFalseTotal
if ((E())->in_check(b, us)) { 65848 2321768 2387616
397 int esc[XQ_MAX_MOVES];
398 65848 ▶ if ((E())->gen_legal(b, esc) == 0) return -XQ_MATE_SCORE + ply;
Branch: 1 branch
BranchTrueFalseTotal
if ((E())->gen_legal(b, esc) == 0) return -XQ_MATE_SCORE + ply; 2141 63707 65848
399 }
400 2385475 return quiesce(b, s, alpha, beta);
401 }
402  
403 365472 n = (E())->gen_moves(b, moves);
404 365472 order(b, moves, n, tt_move);
405 3119516 ▶ for (i = 0; i < n; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < n; i++) { 3055083 64433 3119516
406 struct xq_undo u;
407 int score;
408 3055083 (E())->do_move(b, moves[i], &u);
409 3055083 ▶ if (!legal_after(b, us)) { (E())->undo_move(b, &u); continue; }
Branch: 1 branch
BranchTrueFalseTotal
if (!legal_after(b, us)) { (E())->undo_move(b, &u); continue; } 297382 2757701 3055083
410 2757701 played++;
411 2757701 score = -alphabeta(b, s, depth - 1, -beta, -alpha, ply + 1);
412 2757701 (E())->undo_move(b, &u);
413 2757701 ▶ if (s->stopped) return best > -XQ_MATE_SCORE * 2 ? best : xq_evaluate(b);
Branch: 2 branches
BranchTrueFalseTotal
if (s->stopped) return best > -XQ_MATE_SCORE * 2 ? best : xq_evaluate(b); 1182 2756519 2757701
if (s->stopped) return best > -XQ_MATE_SCORE * 2 ? best : xq_evaluate(b); 452 730 1182
414 2756519 ▶ if (score > best) { best = score; tt_move = moves[i]; }
Branch: 1 branch
BranchTrueFalseTotal
if (score > best) { best = score; tt_move = moves[i]; } 572502 2184017 2756519
415 2756519 ▶ if (best > alpha) alpha = best;
Branch: 1 branch
BranchTrueFalseTotal
if (best > alpha) alpha = best; 392133 2364386 2756519
416 2756519 ▶ if (alpha >= beta) break;
Branch: 1 branch
BranchTrueFalseTotal
if (alpha >= beta) break; 299857 2456662 2756519
417 }
418  
419 /* NO LEGAL MOVE IS A LOSS, in check or not: stalemate is a loss in this game
420 * and a search that returned a draw here would play for one. The score is
421 * adjusted by PLY so a mate in one beats a mate in three. */
422 364290 ▶ if (!played) return -XQ_MATE_SCORE + ply;
Branch: 1 branch
BranchTrueFalseTotal
if (!played) return -XQ_MATE_SCORE + ply; 827 363463 364290
423  
424 /* FAIL-SOFT: `best` is returned, never `alpha`. See the head of this file. */
425 363463 e->key = key;
426 363463 e->move = tt_move;
427 363463 ▶ e->score = (short) (best > 32000 ? 32000 : best < -32000 ? -32000 : best);
Branch: 2 branches
BranchTrueFalseTotal
e->score = (short) (best > 32000 ? 32000 : best < -32000 ? -32000 : best); 363463 0 363463
e->score = (short) (best > 32000 ? 32000 : best < -32000 ? -32000 : best); 363463 0 363463
428 363463 e->depth = (signed char) depth;
429 363463 ▶ e->flag = (unsigned char) (best <= alpha0 ? TT_UPPER
Branch: 2 branches
BranchTrueFalseTotal
e->flag = (unsigned char) (best <= alpha0 ? TT_UPPER 307815 55648 363463
e->flag = (unsigned char) (best <= alpha0 ? TT_UPPER 299857 7958 307815
430 : best >= beta ? TT_LOWER : TT_EXACT);
431 363463 return best;
432 }
433  
434 /* ONE SEARCH, TWO ENTRIES. `search_best` is this with the depth ceiling, so the
435 * depth-limited search that UCCI needs cannot drift away from the one the bot
436 * plays. See the header on why a depth limit exists at all. */
437 527 static int xq_search_to_depth(struct xq_board *b, int max_depth,
438 unsigned long long budget,
439 unsigned int seed, struct xq_search_info *info)
440 {
441 int moves[XQ_MAX_MOVES];
442 int n, i, depth;
443 527 int best_move = 0, best_score = 0;
444 struct search s;
445  
446 527 ▶ if (info) { info->nodes = 0; info->depth = 0; info->score = 0; info->stopped = 0; }
Branch: 1 branch
BranchTrueFalseTotal
if (info) { info->nodes = 0; info->depth = 0; info->score = 0; info->stopped = 0; } 527 0 527
447  
448 527 n = (E())->gen_legal(b, moves);
449 527 ▶ if (n == 0) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (n == 0) return 0; 1 526 527
450  
451 526 s.nodes = 0;
452 526 ▶ s.budget = budget ? budget : 1;
Branch: 1 branch
BranchTrueFalseTotal
s.budget = budget ? budget : 1; 526 0 526
453 526 s.stopped = 0;
454 526 s.seed = seed;
455 526 s.tt = (struct tt_entry *) calloc(TT_SIZE, sizeof(struct tt_entry));
456 526 ▶ if (!s.tt) return moves[0];
Branch: 1 branch
BranchTrueFalseTotal
if (!s.tt) return moves[0]; 0 526 526
457  
458 /* SHUFFLED FIRST, so that a budget too small to finish even depth 1 still
459 * hands back a move drawn by the seed rather than whatever the generator
460 * happened to put first. See `shuffle`. */
461 526 shuffle(moves, n, seed);
462 526 best_move = moves[0];
463  
464 /* ITERATIVE DEEPENING, so a spent budget always leaves a COMPLETE search at
465 * a shallower depth rather than half of a deeper one. */
466 526 ▶ if (max_depth < 1) max_depth = 1;
Branch: 1 branch
BranchTrueFalseTotal
if (max_depth < 1) max_depth = 1; 0 526 526
467 526 ▶ if (max_depth > 64) max_depth = 64;
Branch: 1 branch
BranchTrueFalseTotal
if (max_depth > 64) max_depth = 64; 0 526 526
468  
469 1747 ▶ for (depth = 1; depth <= max_depth; depth++) {
Branch: 1 branch
BranchTrueFalseTotal
for (depth = 1; depth <= max_depth; depth++) { 1741 6 1747
470 int scores[XQ_MAX_MOVES];
471 1741 int local_best = -XQ_MATE_SCORE * 2, alpha = -XQ_MATE_SCORE * 2;
472  
473 1741 order(b, moves, n, best_move);
474 49191 ▶ for (i = 0; i < n; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < n; i++) { 47956 1235 49191
475 struct xq_undo u;
476 47956 (E())->do_move(b, moves[i], &u);
477  
478 47956 scores[i] = -alphabeta(b, &s, depth - 1, -XQ_MATE_SCORE * 2, -alpha, 1);
479 47956 (E())->undo_move(b, &u);
480 47956 ▶ if (s.stopped) break;
Branch: 1 branch
BranchTrueFalseTotal
if (s.stopped) break; 506 47450 47956
481  
482 /* STRICTLY GREATER, AND THE TIE-BREAK IS THE SHUFFLE ABOVE.
483 *
484 * THIS IS THE PHASE'S SECOND BUG AND THE COMMENT THAT USED TO BE HERE
485 * CLAIMED THE OPPOSITE OF WHAT THE CODE DID. The root raised `alpha`,
486 * which is ordinary alpha-beta and right, and then pooled every
487 * `scores[i]` equal to the best and picked among them with the seed,
488 * which is wrong: with the window cut at `-alpha` a root move that is
489 * not an improvement makes its child fail high, and a fail-soft child
490 * that fails high returns a BOUND and not a value. With an integer
491 * evaluation that bound lands EXACTLY on alpha very often, so the pool
492 * filled with moves that were merely not-better and the bot played one
493 * of them at random.
494 *
495 * It got WORSE WITH DEPTH, because a deeper search raises alpha sooner
496 * and cuts more children off at the bound. Measured, sixty games:
497 * rung 40000 scored 38.3% against rung 8000, and 13 of the 44 opening
498 * moves came back "tied". That is Game::Oware's bug in a different
499 * hat, and the paragraph at the head of this file was written to
500 * prevent it and did not.
501 *
502 * The fix is not a full window, which was tried and costs a whole ply
503 * of depth at every rung. It is that A TIE IS NEVER PICKED AT ALL:
504 * only a STRICT improvement replaces the move, so the move that wins
505 * is the FIRST one to reach the best score. The root list is shuffled
506 * by the seed before the search, and `order` below is a stable sort,
507 * so first-to-reach-it IS a uniform draw among the moves that truly
508 * tie. No extra nodes, and the bound never enters the choice. */
509 47450 ▶ if (scores[i] > local_best) {
Branch: 1 branch
BranchTrueFalseTotal
if (scores[i] > local_best) { 3182 44268 47450
510 3182 local_best = scores[i];
511 3182 best_move = moves[i];
512 }
513 47450 ▶ if (local_best > alpha) alpha = local_best;
Branch: 1 branch
BranchTrueFalseTotal
if (local_best > alpha) alpha = local_best; 3182 44268 47450
514 }
515 1755 ▶ if (s.stopped) break;
Branch: 1 branch
BranchTrueFalseTotal
if (s.stopped) break; 506 1235 1741
516  
517 1235 ▶ if (info) { info->depth = depth; info->score = local_best; }
Branch: 1 branch
BranchTrueFalseTotal
if (info) { info->depth = depth; info->score = local_best; } 1235 0 1235
518 1235 ▶ if (XQ_IS_MATE(local_best)) break; /* nothing deeper can improve on mate */
Branch: 2 branches
BranchTrueFalseTotal
if (XQ_IS_MATE(local_best)) break; /* nothing deeper can improve on mate */ 1221 14 1235
if (XQ_IS_MATE(local_best)) break; /* nothing deeper can improve on mate */ 1221 0 1221
519 }
520  
521 526 free(s.tt);
522 526 ▶ if (info) { info->nodes = s.nodes; info->stopped = s.stopped; }
Branch: 1 branch
BranchTrueFalseTotal
if (info) { info->nodes = s.nodes; info->stopped = s.stopped; } 526 0 526
523 (void) best_score;
524 526 return best_move;
525 }
526  
527 /* ---- installed into the table by xq_engine.c ---------------------------------------- */
528  
529 521 static int xq_search_best(struct xq_board *b, unsigned long long budget,
530 unsigned int seed, struct xq_search_info *info)
531 {
532 521 return xq_search_to_depth(b, 64, budget, seed, info);
533 }
534  
535 void xq_search_install(struct xq_abi *t);
536  
537 24 void xq_search_install(struct xq_abi *t)
538 {
539 24 t->evaluate = xq_evaluate;
540 24 t->search_best = xq_search_best;
541 24 t->search_to_depth = xq_search_to_depth;
542 24 }
« xq_moves.c ↑ Summary xq_mate.c »