| 1 |
|
| /* sen_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 sticks. |
| 7 |
|
| * |
| 8 |
|
| * THERE IS NO FLOAT HERE. A chance is a weight in sixteenths from the chance |
| 9 |
|
| * table; a value is an int; and a division rounds toward zero whichever sign it |
| 10 |
|
| * has, written out, because C89 leaves the rounding of a negative quotient to |
| 11 |
|
| * the compiler. |
| 12 |
|
| * |
| 13 |
|
| * NOTHING HERE READS A CLOCK. A search is bounded in NODES, so that the same |
| 14 |
|
| * position, throw and budget give the same move on every machine and under any |
| 15 |
|
| * load. |
| 16 |
|
| * |
| 17 |
|
| * IT READS FIELDS AND NEVER A SET'S NAME: what a piece on a marked house may do |
| 18 |
|
| * is read from the chains, so a term that weighs it knows the set by its table. |
| 19 |
|
| */ |
| 20 |
|
| |
| 21 |
|
| #include <stddef.h> |
| 22 |
|
| #include "sen_abi.h" |
| 23 |
|
| |
| 24 |
|
| static const struct sen_abi *SEN = NULL; |
| 25 |
|
| |
| 26 |
|
| #define HAPPINESS 26 |
| 27 |
|
| #define HOME_HOUSE 31 |
| 28 |
|
| |
| 29 |
|
| /* ---- the evaluation -------------------------------------------------------------- |
| 30 |
|
| * |
| 31 |
|
| * In SIXTEENTHS OF A HOUSE, for one side, and it is the other side's with the |
| 32 |
|
| * sign turned. The plain evaluation is progress: the house each of a side's |
| 33 |
|
| * pieces stands on, a piece at home counting 31, less the same for the other |
| 34 |
|
| * side. WHERE A PIECE ENDS is what counts: a move that falls into the water and |
| 35 |
|
| * walks down to 15 has lost ground, and is valued so. |
| 36 |
|
| * |
| 37 |
|
| * One term may be added, with a weight a rule set's ladder sets: BLOCKADE, the |
| 38 |
|
| * side's own runs wide enough to block with an enemy piece behind them. |
| 39 |
|
| * PROTECT, STUCK and WATER were written, measured and removed: each lost ground |
| 40 |
|
| * or moved nothing under both named sets (plan_game_senet/07, R3). |
| 41 |
|
| */ |
| 42 |
|
| |
| 43 |
111990 |
| static void sen_weights_default(struct sen_weights *w) |
| 44 |
|
| { |
| 45 |
|
| int i; |
| 46 |
111990 |
▶ | if (!w) return; |
Branch: 1 branch
| Branch | True | False | Total |
| if (!w) return; |
0 |
111990 |
111990 |
|
| 47 |
111990 |
| w->blockade = 0; |
| 48 |
111990 |
| w->ties = SEN_TIES_LAST; |
| 49 |
783930 |
▶ | for (i = 0; i < 6; i++) w->reserved[i] = 0; |
Branch: 1 branch
| Branch | True | False | Total |
| for (i = 0; i < 6; i++) w->reserved[i] = 0; |
671940 |
111990 |
783930 |
|
| 50 |
|
| } |
| 51 |
|
| |
| 52 |
6971756 |
| static int sen_progress(const struct sen_board *b, int side) |
| 53 |
|
| { |
| 54 |
6971756 |
| int total = (SEN->home)(b, side) * HOME_HOUSE; |
| 55 |
|
| int h; |
| 56 |
216124436 |
▶ | for (h = 1; h <= SEN_HOUSES; h++) |
Branch: 1 branch
| Branch | True | False | Total |
| for (h = 1; h <= SEN_HOUSES; h++) |
209152680 |
6971756 |
216124436 |
|
| 57 |
209152680 |
▶ | if ((SEN->at)(b, h) == SEN_PIECE_OF(side)) total += h; |
Branch: 1 branch
| Branch | True | False | Total |
| if ((SEN->at)(b, h) == SEN_PIECE_OF(side)) total += h; |
29848968 |
179303712 |
209152680 |
|
| 58 |
6971756 |
| return total; |
| 59 |
|
| } |
| 60 |
|
| |
| 61 |
5785511 |
| static int sen_run_len(const struct sen_board *b, int house, int *lo, int *hi) |
| 62 |
|
| { |
| 63 |
5785511 |
| int p = (SEN->at)(b, house); |
| 64 |
5785511 |
| int l = house, h = house; |
| 65 |
5785511 |
▶ | while (l > 1 && (SEN->at)(b, l - 1) == p) l--; |
Branch: 2 branches
| Branch | True | False | Total |
| while (l > 1 && (SEN->at)(b, l - 1) == p) l--; |
5333147 |
452364 |
5785511 |
| while (l > 1 && (SEN->at)(b, l - 1) == p) l--; |
0 |
5333147 |
5333147 |
|
| 66 |
7668274 |
▶ | while (h < SEN_HOUSES && (SEN->at)(b, h + 1) == p) h++; |
Branch: 2 branches
| Branch | True | False | Total |
| while (h < SEN_HOUSES && (SEN->at)(b, h + 1) == p) h++; |
7647256 |
21018 |
7668274 |
| while (h < SEN_HOUSES && (SEN->at)(b, h + 1) == p) h++; |
1882763 |
5764493 |
7647256 |
|
| 67 |
5785511 |
▶ | if (lo) *lo = l; |
Branch: 1 branch
| Branch | True | False | Total |
| if (lo) *lo = l; |
5785511 |
0 |
5785511 |
|
| 68 |
5785511 |
▶ | if (hi) *hi = h; |
Branch: 1 branch
| Branch | True | False | Total |
| if (hi) *hi = h; |
5785511 |
0 |
5785511 |
|
| 69 |
5785511 |
| return h - l + 1; |
| 70 |
|
| } |
| 71 |
|
| |
| 72 |
|
| /* BLOCKADE: own runs at least `blockade` wide with an enemy piece below them. */ |
| 73 |
1903942 |
| static int sen_term_blockade(const struct sen_board *b, const struct sen_rules *r, int side) |
| 74 |
|
| { |
| 75 |
1903942 |
▶ | int me = SEN_PIECE_OF(side), enemy = SEN_PIECE_OF(SEN_OTHER(side)); |
Branch: 1 branch
| Branch | True | False | Total |
| int me = SEN_PIECE_OF(side), enemy = SEN_PIECE_OF(SEN_OTHER(side)); |
951971 |
951971 |
1903942 |
|
| 76 |
1903942 |
| int h = 1, n = 0, lowest_enemy = 0, x; |
| 77 |
1903942 |
▶ | if (r->blockade == 0) return 0; |
Branch: 1 branch
| Branch | True | False | Total |
| if (r->blockade == 0) return 0; |
0 |
1903942 |
1903942 |
|
| 78 |
11853593 |
▶ | for (x = 1; x <= SEN_HOUSES; x++) |
Branch: 1 branch
| Branch | True | False | Total |
| for (x = 1; x <= SEN_HOUSES; x++) |
11853593 |
0 |
11853593 |
|
| 79 |
11853593 |
▶ | if ((SEN->at)(b, x) == enemy) { lowest_enemy = x; break; } |
Branch: 1 branch
| Branch | True | False | Total |
| if ((SEN->at)(b, x) == enemy) { lowest_enemy = x; break; } |
1903942 |
9949651 |
11853593 |
|
| 80 |
1903942 |
▶ | if (!lowest_enemy) return 0; |
Branch: 1 branch
| Branch | True | False | Total |
| if (!lowest_enemy) return 0; |
0 |
1903942 |
1903942 |
|
| 81 |
57139439 |
▶ | while (h <= SEN_HOUSES) { |
Branch: 1 branch
| Branch | True | False | Total |
| while (h <= SEN_HOUSES) { |
55235497 |
1903942 |
57139439 |
|
| 82 |
|
| int lo, hi; |
| 83 |
55235497 |
▶ | if ((SEN->at)(b, h) != me) { h++; continue; } |
Branch: 1 branch
| Branch | True | False | Total |
| if ((SEN->at)(b, h) != me) { h++; continue; } |
49449986 |
5785511 |
55235497 |
|
| 84 |
5785511 |
▶ | if (sen_run_len(b, h, &lo, &hi) >= r->blockade && lowest_enemy < lo) n++; |
Branch: 2 branches
| Branch | True | False | Total |
| if (sen_run_len(b, h, &lo, &hi) >= r->blockade && lowest_enemy < lo) n++; |
1457607 |
4327904 |
5785511 |
| if (sen_run_len(b, h, &lo, &hi) >= r->blockade && lowest_enemy < lo) n++; |
987687 |
469920 |
1457607 |
|
| 85 |
5785511 |
| h = hi + 1; |
| 86 |
|
| } |
| 87 |
1903942 |
| return n; |
| 88 |
|
| } |
| 89 |
|
| |
| 90 |
3485878 |
| static int sen_evaluate(const struct sen_board *b, const struct sen_rules *r, |
| 91 |
|
| const struct sen_weights *w, int side) |
| 92 |
|
| { |
| 93 |
|
| int enemy, v; |
| 94 |
3485878 |
▶ | if (!b || !r || (side != SEN_SIDE_LIGHT && side != SEN_SIDE_DARK)) return 0; |
Branch: 4 branches
| Branch | True | False | Total |
| if (!b || !r || (side != SEN_SIDE_LIGHT && side != SEN_SIDE_DARK)) return 0; |
3485878 |
0 |
3485878 |
| if (!b || !r || (side != SEN_SIDE_LIGHT && side != SEN_SIDE_DARK)) return 0; |
3485878 |
0 |
3485878 |
| if (!b || !r || (side != SEN_SIDE_LIGHT && side != SEN_SIDE_DARK)) return 0; |
1204382 |
2281496 |
3485878 |
| if (!b || !r || (side != SEN_SIDE_LIGHT && side != SEN_SIDE_DARK)) return 0; |
0 |
1204382 |
1204382 |
|
| 95 |
3485878 |
| enemy = SEN_OTHER(side); |
| 96 |
3485878 |
| v = 16 * (sen_progress(b, side) - sen_progress(b, enemy)); |
| 97 |
3485878 |
▶ | if (w && w->blockade) |
Branch: 2 branches
| Branch | True | False | Total |
| if (w && w->blockade) |
3485878 |
0 |
3485878 |
| if (w && w->blockade) |
951971 |
2533907 |
3485878 |
|
| 98 |
951971 |
| v += w->blockade * (sen_term_blockade(b, r, side) - sen_term_blockade(b, r, enemy)); |
| 99 |
3485878 |
| return v; |
| 100 |
|
| } |
| 101 |
|
| |
| 102 |
|
| /* ---- a choice without looking ahead ------------------------------------------------- |
| 103 |
|
| * |
| 104 |
|
| * Of the moves the roll allows: bear off if one does; else swap if one does; |
| 105 |
|
| * else land on 26 if one does; else the move whose piece ENDS furthest on. A |
| 106 |
|
| * walk down from the water ends low, and is chosen last. Where two moves are |
| 107 |
|
| * alike in that, the later in the list. |
| 108 |
|
| */ |
| 109 |
|
| |
| 110 |
69624 |
▶ | static int sen_ends_at(const struct sen_move *m) { return m->off ? HOME_HOUSE : m->to; } |
Branch: 1 branch
| Branch | True | False | Total |
| static int sen_ends_at(const struct sen_move *m) { return m->off ? HOME_HOUSE : m->to; } |
68324 |
1300 |
69624 |
|
| 111 |
|
| |
| 112 |
30734 |
| static int sen_greedy(const struct sen_board *b, const struct sen_rules *r, int roll, int only) |
| 113 |
|
| { |
| 114 |
|
| struct sen_move m[SEN_MOVES_MAX]; |
| 115 |
30734 |
| int n = (SEN->moves)(b, r, roll, only, m, SEN_MOVES_MAX); |
| 116 |
30734 |
| int k, off = -1, swap = -1, happy = -1, furthest = -1; |
| 117 |
30734 |
▶ | if (n <= 0) return -1; |
Branch: 1 branch
| Branch | True | False | Total |
| if (n <= 0) return -1; |
0 |
30734 |
30734 |
|
| 118 |
30734 |
▶ | if (n > SEN_MOVES_MAX) n = SEN_MOVES_MAX; |
Branch: 1 branch
| Branch | True | False | Total |
| if (n > SEN_MOVES_MAX) n = SEN_MOVES_MAX; |
0 |
30734 |
30734 |
|
| 119 |
95239 |
▶ | for (k = 0; k < n; k++) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (k = 0; k < n; k++) { |
64505 |
30734 |
95239 |
|
| 120 |
64505 |
▶ | if (m[k].off) off = k; |
Branch: 1 branch
| Branch | True | False | Total |
| if (m[k].off) off = k; |
1768 |
62737 |
64505 |
|
| 121 |
64505 |
▶ | if (m[k].swap && (swap < 0 || sen_ends_at(&m[k]) >= sen_ends_at(&m[swap]))) swap = k; |
Branch: 3 branches
| Branch | True | False | Total |
| if (m[k].swap && (swap < 0 || sen_ends_at(&m[k]) >= sen_ends_at(&m[swap]))) swap = k; |
6221 |
58284 |
64505 |
| if (m[k].swap && (swap < 0 || sen_ends_at(&m[k]) >= sen_ends_at(&m[swap]))) swap = k; |
1041 |
5180 |
6221 |
| if (m[k].swap && (swap < 0 || sen_ends_at(&m[k]) >= sen_ends_at(&m[swap]))) swap = k; |
1041 |
0 |
1041 |
|
| 122 |
64505 |
▶ | if (!m[k].off && m[k].to == HAPPINESS) happy = k; |
Branch: 2 branches
| Branch | True | False | Total |
| if (!m[k].off && m[k].to == HAPPINESS) happy = k; |
62737 |
1768 |
64505 |
| if (!m[k].off && m[k].to == HAPPINESS) happy = k; |
2771 |
59966 |
62737 |
|
| 123 |
64505 |
▶ | if (furthest < 0 || sen_ends_at(&m[k]) >= sen_ends_at(&m[furthest])) furthest = k; |
Branch: 2 branches
| Branch | True | False | Total |
| if (furthest < 0 || sen_ends_at(&m[k]) >= sen_ends_at(&m[furthest])) furthest = k; |
33771 |
30734 |
64505 |
| if (furthest < 0 || sen_ends_at(&m[k]) >= sen_ends_at(&m[furthest])) furthest = k; |
33556 |
215 |
33771 |
|
| 124 |
|
| } |
| 125 |
30734 |
▶ | if (off >= 0) return off; |
Branch: 1 branch
| Branch | True | False | Total |
| if (off >= 0) return off; |
1767 |
28967 |
30734 |
|
| 126 |
28967 |
▶ | if (swap >= 0) return swap; |
Branch: 1 branch
| Branch | True | False | Total |
| if (swap >= 0) return swap; |
5019 |
23948 |
28967 |
|
| 127 |
23948 |
▶ | if (happy >= 0) return happy; |
Branch: 1 branch
| Branch | True | False | Total |
| if (happy >= 0) return happy; |
2408 |
21540 |
23948 |
|
| 128 |
21540 |
| return furthest; |
| 129 |
|
| } |
| 130 |
|
| |
| 131 |
|
| /* ---- the search --------------------------------------------------------------------- |
| 132 |
|
| * |
| 133 |
|
| * Expectiminimax. A position's value is the sum, over the five rolls the sticks |
| 134 |
|
| * can make, of that roll's weight in sixteenths times the value of the best move |
| 135 |
|
| * it allows, over sixteen. "Best" is the highest for the side the search is for |
| 136 |
|
| * and the lowest for the other. |
| 137 |
|
| * |
| 138 |
|
| * THE VALUE IS ALWAYS FOR ONE SIDE, fixed where the search starts, and whether |
| 139 |
|
| * a level takes the highest or the lowest is asked of the board each time. It is |
| 140 |
|
| * NOT a sign turned on every ply: after a 1, 4 or 5 the same side throws again, |
| 141 |
|
| * and a turned sign is wrong on exactly those plies. |
| 142 |
|
| * |
| 143 |
|
| * DEPTH COUNTS THROWS. A throw that allows nothing is a forfeit and spends a |
| 144 |
|
| * level like any other, so a chain of extra throws is bounded however long the |
| 145 |
|
| * sticks keep giving. THE BOUND PIECE TRAVELS WITH THE SEARCH, not in the |
| 146 |
|
| * board: after a move onto 26 under throw_on_26 the next throw moves that piece |
| 147 |
|
| * alone. |
| 148 |
|
| */ |
| 149 |
|
| |
| 150 |
|
| struct search { |
| 151 |
|
| const struct sen_rules *rules; |
| 152 |
|
| const struct sen_weights *weights; |
| 153 |
|
| int root; |
| 154 |
|
| unsigned long long nodes; |
| 155 |
|
| unsigned long long budget; |
| 156 |
|
| int unbounded; |
| 157 |
|
| int stopped; |
| 158 |
|
| }; |
| 159 |
|
| |
| 160 |
|
| static int sen_value(struct search *s, struct sen_board *b, int depth, int only); |
| 161 |
|
| |
| 162 |
1240526 |
| static int sen_best(struct search *s, struct sen_board *b, int roll, int depth, int only) |
| 163 |
|
| { |
| 164 |
|
| struct sen_move m[SEN_MOVES_MAX]; |
| 165 |
|
| struct sen_undo u; |
| 166 |
1240526 |
| int n = (SEN->moves)(b, s->rules, roll, only, m, SEN_MOVES_MAX); |
| 167 |
1240526 |
| int k, v, chosen = 0, ours; |
| 168 |
|
| |
| 169 |
1240526 |
▶ | if (n <= 0) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (n <= 0) { |
17605 |
1222921 |
1240526 |
|
| 170 |
17605 |
| (SEN->forfeit)(b, roll, &u); |
| 171 |
17605 |
| v = sen_value(s, b, depth - 1, 0); |
| 172 |
17605 |
| (SEN->unapply)(b, &u); |
| 173 |
17605 |
| return v; |
| 174 |
|
| } |
| 175 |
1222921 |
▶ | if (n > SEN_MOVES_MAX) n = SEN_MOVES_MAX; |
Branch: 1 branch
| Branch | True | False | Total |
| if (n > SEN_MOVES_MAX) n = SEN_MOVES_MAX; |
0 |
1222921 |
1222921 |
|
| 176 |
1222921 |
| ours = (SEN->side)(b) == s->root; |
| 177 |
4675511 |
▶ | for (k = 0; k < n; k++) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (k = 0; k < n; k++) { |
3452828 |
1222683 |
4675511 |
|
| 178 |
3452828 |
| (SEN->apply)(b, s->rules, &m[k], &u); |
| 179 |
3452828 |
| v = sen_value(s, b, depth - 1, u.bound); |
| 180 |
3452828 |
| (SEN->unapply)(b, &u); |
| 181 |
3452828 |
▶ | if (s->stopped) return 0; |
Branch: 1 branch
| Branch | True | False | Total |
| if (s->stopped) return 0; |
238 |
3452590 |
3452828 |
|
| 182 |
3452590 |
▶ | 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; |
2229753 |
1222837 |
3452590 |
| if (k == 0 || (ours ? v > chosen : v < chosen)) chosen = v; |
1201965 |
1027788 |
2229753 |
| if (k == 0 || (ours ? v > chosen : v < chosen)) chosen = v; |
115996 |
1085969 |
1201965 |
| if (k == 0 || (ours ? v > chosen : v < chosen)) chosen = v; |
116849 |
910939 |
1027788 |
|
| 183 |
|
| } |
| 184 |
1222683 |
| return chosen; |
| 185 |
|
| } |
| 186 |
|
| |
| 187 |
3679160 |
| static int sen_value(struct search *s, struct sen_board *b, int depth, int only) |
| 188 |
|
| { |
| 189 |
3679160 |
| int i, roll, weight, denominator, sum = 0, winner; |
| 190 |
|
| |
| 191 |
3679160 |
▶ | 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; } |
3472279 |
206881 |
3679160 |
| if (!s->unbounded && s->nodes >= s->budget) { s->stopped = 1; return 0; } |
108 |
3472171 |
3472279 |
|
| 192 |
3679052 |
| s->nodes++; |
| 193 |
|
| |
| 194 |
3679052 |
| winner = (SEN->winner)(b); |
| 195 |
3679052 |
▶ | if (winner >= 0) return winner == s->root ? SEN_WIN + depth : -(SEN_WIN + depth); |
Branch: 2 branches
| Branch | True | False | Total |
| if (winner >= 0) return winner == s->root ? SEN_WIN + depth : -(SEN_WIN + depth); |
1156 |
3677896 |
3679052 |
| if (winner >= 0) return winner == s->root ? SEN_WIN + depth : -(SEN_WIN + depth); |
475 |
681 |
1156 |
|
| 196 |
3677896 |
▶ | if ((SEN->status)(b) != SEN_ONGOING) return 0; |
Branch: 1 branch
| Branch | True | False | Total |
| if ((SEN->status)(b) != SEN_ONGOING) return 0; |
0 |
3677896 |
3677896 |
|
| 197 |
3677896 |
▶ | if (depth <= 0) return sen_evaluate(b, s->rules, s->weights, s->root); |
Branch: 1 branch
| Branch | True | False | Total |
| if (depth <= 0) return sen_evaluate(b, s->rules, s->weights, s->root); |
3429690 |
248206 |
3677896 |
|
| 198 |
|
| |
| 199 |
1488492 |
▶ | for (i = 0; i < (SEN->chance_count)(); i++) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (i = 0; i < (SEN->chance_count)(); i++) { |
1240526 |
247966 |
1488492 |
|
| 200 |
1240526 |
| (SEN->chance)(i, &roll, &weight, &denominator); |
| 201 |
1240526 |
| sum += weight * sen_best(s, b, roll, depth, only); |
| 202 |
1240526 |
▶ | if (s->stopped) return 0; |
Branch: 1 branch
| Branch | True | False | Total |
| if (s->stopped) return 0; |
240 |
1240286 |
1240526 |
|
| 203 |
|
| } |
| 204 |
247966 |
▶ | return sum >= 0 ? sum / denominator : -((-sum) / denominator); |
Branch: 1 branch
| Branch | True | False | Total |
| return sum >= 0 ? sum / denominator : -((-sum) / denominator); |
107428 |
140538 |
247966 |
|
| 205 |
|
| } |
| 206 |
|
| |
| 207 |
|
| /* The value of a position BEFORE its throw, for `side`, `depth` throws deep. |
| 208 |
|
| * For tests whose answer is worked by hand. */ |
| 209 |
2406 |
| static int sen_expect(const struct sen_board *board, const struct sen_rules *r, |
| 210 |
|
| const struct sen_weights *w, int only, int depth, int side) |
| 211 |
|
| { |
| 212 |
|
| struct sen_weights plain; |
| 213 |
|
| struct sen_board *b; |
| 214 |
|
| struct search s; |
| 215 |
|
| int v; |
| 216 |
2406 |
▶ | if (!board || !r || !(SEN->rules_ok)(r)) return 0; |
Branch: 3 branches
| Branch | True | False | Total |
| if (!board || !r || !(SEN->rules_ok)(r)) return 0; |
2406 |
0 |
2406 |
| if (!board || !r || !(SEN->rules_ok)(r)) return 0; |
2406 |
0 |
2406 |
| if (!board || !r || !(SEN->rules_ok)(r)) return 0; |
0 |
2406 |
2406 |
|
| 217 |
2406 |
▶ | if (!w) { sen_weights_default(&plain); w = &plain; } |
Branch: 1 branch
| Branch | True | False | Total |
| if (!w) { sen_weights_default(&plain); w = &plain; } |
0 |
2406 |
2406 |
|
| 218 |
2406 |
| b = (SEN->board_copy)(board); |
| 219 |
2406 |
▶ | if (!b) return 0; |
Branch: 1 branch
| Branch | True | False | Total |
| if (!b) return 0; |
0 |
2406 |
2406 |
|
| 220 |
2406 |
| s.rules = r; |
| 221 |
2406 |
| s.weights = w; |
| 222 |
2406 |
| s.root = side; |
| 223 |
2406 |
| s.nodes = 0; |
| 224 |
2406 |
| s.budget = 0; |
| 225 |
2406 |
| s.unbounded = 1; |
| 226 |
2406 |
| s.stopped = 0; |
| 227 |
2406 |
| v = sen_value(&s, b, depth, only); |
| 228 |
2406 |
| (SEN->board_drop)(b); |
| 229 |
2406 |
| return v; |
| 230 |
|
| } |
| 231 |
|
| |
| 232 |
53396 |
| static int sen_search(const struct sen_board *board, const struct sen_rules *r, int roll, int only, |
| 233 |
|
| const struct sen_weights *weights, unsigned long long budget, int max_depth, |
| 234 |
|
| struct sen_search_info *info) |
| 235 |
|
| { |
| 236 |
|
| struct sen_weights plain; |
| 237 |
|
| struct sen_search_info local; |
| 238 |
|
| struct sen_move m[SEN_MOVES_MAX]; |
| 239 |
|
| struct sen_undo u; |
| 240 |
|
| struct sen_board *b; |
| 241 |
|
| struct search s; |
| 242 |
53396 |
| int n, depth, k, chosen = 0; |
| 243 |
|
| |
| 244 |
53396 |
▶ | if (!info) info = &local; |
Branch: 1 branch
| Branch | True | False | Total |
| if (!info) info = &local; |
0 |
53396 |
53396 |
|
| 245 |
53396 |
| info->nodes = 0; |
| 246 |
53396 |
| info->depth = 0; |
| 247 |
53396 |
| info->value = 0; |
| 248 |
53396 |
| info->stopped = 0; |
| 249 |
|
| |
| 250 |
53396 |
▶ | if (!board || !r || !(SEN->rules_ok)(r)) return -1; |
Branch: 3 branches
| Branch | True | False | Total |
| if (!board || !r || !(SEN->rules_ok)(r)) return -1; |
53396 |
0 |
53396 |
| if (!board || !r || !(SEN->rules_ok)(r)) return -1; |
53396 |
0 |
53396 |
| if (!board || !r || !(SEN->rules_ok)(r)) return -1; |
0 |
53396 |
53396 |
|
| 251 |
53396 |
▶ | if (!weights) { sen_weights_default(&plain); weights = &plain; } |
Branch: 1 branch
| Branch | True | False | Total |
| if (!weights) { sen_weights_default(&plain); weights = &plain; } |
0 |
53396 |
53396 |
|
| 252 |
53396 |
▶ | if ((SEN->status)(board) != SEN_ONGOING) return -1; |
Branch: 1 branch
| Branch | True | False | Total |
| if ((SEN->status)(board) != SEN_ONGOING) return -1; |
1 |
53395 |
53396 |
|
| 253 |
|
| |
| 254 |
53395 |
| b = (SEN->board_copy)(board); |
| 255 |
53395 |
▶ | if (!b) return -1; |
Branch: 1 branch
| Branch | True | False | Total |
| if (!b) return -1; |
0 |
53395 |
53395 |
|
| 256 |
53395 |
| n = (SEN->moves)(b, r, roll, only, m, SEN_MOVES_MAX); |
| 257 |
53395 |
▶ | if (n <= 0) { (SEN->board_drop)(b); return -1; } |
Branch: 1 branch
| Branch | True | False | Total |
| if (n <= 0) { (SEN->board_drop)(b); return -1; } |
38 |
53357 |
53395 |
|
| 258 |
53357 |
▶ | if (n > SEN_MOVES_MAX) n = SEN_MOVES_MAX; |
Branch: 1 branch
| Branch | True | False | Total |
| if (n > SEN_MOVES_MAX) n = SEN_MOVES_MAX; |
0 |
53357 |
53357 |
|
| 259 |
53357 |
▶ | if (max_depth <= 0 || max_depth > SEN_DEPTH_MAX) max_depth = SEN_DEPTH_MAX; |
Branch: 2 branches
| Branch | True | False | Total |
| if (max_depth <= 0 || max_depth > SEN_DEPTH_MAX) max_depth = SEN_DEPTH_MAX; |
53235 |
122 |
53357 |
| if (max_depth <= 0 || max_depth > SEN_DEPTH_MAX) max_depth = SEN_DEPTH_MAX; |
0 |
53235 |
53235 |
|
| 260 |
|
| |
| 261 |
53357 |
| s.rules = r; |
| 262 |
53357 |
| s.weights = weights; |
| 263 |
53357 |
| s.root = (SEN->side)(b); |
| 264 |
53357 |
| s.nodes = 0; |
| 265 |
53357 |
| s.budget = budget; |
| 266 |
|
| |
| 267 |
119332 |
▶ | for (depth = 1; depth <= max_depth; depth++) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (depth = 1; depth <= max_depth; depth++) { |
82665 |
36667 |
119332 |
|
| 268 |
82665 |
| int best_k = 0, best_v = 0, v; |
| 269 |
82665 |
| s.unbounded = (depth == 1); |
| 270 |
82665 |
| s.stopped = 0; |
| 271 |
288878 |
▶ | for (k = 0; k < n; k++) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (k = 0; k < n; k++) { |
206321 |
82557 |
288878 |
|
| 272 |
206321 |
| (SEN->apply)(b, r, &m[k], &u); |
| 273 |
206321 |
| v = sen_value(&s, b, depth - 1, u.bound); |
| 274 |
206321 |
| (SEN->unapply)(b, &u); |
| 275 |
206321 |
▶ | if (s.stopped) break; |
Branch: 1 branch
| Branch | True | False | Total |
| if (s.stopped) break; |
108 |
206213 |
206321 |
|
| 276 |
206213 |
▶ | if (k == 0 || (weights->ties == SEN_TIES_LAST ? v >= best_v : v > best_v)) { |
Branch: 4 branches
| Branch | True | False | Total |
| if (k == 0 || (weights->ties == SEN_TIES_LAST ? v >= best_v : v > best_v)) { |
123604 |
82609 |
206213 |
| if (k == 0 || (weights->ties == SEN_TIES_LAST ? v >= best_v : v > best_v)) { |
123604 |
0 |
123604 |
| if (k == 0 || (weights->ties == SEN_TIES_LAST ? v >= best_v : v > best_v)) { |
74179 |
49425 |
123604 |
| if (k == 0 || (weights->ties == SEN_TIES_LAST ? v >= best_v : v > best_v)) { |
0 |
0 |
0 |
|
| 277 |
156788 |
| best_v = v; |
| 278 |
156788 |
| best_k = k; |
| 279 |
|
| } |
| 280 |
|
| } |
| 281 |
82665 |
▶ | if (s.stopped) { info->stopped = 1; break; } |
Branch: 1 branch
| Branch | True | False | Total |
| if (s.stopped) { info->stopped = 1; break; } |
108 |
82557 |
82665 |
|
| 282 |
82557 |
| chosen = best_k; |
| 283 |
82557 |
| info->depth = depth; |
| 284 |
82557 |
| info->value = best_v; |
| 285 |
82557 |
▶ | if (n == 1) break; |
Branch: 1 branch
| Branch | True | False | Total |
| if (n == 1) break; |
16576 |
65981 |
82557 |
|
| 286 |
65981 |
▶ | if (s.nodes >= s.budget) break; |
Branch: 1 branch
| Branch | True | False | Total |
| if (s.nodes >= s.budget) break; |
6 |
65975 |
65981 |
|
| 287 |
|
| } |
| 288 |
|
| |
| 289 |
53357 |
| info->nodes = s.nodes; |
| 290 |
53357 |
| (SEN->board_drop)(b); |
| 291 |
53357 |
| return chosen; |
| 292 |
|
| } |
| 293 |
|
| |
| 294 |
|
| /* ---- the table ------------------------------------------------------------------- */ |
| 295 |
|
| |
| 296 |
80 |
| void sen_search_install(struct sen_abi *t) |
| 297 |
|
| { |
| 298 |
80 |
| SEN = t; |
| 299 |
80 |
| t->weights_default = sen_weights_default; |
| 300 |
80 |
| t->evaluate = sen_evaluate; |
| 301 |
80 |
| t->greedy = sen_greedy; |
| 302 |
80 |
| t->search = sen_search; |
| 303 |
80 |
| t->expect = sen_expect; |
| 304 |
80 |
| } |