| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| if (w) return w; |
2004793 |
0 |
2004793 |
|
| 57 |
0 |
▶ | if (!ready) { fn_weights_default(&def); ready = 1; } |
Branch: 1 branch
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| for (rank = 0; rank < rows; rank++) { |
10010079 |
2002341 |
12012420 |
|
| 73 |
100086156 |
▶ | for (file = 0; file < cols; file++) { |
Branch: 1 branch
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| if (w->centre) { |
5810375 |
10 |
5810385 |
|
| 81 |
5810375 |
▶ | df = file > mid_file ? file - mid_file : mid_file - file; |
Branch: 1 branch
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| if (w->room) { |
5810375 |
10 |
5810385 |
|
| 86 |
52293375 |
▶ | for (d = 0; d < FN_DIRS; d++) { |
Branch: 1 branch
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| if (!winner) return 0; |
895 |
226696 |
227591 |
|
| 168 |
226696 |
▶ | return winner == side ? FN_WIN_SCORE - ply : -(FN_WIN_SCORE - ply); |
Branch: 1 branch
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| if (n > FN_STEPS_MAX) n = FN_STEPS_MAX; |
0 |
1105523 |
1105523 |
|
| 192 |
1105523 |
▶ | if (n == 0) break; |
Branch: 1 branch
| Branch | True | False | Total |
| if (n == 0) break; |
0 |
1105523 |
1105523 |
|
| 193 |
1105523 |
▶ | if ((T->chain_at)(b) < 0) { |
Branch: 1 branch
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| if (side != FN_WHITE) score = -score; |
102670 |
53244 |
155914 |
|
| 222 |
|
| } |
| 223 |
1303179 |
▶ | while (made-- > 0) (T->game_undo)(c->g); |
Branch: 1 branch
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| if (n > FN_STEPS_MAX) n = FN_STEPS_MAX; |
0 |
4312250 |
4312250 |
|
| 252 |
|
| |
| 253 |
4312250 |
▶ | if (!in_chain) { |
Branch: 1 branch
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| return side == FN_WHITE ? s : -s; |
1179914 |
666486 |
1846400 |
|
| 261 |
|
| } |
| 262 |
2062644 |
| key = (T->key)(b); |
| 263 |
2062644 |
▶ | if (c->tt) { |
Branch: 1 branch
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| if (alpha >= beta) return e->score; |
460602 |
51209 |
511811 |
|
| 270 |
|
| } |
| 271 |
1539490 |
▶ | if (e->key != key) e = NULL; |
Branch: 1 branch
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| if (c->stopped) return 0; |
101 |
49535 |
49636 |
|
| 285 |
49535 |
| best = s; |
| 286 |
49535 |
▶ | if (best > alpha) alpha = best; |
Branch: 1 branch
| Branch | True | False | Total |
| if (best > alpha) alpha = best; |
14987 |
34548 |
49535 |
|
| 287 |
|
| } |
| 288 |
|
| |
| 289 |
6056553 |
▶ | for (i = 0; i < n && alpha < beta; i++) { |
Branch: 2 branches
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| if (c->stopped) return 0; |
10146 |
4467528 |
4477674 |
|
| 302 |
4467528 |
▶ | if (s > best) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (s > best) { |
2150528 |
2317000 |
4467528 |
|
| 303 |
2150528 |
| best = s; |
| 304 |
2150528 |
| best_i = i; |
| 305 |
2150528 |
▶ | if (line) { |
Branch: 1 branch
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| c.seed = seed ? seed : 1; |
2452 |
0 |
2452 |
|
| 367 |
|
| |
| 368 |
7332 |
▶ | while (size < budget && size < ((size_t) 1 << 20)) size <<= 1; |
Branch: 2 branches
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| if (c.nodes >= c.budget) break; |
13 |
11566 |
11579 |
|
| 387 |
|
| } |
| 388 |
|
| |
| 389 |
2452 |
▶ | if (best) *best = kept; |
Branch: 1 branch
| Branch | True | False | Total |
| if (best) *best = kept; |
2452 |
0 |
2452 |
|
| 390 |
2452 |
▶ | if (info) { |
Branch: 1 branch
| Branch | True | False | Total |
| 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 |
| } |