ru_search.c

filter: Statementstmt 97.9% 146 / 149 Branchbran 85.7% 120 / 140 Conditioncond n/a MC/DCmcdc n/a Subroutinesub n/a Podpod n/a totaltotal 92.0% 266 / 289 CC 0 SCAR 0
CC
0
Cov
0%
CRAP 0
« ru_moves.c ↑ Summary ru_engine.c »
1 /* ru_search.c - choosing a move.
2 *
3 * PERL-FREE, like the rest, and it reaches the board only through the table.
4 *
5 * THIS FILE'S SCOPE. An evaluation of a position in whole numbers, a choice
6 * made without looking ahead, and a search that looks ahead through the dice.
7 *
8 * THERE IS NO FLOAT HERE. A chance is a weight over a denominator, both whole
9 * numbers from the chance table; a value is an int; and a division rounds
10 * toward zero whichever sign it has, so that a position and its mirror are
11 * valued alike.
12 *
13 * NOTHING HERE READS A CLOCK. A search is bounded in NODES, so that the same
14 * position, roll and budget give the same move on every machine and under any
15 * load.
16 */
17  
18 #include <stddef.h>
19 #include "ru_abi.h"
20  
21 static const struct ru_abi *RU = NULL;
22  
23 /* ---- the evaluation --------------------------------------------------------------
24 *
25 * In SIXTEENTHS OF A STEP, for one side, and it is the other side's with the
26 * sign turned.
27 *
28 * The plain evaluation is progress: every step each of a side's pieces has
29 * taken, a piece at home counting one more than the route is long and a piece
30 * in hand counting nothing, less the same for the other side.
31 *
32 * Three terms may be added to it, each with a weight that is 0 unless a caller
33 * sets it.
34 */
35  
36 6052 static void ru_weights_default(struct ru_weights *w)
37 {
38 int i;
39 6052 ▶ if (!w) return;
Branch: 1 branch
BranchTrueFalseTotal
if (!w) return; 0 6052 6052
40 6052 w->exposed = 0;
41 6052 w->rosette = 0;
42 6052 w->entry = 0;
43 36312 ▶ for (i = 0; i < 5; i++) w->reserved[i] = 0;
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < 5; i++) w->reserved[i] = 0; 30260 6052 36312
44 }
45  
46 11124824 static int progress(const struct ru_board *b, const struct ru_rules *r, int side)
47 {
48 11124824 int len = (RU->route_len)(r->route);
49 11124824 int total = (RU->home)(b, side) * (len + 1);
50 int step;
51 176058728 ▶ for (step = 1; step <= len; step++)
Branch: 1 branch
BranchTrueFalseTotal
for (step = 1; step <= len; step++) 164933904 11124824 176058728
52 164933904 ▶ if ((RU->at)(b, (RU->route_cell)(r->route, side, step)) == RU_PIECE_OF(side))
Branch: 1 branch
BranchTrueFalseTotal
if ((RU->at)(b, (RU->route_cell)(r->route, side, step)) == RU_PIECE_OF(side)) 33909360 131024544 164933904
53 33909360 total += step;
54 11124824 return total;
55 }
56  
57 /* The chance, in sixteenths, that the dice roll exactly `distance`. */
58 13517363 static int chance16(const struct ru_rules *r, int distance)
59 {
60 13517363 int n = (RU->chance_count)(r->dice, r->zero_rolls);
61 int i, roll, weight, denominator;
62 43498008 ▶ for (i = 0; i < n; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < n; i++) { 43498008 0 43498008
63 43498008 (RU->chance)(r->dice, r->zero_rolls, i, &roll, &weight, &denominator);
64 43498008 ▶ if (roll == distance) return weight * 16 / denominator;
Branch: 1 branch
BranchTrueFalseTotal
if (roll == distance) return weight * 16 / denominator; 13517363 29980645 43498008
65 }
66 0 return 0;
67 }
68  
69 /* What a side stands to lose to the enemy's next roll: for each of its pieces
70 * an enemy piece could land on, the chance of the roll that does it times the
71 * steps the piece would be sent back. In sixteenths of a step.
72 *
73 * A piece is asked of ITS OWN step and its attacker of the ENEMY's step for
74 * the same cell, which on the long route is a different number. */
75 10510254 static int exposure(const struct ru_board *b, const struct ru_rules *r, int side)
76 {
77 10510254 int len = (RU->route_len)(r->route);
78 10510254 int enemy = RU_OTHER(side);
79 10510254 int total = 0, step, distance;
80  
81 166566050 ▶ for (step = 1; step <= len; step++) {
Branch: 1 branch
BranchTrueFalseTotal
for (step = 1; step <= len; step++) { 156055796 10510254 166566050
82 156055796 int cell = (RU->route_cell)(r->route, side, step);
83 156055796 int theirs, chance = 0;
84 156055796 ▶ if ((RU->at)(b, cell) != RU_PIECE_OF(side)) continue;
Branch: 1 branch
BranchTrueFalseTotal
if ((RU->at)(b, cell) != RU_PIECE_OF(side)) continue; 123942555 32113241 156055796
85 32113241 ▶ if (!(RU->route_shared)(r->route, cell)) continue;
Branch: 1 branch
BranchTrueFalseTotal
if (!(RU->route_shared)(r->route, cell)) continue; 17458466 14654775 32113241
86 14654775 ▶ if (r->safe_rosettes && (RU->is_rosette)(cell)) continue;
Branch: 2 branches
BranchTrueFalseTotal
if (r->safe_rosettes && (RU->is_rosette)(cell)) continue; 8144084 6510691 14654775
if (r->safe_rosettes && (RU->is_rosette)(cell)) continue; 1228198 6915886 8144084
87  
88 13426577 theirs = (RU->route_step)(r->route, enemy, cell);
89 67132885 ▶ for (distance = 1; distance <= RU_ROLL_MAX; distance++) {
Branch: 1 branch
BranchTrueFalseTotal
for (distance = 1; distance <= RU_ROLL_MAX; distance++) { 53706308 13426577 67132885
90 53706308 int from = theirs - distance;
91 53706308 ▶ if (from < 0) continue;
Branch: 1 branch
BranchTrueFalseTotal
if (from < 0) continue; 0 53706308 53706308
92 53706308 ▶ if (from == 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (from == 0) { 0 53706308 53706308
93 0 ▶ if ((RU->hand)(b, enemy) > 0) chance += chance16(r, distance);
Branch: 1 branch
BranchTrueFalseTotal
if ((RU->hand)(b, enemy) > 0) chance += chance16(r, distance); 0 0 0
94 }
95 53706308 ▶ else if ((RU->at)(b, (RU->route_cell)(r->route, enemy, from)) == RU_PIECE_OF(enemy)) {
Branch: 1 branch
BranchTrueFalseTotal
else if ((RU->at)(b, (RU->route_cell)(r->route, enemy, from)) == RU_PIECE_OF(enemy)) { 13517363 40188945 53706308
96 13517363 chance += chance16(r, distance);
97 }
98 }
99 13426577 ▶ if (chance > 16) chance = 16;
Branch: 1 branch
BranchTrueFalseTotal
if (chance > 16) chance = 16; 0 13426577 13426577
100 13426577 total += chance * step;
101 }
102 10510254 return total;
103 }
104  
105 /* A side's pieces standing on rosettes both sides visit. */
106 6054130 static int rosettes_held(const struct ru_board *b, const struct ru_rules *r, int side)
107 {
108 6054130 int len = (RU->route_len)(r->route);
109 6054130 int n = 0, step;
110 90811950 ▶ for (step = 1; step <= len; step++) {
Branch: 1 branch
BranchTrueFalseTotal
for (step = 1; step <= len; step++) { 84757820 6054130 90811950
111 84757820 int cell = (RU->route_cell)(r->route, side, step);
112 84757820 ▶ if ((RU->at)(b, cell) == RU_PIECE_OF(side)
Branch: 1 branch
BranchTrueFalseTotal
if ((RU->at)(b, cell) == RU_PIECE_OF(side) 19363701 65394119 84757820
113 19363701 ▶ && (RU->is_rosette)(cell) && (RU->route_shared)(r->route, cell)) n++;
Branch: 2 branches
BranchTrueFalseTotal
&& (RU->is_rosette)(cell) && (RU->route_shared)(r->route, cell)) n++; 4723623 14640078 19363701
&& (RU->is_rosette)(cell) && (RU->route_shared)(r->route, cell)) n++; 1228199 3495424 4723623
114 }
115 6054130 return n;
116 }
117  
118 0 static void standard_rules(struct ru_rules *r) { (RU->rules_named)(RU_RULES_FINKEL, r); }
119  
120 5562413 static int ru_evaluate(const struct ru_board *b, const struct ru_rules *rules,
121 const struct ru_weights *w, int side)
122 {
123 struct ru_rules standard;
124 int enemy, v;
125 5562413 ▶ if (!b || (side != RU_SIDE_LIGHT && side != RU_SIDE_DARK)) return 0;
Branch: 3 branches
BranchTrueFalseTotal
if (!b || (side != RU_SIDE_LIGHT && side != RU_SIDE_DARK)) return 0; 5562413 0 5562413
if (!b || (side != RU_SIDE_LIGHT && side != RU_SIDE_DARK)) return 0; 2895809 2666604 5562413
if (!b || (side != RU_SIDE_LIGHT && side != RU_SIDE_DARK)) return 0; 1 2895808 2895809
126 5562412 ▶ if (!rules) { standard_rules(&standard); rules = &standard; }
Branch: 1 branch
BranchTrueFalseTotal
if (!rules) { standard_rules(&standard); rules = &standard; } 0 5562412 5562412
127 5562412 ▶ if (!(RU->rules_ok)(rules)) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (!(RU->rules_ok)(rules)) return 0; 0 5562412 5562412
128 5562412 enemy = RU_OTHER(side);
129  
130 5562412 v = 16 * (progress(b, rules, side) - progress(b, rules, enemy));
131 5562412 ▶ if (w && w->exposed)
Branch: 2 branches
BranchTrueFalseTotal
if (w && w->exposed) 5562412 0 5562412
if (w && w->exposed) 5255127 307285 5562412
132 5255127 v -= w->exposed * (exposure(b, rules, side) - exposure(b, rules, enemy)) / 16;
133 5562412 ▶ if (w && w->rosette)
Branch: 2 branches
BranchTrueFalseTotal
if (w && w->rosette) 5562412 0 5562412
if (w && w->rosette) 3027065 2535347 5562412
134 3027065 v += w->rosette * (rosettes_held(b, rules, side) - rosettes_held(b, rules, enemy));
135 5562412 ▶ if (w && w->entry)
Branch: 2 branches
BranchTrueFalseTotal
if (w && w->entry) 5562412 0 5562412
if (w && w->entry) 3027065 2535347 5562412
136 3027065 v -= w->entry * ((RU->hand)(b, side) - (RU->hand)(b, enemy));
137 5562412 return v;
138 }
139  
140 /* ---- a choice without looking ahead -------------------------------------------------
141 *
142 * Of the moves the roll allows: one that captures, if any does; else one that
143 * lands on a rosette, if any does; else the piece furthest along. Where two
144 * moves are alike in that, the one further along.
145 */
146  
147 1768 static int ru_greedy(const struct ru_board *b, const struct ru_rules *rules, int roll)
148 {
149 struct ru_move m[RU_MOVES_MAX];
150 1768 int n = (RU->moves)(b, rules, roll, m, RU_MOVES_MAX);
151 1768 int k, capture = -1, rosette = -1;
152 1768 ▶ if (n <= 0) return -1;
Branch: 1 branch
BranchTrueFalseTotal
if (n <= 0) return -1; 1 1767 1768
153 5796 ▶ for (k = 0; k < n; k++) {
Branch: 1 branch
BranchTrueFalseTotal
for (k = 0; k < n; k++) { 4029 1767 5796
154 4029 ▶ if (m[k].captures) capture = k;
Branch: 1 branch
BranchTrueFalseTotal
if (m[k].captures) capture = k; 213 3816 4029
155 4029 ▶ if (m[k].rosette) rosette = k;
Branch: 1 branch
BranchTrueFalseTotal
if (m[k].rosette) rosette = k; 562 3467 4029
156 }
157 1767 ▶ if (capture >= 0) return capture;
Branch: 1 branch
BranchTrueFalseTotal
if (capture >= 0) return capture; 207 1560 1767
158 1560 ▶ if (rosette >= 0) return rosette;
Branch: 1 branch
BranchTrueFalseTotal
if (rosette >= 0) return rosette; 466 1094 1560
159 1094 return n - 1;
160 }
161  
162 /* ---- the search ---------------------------------------------------------------------
163 *
164 * Expectiminimax. A position's value is the sum, over every roll the dice can
165 * make, of that roll's weight times the value of the best move it allows,
166 * over the denominator. "Best" is the highest for the side the search is for
167 * and the lowest for the other.
168 *
169 * THE VALUE IS ALWAYS FOR ONE SIDE, fixed where the search starts, and whether
170 * a level takes the highest or the lowest is asked of the board each time. It
171 * is NOT a sign turned on every ply: after a rosette the same side moves
172 * again, and a turned sign is wrong on exactly those plies.
173 *
174 * A roll that allows nothing is a level like any other: the turn is lost, and
175 * the search goes on from the other side.
176 */
177  
178 struct search {
179 const struct ru_rules *rules;
180 const struct ru_weights *weights;
181 int root;
182 unsigned long long nodes;
183 unsigned long long budget;
184 int unbounded; /* the first depth always finishes */
185 int stopped;
186 };
187  
188 static int value(struct search *s, struct ru_board *b, int depth);
189  
190 2312199 static int best(struct search *s, struct ru_board *b, int roll, int depth)
191 {
192 struct ru_move m[RU_MOVES_MAX];
193 struct ru_undo u;
194 2312199 int n = (RU->moves)(b, s->rules, roll, m, RU_MOVES_MAX);
195 2312199 int k, v, chosen = 0, ours;
196  
197 2312199 ▶ if (n <= 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (n <= 0) { 287388 2024811 2312199
198 287388 (RU->forfeit)(b, &u);
199 287388 v = value(s, b, depth - 1);
200 287388 (RU->unapply)(b, &u);
201 287388 return v;
202 }
203 2024811 ours = (RU->side)(b) == s->root;
204 7770838 ▶ for (k = 0; k < n; k++) {
Branch: 1 branch
BranchTrueFalseTotal
for (k = 0; k < n; k++) { 5746049 2024789 7770838
205 5746049 (RU->apply)(b, s->rules, &m[k], &u);
206 5746049 v = value(s, b, depth - 1);
207 5746049 (RU->unapply)(b, &u);
208 5746049 ▶ if (s->stopped) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (s->stopped) return 0; 22 5746027 5746049
209 5746027 ▶ if (k == 0 || (ours ? v > chosen : v < chosen)) chosen = v;
Branch: 4 branches
BranchTrueFalseTotal
if (k == 0 || (ours ? v > chosen : v < chosen)) chosen = v; 3721223 2024804 5746027
if (k == 0 || (ours ? v > chosen : v < chosen)) chosen = v; 1687774 2033449 3721223
if (k == 0 || (ours ? v > chosen : v < chosen)) chosen = v; 609383 1078391 1687774
if (k == 0 || (ours ? v > chosen : v < chosen)) chosen = v; 800699 1232750 2033449
210 }
211 2024789 return chosen;
212 }
213  
214 6069464 static int value(struct search *s, struct ru_board *b, int depth)
215 {
216 6069464 int rolls, i, roll, weight, denominator = 1, sum = 0, winner;
217  
218 6069464 ▶ if (!s->unbounded && s->nodes >= s->budget) { s->stopped = 1; return 0; }
Branch: 2 branches
BranchTrueFalseTotal
if (!s->unbounded && s->nodes >= s->budget) { s->stopped = 1; return 0; } 6055151 14313 6069464
if (!s->unbounded && s->nodes >= s->budget) { s->stopped = 1; return 0; } 13 6055138 6055151
219 6069451 s->nodes++;
220  
221 6069451 winner = (RU->winner)(b, s->rules);
222 6069451 ▶ if (winner >= 0) return winner == s->root ? RU_WIN + depth : -(RU_WIN + depth);
Branch: 2 branches
BranchTrueFalseTotal
if (winner >= 0) return winner == s->root ? RU_WIN + depth : -(RU_WIN + depth); 133 6069318 6069451
if (winner >= 0) return winner == s->root ? RU_WIN + depth : -(RU_WIN + depth); 20 113 133
223 6069318 ▶ if ((RU->status)(b, s->rules) != RU_ONGOING) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if ((RU->status)(b, s->rules) != RU_ONGOING) return 0; 0 6069318 6069318
224 6069318 ▶ if (depth <= 0) return ru_evaluate(b, s->rules, s->weights, s->root);
Branch: 1 branch
BranchTrueFalseTotal
if (depth <= 0) return ru_evaluate(b, s->rules, s->weights, s->root); 5562393 506925 6069318
225  
226 506925 rolls = (RU->chance_count)(s->rules->dice, s->rules->zero_rolls);
227 2819099 ▶ for (i = 0; i < rolls; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < rolls; i++) { 2312199 506900 2819099
228 2312199 (RU->chance)(s->rules->dice, s->rules->zero_rolls, i, &roll, &weight, &denominator);
229 2312199 sum += weight * best(s, b, roll, depth);
230 2312199 ▶ if (s->stopped) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (s->stopped) return 0; 25 2312174 2312199
231 }
232 506900 return sum / denominator;
233 }
234  
235 6030 static int ru_search(const struct ru_board *board, const struct ru_rules *rules, int roll,
236 const struct ru_weights *weights, unsigned long long budget, int max_depth,
237 struct ru_search_info *info)
238 {
239 struct ru_rules standard;
240 struct ru_weights plain;
241 struct ru_search_info local;
242 struct ru_move m[RU_MOVES_MAX];
243 struct ru_undo u;
244 struct ru_board *b;
245 struct search s;
246 6030 int n, depth, k, chosen = 0;
247  
248 6030 ▶ if (!info) info = &local;
Branch: 1 branch
BranchTrueFalseTotal
if (!info) info = &local; 0 6030 6030
249 6030 info->nodes = 0;
250 6030 info->depth = 0;
251 6030 info->value = 0;
252 6030 info->stopped = 0;
253  
254 6030 ▶ if (!board) return -1;
Branch: 1 branch
BranchTrueFalseTotal
if (!board) return -1; 0 6030 6030
255 6030 ▶ if (!rules) { standard_rules(&standard); rules = &standard; }
Branch: 1 branch
BranchTrueFalseTotal
if (!rules) { standard_rules(&standard); rules = &standard; } 0 6030 6030
256 6030 ▶ if (!weights) { ru_weights_default(&plain); weights = &plain; }
Branch: 1 branch
BranchTrueFalseTotal
if (!weights) { ru_weights_default(&plain); weights = &plain; } 0 6030 6030
257 6030 ▶ if ((RU->status)(board, rules) != RU_ONGOING) return -1;
Branch: 1 branch
BranchTrueFalseTotal
if ((RU->status)(board, rules) != RU_ONGOING) return -1; 1 6029 6030
258  
259 6029 b = (RU->board_copy)(board);
260 6029 ▶ if (!b) return -1;
Branch: 1 branch
BranchTrueFalseTotal
if (!b) return -1; 0 6029 6029
261 6029 n = (RU->moves)(b, rules, roll, m, RU_MOVES_MAX);
262 6029 ▶ if (n <= 0) { (RU->board_drop)(b); return -1; }
Branch: 1 branch
BranchTrueFalseTotal
if (n <= 0) { (RU->board_drop)(b); return -1; } 57 5972 6029
263 5972 ▶ if (max_depth <= 0 || max_depth > RU_DEPTH_MAX) max_depth = RU_DEPTH_MAX;
Branch: 2 branches
BranchTrueFalseTotal
if (max_depth <= 0 || max_depth > RU_DEPTH_MAX) max_depth = RU_DEPTH_MAX; 5951 21 5972
if (max_depth <= 0 || max_depth > RU_DEPTH_MAX) max_depth = RU_DEPTH_MAX; 0 5951 5951
264  
265 5972 s.rules = rules;
266 5972 s.weights = weights;
267 5972 s.root = (RU->side)(b);
268 5972 s.nodes = 0;
269 5972 s.budget = budget;
270  
271 /* MOVES OF EQUAL VALUE GO TO THE LAST OF THEM, which is the piece furthest
272 * along. That is a measurement and not a taste: with ties to the first,
273 * the piece least far along, a search one level deep lost 386 games in 400
274 * to the choice made without looking ahead (plan_game_royalur/07). */
275 18965 ▶ for (depth = 1; depth <= max_depth; depth++) {
Branch: 1 branch
BranchTrueFalseTotal
for (depth = 1; depth <= max_depth; depth++) { 14036 4929 18965
276 14036 int best_k = 0, best_v = 0, v;
277 14036 s.unbounded = (depth == 1);
278 14036 s.stopped = 0;
279 50050 ▶ for (k = 0; k < n; k++) {
Branch: 1 branch
BranchTrueFalseTotal
for (k = 0; k < n; k++) { 36027 14023 50050
280 36027 (RU->apply)(b, rules, &m[k], &u);
281 36027 v = value(&s, b, depth - 1);
282 36027 (RU->unapply)(b, &u);
283 36027 ▶ if (s.stopped) break;
Branch: 1 branch
BranchTrueFalseTotal
if (s.stopped) break; 13 36014 36027
284 36014 ▶ if (k == 0 || v >= best_v) { best_v = v; best_k = k; }
Branch: 2 branches
BranchTrueFalseTotal
if (k == 0 || v >= best_v) { best_v = v; best_k = k; } 21984 14030 36014
if (k == 0 || v >= best_v) { best_v = v; best_k = k; } 10460 11524 21984
285 }
286 14036 ▶ if (s.stopped) { info->stopped = 1; break; }
Branch: 1 branch
BranchTrueFalseTotal
if (s.stopped) { info->stopped = 1; break; } 13 14023 14036
287 14023 chosen = best_k;
288 14023 info->depth = depth;
289 14023 info->value = best_v;
290 14023 ▶ if (n == 1) break;
Branch: 1 branch
BranchTrueFalseTotal
if (n == 1) break; 1022 13001 14023
291 13001 ▶ if (s.nodes >= s.budget) break;
Branch: 1 branch
BranchTrueFalseTotal
if (s.nodes >= s.budget) break; 8 12993 13001
292 }
293  
294 5972 info->nodes = s.nodes;
295 5972 (RU->board_drop)(b);
296 5972 return chosen;
297 }
298  
299 /* ---- the table ------------------------------------------------------------------- */
300  
301 73 void ru_search_install(struct ru_abi *t)
302 {
303 73 RU = t;
304 73 t->weights_default = ru_weights_default;
305 73 t->evaluate = ru_evaluate;
306 73 t->greedy = ru_greedy;
307 73 t->search = ru_search;
308 73 }
« ru_moves.c ↑ Summary ru_engine.c »