| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| if (from < 0) continue; |
0 |
53706308 |
53706308 |
|
| 92 |
53706308 |
▶ | if (from == 0) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (from == 0) { |
0 |
53706308 |
53706308 |
|
| 93 |
0 |
▶ | if ((RU->hand)(b, enemy) > 0) chance += chance16(r, distance); |
Branch: 1 branch
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| && (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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| if (!rules) { standard_rules(&standard); rules = &standard; } |
0 |
5562412 |
5562412 |
|
| 127 |
5562412 |
▶ | if (!(RU->rules_ok)(rules)) return 0; |
Branch: 1 branch
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| if (n <= 0) return -1; |
1 |
1767 |
1768 |
|
| 153 |
5796 |
▶ | for (k = 0; k < n; k++) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (k = 0; k < n; k++) { |
4029 |
1767 |
5796 |
|
| 154 |
4029 |
▶ | if (m[k].captures) capture = k; |
Branch: 1 branch
| Branch | True | False | Total |
| if (m[k].captures) capture = k; |
213 |
3816 |
4029 |
|
| 155 |
4029 |
▶ | if (m[k].rosette) rosette = k; |
Branch: 1 branch
| Branch | True | False | Total |
| if (m[k].rosette) rosette = k; |
562 |
3467 |
4029 |
|
| 156 |
|
| } |
| 157 |
1767 |
▶ | if (capture >= 0) return capture; |
Branch: 1 branch
| Branch | True | False | Total |
| if (capture >= 0) return capture; |
207 |
1560 |
1767 |
|
| 158 |
1560 |
▶ | if (rosette >= 0) return rosette; |
Branch: 1 branch
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| if (s->stopped) return 0; |
22 |
5746027 |
5746049 |
|
| 209 |
5746027 |
▶ | if (k == 0 || (ours ? v > chosen : v < chosen)) chosen = v; |
Branch: 4 branches
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| if (!board) return -1; |
0 |
6030 |
6030 |
|
| 255 |
6030 |
▶ | if (!rules) { standard_rules(&standard); rules = &standard; } |
Branch: 1 branch
| Branch | True | False | Total |
| if (!rules) { standard_rules(&standard); rules = &standard; } |
0 |
6030 |
6030 |
|
| 256 |
6030 |
▶ | if (!weights) { ru_weights_default(&plain); weights = &plain; } |
Branch: 1 branch
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| if (s.stopped) break; |
13 |
36014 |
36027 |
|
| 284 |
36014 |
▶ | if (k == 0 || v >= best_v) { best_v = v; best_k = k; } |
Branch: 2 branches
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| if (n == 1) break; |
1022 |
13001 |
14023 |
|
| 291 |
13001 |
▶ | if (s.nodes >= s.budget) break; |
Branch: 1 branch
| Branch | True | False | Total |
| 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 |
| } |