go_search.c

filter: Statementstmt 100% 179 / 179 Branchbran 86.0% 148 / 172 Conditioncond n/a MC/DCmcdc n/a Subroutinesub n/a Podpod n/a totaltotal 93.1% 327 / 351 CC 0 SCAR 0
CC
0
Cov
0%
CRAP 0
« go_engine.c ↑ Summary
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
if (c == GO_BORDER) { on_edge = 1; continue; } 25730073 259743661 285473734
78 259743661 ▶ if (c != colour) return 0;
Branch: 1 branch
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
if (c == GO_BORDER) continue; 13561711 37302309 50864020
89 37302309 ▶ if (c != colour) wrong++;
Branch: 1 branch
BranchTrueFalseTotal
if (c != colour) wrong++; 9888275 27414034 37302309
90 }
91  
92 12716005 ▶ return on_edge ? (wrong == 0) : (wrong <= 1);
Branch: 1 branch
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
for (r = 0; r < size; r++) { 49815583 4812153 54627736
120 608113328 ▶ for (c = 0; c < size; c++) {
Branch: 1 branch
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
colour = GO_OTHER(colour); 2408870 2403283 4812153
139 }
140  
141 55010 ▶ if (moves >= cap && capped_out) (*capped_out)++;
Branch: 2 branches
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
if (!b) return 0; 0 120 120
159 120 work = (EN->board_copy)(b);
160 120 ▶ if (!work) return 0;
Branch: 1 branch
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
if (keep < 1) keep = 1; 0 696 696
277  
278 27625 ▶ for (i = nroots - 1; i > 0; i--) {
Branch: 1 branch
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
if (pick_slot < 0) break; 0 53570 53570
306  
307 53570 work = (EN->board_copy)(b);
308 53570 ▶ if (!work) break;
Branch: 1 branch
BranchTrueFalseTotal
if (!work) break; 0 53570 53570
309  
310 53570 ▶ if (pick < 0) (EN->pass)(work, colour);
Branch: 1 branch
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
int slot = pt < 0 ? pass_slot : pt; 313 5276 5589
349 5589 ▶ if (best < 0) { best = slot; continue; }
Branch: 1 branch
BranchTrueFalseTotal
if (best < 0) { best = slot; continue; } 799 4790 5589
350 4790 ▶ if (wins[slot] > wins[best]) { best = slot; continue; }
Branch: 1 branch
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
if (best < 0) return; 0 799 799
354  
355 799 ▶ out->point = (best == pass_slot) ? -1 : best;
Branch: 1 branch
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
for (r = 0; r < size; r++) { 198 22 220
412 1980 ▶ for (c = 0; c < size; c++) {
Branch: 1 branch
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
if (low != pt) continue; 982 57 1039
426 }
427  
428 1096 ▶ for (j = 0; j < len; j++) {
Branch: 1 branch
BranchTrueFalseTotal
for (j = 0; j < len; j++) { 1039 57 1096
429 1039 ▶ if (!seen[chain[j]]) continue;
Branch: 1 branch
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
for (j = 0; j < len; j++) { 24 12 36
436 24 ▶ if (out) out[n] = chain[j];
Branch: 1 branch
BranchTrueFalseTotal
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 }
« go_engine.c ↑ Summary