| 1 |
|
| /* go_search.c - the playouts, and the confidence bound over the root moves. |
| 2 |
|
| * |
| 3 |
|
| * PERL-FREE, like go_engine.c, and under the same rules: no perl.h, no stdio.h, |
| 4 |
|
| * no rand, no time. t/24-no-io.t scans this file too. |
| 5 |
|
| * |
| 6 |
|
| * ALPHA-BETA DOES NOT WORK ON GO. There is no static evaluation to search with |
| 7 |
|
| * (whether a stone is strong depends on whether its group will live, which is |
| 8 |
|
| * the thing an evaluation was wanted for) and the branching factor is 361 at |
| 9 |
|
| * the root. So the leaf value here is the result of playing the position out at |
| 10 |
|
| * random and counting it, which needs no evaluation function at all. |
| 11 |
|
| * |
| 12 |
|
| * EVERYTHING IS INTEGER, the confidence bound included. A float in the selection |
| 13 |
|
| * formula is an implementation-defined rounding in the middle of a move choice, |
| 14 |
|
| * and this bot has to return the same move on every machine or the replay of a |
| 15 |
|
| * bot game stops reproducing. |
| 16 |
|
| */ |
| 17 |
|
| |
| 18 |
|
| #include <stdlib.h> |
| 19 |
|
| #include <string.h> |
| 20 |
|
| |
| 21 |
|
| #include "go_abi.h" |
| 22 |
|
| |
| 23 |
|
| /* go_engine.c's table, fetched once. Using the published ABI rather than |
| 24 |
|
| * reaching for its statics keeps this file a consumer like any other, and keeps |
| 25 |
|
| * the engine's internals the engine's business. */ |
| 26 |
|
| static const struct go_abi *EN = NULL; |
| 27 |
55951 |
▶ | static void need_engine(void) { if (!EN) EN = go_abi_table(); } |
Branch: 1 branch
| Branch | True | False | Total |
| static void need_engine(void) { if (!EN) EN = go_abi_table(); } |
9 |
55942 |
55951 |
|
| 28 |
|
| |
| 29 |
|
| /* ---------------------------------------------------------------- xorshift32 -- |
| 30 |
|
| * |
| 31 |
|
| * The whole generator, and the reason it is this one rather than something |
| 32 |
|
| * wider, is in go_abi.h: a 64-bit product on a perl with 32-bit integers goes |
| 33 |
|
| * silently through an NV and loses its low bits, so a generator anybody might |
| 34 |
|
| * mirror from Perl has to live in add, xor and shift. |
| 35 |
|
| */ |
| 36 |
4552908 |
| static unsigned int go_prng_next(unsigned int *state) |
| 37 |
|
| { |
| 38 |
|
| unsigned int x; |
| 39 |
4552908 |
▶ | if (!state) return 0; |
Branch: 1 branch
| Branch | True | False | Total |
| if (!state) return 0; |
0 |
4552908 |
4552908 |
|
| 40 |
|
| |
| 41 |
|
| /* ZERO IS A FIXED POINT of xorshift, so a zero state would make every |
| 42 |
|
| * playout identical while every test still passed. Corrected rather than |
| 43 |
|
| * accepted, and the constant is arbitrary but pinned. */ |
| 44 |
4552908 |
▶ | if (*state == 0) *state = 2463534242u; |
Branch: 1 branch
| Branch | True | False | Total |
| if (*state == 0) *state = 2463534242u; |
3 |
4552905 |
4552908 |
|
| 45 |
|
| |
| 46 |
4552908 |
| x = *state; |
| 47 |
4552908 |
| x ^= x << 13; |
| 48 |
4552908 |
| x ^= x >> 17; |
| 49 |
4552908 |
| x ^= x << 5; |
| 50 |
4552908 |
| *state = x; |
| 51 |
4552908 |
| return x; |
| 52 |
|
| } |
| 53 |
|
| |
| 54 |
|
| /* ------------------------------------------------------------------ the eye -- |
| 55 |
|
| * |
| 56 |
|
| * A TRUE EYE, and the definition is what makes a playout terminate at all. A |
| 57 |
|
| * uniformly random legal move fills its own eyes, which kills its own groups, |
| 58 |
|
| * which means the position never settles and the playout runs to its cap. |
| 59 |
|
| * |
| 60 |
|
| * a point is a true eye for colour C when |
| 61 |
|
| * every orthogonal neighbour is C or off the board, AND |
| 62 |
|
| * of the diagonals that are on the board, |
| 63 |
|
| * at most one is not C -- in the middle |
| 64 |
|
| * none is not C -- on an edge or in a corner |
| 65 |
|
| * |
| 66 |
|
| * THE EDGE CLAUSE IS THE HALF EVERYBODY LEAVES OUT, and leaving it out makes a |
| 67 |
|
| * playout fill real eyes on the first line. t/20-bot-eyes.t has a position for |
| 68 |
|
| * each clause. |
| 69 |
|
| */ |
| 70 |
186577737 |
| static int is_true_eye(const struct go_board *b, int pt, int colour) |
| 71 |
|
| { |
| 72 |
186577737 |
| int i, on_edge = 0, wrong = 0; |
| 73 |
|
| int diag[4]; |
| 74 |
|
| |
| 75 |
298189739 |
▶ | for (i = 0; i < 4; i++) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (i = 0; i < 4; i++) { |
285473734 |
12716005 |
298189739 |
|
| 76 |
285473734 |
| int c = b->colour[pt + b->nbr[i]]; |
| 77 |
285473734 |
▶ | if (c == GO_BORDER) { on_edge = 1; continue; } |
Branch: 1 branch
| Branch | True | False | Total |
| if (c == GO_BORDER) { on_edge = 1; continue; } |
25730073 |
259743661 |
285473734 |
|
| 78 |
259743661 |
▶ | if (c != colour) return 0; |
Branch: 1 branch
| Branch | True | False | Total |
| if (c != colour) return 0; |
173861732 |
85881929 |
259743661 |
|
| 79 |
|
| } |
| 80 |
|
| |
| 81 |
12716005 |
| diag[0] = pt - 1 - b->stride; |
| 82 |
12716005 |
| diag[1] = pt + 1 - b->stride; |
| 83 |
12716005 |
| diag[2] = pt - 1 + b->stride; |
| 84 |
12716005 |
| diag[3] = pt + 1 + b->stride; |
| 85 |
|
| |
| 86 |
63580025 |
▶ | for (i = 0; i < 4; i++) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (i = 0; i < 4; i++) { |
50864020 |
12716005 |
63580025 |
|
| 87 |
50864020 |
| int c = b->colour[diag[i]]; |
| 88 |
50864020 |
▶ | if (c == GO_BORDER) continue; |
Branch: 1 branch
| Branch | True | False | Total |
| if (c == GO_BORDER) continue; |
13561711 |
37302309 |
50864020 |
|
| 89 |
37302309 |
▶ | if (c != colour) wrong++; |
Branch: 1 branch
| Branch | True | False | Total |
| if (c != colour) wrong++; |
9888275 |
27414034 |
37302309 |
|
| 90 |
|
| } |
| 91 |
|
| |
| 92 |
12716005 |
▶ | return on_edge ? (wrong == 0) : (wrong <= 1); |
Branch: 1 branch
| Branch | True | False | Total |
| return on_edge ? (wrong == 0) : (wrong <= 1); |
6029278 |
6686727 |
12716005 |
|
| 93 |
|
| } |
| 94 |
|
| |
| 95 |
|
| /* ---------------------------------------------------------------- a playout -- |
| 96 |
|
| * |
| 97 |
|
| * Random legal moves, alternating, until both players pass or the cap trips. |
| 98 |
|
| * Returns the AREA score difference in points, from black's side. |
| 99 |
|
| * |
| 100 |
|
| * The board is played on DESTRUCTIVELY, so the caller hands over a copy. The |
| 101 |
|
| * history is null, which the engine reads as simple ko and nothing else: see |
| 102 |
|
| * go_abi.h for why a playout does not carry a superko history. |
| 103 |
|
| */ |
| 104 |
55010 |
| static int playout_on(struct go_board *b, int colour, unsigned int *state, |
| 105 |
|
| int *moves_out, int *capped_out) |
| 106 |
|
| { |
| 107 |
|
| int choices[GO_MAX_PTS]; |
| 108 |
|
| struct go_played res; |
| 109 |
|
| struct go_score s; |
| 110 |
55010 |
| int passes = 0, moves = 0, cap, size; |
| 111 |
|
| |
| 112 |
55010 |
| need_engine(); |
| 113 |
55010 |
| size = (EN->size_of)(b); |
| 114 |
55010 |
| cap = 3 * size * size; |
| 115 |
|
| |
| 116 |
4867163 |
▶ | while (passes < 2 && moves < cap) { |
Branch: 2 branches
| Branch | True | False | Total |
| while (passes < 2 && moves < cap) { |
4812153 |
55010 |
4867163 |
| while (passes < 2 && moves < cap) { |
4812153 |
0 |
4812153 |
|
| 117 |
4812153 |
| int n = 0, r, c; |
| 118 |
|
| |
| 119 |
54627736 |
▶ | for (r = 0; r < size; r++) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (r = 0; r < size; r++) { |
49815583 |
4812153 |
54627736 |
|
| 120 |
608113328 |
▶ | for (c = 0; c < size; c++) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (c = 0; c < size; c++) { |
558297745 |
49815583 |
608113328 |
|
| 121 |
558297745 |
| int pt = (EN->point_of)(b, c, r); |
| 122 |
558297745 |
▶ | if ((EN->at)(b, pt) != GO_EMPTY) continue; |
Branch: 1 branch
| Branch | True | False | Total |
| if ((EN->at)(b, pt) != GO_EMPTY) continue; |
356624700 |
201673045 |
558297745 |
|
| 123 |
201673045 |
▶ | if ((EN->legal)(b, NULL, pt, colour) != GO_OK) continue; |
Branch: 1 branch
| Branch | True | False | Total |
| if ((EN->legal)(b, NULL, pt, colour) != GO_OK) continue; |
15095308 |
186577737 |
201673045 |
|
| 124 |
186577737 |
▶ | if (is_true_eye(b, pt, colour)) continue; /* never its own eye */ |
Branch: 1 branch
| Branch | True | False | Total |
| if (is_true_eye(b, pt, colour)) continue; /* never its own eye */ |
8612074 |
177965663 |
186577737 |
|
| 125 |
177965663 |
| choices[n++] = pt; |
| 126 |
|
| } |
| 127 |
|
| } |
| 128 |
|
| |
| 129 |
4812153 |
▶ | if (n == 0) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (n == 0) { |
290273 |
4521880 |
4812153 |
|
| 130 |
290273 |
| (EN->pass)(b, colour); |
| 131 |
290273 |
| passes++; |
| 132 |
|
| } else { |
| 133 |
4521880 |
| (EN->play)(b, NULL, choices[go_prng_next(state) % (unsigned int)n], |
| 134 |
|
| colour, &res); |
| 135 |
4521880 |
| passes = 0; |
| 136 |
4521880 |
| moves++; |
| 137 |
|
| } |
| 138 |
4812153 |
▶ | colour = GO_OTHER(colour); |
Branch: 1 branch
| Branch | True | False | Total |
| colour = GO_OTHER(colour); |
2408870 |
2403283 |
4812153 |
|
| 139 |
|
| } |
| 140 |
|
| |
| 141 |
55010 |
▶ | if (moves >= cap && capped_out) (*capped_out)++; |
Branch: 2 branches
| Branch | True | False | Total |
| if (moves >= cap && capped_out) (*capped_out)++; |
0 |
55010 |
55010 |
| if (moves >= cap && capped_out) (*capped_out)++; |
0 |
0 |
0 |
|
| 142 |
55010 |
▶ | if (moves_out) *moves_out += moves; |
Branch: 1 branch
| Branch | True | False | Total |
| if (moves_out) *moves_out += moves; |
53690 |
1320 |
55010 |
|
| 143 |
|
| |
| 144 |
|
| /* AREA SCORING, because a playout has nobody to agree dead stones with. |
| 145 |
|
| * Komi is not applied here: the search compares playouts against each |
| 146 |
|
| * other, and a constant added to every one of them changes nothing. */ |
| 147 |
55010 |
| (EN->score_area)(b, &s); |
| 148 |
55010 |
| return s.area_b - s.area_w; |
| 149 |
|
| } |
| 150 |
|
| |
| 151 |
120 |
| static int go_playout(const struct go_board *b, int colour, |
| 152 |
|
| unsigned int *state, int *moves_out) |
| 153 |
|
| { |
| 154 |
|
| struct go_board *work; |
| 155 |
|
| int diff; |
| 156 |
|
| |
| 157 |
120 |
| need_engine(); |
| 158 |
120 |
▶ | if (!b) return 0; |
Branch: 1 branch
| Branch | True | False | Total |
| if (!b) return 0; |
0 |
120 |
120 |
|
| 159 |
120 |
| work = (EN->board_copy)(b); |
| 160 |
120 |
▶ | if (!work) return 0; |
Branch: 1 branch
| Branch | True | False | Total |
| if (!work) return 0; |
0 |
120 |
120 |
|
| 161 |
|
| |
| 162 |
120 |
| diff = playout_on(work, colour, state, moves_out, NULL); |
| 163 |
120 |
| (EN->board_drop)(work); |
| 164 |
120 |
| return diff; |
| 165 |
|
| } |
| 166 |
|
| |
| 167 |
|
| /* ----------------------------------------------------- the confidence bound -- |
| 168 |
|
| * |
| 169 |
|
| * UCB1, in integers. Integer square root by Newton, and a floor-log-2 standing |
| 170 |
|
| * in for the natural log: the difference between them is a constant factor, and |
| 171 |
|
| * the constant is a tunable rather than a fact. |
| 172 |
|
| */ |
| 173 |
1258207 |
| static unsigned int isqrt32(unsigned int n) |
| 174 |
|
| { |
| 175 |
|
| unsigned int x, y; |
| 176 |
1258207 |
▶ | if (n == 0) return 0; |
Branch: 1 branch
| Branch | True | False | Total |
| if (n == 0) return 0; |
0 |
1258207 |
1258207 |
|
| 177 |
1258207 |
| x = n; |
| 178 |
|
| for (;;) { |
| 179 |
17277965 |
| y = (x + n / x) / 2; |
| 180 |
17277965 |
▶ | if (y >= x) break; |
Branch: 1 branch
| Branch | True | False | Total |
| if (y >= x) break; |
1258207 |
16019758 |
17277965 |
|
| 181 |
16019758 |
| x = y; |
| 182 |
|
| } |
| 183 |
1258207 |
| return x; |
| 184 |
|
| } |
| 185 |
|
| |
| 186 |
1258207 |
| static int ilog2i(unsigned int n) |
| 187 |
|
| { |
| 188 |
1258207 |
| int r = 0; |
| 189 |
11273614 |
▶ | while (n >>= 1) r++; |
Branch: 1 branch
| Branch | True | False | Total |
| while (n >>= 1) r++; |
10015407 |
1258207 |
11273614 |
|
| 190 |
1258207 |
| return r; |
| 191 |
|
| } |
| 192 |
|
| |
| 193 |
|
| /* In permille. An unvisited move sorts above every visited one, so the first |
| 194 |
|
| * pass over the root tries each move once, IN POINT ORDER. */ |
| 195 |
|
| #define GO_UNVISITED (1 << 28) |
| 196 |
|
| |
| 197 |
|
| /* The fewest samples at which a root move's win count means anything. A single |
| 198 |
|
| * playout of a Go position is close to a coin flip, so below this the selection |
| 199 |
|
| * is reading noise. Used to cut the root set down to what the budget can |
| 200 |
|
| * actually compare: see the note in go_search. */ |
| 201 |
|
| #define GO_MIN_VISITS 8 |
| 202 |
|
| |
| 203 |
1313950 |
| static int ucb_permille(int wins, int visits, int total, int explore) |
| 204 |
|
| { |
| 205 |
|
| int exploit, term, lg; |
| 206 |
|
| |
| 207 |
1313950 |
▶ | if (visits <= 0) return GO_UNVISITED; |
Branch: 1 branch
| Branch | True | False | Total |
| if (visits <= 0) return GO_UNVISITED; |
55743 |
1258207 |
1313950 |
|
| 208 |
|
| |
| 209 |
1258207 |
| exploit = (wins * 1000) / visits; |
| 210 |
|
| |
| 211 |
1258207 |
▶ | lg = ilog2i((unsigned int)(total < 2 ? 2 : total)); |
Branch: 1 branch
| Branch | True | False | Total |
| lg = ilog2i((unsigned int)(total < 2 ? 2 : total)); |
1257408 |
799 |
1258207 |
|
| 212 |
1258207 |
| term = (int)isqrt32((unsigned int)((lg * 1000000) / visits)); |
| 213 |
|
| |
| 214 |
1258207 |
| return exploit + (explore * term) / 1000; |
| 215 |
|
| } |
| 216 |
|
| |
| 217 |
|
| /* ------------------------------------------------------------- the search ---- |
| 218 |
|
| * |
| 219 |
|
| * FLAT, meaning the tree is one level: an array of visits and wins indexed by |
| 220 |
|
| * point, over the root moves the caller handed in. That is what the plan asked |
| 221 |
|
| * for and it is what a beginner-strength bot needs; a deep tree is strength for |
| 222 |
|
| * a lot more memory and a much harder determinism argument. |
| 223 |
|
| * |
| 224 |
|
| * `allowed` is the root moves the CALLER filtered, which is how this file never |
| 225 |
|
| * has to see the superko history. A point of -1 is a pass. |
| 226 |
|
| */ |
| 227 |
799 |
| static void go_search(const struct go_board *b, int colour, |
| 228 |
|
| const int *allowed, int nallowed, |
| 229 |
|
| unsigned int seed, int playouts, int explore, |
| 230 |
|
| struct go_search *out) |
| 231 |
|
| { |
| 232 |
|
| int visits[GO_MAX_PTS + 1]; |
| 233 |
|
| int wins[GO_MAX_PTS + 1]; |
| 234 |
|
| int roots[GO_MAX_PTS + 1]; /* the root moves actually searched */ |
| 235 |
799 |
| unsigned int state = seed; |
| 236 |
799 |
| int i, done = 0, best = 0, nroots = 0; |
| 237 |
799 |
| int pass_slot = GO_MAX_PTS; /* the pass lives past the last real point */ |
| 238 |
|
| |
| 239 |
799 |
| need_engine(); |
| 240 |
799 |
▶ | if (!out) return; |
Branch: 1 branch
| Branch | True | False | Total |
| if (!out) return; |
0 |
799 |
799 |
|
| 241 |
799 |
| out->point = -1; |
| 242 |
799 |
| out->playouts = 0; |
| 243 |
799 |
| out->visits = 0; |
| 244 |
799 |
| out->win_permille = 0; |
| 245 |
799 |
| out->capped = 0; |
| 246 |
799 |
| out->moves = 0; |
| 247 |
799 |
▶ | if (!b || !allowed || nallowed <= 0) return; |
Branch: 3 branches
| Branch | True | False | Total |
| if (!b || !allowed || nallowed <= 0) return; |
799 |
0 |
799 |
| if (!b || !allowed || nallowed <= 0) return; |
799 |
0 |
799 |
| if (!b || !allowed || nallowed <= 0) return; |
0 |
799 |
799 |
|
| 248 |
|
| |
| 249 |
353957 |
▶ | for (i = 0; i <= GO_MAX_PTS; i++) { visits[i] = 0; wins[i] = 0; } |
Branch: 1 branch
| Branch | True | False | Total |
| for (i = 0; i <= GO_MAX_PTS; i++) { visits[i] = 0; wins[i] = 0; } |
353158 |
799 |
353957 |
|
| 250 |
|
| |
| 251 |
|
| /* ---- THE BUDGET DECIDES HOW MANY MOVES CAN BE COMPARED AT ALL ---------- |
| 252 |
|
| * |
| 253 |
|
| * This is arithmetic about the search and not knowledge about Go, which is |
| 254 |
|
| * why it is here rather than in a heuristic. |
| 255 |
|
| * |
| 256 |
|
| * With P playouts spread over M root moves, each move gets P/M samples. A |
| 257 |
|
| * single playout of a Go position is close to a coin flip, so at one or two |
| 258 |
|
| * samples a move's win count carries no information and the selection |
| 259 |
|
| * resolves to whatever the tie-break is. MEASURED: on a 19x19 board with |
| 260 |
|
| * 361 root moves and 300 playouts the search chose the top left corner |
| 261 |
|
| * every time, because every move ended on one visit. |
| 262 |
|
| * |
| 263 |
|
| * So when the budget cannot afford GO_MIN_VISITS samples per move, the root |
| 264 |
|
| * set is CUT DOWN to the number it can afford, chosen by the seed. A |
| 265 |
|
| * shallow search over a random forty moves is a real search result; a |
| 266 |
|
| * one-sample look at every move is a sorting artifact. |
| 267 |
|
| * |
| 268 |
|
| * The shuffle is Fisher-Yates over a copy, driven by the same PRNG as the |
| 269 |
|
| * playouts, so the subset is a function of the seed and nothing else. |
| 270 |
|
| */ |
| 271 |
29050 |
▶ | for (i = 0; i < nallowed && i <= GO_MAX_PTS; i++) roots[i] = allowed[i]; |
Branch: 2 branches
| Branch | True | False | Total |
| for (i = 0; i < nallowed && i <= GO_MAX_PTS; i++) roots[i] = allowed[i]; |
28251 |
799 |
29050 |
| for (i = 0; i < nallowed && i <= GO_MAX_PTS; i++) roots[i] = allowed[i]; |
28251 |
0 |
28251 |
|
| 272 |
799 |
| nroots = nallowed; |
| 273 |
|
| |
| 274 |
799 |
▶ | if (playouts / GO_MIN_VISITS < nroots) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (playouts / GO_MIN_VISITS < nroots) { |
696 |
103 |
799 |
|
| 275 |
696 |
| int keep = playouts / GO_MIN_VISITS; |
| 276 |
696 |
▶ | if (keep < 1) keep = 1; |
Branch: 1 branch
| Branch | True | False | Total |
| if (keep < 1) keep = 1; |
0 |
696 |
696 |
|
| 277 |
|
| |
| 278 |
27625 |
▶ | for (i = nroots - 1; i > 0; i--) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (i = nroots - 1; i > 0; i--) { |
26929 |
696 |
27625 |
|
| 279 |
26929 |
| unsigned int j = go_prng_next(&state) % (unsigned int)(i + 1); |
| 280 |
26929 |
| int tmp = roots[i]; |
| 281 |
26929 |
| roots[i] = roots[j]; |
| 282 |
26929 |
| roots[j] = tmp; |
| 283 |
|
| } |
| 284 |
696 |
| nroots = keep; |
| 285 |
|
| } |
| 286 |
|
| |
| 287 |
54369 |
▶ | while (done < playouts) { |
Branch: 1 branch
| Branch | True | False | Total |
| while (done < playouts) { |
53570 |
799 |
54369 |
|
| 288 |
53570 |
| int pick = -1, pick_slot = -1, pick_score = -1; |
| 289 |
|
| struct go_board *work; |
| 290 |
|
| struct go_played res; |
| 291 |
|
| int diff; |
| 292 |
|
| |
| 293 |
|
| /* selection, with ties to the LOWER POINT INDEX so the choice is total |
| 294 |
|
| * and does not depend on the order anything was stored in */ |
| 295 |
1367520 |
▶ | for (i = 0; i < nroots; i++) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (i = 0; i < nroots; i++) { |
1313950 |
53570 |
1367520 |
|
| 296 |
1313950 |
| int pt = roots[i]; |
| 297 |
1313950 |
▶ | int slot = pt < 0 ? pass_slot : pt; |
Branch: 1 branch
| Branch | True | False | Total |
| int slot = pt < 0 ? pass_slot : pt; |
27600 |
1286350 |
1313950 |
|
| 298 |
1313950 |
| int score = ucb_permille(wins[slot], visits[slot], done, explore); |
| 299 |
1313950 |
▶ | if (score > pick_score) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (score > pick_score) { |
130907 |
1183043 |
1313950 |
|
| 300 |
130907 |
| pick_score = score; |
| 301 |
130907 |
| pick = pt; |
| 302 |
130907 |
| pick_slot = slot; |
| 303 |
|
| } |
| 304 |
|
| } |
| 305 |
53570 |
▶ | if (pick_slot < 0) break; |
Branch: 1 branch
| Branch | True | False | Total |
| if (pick_slot < 0) break; |
0 |
53570 |
53570 |
|
| 306 |
|
| |
| 307 |
53570 |
| work = (EN->board_copy)(b); |
| 308 |
53570 |
▶ | if (!work) break; |
Branch: 1 branch
| Branch | True | False | Total |
| if (!work) break; |
0 |
53570 |
53570 |
|
| 309 |
|
| |
| 310 |
53570 |
▶ | if (pick < 0) (EN->pass)(work, colour); |
Branch: 1 branch
| Branch | True | False | Total |
| if (pick < 0) (EN->pass)(work, colour); |
3899 |
49671 |
53570 |
|
| 311 |
49671 |
| else (EN->play)(work, NULL, pick, colour, &res); |
| 312 |
|
| |
| 313 |
53570 |
▶ | diff = playout_on(work, GO_OTHER(colour), &state, &out->moves, &out->capped); |
Branch: 1 branch
| Branch | True | False | Total |
| diff = playout_on(work, GO_OTHER(colour), &state, &out->moves, &out->capped); |
31170 |
22400 |
53570 |
|
| 314 |
53570 |
| (EN->board_drop)(work); |
| 315 |
|
| |
| 316 |
|
| /* A win from the SEARCHING colour's side. A draw counts for nobody, |
| 317 |
|
| * which on an integer area difference means only an exact zero. */ |
| 318 |
53570 |
| visits[pick_slot]++; |
| 319 |
53570 |
▶ | if (colour == GO_BLACK) { if (diff > 0) wins[pick_slot]++; } |
Branch: 2 branches
| Branch | True | False | Total |
| if (colour == GO_BLACK) { if (diff > 0) wins[pick_slot]++; } |
31170 |
22400 |
53570 |
| if (colour == GO_BLACK) { if (diff > 0) wins[pick_slot]++; } |
21770 |
9400 |
31170 |
|
| 320 |
22400 |
▶ | else { if (diff < 0) wins[pick_slot]++; } |
Branch: 1 branch
| Branch | True | False | Total |
| else { if (diff < 0) wins[pick_slot]++; } |
7779 |
14621 |
22400 |
|
| 321 |
|
| |
| 322 |
53570 |
| done++; |
| 323 |
|
| } |
| 324 |
|
| |
| 325 |
799 |
| out->playouts = done; |
| 326 |
|
| |
| 327 |
|
| /* THE MOVE IS THE MOST WINS, then the most visits, then the lower point. |
| 328 |
|
| * |
| 329 |
|
| * "Most visited" is the standard choice and it is the RIGHT one for a |
| 330 |
|
| * search whose budget exceeded its root move count, because the bound |
| 331 |
|
| * concentrates visits on the move it likes and the visit count is what it |
| 332 |
|
| * spent the budget deciding. |
| 333 |
|
| * |
| 334 |
|
| * IT IS WRONG WHEN THE BUDGET DID NOT. The first pass over the root visits |
| 335 |
|
| * every move once, in point order, so on a 19x19 board with 361 root moves |
| 336 |
|
| * and a few hundred playouts every move ends on one visit and "most |
| 337 |
|
| * visited" resolves to the LOWEST POINT INDEX: the bot played the top left |
| 338 |
|
| * corner every single time. That was measured, not reasoned about. |
| 339 |
|
| * |
| 340 |
|
| * Ordering by wins first fixes it without a heuristic and without changing |
| 341 |
|
| * the well-funded case: where visits are concentrated the most-visited move |
| 342 |
|
| * is also the most-won, and where they are not, wins is the only thing in |
| 343 |
|
| * the table that means anything. |
| 344 |
|
| */ |
| 345 |
799 |
| best = -1; |
| 346 |
6388 |
▶ | for (i = 0; i < nroots; i++) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (i = 0; i < nroots; i++) { |
5589 |
799 |
6388 |
|
| 347 |
5589 |
| int pt = roots[i]; |
| 348 |
5589 |
▶ | int slot = pt < 0 ? pass_slot : pt; |
Branch: 1 branch
| Branch | True | False | Total |
| int slot = pt < 0 ? pass_slot : pt; |
313 |
5276 |
5589 |
|
| 349 |
5589 |
▶ | if (best < 0) { best = slot; continue; } |
Branch: 1 branch
| Branch | True | False | Total |
| if (best < 0) { best = slot; continue; } |
799 |
4790 |
5589 |
|
| 350 |
4790 |
▶ | if (wins[slot] > wins[best]) { best = slot; continue; } |
Branch: 1 branch
| Branch | True | False | Total |
| if (wins[slot] > wins[best]) { best = slot; continue; } |
498 |
4292 |
4790 |
|
| 351 |
4292 |
▶ | if (wins[slot] == wins[best] && visits[slot] > visits[best]) best = slot; |
Branch: 2 branches
| Branch | True | False | Total |
| if (wins[slot] == wins[best] && visits[slot] > visits[best]) best = slot; |
1196 |
3096 |
4292 |
| if (wins[slot] == wins[best] && visits[slot] > visits[best]) best = slot; |
8 |
1188 |
1196 |
|
| 352 |
|
| } |
| 353 |
799 |
▶ | if (best < 0) return; |
Branch: 1 branch
| Branch | True | False | Total |
| if (best < 0) return; |
0 |
799 |
799 |
|
| 354 |
|
| |
| 355 |
799 |
▶ | out->point = (best == pass_slot) ? -1 : best; |
Branch: 1 branch
| Branch | True | False | Total |
| out->point = (best == pass_slot) ? -1 : best; |
753 |
46 |
799 |
|
| 356 |
799 |
| out->visits = visits[best]; |
| 357 |
799 |
▶ | out->win_permille = visits[best] ? (wins[best] * 1000) / visits[best] : 0; |
Branch: 1 branch
| Branch | True | False | Total |
| out->win_permille = visits[best] ? (wins[best] * 1000) / visits[best] : 0; |
799 |
0 |
799 |
|
| 358 |
|
| } |
| 359 |
|
| |
| 360 |
|
| /* -------------------------------------------------------------- dead stones -- |
| 361 |
|
| * |
| 362 |
|
| * PLAYOUTS AND NOT HEURISTICS. From the stopped position, play it out N times |
| 363 |
|
| * and see whose the points end up being; a chain whose own points mostly end up |
| 364 |
|
| * the opponent's is dead. That is what `final_status_list dead` means in every |
| 365 |
|
| * playout engine, and it costs nothing new because the playout is already here. |
| 366 |
|
| */ |
| 367 |
22 |
| static int go_dead_guess(const struct go_board *b, unsigned int seed, |
| 368 |
|
| int playouts, int *out) |
| 369 |
|
| { |
| 370 |
|
| int lost[GO_MAX_PTS]; |
| 371 |
|
| int seen[GO_MAX_PTS]; |
| 372 |
|
| signed char owner[GO_MAX_PTS]; |
| 373 |
|
| int chain[GO_MAX_PTS]; |
| 374 |
22 |
| unsigned int state = seed; |
| 375 |
22 |
| int i, n = 0, r, c, size, pts; |
| 376 |
|
| |
| 377 |
22 |
| need_engine(); |
| 378 |
22 |
▶ | if (!b) return 0; |
Branch: 1 branch
| Branch | True | False | Total |
| if (!b) return 0; |
0 |
22 |
22 |
|
| 379 |
22 |
| size = (EN->size_of)(b); |
| 380 |
22 |
| pts = (EN->stride_of)(b) * (EN->stride_of)(b); |
| 381 |
|
| |
| 382 |
2684 |
▶ | for (i = 0; i < pts; i++) { lost[i] = 0; seen[i] = 0; } |
Branch: 1 branch
| Branch | True | False | Total |
| for (i = 0; i < pts; i++) { lost[i] = 0; seen[i] = 0; } |
2662 |
22 |
2684 |
|
| 383 |
|
| |
| 384 |
1342 |
▶ | for (i = 0; i < playouts; i++) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (i = 0; i < playouts; i++) { |
1320 |
22 |
1342 |
|
| 385 |
1320 |
| struct go_board *work = (EN->board_copy)(b); |
| 386 |
|
| int j; |
| 387 |
1320 |
▶ | if (!work) break; |
Branch: 1 branch
| Branch | True | False | Total |
| if (!work) break; |
0 |
1320 |
1320 |
|
| 388 |
|
| |
| 389 |
|
| /* Black to play is arbitrary and it does not matter: the question is |
| 390 |
|
| * whose the points end up being, and both sides get to answer. */ |
| 391 |
1320 |
| (void)playout_on(work, GO_BLACK, &state, NULL, NULL); |
| 392 |
1320 |
| (EN->territory)(work, NULL, 0, NULL, 0, owner); |
| 393 |
|
| |
| 394 |
161040 |
▶ | for (j = 0; j < pts; j++) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (j = 0; j < pts; j++) { |
159720 |
1320 |
161040 |
|
| 395 |
159720 |
| int was = (EN->at)(b, j); |
| 396 |
159720 |
▶ | if (was != GO_BLACK && was != GO_WHITE) continue; |
Branch: 2 branches
| Branch | True | False | Total |
| if (was != GO_BLACK && was != GO_WHITE) continue; |
105960 |
53760 |
159720 |
| if (was != GO_BLACK && was != GO_WHITE) continue; |
97380 |
8580 |
105960 |
|
| 397 |
62340 |
| seen[j]++; |
| 398 |
|
| /* the point ended up the opponent's, either as territory or under |
| 399 |
|
| * an opposing stone */ |
| 400 |
62340 |
▶ | if (owner[j] == GO_OTHER(was) || (EN->at)(work, j) == GO_OTHER(was)) |
Branch: 4 branches
| Branch | True | False | Total |
| if (owner[j] == GO_OTHER(was) || (EN->at)(work, j) == GO_OTHER(was)) |
53760 |
8580 |
62340 |
| if (owner[j] == GO_OTHER(was) || (EN->at)(work, j) == GO_OTHER(was)) |
61532 |
808 |
62340 |
| if (owner[j] == GO_OTHER(was) || (EN->at)(work, j) == GO_OTHER(was)) |
53725 |
7807 |
61532 |
| if (owner[j] == GO_OTHER(was) || (EN->at)(work, j) == GO_OTHER(was)) |
877 |
60655 |
61532 |
|
| 401 |
1685 |
| lost[j]++; |
| 402 |
|
| } |
| 403 |
1320 |
| (EN->board_drop)(work); |
| 404 |
|
| } |
| 405 |
|
| |
| 406 |
|
| /* A chain is dead when MOST of its stones mostly ended up the opponent's. |
| 407 |
|
| * Per chain rather than per stone, because life and death is a property of |
| 408 |
|
| * a chain and half a dead group is not a thing. */ |
| 409 |
2684 |
▶ | for (i = 0; i < pts; i++) seen[i] = seen[i] ? seen[i] : 0; |
Branch: 1 branch
| Branch | True | False | Total |
| for (i = 0; i < pts; i++) seen[i] = seen[i] ? seen[i] : 0; |
2662 |
22 |
2684 |
|
| 410 |
|
| |
| 411 |
220 |
▶ | for (r = 0; r < size; r++) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (r = 0; r < size; r++) { |
198 |
22 |
220 |
|
| 412 |
1980 |
▶ | for (c = 0; c < size; c++) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (c = 0; c < size; c++) { |
1782 |
198 |
1980 |
|
| 413 |
1782 |
| int pt = (EN->point_of)(b, c, r); |
| 414 |
1782 |
| int len, j, dead_stones = 0, root_seen = 0; |
| 415 |
|
| |
| 416 |
1782 |
▶ | if ((EN->at)(b, pt) != GO_BLACK && (EN->at)(b, pt) != GO_WHITE) continue; |
Branch: 2 branches
| Branch | True | False | Total |
| if ((EN->at)(b, pt) != GO_BLACK && (EN->at)(b, pt) != GO_WHITE) continue; |
886 |
896 |
1782 |
| if ((EN->at)(b, pt) != GO_BLACK && (EN->at)(b, pt) != GO_WHITE) continue; |
743 |
143 |
886 |
|
| 417 |
|
| |
| 418 |
1039 |
| len = (EN->chain_at)(b, pt, chain); |
| 419 |
1039 |
▶ | if (len <= 0) continue; |
Branch: 1 branch
| Branch | True | False | Total |
| if (len <= 0) continue; |
0 |
1039 |
1039 |
|
| 420 |
|
| |
| 421 |
|
| /* only from the chain's lowest point, so each chain is judged once */ |
| 422 |
|
| { |
| 423 |
1039 |
| int low = chain[0]; |
| 424 |
68287 |
▶ | for (j = 1; j < len; j++) if (chain[j] < low) low = chain[j]; |
Branch: 2 branches
| Branch | True | False | Total |
| for (j = 1; j < len; j++) if (chain[j] < low) low = chain[j]; |
1849 |
65399 |
67248 |
| for (j = 1; j < len; j++) if (chain[j] < low) low = chain[j]; |
67248 |
1039 |
68287 |
|
| 425 |
1039 |
▶ | if (low != pt) continue; |
Branch: 1 branch
| Branch | True | False | Total |
| if (low != pt) continue; |
982 |
57 |
1039 |
|
| 426 |
|
| } |
| 427 |
|
| |
| 428 |
1096 |
▶ | for (j = 0; j < len; j++) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (j = 0; j < len; j++) { |
1039 |
57 |
1096 |
|
| 429 |
1039 |
▶ | if (!seen[chain[j]]) continue; |
Branch: 1 branch
| Branch | True | False | Total |
| if (!seen[chain[j]]) continue; |
0 |
1039 |
1039 |
|
| 430 |
1039 |
| root_seen++; |
| 431 |
1039 |
▶ | if (lost[chain[j]] * 2 > seen[chain[j]]) dead_stones++; |
Branch: 1 branch
| Branch | True | False | Total |
| if (lost[chain[j]] * 2 > seen[chain[j]]) dead_stones++; |
24 |
1015 |
1039 |
|
| 432 |
|
| } |
| 433 |
|
| |
| 434 |
57 |
▶ | if (root_seen && dead_stones * 2 > root_seen) { |
Branch: 2 branches
| Branch | True | False | Total |
| if (root_seen && dead_stones * 2 > root_seen) { |
57 |
0 |
57 |
| if (root_seen && dead_stones * 2 > root_seen) { |
12 |
45 |
57 |
|
| 435 |
36 |
▶ | for (j = 0; j < len; j++) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (j = 0; j < len; j++) { |
24 |
12 |
36 |
|
| 436 |
24 |
▶ | if (out) out[n] = chain[j]; |
Branch: 1 branch
| Branch | True | False | Total |
| if (out) out[n] = chain[j]; |
24 |
0 |
24 |
|
| 437 |
24 |
| n++; |
| 438 |
|
| } |
| 439 |
|
| } |
| 440 |
|
| } |
| 441 |
|
| } |
| 442 |
|
| |
| 443 |
22 |
| return n; |
| 444 |
|
| } |
| 445 |
|
| |
| 446 |
|
| /* ------------------------------------------------------------- the exports --- |
| 447 |
|
| * |
| 448 |
|
| * Appended to go_engine.c's table by go_search_install, which is called from |
| 449 |
|
| * go_abi_table. Filled in BY NAME, for the reason the rest of the table is. |
| 450 |
|
| */ |
| 451 |
26 |
| void go_search_install(struct go_abi *t) |
| 452 |
|
| { |
| 453 |
26 |
| t->prng_next = go_prng_next; |
| 454 |
26 |
| t->playout = go_playout; |
| 455 |
26 |
| t->search = go_search; |
| 456 |
26 |
| t->dead_guess = go_dead_guess; |
| 457 |
26 |
| } |