fn_search.c

filter: Statementstmt 97.9% 192 / 196 Branchbran 87.2% 192 / 220 Conditioncond n/a MC/DCmcdc n/a Subroutinesub n/a Podpod n/a totaltotal 92.3% 384 / 416 CC 0 SCAR 0
CC
0
Cov
0%
CRAP 0
« fn_moves.c ↑ Summary fn_engine.c »
1 /* fn_search.c - choosing a move: an evaluation, and a search bounded in nodes.
2 *
3 * PERL-FREE, as the other files are, and INTEGER ONLY: no float is declared
4 * here and no clock is read. The same position, budget and seed give the same
5 * move on every machine.
6 *
7 * THE SEARCH WALKS STEPS, NOT MOVES. A position can have thousands of whole
8 * moves and never more than a couple of hundred steps, so a node here is a
9 * position, possibly with a chain open, and its children are the steps that
10 * may be made next. Inside a chain the same side is still to move, so the
11 * score is not negated there; and stopping is a child like any other.
12 *
13 * DEPTH IS COUNTED IN WHOLE MOVES. A chain of five steps costs one. The
14 * depth goes down when the turn passes and at no other time.
15 *
16 * AT THE END OF ITS DEPTH THE SEARCH DOES NOT SCORE A POSITION IN WHICH A STONE
17 * CAN BE TAKEN. Taking is compulsory, so that is not a position anyone may sit
18 * in. But it does not SEARCH the captures either: in the opening they cascade
19 * for twenty moves with a choice at every step and a stop after every step,
20 * and a search that followed all of it never came back from its first move.
21 * It SETTLES the position instead: each side in turn makes the capture that
22 * takes most, step by step, until the side to move has only quiet moves or a
23 * few moves have been made, and that is the position scored. It is one line
24 * and not a tree, so it costs a handful of steps; it is a guess at how the
25 * exchange comes out and not a proof, and it is what stops the search
26 * counting a stone that is about to be taken.
27 */
28  
29 #include <stdlib.h>
30 #include <string.h>
31 #include "fn_abi.h"
32  
33 static const struct fn_abi *T = NULL;
34  
35 /* ---- the weights --------------------------------------------------------------- */
36  
37 4960 static void fn_weights_default(struct fn_weights *w)
38 {
39 4960 ▶ if (!w) return;
Branch: 1 branch
BranchTrueFalseTotal
if (!w) return; 0 4960 4960
40 4960 memset(w, 0, sizeof(*w));
41 /* MEASURED, each term at 2,000 games against the terms already in, and
42 * kept only if it earned three standard deviations. Room to move and
43 * standing towards the centre did. Standing on a strong point did by
44 * itself and did NOT once the other two were in, so it is here to be
45 * given a weight and is given none. */
46 4960 w->stone = 100;
47 4960 w->strong = 0;
48 4960 w->centre = 2;
49 4960 w->room = 2;
50 }
51  
52 2004793 static const struct fn_weights *weights_or_default(const struct fn_weights *w)
53 {
54 static struct fn_weights def;
55 static int ready = 0;
56 2004793 ▶ if (w) return w;
Branch: 1 branch
BranchTrueFalseTotal
if (w) return w; 2004793 0 2004793
57 0 ▶ if (!ready) { fn_weights_default(&def); ready = 1; }
Branch: 1 branch
BranchTrueFalseTotal
if (!ready) { fn_weights_default(&def); ready = 1; } 0 0 0
58 0 return &def;
59 }
60  
61 /* ---- the evaluation --------------------------------------------------------------
62 *
63 * For White. Each term is counted for White's stones and against Black's.
64 */
65  
66 2002341 static int fn_evaluate(const struct fn_board *b, const struct fn_weights *w)
67 {
68 2002341 int cols = (T->cols)(b), rows = (T->rows)(b);
69 2002341 int mid_file = cols / 2, mid_rank = rows / 2;
70 2002341 int rank, file, d, score = 0;
71 2002341 w = weights_or_default(w);
72 12012420 ▶ for (rank = 0; rank < rows; rank++) {
Branch: 1 branch
BranchTrueFalseTotal
for (rank = 0; rank < rows; rank++) { 10010079 2002341 12012420
73 100086156 ▶ for (file = 0; file < cols; file++) {
Branch: 1 branch
BranchTrueFalseTotal
for (file = 0; file < cols; file++) { 90076077 10010079 100086156
74 90076077 int sq = (T->square_of)(file, rank);
75 90076077 int stone = (T->at)(b, sq);
76 int worth, df, dr;
77 90076077 ▶ if (!FN_IS_STONE(stone)) continue;
Branch: 2 branches
BranchTrueFalseTotal
if (!FN_IS_STONE(stone)) continue; 86740597 3335480 90076077
if (!FN_IS_STONE(stone)) continue; 84265692 2474905 86740597
78 5810385 worth = w->stone;
79 5810385 ▶ if (w->strong && (T->is_strong)(sq)) worth += w->strong;
Branch: 2 branches
BranchTrueFalseTotal
if (w->strong && (T->is_strong)(sq)) worth += w->strong; 4 5810381 5810385
if (w->strong && (T->is_strong)(sq)) worth += w->strong; 3 1 4
80 5810385 ▶ if (w->centre) {
Branch: 1 branch
BranchTrueFalseTotal
if (w->centre) { 5810375 10 5810385
81 5810375 ▶ df = file > mid_file ? file - mid_file : mid_file - file;
Branch: 1 branch
BranchTrueFalseTotal
df = file > mid_file ? file - mid_file : mid_file - file; 2700775 3109600 5810375
82 5810375 ▶ dr = rank > mid_rank ? rank - mid_rank : mid_rank - rank;
Branch: 1 branch
BranchTrueFalseTotal
dr = rank > mid_rank ? rank - mid_rank : mid_rank - rank; 2653796 3156579 5810375
83 5810375 worth += w->centre * ((mid_file - df) + (mid_rank - dr));
84 }
85 5810385 ▶ if (w->room) {
Branch: 1 branch
BranchTrueFalseTotal
if (w->room) { 5810375 10 5810385
86 52293375 ▶ for (d = 0; d < FN_DIRS; d++) {
Branch: 1 branch
BranchTrueFalseTotal
for (d = 0; d < FN_DIRS; d++) { 46483000 5810375 52293375
87 46483000 int to = (T->next)(b, sq, d);
88 46483000 ▶ if (to >= 0 && (T->at)(b, to) == FN_EMPTY) worth += w->room;
Branch: 2 branches
BranchTrueFalseTotal
if (to >= 0 && (T->at)(b, to) == FN_EMPTY) worth += w->room; 29720989 16762011 46483000
if (to >= 0 && (T->at)(b, to) == FN_EMPTY) worth += w->room; 28353271 1367718 29720989
89 }
90 }
91 5810385 ▶ score += stone == FN_WHITE ? worth : -worth;
Branch: 1 branch
BranchTrueFalseTotal
score += stone == FN_WHITE ? worth : -worth; 2474905 3335480 5810385
92 }
93 }
94 2002341 return score;
95 }
96  
97 /* ---- the table of positions already searched ------------------------------------ */
98  
99 #define TT_EXACT 0
100 #define TT_LOWER 1
101 #define TT_UPPER 2
102  
103 struct tt_entry {
104 unsigned long long key;
105 int score;
106 short depth;
107 unsigned char flag;
108 unsigned char used;
109 short from;
110 unsigned char dir;
111 unsigned char kind;
112 };
113  
114 #define FN_INF (FN_WIN_SCORE + 1000)
115 #define FN_DEPTH_MAX 60
116  
117 /* how deep one line may run in STEPS: the bound on the recursion */
118 #define FN_LINE_STEPS 512
119  
120 struct ctx {
121 struct fn_game *g;
122 const struct fn_weights *w;
123 unsigned long long nodes, budget, seed;
124 int may_stop;
125 int stopped;
126 struct tt_entry *tt;
127 size_t mask;
128 };
129  
130 74715 static unsigned long long mix(unsigned long long z)
131 {
132 74715 z += 0x9E3779B97F4A7C15ULL;
133 74715 z = (z ^ (z >> 30)) * 0xBF58476D1CE4E5B9ULL;
134 74715 z = (z ^ (z >> 27)) * 0x94D049BB133111EBULL;
135 74715 return z ^ (z >> 31);
136 }
137  
138 /* THE ORDER STEPS ARE TRIED IN: the step the table remembers, then the steps
139 * that take most. It changes how many nodes a search costs and never which
140 * move a search to a fixed depth returns, apart from the choice among moves of
141 * equal score, which `salt` settles at the root and a test holds to that. */
142 1589126 static void order_steps(struct fn_step *list, int n, const struct tt_entry *e, unsigned long long salt)
143 {
144 int key[FN_STEPS_MAX];
145 int i, j;
146 9583796 ▶ for (i = 0; i < n; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < n; i++) { 7994670 1589126 9583796
147 7994670 int k = list[i].taken_n * 1000;
148 7994670 ▶ if (e && e->used && e->from == list[i].from && e->dir == list[i].dir && e->kind == list[i].kind) k += 100000;
Branch: 5 branches
BranchTrueFalseTotal
if (e && e->used && e->from == list[i].from && e->dir == list[i].dir && e->kind == list[i].kind) k += 100000; 3596996 4397674 7994670
if (e && e->used && e->from == list[i].from && e->dir == list[i].dir && e->kind == list[i].kind) k += 100000; 3596996 0 3596996
if (e && e->used && e->from == list[i].from && e->dir == list[i].dir && e->kind == list[i].kind) k += 100000; 3153616 443380 3596996
if (e && e->used && e->from == list[i].from && e->dir == list[i].dir && e->kind == list[i].kind) k += 100000; 606161 2547455 3153616
if (e && e->used && e->from == list[i].from && e->dir == list[i].dir && e->kind == list[i].kind) k += 100000; 605986 175 606161
149 7994670 ▶ if (salt) {
Branch: 1 branch
BranchTrueFalseTotal
if (salt) { 74715 7919955 7994670
150 74715 unsigned long long id = ((unsigned long long) list[i].from << 8) | ((unsigned long long) list[i].dir << 4) | (unsigned long long) list[i].kind;
151 74715 k += (int) (mix(salt ^ (id * 0x100000001B3ULL)) & 0xFF);
152 }
153 7994670 key[i] = k;
154 }
155 7994670 ▶ for (i = 1; i < n; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (i = 1; i < n; i++) { 6405544 1589126 7994670
156 6405544 struct fn_step s = list[i];
157 6405544 int k = key[i];
158 7455728 ▶ 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]; } 7094705 361023 7455728
for (j = i - 1; j >= 0 && key[j] < k; j--) { list[j + 1] = list[j]; key[j + 1] = key[j]; } 1050184 6044521 7094705
159 6405544 list[j + 1] = s; key[j + 1] = k;
160 }
161 1589126 }
162  
163 /* A finished game, scored for the side to move. */
164 227591 static int score_of_end(const struct ctx *c, int side, int ply)
165 {
166 227591 int winner = (T->game_winner)(c->g);
167 227591 ▶ if (!winner) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (!winner) return 0; 895 226696 227591
168 226696 ▶ return winner == side ? FN_WIN_SCORE - ply : -(FN_WIN_SCORE - ply);
Branch: 1 branch
BranchTrueFalseTotal
return winner == side ? FN_WIN_SCORE - ply : -(FN_WIN_SCORE - ply); 0 226696 226696
169 }
170  
171 /* THE SETTLING. From a position between moves in which the side to move can
172 * take: play the largest capture, step by step, for each side in turn, until
173 * nobody can take or FN_SETTLE_MOVES moves have been made; score what is left
174 * for the side that was to move at the start; and take it all back. */
175 #define FN_SETTLE_MOVES 6
176  
177 /* what an ending met while settling is worth: more than any count of stones,
178 * and well short of the scores that mean a win has been proved */
179 #define FN_SETTLED_WIN 20000
180  
181 353570 static int settle(struct ctx *c)
182 {
183 struct fn_step list[FN_STEPS_MAX];
184 353570 int side = (T->side)((T->game_board)(c->g));
185 353570 int made = 0, moves = 0, score;
186 949609 for (;;) {
187 1303179 const struct fn_board *b = (T->game_board)(c->g);
188 1303179 int n, i, pick = 0;
189 1303179 ▶ if ((T->game_outcome)(c->g) != FN_ONGOING) break;
Branch: 1 branch
BranchTrueFalseTotal
if ((T->game_outcome)(c->g) != FN_ONGOING) break; 197656 1105523 1303179
190 1105523 n = (T->game_steps)(c->g, list, FN_STEPS_MAX);
191 1105523 ▶ if (n > FN_STEPS_MAX) n = FN_STEPS_MAX;
Branch: 1 branch
BranchTrueFalseTotal
if (n > FN_STEPS_MAX) n = FN_STEPS_MAX; 0 1105523 1105523
192 1105523 ▶ if (n == 0) break;
Branch: 1 branch
BranchTrueFalseTotal
if (n == 0) break; 0 1105523 1105523
193 1105523 ▶ if ((T->chain_at)(b) < 0) {
Branch: 1 branch
BranchTrueFalseTotal
if ((T->chain_at)(b) < 0) { 799908 305615 1105523
194 799908 ▶ if (list[0].kind == FN_PAIKA || moves >= FN_SETTLE_MOVES) break;
Branch: 2 branches
BranchTrueFalseTotal
if (list[0].kind == FN_PAIKA || moves >= FN_SETTLE_MOVES) break; 668568 131340 799908
if (list[0].kind == FN_PAIKA || moves >= FN_SETTLE_MOVES) break; 643994 24574 668568
195 643994 moves++;
196 }
197 2375781 ▶ for (i = 1; i < n; i++) if (list[i].taken_n > list[pick].taken_n) pick = i;
Branch: 2 branches
BranchTrueFalseTotal
for (i = 1; i < n; i++) if (list[i].taken_n > list[pick].taken_n) pick = i; 196511 1229661 1426172
for (i = 1; i < n; i++) if (list[i].taken_n > list[pick].taken_n) pick = i; 1426172 949609 2375781
198 949609 (T->game_step)(c->g, list[pick].from, list[pick].dir, list[pick].kind, NULL);
199 949609 made++;
200 949609 c->nodes++;
201 }
202 353570 ▶ if ((T->game_outcome)(c->g) == FN_ONGOING && (T->chain_at)((T->game_board)(c->g)) >= 0) {
Branch: 2 branches
BranchTrueFalseTotal
if ((T->game_outcome)(c->g) == FN_ONGOING && (T->chain_at)((T->game_board)(c->g)) >= 0) { 155914 197656 353570
if ((T->game_outcome)(c->g) == FN_ONGOING && (T->chain_at)((T->game_board)(c->g)) >= 0) { 0 155914 155914
203 /* the cap fell in the middle of a chain: end the move where it is */
204 0 (T->game_stop)(c->g);
205 0 made++;
206 }
207 353570 ▶ if ((T->game_outcome)(c->g) != FN_ONGOING) {
Branch: 1 branch
BranchTrueFalseTotal
if ((T->game_outcome)(c->g) != FN_ONGOING) { 197656 155914 353570
208 /* A GAME THAT ENDS WHILE SETTLING HAS NOT BEEN PROVED TO END THAT WAY.
209 * The settling is one line of largest captures, and where two captures
210 * are as large as each other it takes the first; the other may be the
211 * one that wins. So this is scored as very good or very bad and NEVER
212 * as a win seen to its end, which would stop the search looking any
213 * deeper and did, once, make it throw away a won game on the first
214 * iteration. Scored for the side that was to move when the settling
215 * began, whoever is to move now. */
216 197656 int winner = (T->game_winner)(c->g);
217 197656 ▶ score = !winner ? 0 : winner == side ? FN_SETTLED_WIN : -FN_SETTLED_WIN;
Branch: 2 branches
BranchTrueFalseTotal
score = !winner ? 0 : winner == side ? FN_SETTLED_WIN : -FN_SETTLED_WIN; 197656 0 197656
score = !winner ? 0 : winner == side ? FN_SETTLED_WIN : -FN_SETTLED_WIN; 197122 534 197656
218 }
219 else {
220 155914 score = fn_evaluate((T->game_board)(c->g), c->w);
221 155914 ▶ if (side != FN_WHITE) score = -score;
Branch: 1 branch
BranchTrueFalseTotal
if (side != FN_WHITE) score = -score; 102670 53244 155914
222 }
223 1303179 ▶ while (made-- > 0) (T->game_undo)(c->g);
Branch: 1 branch
BranchTrueFalseTotal
while (made-- > 0) (T->game_undo)(c->g); 949609 353570 1303179
224 353570 return score;
225 }
226  
227 /* One position. `line`, when it is not NULL, receives the rest of the move the
228 * side to move should make from here: the caller is that same side, part way
229 * through choosing. A node asked for a line never takes its answer from the
230 * table, because the table remembers a score and one step and not a line. */
231 4541306 static int node(struct ctx *c, int depth, int alpha, int beta, int ply, struct fn_move *line)
232 {
233 4541306 const struct fn_board *b = (T->game_board)(c->g);
234 struct fn_step list[FN_STEPS_MAX];
235 struct fn_move child;
236 4541306 struct tt_entry *e = NULL;
237 4541306 unsigned long long key = 0;
238 4541306 int side = (T->side)(b);
239 4541306 int in_chain = (T->chain_at)(b) >= 0;
240 4541306 int n, i, best = -FN_INF, alpha0 = alpha, best_i = -1;
241  
242 4541306 ▶ if (line) { line->n = 0; line->from = -1; line->taken = 0; }
Branch: 1 branch
BranchTrueFalseTotal
if (line) { line->n = 0; line->from = -1; line->taken = 0; } 16078 4525228 4541306
243  
244 4541306 c->nodes++;
245 4541306 ▶ if (c->may_stop && c->nodes >= c->budget) c->stopped = 1;
Branch: 2 branches
BranchTrueFalseTotal
if (c->may_stop && c->nodes >= c->budget) c->stopped = 1; 4523317 17989 4541306
if (c->may_stop && c->nodes >= c->budget) c->stopped = 1; 1465 4521852 4523317
246 4541306 ▶ if (c->stopped) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (c->stopped) return 0; 1465 4539841 4541306
247  
248 4539841 ▶ if ((T->game_outcome)(c->g) != FN_ONGOING) return score_of_end(c, side, ply);
Branch: 1 branch
BranchTrueFalseTotal
if ((T->game_outcome)(c->g) != FN_ONGOING) return score_of_end(c, side, ply); 227591 4312250 4539841
249  
250 4312250 n = (T->game_steps)(c->g, list, FN_STEPS_MAX);
251 4312250 ▶ if (n > FN_STEPS_MAX) n = FN_STEPS_MAX;
Branch: 1 branch
BranchTrueFalseTotal
if (n > FN_STEPS_MAX) n = FN_STEPS_MAX; 0 4312250 4312250
252  
253 4312250 ▶ if (!in_chain) {
Branch: 1 branch
BranchTrueFalseTotal
if (!in_chain) { 4262614 49636 4312250
254 /* the obligation makes a list all captures or all paikas */
255 4262614 ▶ int can_take = n > 0 && list[0].kind != FN_PAIKA;
Branch: 2 branches
BranchTrueFalseTotal
int can_take = n > 0 && list[0].kind != FN_PAIKA; 4262614 0 4262614
int can_take = n > 0 && list[0].kind != FN_PAIKA; 668002 3594612 4262614
256 4262614 ▶ if (depth <= 0 || ply >= FN_LINE_STEPS) {
Branch: 2 branches
BranchTrueFalseTotal
if (depth <= 0 || ply >= FN_LINE_STEPS) { 2062644 2199970 4262614
if (depth <= 0 || ply >= FN_LINE_STEPS) { 0 2062644 2062644
257 int s;
258 2199970 ▶ if (can_take) return settle(c);
Branch: 1 branch
BranchTrueFalseTotal
if (can_take) return settle(c); 353570 1846400 2199970
259 1846400 s = fn_evaluate(b, c->w);
260 1846400 ▶ return side == FN_WHITE ? s : -s;
Branch: 1 branch
BranchTrueFalseTotal
return side == FN_WHITE ? s : -s; 1179914 666486 1846400
261 }
262 2062644 key = (T->key)(b);
263 2062644 ▶ if (c->tt) {
Branch: 1 branch
BranchTrueFalseTotal
if (c->tt) { 2062644 0 2062644
264 2062644 e = &c->tt[(size_t) key & c->mask];
265 2062644 ▶ if (!line && e->used && e->key == key && e->depth >= depth) {
Branch: 4 branches
BranchTrueFalseTotal
if (!line && e->used && e->key == key && e->depth >= depth) { 2048681 13963 2062644
if (!line && e->used && e->key == key && e->depth >= depth) { 1198219 850462 2048681
if (!line && e->used && e->key == key && e->depth >= depth) { 1117625 80594 1198219
if (!line && e->used && e->key == key && e->depth >= depth) { 574363 543262 1117625
266 574363 ▶ if (e->flag == TT_EXACT) return e->score;
Branch: 1 branch
BranchTrueFalseTotal
if (e->flag == TT_EXACT) return e->score; 62552 511811 574363
267 511811 ▶ 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; 438685 73126 511811
if (e->flag == TT_LOWER && e->score > alpha) alpha = e->score; 419618 19067 438685
268 511811 ▶ 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; 73126 438685 511811
if (e->flag == TT_UPPER && e->score < beta) beta = e->score; 59487 13639 73126
269 511811 ▶ if (alpha >= beta) return e->score;
Branch: 1 branch
BranchTrueFalseTotal
if (alpha >= beta) return e->score; 460602 51209 511811
270 }
271 1539490 ▶ if (e->key != key) e = NULL;
Branch: 1 branch
BranchTrueFalseTotal
if (e->key != key) e = NULL; 933504 605986 1539490
272 }
273 }
274  
275 1589126 ▶ order_steps(list, n, e, (ply == 0 && !in_chain) ? c->seed : 0);
Branch: 2 branches
BranchTrueFalseTotal
order_steps(list, n, e, (ply == 0 && !in_chain) ? c->seed : 0); 13995 1575131 1589126
order_steps(list, n, e, (ply == 0 && !in_chain) ? c->seed : 0); 13963 32 13995
276 1589126 ▶ if (c->tt && !in_chain) e = &c->tt[(size_t) key & c->mask];
Branch: 2 branches
BranchTrueFalseTotal
if (c->tt && !in_chain) e = &c->tt[(size_t) key & c->mask]; 1589126 0 1589126
if (c->tt && !in_chain) e = &c->tt[(size_t) key & c->mask]; 1539490 49636 1589126
277  
278 1589126 ▶ if (in_chain) {
Branch: 1 branch
BranchTrueFalseTotal
if (in_chain) { 49636 1539490 1589126
279 /* STOPPING IS A MOVE. It ends this side's move here. */
280 int s;
281 49636 (T->game_stop)(c->g);
282 49636 s = -node(c, depth - 1, -beta, -alpha, ply + 1, NULL);
283 49636 (T->game_undo)(c->g);
284 49636 ▶ if (c->stopped) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (c->stopped) return 0; 101 49535 49636
285 49535 best = s;
286 49535 ▶ if (best > alpha) alpha = best;
Branch: 1 branch
BranchTrueFalseTotal
if (best > alpha) alpha = best; 14987 34548 49535
287 }
288  
289 6056553 ▶ for (i = 0; i < n && alpha < beta; i++) {
Branch: 2 branches
BranchTrueFalseTotal
for (i = 0; i < n && alpha < beta; i++) { 5246855 809698 6056553
for (i = 0; i < n && alpha < beta; i++) { 4477674 769181 5246855
290 int s, why;
291 4477674 (T->game_step)(c->g, list[i].from, list[i].dir, list[i].kind, &why);
292 4477674 ▶ if ((T->chain_at)((T->game_board)(c->g)) >= 0) {
Branch: 1 branch
BranchTrueFalseTotal
if ((T->chain_at)((T->game_board)(c->g)) >= 0) { 49637 4428037 4477674
293 /* the same side goes on: no negation, and no depth spent */
294 49637 ▶ s = node(c, depth, alpha, beta, ply + 1, line ? &child : NULL);
Branch: 1 branch
BranchTrueFalseTotal
s = node(c, depth, alpha, beta, ply + 1, line ? &child : NULL); 2082 47555 49637
295 }
296 else {
297 4428037 s = -node(c, depth - 1, -beta, -alpha, ply + 1, NULL);
298 4428037 child.n = 0;
299 }
300 4477674 (T->game_undo)(c->g);
301 4477674 ▶ if (c->stopped) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (c->stopped) return 0; 10146 4467528 4477674
302 4467528 ▶ if (s > best) {
Branch: 1 branch
BranchTrueFalseTotal
if (s > best) { 2150528 2317000 4467528
303 2150528 best = s;
304 2150528 best_i = i;
305 2150528 ▶ if (line) {
Branch: 1 branch
BranchTrueFalseTotal
if (line) { 18045 2132483 2150528
306 int k;
307 18045 line->from = list[i].from;
308 18045 line->n = 1;
309 18045 line->dir[0] = (unsigned char) list[i].dir;
310 18045 line->kind[0] = (unsigned char) list[i].kind;
311 18045 line->taken = list[i].taken_n;
312 20233 ▶ for (k = 0; k < child.n && line->n < FN_CHAIN_MAX; k++) {
Branch: 2 branches
BranchTrueFalseTotal
for (k = 0; k < child.n && line->n < FN_CHAIN_MAX; k++) { 2188 18045 20233
for (k = 0; k < child.n && line->n < FN_CHAIN_MAX; k++) { 2188 0 2188
313 2188 line->dir[line->n] = child.dir[k];
314 2188 line->kind[line->n] = child.kind[k];
315 2188 line->n++;
316 }
317 }
318 }
319 4467528 ▶ if (best > alpha) alpha = best;
Branch: 1 branch
BranchTrueFalseTotal
if (best > alpha) alpha = best; 1417226 3050302 4467528
320 }
321  
322 /* A score that is a win or a loss carries the distance from the ROOT, which
323 * is the wrong distance for the same position met by another road, so
324 * those are left out of the table. So is anything found inside a chain:
325 * the table is for positions, and the middle of a move is not one. */
326 1578879 ▶ if (e && !in_chain && best > -(FN_WIN_SCORE - 1000) && best < FN_WIN_SCORE - 1000) {
Branch: 4 branches
BranchTrueFalseTotal
if (e && !in_chain && best > -(FN_WIN_SCORE - 1000) && best < FN_WIN_SCORE - 1000) { 1529535 49344 1578879
if (e && !in_chain && best > -(FN_WIN_SCORE - 1000) && best < FN_WIN_SCORE - 1000) { 1529535 0 1529535
if (e && !in_chain && best > -(FN_WIN_SCORE - 1000) && best < FN_WIN_SCORE - 1000) { 1511728 17807 1529535
if (e && !in_chain && best > -(FN_WIN_SCORE - 1000) && best < FN_WIN_SCORE - 1000) { 1273700 238028 1511728
327 1273700 e->used = 1;
328 1273700 e->key = key;
329 1273700 e->score = best;
330 1273700 e->depth = (short) depth;
331 1273700 ▶ 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); 963165 310535 1273700
e->flag = (unsigned char) (best <= alpha0 ? TT_UPPER : best >= beta ? TT_LOWER : TT_EXACT); 813927 149238 963165
332 1273700 ▶ if (best_i >= 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (best_i >= 0) { 1273700 0 1273700
333 1273700 e->from = (short) list[best_i].from;
334 1273700 e->dir = (unsigned char) list[best_i].dir;
335 1273700 e->kind = (unsigned char) list[best_i].kind;
336 }
337 }
338 1578879 return best;
339 }
340  
341 /* THE MOVE RETURNED IS THE BEST OF THE LAST ITERATION THAT FINISHED. An
342 * iteration cut short by the budget has looked at some of the moves and not
343 * others, and its "best so far" is the best of an arbitrary subset.
344 *
345 * The first iteration is never cut short, so there is always a move to
346 * return.
347 */
348 2452 static int fn_search(const struct fn_game *game, const struct fn_weights *w,
349 unsigned long long budget, unsigned long long seed, int max_depth,
350 struct fn_move *best, struct fn_search_info *info)
351 {
352 struct ctx c;
353 struct fn_move line, kept;
354 2452 int depth, done = 0, best_score = 0;
355 2452 size_t size = 1024;
356  
357 2452 ▶ if (info) memset(info, 0, sizeof(*info));
Branch: 1 branch
BranchTrueFalseTotal
if (info) memset(info, 0, sizeof(*info)); 2452 0 2452
358 2452 ▶ if (best) { memset(best, 0, sizeof(*best)); best->from = -1; }
Branch: 1 branch
BranchTrueFalseTotal
if (best) { memset(best, 0, sizeof(*best)); best->from = -1; } 2452 0 2452
359 2452 ▶ if (!game || (T->game_outcome)(game) != FN_ONGOING) return 0;
Branch: 2 branches
BranchTrueFalseTotal
if (!game || (T->game_outcome)(game) != FN_ONGOING) return 0; 2452 0 2452
if (!game || (T->game_outcome)(game) != FN_ONGOING) return 0; 0 2452 2452
360  
361 2452 memset(&c, 0, sizeof(c));
362 2452 c.g = (T->game_copy)(game);
363 2452 ▶ if (!c.g) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (!c.g) return 0; 0 2452 2452
364 2452 c.w = weights_or_default(w);
365 2452 c.budget = budget;
366 2452 ▶ c.seed = seed ? seed : 1;
Branch: 1 branch
BranchTrueFalseTotal
c.seed = seed ? seed : 1; 2452 0 2452
367  
368 7332 ▶ while (size < budget && size < ((size_t) 1 << 20)) size <<= 1;
Branch: 2 branches
BranchTrueFalseTotal
while (size < budget && size < ((size_t) 1 << 20)) size <<= 1; 4880 2452 7332
while (size < budget && size < ((size_t) 1 << 20)) size <<= 1; 4880 0 4880
369 2452 c.tt = (struct tt_entry *) calloc(size, sizeof(struct tt_entry));
370 2452 c.mask = size - 1;
371  
372 2452 ▶ if (max_depth <= 0 || max_depth > FN_DEPTH_MAX) max_depth = FN_DEPTH_MAX;
Branch: 2 branches
BranchTrueFalseTotal
if (max_depth <= 0 || max_depth > FN_DEPTH_MAX) max_depth = FN_DEPTH_MAX; 18 2434 2452
if (max_depth <= 0 || max_depth > FN_DEPTH_MAX) max_depth = FN_DEPTH_MAX; 0 18 18
373 2452 memset(&kept, 0, sizeof(kept));
374 2452 kept.from = -1;
375  
376 14018 ▶ for (depth = 1; depth <= max_depth; depth++) {
Branch: 1 branch
BranchTrueFalseTotal
for (depth = 1; depth <= max_depth; depth++) { 13996 22 14018
377 int s;
378 13996 c.may_stop = depth > 1;
379 13996 s = node(&c, depth, -FN_INF, FN_INF, 0, &line);
380 13996 ▶ if (c.stopped) break;
Branch: 1 branch
BranchTrueFalseTotal
if (c.stopped) break; 1465 12531 13996
381 12531 kept = line;
382 12531 best_score = s;
383 12531 done = depth;
384 /* a win or a loss that is forced has been seen to its end */
385 12531 ▶ if (best_score > FN_WIN_SCORE - 1000 || best_score < -(FN_WIN_SCORE - 1000)) break;
Branch: 2 branches
BranchTrueFalseTotal
if (best_score > FN_WIN_SCORE - 1000 || best_score < -(FN_WIN_SCORE - 1000)) break; 11603 928 12531
if (best_score > FN_WIN_SCORE - 1000 || best_score < -(FN_WIN_SCORE - 1000)) break; 11579 24 11603
386 11579 ▶ if (c.nodes >= c.budget) break;
Branch: 1 branch
BranchTrueFalseTotal
if (c.nodes >= c.budget) break; 13 11566 11579
387 }
388  
389 2452 ▶ if (best) *best = kept;
Branch: 1 branch
BranchTrueFalseTotal
if (best) *best = kept; 2452 0 2452
390 2452 ▶ if (info) {
Branch: 1 branch
BranchTrueFalseTotal
if (info) { 2452 0 2452
391 2452 info->nodes = c.nodes;
392 2452 info->depth = done;
393 2452 info->score = best_score;
394 2452 info->stopped = c.stopped;
395 }
396 2452 free(c.tt);
397 2452 (T->game_drop)(c.g);
398 2452 return 1;
399 }
400  
401 /* ---- installed into the table by fn_engine.c -------------------------------------- */
402  
403 void fn_search_install(struct fn_abi *t);
404  
405 43 void fn_search_install(struct fn_abi *t)
406 {
407 43 T = t;
408 43 t->weights_default = fn_weights_default;
409 43 t->evaluate = fn_evaluate;
410 43 t->search = fn_search;
411 43 }
« fn_moves.c ↑ Summary fn_engine.c »