go_engine.c

filter: Statementstmt 97.2% 597 / 614 Branchbran 77.2% 490 / 634 Conditioncond n/a MC/DCmcdc n/a Subroutinesub n/a Podpod n/a totaltotal 87.1% 1087 / 1248 CC 0 SCAR 0
CC
0
Cov
0%
CRAP 0
« Go.xs ↑ Summary go_search.c »
1 /* go_engine.c - the Go board, the chains, the liberties, and the zobrist hash.
2 *
3 * PERL-FREE. This file must never include perl.h, XSUB.h or stdio.h, and must
4 * never call rand, time, printf or anything that touches a handle. t/24-no-io.t
5 * scans this source for all of those after stripping comments, so a decimal
6 * number is formatted by hand below rather than with sprintf.
7 *
8 * What this file owns is in include/go_abi.h under "what this header covers,
9 * and what it does not": the board and only the board. Nothing here knows
10 * whether a move was legal.
11 */
12  
13 #include <stdlib.h>
14 #include <string.h>
15  
16 #include "go_abi.h"
17  
18 #define M32(x) ((x) & 0xFFFFFFFFu)
19  
20 /* ------------------------------------------------------------------ SHA-256 --
21 *
22 * Here for one reason: the zobrist table is derived from SHA-256 so that it is
23 * identical on every platform and every build, and so that a test can verify
24 * any entry from Perl with Digest::SHA. Deriving it from a PRNG would make the
25 * hash values a build artifact and put an unverifiable number in the middle of
26 * the legality path.
27 *
28 * Only ever called with a message shorter than 56 bytes (the longest label is
29 * "go-zobrist:2:440", sixteen characters), so this is the single-block case
30 * and needs no streaming state.
31 */
32  
33 static const unsigned int SHA_K[64] = {
34 0x428a2f98u, 0x71374491u, 0xb5c0fbcfu, 0xe9b5dba5u,
35 0x3956c25bu, 0x59f111f1u, 0x923f82a4u, 0xab1c5ed5u,
36 0xd807aa98u, 0x12835b01u, 0x243185beu, 0x550c7dc3u,
37 0x72be5d74u, 0x80deb1feu, 0x9bdc06a7u, 0xc19bf174u,
38 0xe49b69c1u, 0xefbe4786u, 0x0fc19dc6u, 0x240ca1ccu,
39 0x2de92c6fu, 0x4a7484aau, 0x5cb0a9dcu, 0x76f988dau,
40 0x983e5152u, 0xa831c66du, 0xb00327c8u, 0xbf597fc7u,
41 0xc6e00bf3u, 0xd5a79147u, 0x06ca6351u, 0x14292967u,
42 0x27b70a85u, 0x2e1b2138u, 0x4d2c6dfcu, 0x53380d13u,
43 0x650a7354u, 0x766a0abbu, 0x81c2c92eu, 0x92722c85u,
44 0xa2bfe8a1u, 0xa81a664bu, 0xc24b8b70u, 0xc76c51a3u,
45 0xd192e819u, 0xd6990624u, 0xf40e3585u, 0x106aa070u,
46 0x19a4c116u, 0x1e376c08u, 0x2748774cu, 0x34b0bcb5u,
47 0x391c0cb3u, 0x4ed8aa4au, 0x5b9cca4fu, 0x682e6ff3u,
48 0x748f82eeu, 0x78a5636fu, 0x84c87814u, 0x8cc70208u,
49 0x90befffau, 0xa4506cebu, 0xbef9a3f7u, 0xc67178f2u
50 };
51  
52 #define ROR32(x, n) (M32(((x) >> (n)) | ((x) << (32 - (n)))))
53  
54 22050 static void sha256_short(const unsigned char *msg, int len, unsigned char out[32])
55 {
56 unsigned int h[8];
57 unsigned int w[64];
58 unsigned char blk[64];
59 int i;
60  
61 22050 h[0] = 0x6a09e667u; h[1] = 0xbb67ae85u; h[2] = 0x3c6ef372u; h[3] = 0xa54ff53au;
62 22050 h[4] = 0x510e527fu; h[5] = 0x9b05688cu; h[6] = 0x1f83d9abu; h[7] = 0x5be0cd19u;
63  
64 22050 memset(blk, 0, sizeof(blk));
65 22050 memcpy(blk, msg, (size_t)len);
66 22050 blk[len] = 0x80;
67 /* the message is short, so the length in bits fits the last two bytes */
68 22050 blk[62] = (unsigned char)(((unsigned)len * 8u) >> 8);
69 22050 blk[63] = (unsigned char)(((unsigned)len * 8u) & 0xffu);
70  
71 374850 ▶ for (i = 0; i < 16; i++)
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < 16; i++) 352800 22050 374850
72 352800 w[i] = ((unsigned int)blk[i * 4] << 24) | ((unsigned int)blk[i * 4 + 1] << 16)
73 352800 | ((unsigned int)blk[i * 4 + 2] << 8) | (unsigned int)blk[i * 4 + 3];
74 1080450 ▶ for (i = 16; i < 64; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (i = 16; i < 64; i++) { 1058400 22050 1080450
75 1058400 unsigned int s0 = ROR32(w[i - 15], 7) ^ ROR32(w[i - 15], 18) ^ M32(w[i - 15] >> 3);
76 1058400 unsigned int s1 = ROR32(w[i - 2], 17) ^ ROR32(w[i - 2], 19) ^ M32(w[i - 2] >> 10);
77 1058400 w[i] = M32(w[i - 16] + s0 + w[i - 7] + s1);
78 }
79  
80 {
81 22050 unsigned int a = h[0], b = h[1], c = h[2], d = h[3];
82 22050 unsigned int e = h[4], f = h[5], g = h[6], hh = h[7];
83 1433250 ▶ for (i = 0; i < 64; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < 64; i++) { 1411200 22050 1433250
84 1411200 unsigned int S1 = ROR32(e, 6) ^ ROR32(e, 11) ^ ROR32(e, 25);
85 1411200 unsigned int ch = (e & f) ^ ((~e) & g);
86 1411200 unsigned int t1 = M32(hh + S1 + ch + SHA_K[i] + w[i]);
87 1411200 unsigned int S0 = ROR32(a, 2) ^ ROR32(a, 13) ^ ROR32(a, 22);
88 1411200 unsigned int mj = (a & b) ^ (a & c) ^ (b & c);
89 1411200 unsigned int t2 = M32(S0 + mj);
90 1411200 hh = g; g = f; f = e; e = M32(d + t1);
91 1411200 d = c; c = b; b = a; a = M32(t1 + t2);
92 }
93 22050 h[0] = M32(h[0] + a); h[1] = M32(h[1] + b); h[2] = M32(h[2] + c);
94 22050 h[3] = M32(h[3] + d); h[4] = M32(h[4] + e); h[5] = M32(h[5] + f);
95 22050 h[6] = M32(h[6] + g); h[7] = M32(h[7] + hh);
96 }
97  
98 198450 ▶ for (i = 0; i < 8; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < 8; i++) { 176400 22050 198450
99 176400 out[i * 4] = (unsigned char)((h[i] >> 24) & 0xffu);
100 176400 out[i * 4 + 1] = (unsigned char)((h[i] >> 16) & 0xffu);
101 176400 out[i * 4 + 2] = (unsigned char)((h[i] >> 8) & 0xffu);
102 176400 out[i * 4 + 3] = (unsigned char)(h[i] & 0xffu);
103 }
104 22050 }
105  
106 /* ------------------------------------------------------------ the zobrist ---- */
107  
108 static unsigned long long ZOB[4][GO_MAX_PTS];
109 static int ZOB_READY = 0;
110  
111 /* Decimal by hand, because sprintf would mean stdio.h and t/24-no-io.t scans
112 * for it. Returns the number of characters written. */
113 44100 static int put_dec(unsigned char *at, int n)
114 {
115 unsigned char tmp[12];
116 44100 int i = 0, j = 0;
117 44100 ▶ if (n == 0) { at[0] = '0'; return 1; }
Branch: 1 branch
BranchTrueFalseTotal
if (n == 0) { at[0] = '0'; return 1; } 50 44050 44100
118 126700 ▶ while (n > 0) { tmp[i++] = (unsigned char)('0' + (n % 10)); n /= 10; }
Branch: 1 branch
BranchTrueFalseTotal
while (n > 0) { tmp[i++] = (unsigned char)('0' + (n % 10)); n /= 10; } 82650 44050 126700
119 126700 ▶ while (i > 0) at[j++] = tmp[--i];
Branch: 1 branch
BranchTrueFalseTotal
while (i > 0) at[j++] = tmp[--i]; 82650 44050 126700
120 44050 return j;
121 }
122  
123 /* The label whose SHA-256 is the entry: go-zobrist:<colour>:<point>
124 * A test asserts this exactly, so the spelling is part of the ABI. */
125 22050 static int zob_label(unsigned char *buf, int colour, int pt)
126 {
127 static const char pre[] = "go-zobrist:";
128 22050 int n = (int)(sizeof(pre) - 1);
129 22050 memcpy(buf, pre, (size_t)n);
130 22050 n += put_dec(buf + n, colour);
131 22050 buf[n++] = ':';
132 22050 n += put_dec(buf + n, pt);
133 22050 return n;
134 }
135  
136 /* Deterministic, so the benign race of two threads building it at once writes
137 * identical bytes. That is the whole reason it is derived rather than random. */
138 6795601 static void zob_init(void)
139 {
140 unsigned char msg[64], dig[32];
141 int colour, pt, i;
142  
143 6795601 ▶ if (ZOB_READY) return;
Branch: 1 branch
BranchTrueFalseTotal
if (ZOB_READY) return; 6795576 25 6795601
144 75 ▶ for (colour = GO_BLACK; colour <= GO_WHITE; colour++) {
Branch: 1 branch
BranchTrueFalseTotal
for (colour = GO_BLACK; colour <= GO_WHITE; colour++) { 50 25 75
145 22100 ▶ for (pt = 0; pt < GO_MAX_PTS; pt++) {
Branch: 1 branch
BranchTrueFalseTotal
for (pt = 0; pt < GO_MAX_PTS; pt++) { 22050 50 22100
146 22050 unsigned long long v = 0;
147 22050 int len = zob_label(msg, colour, pt);
148 22050 sha256_short(msg, len, dig);
149 198450 ▶ for (i = 0; i < 8; i++)
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < 8; i++) 176400 22050 198450
150 176400 v = (v << 8) | (unsigned long long)dig[i];
151 22050 ZOB[colour][pt] = v;
152 }
153 }
154 25 ZOB_READY = 1;
155 }
156  
157 6795111 static unsigned long long zob(int colour, int pt)
158 {
159 6795111 ▶ if (colour != GO_BLACK && colour != GO_WHITE) return 0;
Branch: 2 branches
BranchTrueFalseTotal
if (colour != GO_BLACK && colour != GO_WHITE) return 0; 3639628 3155483 6795111
if (colour != GO_BLACK && colour != GO_WHITE) return 0; 2 3639626 3639628
160 6795109 ▶ if (pt < 0 || pt >= GO_MAX_PTS) return 0;
Branch: 2 branches
BranchTrueFalseTotal
if (pt < 0 || pt >= GO_MAX_PTS) return 0; 6795109 0 6795109
if (pt < 0 || pt >= GO_MAX_PTS) return 0; 0 6795109 6795109
161 6795109 zob_init();
162 6795109 return ZOB[colour][pt];
163 }
164  
165 1797 static unsigned long long go_zobrist(int colour, int pt) { return zob(colour, pt); }
166  
167 /* ------------------------------------------------------------- the board ----- */
168  
169 492 static struct go_board *go_board_new(int size)
170 {
171 struct go_board *b;
172 int r, c;
173  
174 492 ▶ if (size < GO_MIN_SIZE || size > GO_MAX_SIZE) return NULL;
Branch: 2 branches
BranchTrueFalseTotal
if (size < GO_MIN_SIZE || size > GO_MAX_SIZE) return NULL; 492 0 492
if (size < GO_MIN_SIZE || size > GO_MAX_SIZE) return NULL; 0 492 492
175 492 zob_init();
176  
177 492 b = (struct go_board *)calloc(1, sizeof(struct go_board));
178 492 ▶ if (!b) return NULL;
Branch: 1 branch
BranchTrueFalseTotal
if (!b) return NULL; 0 492 492
179  
180 492 b->size = size;
181 492 b->stride = size + 2;
182 492 b->pts = b->stride * b->stride;
183 492 b->nbr[0] = -1;
184 492 b->nbr[1] = 1;
185 492 b->nbr[2] = -b->stride;
186 492 b->nbr[3] = b->stride;
187  
188 /* -1 and not 0: 0 is a real index into the padded array (the top left of
189 * the ring), so 0 as "no ko" would forbid a point that exists. */
190 492 b->ko_point = -1;
191 492 b->ko_colour = GO_EMPTY;
192 492 b->superko_on = 1;
193  
194 /* GO_EMPTY is 0 and calloc zeroed the interior, so only the ring is set.
195 * The ring is the only thing making the neighbour arithmetic safe. */
196 6422 ▶ for (r = 0; r < b->stride; r++) {
Branch: 1 branch
BranchTrueFalseTotal
for (r = 0; r < b->stride; r++) { 5930 492 6422
197 81844 ▶ for (c = 0; c < b->stride; c++) {
Branch: 1 branch
BranchTrueFalseTotal
for (c = 0; c < b->stride; c++) { 75914 5930 81844
198 75914 ▶ if (r == 0 || r == b->stride - 1 || c == 0 || c == b->stride - 1)
Branch: 4 branches
BranchTrueFalseTotal
if (r == 0 || r == b->stride - 1 || c == 0 || c == b->stride - 1) 69984 5930 75914
if (r == 0 || r == b->stride - 1 || c == 0 || c == b->stride - 1) 64054 5930 69984
if (r == 0 || r == b->stride - 1 || c == 0 || c == b->stride - 1) 59108 4946 64054
if (r == 0 || r == b->stride - 1 || c == 0 || c == b->stride - 1) 4946 54162 59108
199 21752 b->colour[r * b->stride + c] = GO_BORDER;
200 }
201 }
202 492 return b;
203 }
204  
205 56909 ▶static void go_board_drop(struct go_board *b) { if (b) free(b); }
Branch: 1 branch
BranchTrueFalseTotal
static void go_board_drop(struct go_board *b) { if (b) free(b); } 56909 0 56909
206  
207 56417 static struct go_board *go_board_copy(const struct go_board *b)
208 {
209 struct go_board *n;
210 56417 ▶ if (!b) return NULL;
Branch: 1 branch
BranchTrueFalseTotal
if (!b) return NULL; 0 56417 56417
211 56417 n = (struct go_board *)malloc(sizeof(struct go_board));
212 56417 ▶ if (!n) return NULL;
Branch: 1 branch
BranchTrueFalseTotal
if (!n) return NULL; 0 56417 56417
213 /* No pointers in the struct, so a copy is a flat byte copy and the two
214 * boards share nothing at all. */
215 56417 memcpy(n, b, sizeof(struct go_board));
216 56417 return n;
217 }
218  
219 /* ------------------------------------------------------------- the chains ---- */
220  
221 /* A stamp rather than a clear, so the distinct-liberty count is O(chain).
222 * The wrap is handled rather than ignored: a gate run does hundreds of
223 * millions of counts and a wrapped stamp would silently collide with a stale
224 * mark, undercounting a liberty in one position in a way nothing reports. */
225 10833578 static int next_stamp(struct go_board *b)
226 {
227 10833578 ▶ if (b->mark_stamp >= 0x7ffffffe) {
Branch: 1 branch
BranchTrueFalseTotal
if (b->mark_stamp >= 0x7ffffffe) { 0 10833578 10833578
228 0 memset(b->mark, 0, sizeof(b->mark));
229 0 b->mark_stamp = 0;
230 }
231 10833578 return ++b->mark_stamp;
232 }
233  
234 /* EXACT, and distinctness is the whole point: an empty point adjacent to two
235 * stones of the same chain is ONE liberty. Counting occurrences instead is the
236 * bug the liberty-delta shortcut has, and phase 01 chose not to have it. */
237 10833578 static void recount(struct go_board *b, int root)
238 {
239 10833578 int stamp, n = 0, pt;
240 10833578 ▶ if (root < 0 || root >= b->pts) return;
Branch: 2 branches
BranchTrueFalseTotal
if (root < 0 || root >= b->pts) return; 10833578 0 10833578
if (root < 0 || root >= b->pts) return; 0 10833578 10833578
241 10833578 ▶ if (b->colour[root] != GO_BLACK && b->colour[root] != GO_WHITE) return;
Branch: 2 branches
BranchTrueFalseTotal
if (b->colour[root] != GO_BLACK && b->colour[root] != GO_WHITE) return; 5216011 5617567 10833578
if (b->colour[root] != GO_BLACK && b->colour[root] != GO_WHITE) return; 0 5216011 5216011
242  
243 10833578 stamp = next_stamp(b);
244 10833578 pt = root;
245 do {
246 int i;
247 931067515 ▶ for (i = 0; i < 4; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < 4; i++) { 744854012 186213503 931067515
248 744854012 int q = pt + b->nbr[i];
249 744854012 ▶ if (b->colour[q] == GO_EMPTY && b->mark[q] != stamp) {
Branch: 2 branches
BranchTrueFalseTotal
if (b->colour[q] == GO_EMPTY && b->mark[q] != stamp) { 110447421 634406591 744854012
if (b->colour[q] == GO_EMPTY && b->mark[q] != stamp) { 52287595 58159826 110447421
250 52287595 b->mark[q] = stamp;
251 52287595 n++;
252 }
253 }
254 186213503 pt = b->chain_next[pt];
255 186213503 ▶ } while (pt != root);
Branch: 1 branch
BranchTrueFalseTotal
} while (pt != root); 175379925 10833578 186213503
256  
257 10833578 b->chain_libs[root] = n;
258 }
259  
260 /* Relabel the SMALLER chain into the larger, which keeps chain_root a direct
261 * answer rather than a tree needing path compression, and makes the work
262 * O(smaller). Splicing two circular lists is two assignments. */
263 5451219 static int merge(struct go_board *b, int ra, int rb)
264 {
265 int big, small, pt, tmp;
266  
267 5451219 ▶ if (ra == rb) return ra;
Branch: 1 branch
BranchTrueFalseTotal
if (ra == rb) return ra; 1478721 3972498 5451219
268 3972498 ▶ if (b->chain_size[ra] >= b->chain_size[rb]) { big = ra; small = rb; }
Branch: 1 branch
BranchTrueFalseTotal
if (b->chain_size[ra] >= b->chain_size[rb]) { big = ra; small = rb; } 1594722 2377776 3972498
269 2377776 else { big = rb; small = ra; }
270  
271 3972498 pt = small;
272 5633251 ▶ do { b->chain_root[pt] = big; pt = b->chain_next[pt]; } while (pt != small);
Branch: 1 branch
BranchTrueFalseTotal
do { b->chain_root[pt] = big; pt = b->chain_next[pt]; } while (pt != small); 1660753 3972498 5633251
273  
274 3972498 tmp = b->chain_next[big];
275 3972498 b->chain_next[big] = b->chain_next[small];
276 3972498 b->chain_next[small] = tmp;
277  
278 3972498 b->chain_size[big] += b->chain_size[small];
279 3972498 b->chain_size[small] = 0;
280 3972498 b->chain_libs[small] = 0;
281 3972498 return big;
282 }
283  
284 /* A STRUCTURE PRIMITIVE. It does not check legality, does not capture, and does
285 * not know whose turn it is. An occupied or off-board point is a no-op rather
286 * than a corruption, because the rules layer is what refuses those and it
287 * should be the thing reporting the reason. */
288 4575409 static void go_put(struct go_board *b, int pt, int colour)
289 {
290 int i, root;
291  
292 4575409 ▶ if (!b || pt < 0 || pt >= b->pts) return;
Branch: 3 branches
BranchTrueFalseTotal
if (!b || pt < 0 || pt >= b->pts) return; 4575409 0 4575409
if (!b || pt < 0 || pt >= b->pts) return; 4575409 0 4575409
if (!b || pt < 0 || pt >= b->pts) return; 0 4575409 4575409
293 4575409 ▶ if (colour != GO_BLACK && colour != GO_WHITE) return;
Branch: 2 branches
BranchTrueFalseTotal
if (colour != GO_BLACK && colour != GO_WHITE) return; 2246516 2328893 4575409
if (colour != GO_BLACK && colour != GO_WHITE) return; 0 2246516 2246516
294 4575409 ▶ if (b->colour[pt] != GO_EMPTY) return; /* border is never empty, so this covers it */
Branch: 1 branch
BranchTrueFalseTotal
if (b->colour[pt] != GO_EMPTY) return; /* border is never empty, so this covers it */ 2 4575407 4575409
295  
296 4575407 b->colour[pt] = (signed char)colour;
297 4575407 b->hash ^= zob(colour, pt);
298 4575407 b->stones[colour]++;
299  
300 4575407 b->chain_root[pt] = pt;
301 4575407 b->chain_next[pt] = pt;
302 4575407 b->chain_size[pt] = 1;
303 4575407 b->chain_libs[pt] = 0;
304  
305 4575407 root = pt;
306 22877035 ▶ for (i = 0; i < 4; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < 4; i++) { 18301628 4575407 22877035
307 18301628 int q = pt + b->nbr[i];
308 18301628 ▶ if (b->colour[q] == colour) root = merge(b, root, b->chain_root[q]);
Branch: 1 branch
BranchTrueFalseTotal
if (b->colour[q] == colour) root = merge(b, root, b->chain_root[q]); 5451219 12850409 18301628
309 }
310 4575407 recount(b, root);
311  
312 /* every adjacent enemy chain just lost a liberty. Recounting the same root
313 * twice is idempotent because the count is exact, so no bookkeeping. */
314 22877035 ▶ for (i = 0; i < 4; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < 4; i++) { 18301628 4575407 22877035
315 18301628 int q = pt + b->nbr[i];
316 18301628 ▶ if (b->colour[q] == GO_OTHER(colour)) recount(b, b->chain_root[q]);
Branch: 2 branches
BranchTrueFalseTotal
if (b->colour[q] == GO_OTHER(colour)) recount(b, b->chain_root[q]); 9315568 8986060 18301628
if (b->colour[q] == GO_OTHER(colour)) recount(b, b->chain_root[q]); 4780089 13521539 18301628
317 }
318 }
319  
320 /* The other structure primitive: take the chain at pt off the board. Says
321 * nothing about why. Returns the number of stones removed. */
322 945710 static int go_lift(struct go_board *b, int pt)
323 {
324 int pts[GO_MAX_PTS];
325 int roots[GO_MAX_PTS];
326 945710 int n = 0, nroots = 0, i, k, root, cur, colour;
327  
328 945710 ▶ if (!b || pt < 0 || pt >= b->pts) return 0;
Branch: 3 branches
BranchTrueFalseTotal
if (!b || pt < 0 || pt >= b->pts) return 0; 945710 0 945710
if (!b || pt < 0 || pt >= b->pts) return 0; 945710 0 945710
if (!b || pt < 0 || pt >= b->pts) return 0; 0 945710 945710
329 945710 colour = b->colour[pt];
330 945710 ▶ if (colour != GO_BLACK && colour != GO_WHITE) return 0;
Branch: 2 branches
BranchTrueFalseTotal
if (colour != GO_BLACK && colour != GO_WHITE) return 0; 561402 384308 945710
if (colour != GO_BLACK && colour != GO_WHITE) return 0; 0 561402 561402
331  
332 945710 root = b->chain_root[pt];
333 945710 cur = root;
334 2179598 ▶ do { pts[n++] = cur; cur = b->chain_next[cur]; } while (cur != root);
Branch: 1 branch
BranchTrueFalseTotal
do { pts[n++] = cur; cur = b->chain_next[cur]; } while (cur != root); 1233888 945710 2179598
335  
336 /* Collect the distinct neighbouring enemy chains BEFORE the stones go,
337 * because once they are empty the adjacency that named them is gone. */
338 3125308 ▶ for (i = 0; i < n; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < n; i++) { 2179598 945710 3125308
339 10897990 ▶ for (k = 0; k < 4; k++) {
Branch: 1 branch
BranchTrueFalseTotal
for (k = 0; k < 4; k++) { 8718392 2179598 10897990
340 8718392 int q = pts[i] + b->nbr[k];
341 8718392 ▶ if (b->colour[q] == GO_OTHER(colour)) {
Branch: 2 branches
BranchTrueFalseTotal
if (b->colour[q] == GO_OTHER(colour)) { 3231764 5486628 8718392
if (b->colour[q] == GO_OTHER(colour)) { 4720550 3997842 8718392
342 4720550 int r = b->chain_root[q], j, seen = 0;
343 6076589 ▶ for (j = 0; j < nroots; j++) if (roots[j] == r) { seen = 1; break; }
Branch: 2 branches
BranchTrueFalseTotal
for (j = 0; j < nroots; j++) if (roots[j] == r) { seen = 1; break; } 3242468 1356039 4598507
for (j = 0; j < nroots; j++) if (roots[j] == r) { seen = 1; break; } 4598507 1478082 6076589
344 4720550 ▶ if (!seen) roots[nroots++] = r;
Branch: 1 branch
BranchTrueFalseTotal
if (!seen) roots[nroots++] = r; 1478082 3242468 4720550
345 }
346 }
347 }
348  
349 3125308 ▶ for (i = 0; i < n; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < n; i++) { 2179598 945710 3125308
350 2179598 b->colour[pts[i]] = GO_EMPTY;
351 2179598 b->hash ^= zob(colour, pts[i]);
352 2179598 b->chain_root[pts[i]] = 0;
353 2179598 b->chain_next[pts[i]] = 0;
354 2179598 b->chain_size[pts[i]] = 0;
355 2179598 b->chain_libs[pts[i]] = 0;
356 }
357 945710 b->stones[colour] -= n;
358  
359 2423792 ▶ for (i = 0; i < nroots; i++) recount(b, roots[i]);
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < nroots; i++) recount(b, roots[i]); 1478082 945710 2423792
360 945710 return n;
361 }
362  
363 /* ----------------------------------------------------------- reading it ------ */
364  
365 558542990 static int go_at(const struct go_board *b, int pt)
366 {
367 558542990 ▶ if (!b || pt < 0 || pt >= b->pts) return GO_BORDER;
Branch: 3 branches
BranchTrueFalseTotal
if (!b || pt < 0 || pt >= b->pts) return GO_BORDER; 558542990 0 558542990
if (!b || pt < 0 || pt >= b->pts) return GO_BORDER; 558542989 1 558542990
if (!b || pt < 0 || pt >= b->pts) return GO_BORDER; 1 558542988 558542989
368 558542988 return b->colour[pt];
369 }
370  
371 240 static int go_libs(const struct go_board *b, int pt)
372 {
373 240 ▶ if (!b || pt < 0 || pt >= b->pts) return -1;
Branch: 3 branches
BranchTrueFalseTotal
if (!b || pt < 0 || pt >= b->pts) return -1; 240 0 240
if (!b || pt < 0 || pt >= b->pts) return -1; 240 0 240
if (!b || pt < 0 || pt >= b->pts) return -1; 0 240 240
374 240 ▶ if (b->colour[pt] != GO_BLACK && b->colour[pt] != GO_WHITE) return -1;
Branch: 2 branches
BranchTrueFalseTotal
if (b->colour[pt] != GO_BLACK && b->colour[pt] != GO_WHITE) return -1; 97 143 240
if (b->colour[pt] != GO_BLACK && b->colour[pt] != GO_WHITE) return -1; 1 96 97
375 239 return b->chain_libs[b->chain_root[pt]];
376 }
377  
378 578 static int go_chain_size(const struct go_board *b, int pt)
379 {
380 578 ▶ if (!b || pt < 0 || pt >= b->pts) return 0;
Branch: 3 branches
BranchTrueFalseTotal
if (!b || pt < 0 || pt >= b->pts) return 0; 578 0 578
if (!b || pt < 0 || pt >= b->pts) return 0; 578 0 578
if (!b || pt < 0 || pt >= b->pts) return 0; 0 578 578
381 578 ▶ if (b->colour[pt] != GO_BLACK && b->colour[pt] != GO_WHITE) return 0;
Branch: 2 branches
BranchTrueFalseTotal
if (b->colour[pt] != GO_BLACK && b->colour[pt] != GO_WHITE) return 0; 219 359 578
if (b->colour[pt] != GO_BLACK && b->colour[pt] != GO_WHITE) return 0; 1 218 219
382 577 return b->chain_size[b->chain_root[pt]];
383 }
384  
385 1541 static int go_chain_at(const struct go_board *b, int pt, int *out)
386 {
387 1541 int n = 0, root, cur;
388 1541 ▶ if (!b || pt < 0 || pt >= b->pts) return 0;
Branch: 3 branches
BranchTrueFalseTotal
if (!b || pt < 0 || pt >= b->pts) return 0; 1541 0 1541
if (!b || pt < 0 || pt >= b->pts) return 0; 1541 0 1541
if (!b || pt < 0 || pt >= b->pts) return 0; 0 1541 1541
389 1541 ▶ if (b->colour[pt] != GO_BLACK && b->colour[pt] != GO_WHITE) return 0;
Branch: 2 branches
BranchTrueFalseTotal
if (b->colour[pt] != GO_BLACK && b->colour[pt] != GO_WHITE) return 0; 390 1151 1541
if (b->colour[pt] != GO_BLACK && b->colour[pt] != GO_WHITE) return 0; 3 387 390
390 1538 root = b->chain_root[pt];
391 1538 cur = root;
392 72024 ▶ do { if (out) out[n] = cur; n++; cur = b->chain_next[cur]; } while (cur != root);
Branch: 2 branches
BranchTrueFalseTotal
do { if (out) out[n] = cur; n++; cur = b->chain_next[cur]; } while (cur != root); 72024 0 72024
do { if (out) out[n] = cur; n++; cur = b->chain_next[cur]; } while (cur != root); 70486 1538 72024
393 1538 return n;
394 }
395  
396 /* One byte per REAL point, row by row from the top. This is what makes a
397 * zobrist match into a certainty: on a hash hit the caller memcmps this. */
398 3930 static int go_pack(const struct go_board *b, unsigned char *buf)
399 {
400 3930 int r, c, n = 0;
401 3930 ▶ if (!b || !buf) return 0;
Branch: 2 branches
BranchTrueFalseTotal
if (!b || !buf) return 0; 3930 0 3930
if (!b || !buf) return 0; 0 3930 3930
402 40278 ▶ for (r = 0; r < b->size; r++)
Branch: 1 branch
BranchTrueFalseTotal
for (r = 0; r < b->size; r++) 36348 3930 40278
403 381842 ▶ for (c = 0; c < b->size; c++)
Branch: 1 branch
BranchTrueFalseTotal
for (c = 0; c < b->size; c++) 345494 36348 381842
404 345494 buf[n++] = (unsigned char)b->colour[(r + 1) * b->stride + (c + 1)];
405 3930 return n;
406 }
407  
408 29 ▶static unsigned long long go_hash(const struct go_board *b) { return b ? b->hash : 0; }
Branch: 1 branch
BranchTrueFalseTotal
static unsigned long long go_hash(const struct go_board *b) { return b ? b->hash : 0; } 29 0 29
409  
410 72 static int go_stones(const struct go_board *b, int colour)
411 {
412 72 ▶ if (!b || colour < 0 || colour > 3) return 0;
Branch: 3 branches
BranchTrueFalseTotal
if (!b || colour < 0 || colour > 3) return 0; 72 0 72
if (!b || colour < 0 || colour > 3) return 0; 72 0 72
if (!b || colour < 0 || colour > 3) return 0; 0 72 72
413 72 return b->stones[colour];
414 }
415  
416 /* ---------------------------------------------------------------- points ----- */
417  
418 558339046 static int go_point_of(const struct go_board *b, int col, int row)
419 {
420 558339046 ▶ if (!b || col < 0 || row < 0 || col >= b->size || row >= b->size) return -1;
Branch: 5 branches
BranchTrueFalseTotal
if (!b || col < 0 || row < 0 || col >= b->size || row >= b->size) return -1; 558339046 0 558339046
if (!b || col < 0 || row < 0 || col >= b->size || row >= b->size) return -1; 558339040 6 558339046
if (!b || col < 0 || row < 0 || col >= b->size || row >= b->size) return -1; 558339039 1 558339040
if (!b || col < 0 || row < 0 || col >= b->size || row >= b->size) return -1; 558339034 5 558339039
if (!b || col < 0 || row < 0 || col >= b->size || row >= b->size) return -1; 4 558339030 558339034
421 558339030 return (row + 1) * b->stride + (col + 1);
422 }
423  
424 3996 static int go_col_of(const struct go_board *b, int pt)
425 {
426 3996 ▶ if (!b || pt < 0 || pt >= b->pts) return -1;
Branch: 3 branches
BranchTrueFalseTotal
if (!b || pt < 0 || pt >= b->pts) return -1; 3996 0 3996
if (!b || pt < 0 || pt >= b->pts) return -1; 3996 0 3996
if (!b || pt < 0 || pt >= b->pts) return -1; 0 3996 3996
427 3996 return pt % b->stride - 1;
428 }
429  
430 3996 static int go_row_of(const struct go_board *b, int pt)
431 {
432 3996 ▶ if (!b || pt < 0 || pt >= b->pts) return -1;
Branch: 3 branches
BranchTrueFalseTotal
if (!b || pt < 0 || pt >= b->pts) return -1; 3996 0 3996
if (!b || pt < 0 || pt >= b->pts) return -1; 3996 0 3996
if (!b || pt < 0 || pt >= b->pts) return -1; 0 3996 3996
433 3996 return pt / b->stride - 1;
434 }
435  
436 55809 ▶static int go_size_of(const struct go_board *b) { return b ? b->size : 0; }
Branch: 1 branch
BranchTrueFalseTotal
static int go_size_of(const struct go_board *b) { return b ? b->size : 0; } 55809 0 55809
437 49 ▶static int go_stride_of(const struct go_board *b) { return b ? b->stride : 0; }
Branch: 1 branch
BranchTrueFalseTotal
static int go_stride_of(const struct go_board *b) { return b ? b->stride : 0; } 49 0 49
438  
439 /* The index into a packed position of a padded point, or -1 for the ring. */
440 4 static int buf_index(const struct go_board *b, int pt)
441 {
442 int row, col;
443 4 ▶ if (!b || pt < 0 || pt >= b->pts) return -1;
Branch: 3 branches
BranchTrueFalseTotal
if (!b || pt < 0 || pt >= b->pts) return -1; 4 0 4
if (!b || pt < 0 || pt >= b->pts) return -1; 4 0 4
if (!b || pt < 0 || pt >= b->pts) return -1; 0 4 4
444 4 row = pt / b->stride - 1;
445 4 col = pt % b->stride - 1;
446 4 ▶ if (row < 0 || col < 0 || row >= b->size || col >= b->size) return -1;
Branch: 4 branches
BranchTrueFalseTotal
if (row < 0 || col < 0 || row >= b->size || col >= b->size) return -1; 4 0 4
if (row < 0 || col < 0 || row >= b->size || col >= b->size) return -1; 4 0 4
if (row < 0 || col < 0 || row >= b->size || col >= b->size) return -1; 4 0 4
if (row < 0 || col < 0 || row >= b->size || col >= b->size) return -1; 0 4 4
447 4 return row * b->size + col;
448 }
449  
450 /* ==========================================================================
451 * THE RULES OF PLAY. Everything above this line judges nothing.
452 * ========================================================================== */
453  
454 /* ------------------------------------------------- the superko history ------
455 *
456 * A separate object, not a member of the board, and include/go_abi.h says why:
457 * a board carrying its own history would make every playout copy 110 KB.
458 */
459  
460 struct go_hist {
461 int n;
462 int cap;
463 int pts; /* bytes per position: size * size */
464 unsigned long long *hash;
465 unsigned char *pos;
466 };
467  
468 485 static struct go_hist *go_hist_new(int size)
469 {
470 struct go_hist *h;
471 485 ▶ if (size < GO_MIN_SIZE || size > GO_MAX_SIZE) return NULL;
Branch: 2 branches
BranchTrueFalseTotal
if (size < GO_MIN_SIZE || size > GO_MAX_SIZE) return NULL; 485 0 485
if (size < GO_MIN_SIZE || size > GO_MAX_SIZE) return NULL; 0 485 485
472  
473 485 h = (struct go_hist *)calloc(1, sizeof(struct go_hist));
474 485 ▶ if (!h) return NULL;
Branch: 1 branch
BranchTrueFalseTotal
if (!h) return NULL; 0 485 485
475  
476 485 h->pts = size * size;
477 485 h->cap = 64;
478 485 h->hash = (unsigned long long *)malloc(sizeof(unsigned long long) * (size_t)h->cap);
479 485 h->pos = (unsigned char *)malloc((size_t)h->cap * (size_t)h->pts);
480 485 ▶ if (!h->hash || !h->pos) {
Branch: 2 branches
BranchTrueFalseTotal
if (!h->hash || !h->pos) { 485 0 485
if (!h->hash || !h->pos) { 0 485 485
481 0 ▶ if (h->hash) free(h->hash);
Branch: 1 branch
BranchTrueFalseTotal
if (h->hash) free(h->hash); 0 0 0
482 0 ▶ if (h->pos) free(h->pos);
Branch: 1 branch
BranchTrueFalseTotal
if (h->pos) free(h->pos); 0 0 0
483 0 free(h);
484 0 return NULL;
485 }
486 485 return h;
487 }
488  
489 487 static void go_hist_drop(struct go_hist *h)
490 {
491 487 ▶ if (!h) return;
Branch: 1 branch
BranchTrueFalseTotal
if (!h) return; 0 487 487
492 487 ▶ if (h->hash) free(h->hash);
Branch: 1 branch
BranchTrueFalseTotal
if (h->hash) free(h->hash); 487 0 487
493 487 ▶ if (h->pos) free(h->pos);
Branch: 1 branch
BranchTrueFalseTotal
if (h->pos) free(h->pos); 487 0 487
494 487 free(h);
495 }
496  
497 /* A cloned board must get its own history with the same contents. Sharing one
498 * would mean a move explored down one line refusing a move in the other, and
499 * truncating one to just the current position would silently turn superko off
500 * for the clone. Both failures look like one inexplicable refusal much later. */
501 2 static struct go_hist *go_hist_copy(const struct go_hist *h)
502 {
503 struct go_hist *n;
504 2 ▶ if (!h) return NULL;
Branch: 1 branch
BranchTrueFalseTotal
if (!h) return NULL; 0 2 2
505  
506 2 n = (struct go_hist *)calloc(1, sizeof(struct go_hist));
507 2 ▶ if (!n) return NULL;
Branch: 1 branch
BranchTrueFalseTotal
if (!n) return NULL; 0 2 2
508  
509 2 n->pts = h->pts;
510 2 n->cap = h->cap;
511 2 n->n = h->n;
512 2 n->hash = (unsigned long long *)malloc(sizeof(unsigned long long) * (size_t)n->cap);
513 2 n->pos = (unsigned char *)malloc((size_t)n->cap * (size_t)n->pts);
514 2 ▶ if (!n->hash || !n->pos) {
Branch: 2 branches
BranchTrueFalseTotal
if (!n->hash || !n->pos) { 2 0 2
if (!n->hash || !n->pos) { 0 2 2
515 0 ▶ if (n->hash) free(n->hash);
Branch: 1 branch
BranchTrueFalseTotal
if (n->hash) free(n->hash); 0 0 0
516 0 ▶ if (n->pos) free(n->pos);
Branch: 1 branch
BranchTrueFalseTotal
if (n->pos) free(n->pos); 0 0 0
517 0 free(n);
518 0 return NULL;
519 }
520 2 memcpy(n->hash, h->hash, sizeof(unsigned long long) * (size_t)h->n);
521 2 memcpy(n->pos, h->pos, (size_t)h->n * (size_t)h->pts);
522 2 return n;
523 }
524  
525 6 ▶static int go_hist_len(const struct go_hist *h) { return h ? h->n : 0; }
Branch: 1 branch
BranchTrueFalseTotal
static int go_hist_len(const struct go_hist *h) { return h ? h->n : 0; } 6 0 6
526 0 ▶static void go_hist_clear(struct go_hist *h) { if (h) h->n = 0; }
Branch: 1 branch
BranchTrueFalseTotal
static void go_hist_clear(struct go_hist *h) { if (h) h->n = 0; } 0 0 0
527  
528 11 static int hist_grow(struct go_hist *h)
529 {
530 unsigned long long *nh;
531 unsigned char *np;
532 11 int cap = h->cap * 2;
533  
534 11 nh = (unsigned long long *)realloc(h->hash, sizeof(unsigned long long) * (size_t)cap);
535 11 ▶ if (!nh) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (!nh) return 0; 0 11 11
536 11 h->hash = nh;
537  
538 11 np = (unsigned char *)realloc(h->pos, (size_t)cap * (size_t)h->pts);
539 11 ▶ if (!np) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (!np) return 0; 0 11 11
540 11 h->pos = np;
541  
542 11 h->cap = cap;
543 11 return 1;
544 }
545  
546 3913 static int go_hist_push(struct go_hist *h, const struct go_board *b)
547 {
548 3913 ▶ if (!h || !b) return 0;
Branch: 2 branches
BranchTrueFalseTotal
if (!h || !b) return 0; 3913 0 3913
if (!h || !b) return 0; 0 3913 3913
549 3913 ▶ if (b->size * b->size != h->pts) return 0; /* a history is for one size */
Branch: 1 branch
BranchTrueFalseTotal
if (b->size * b->size != h->pts) return 0; /* a history is for one size */ 0 3913 3913
550 3913 ▶ if (h->n == h->cap && !hist_grow(h)) return 0;
Branch: 2 branches
BranchTrueFalseTotal
if (h->n == h->cap && !hist_grow(h)) return 0; 11 3902 3913
if (h->n == h->cap && !hist_grow(h)) return 0; 0 11 11
551 3913 h->hash[h->n] = b->hash;
552 3913 (void)go_pack(b, h->pos + (size_t)h->n * (size_t)h->pts);
553 3913 h->n++;
554 3913 return 1;
555 }
556  
557 /* THE HASH IS A FILTER AND THE COMPARE IS THE VERDICT.
558 *
559 * A 64-bit collision across the few hundred positions of one game is somewhere
560 * around one in 10^14, and that is still not a reason to let a hash decide
561 * whether a move is legal: the symptom would be a legal move refused, once, in
562 * a game nobody can reproduce. So a hash match is followed by a memcmp of the
563 * packed position, and only an exact match refuses. The memcmp costs at most
564 * 361 bytes and happens only on a hit. */
565 4 static int hist_seen(const struct go_hist *h, unsigned long long hash,
566 const unsigned char *packed)
567 {
568 int i;
569 4 ▶ if (!h) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (!h) return 0; 0 4 4
570 8 ▶ for (i = 0; i < h->n; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < h->n; i++) { 8 0 8
571 8 ▶ if (h->hash[i] != hash) continue;
Branch: 1 branch
BranchTrueFalseTotal
if (h->hash[i] != hash) continue; 4 4 8
572 4 ▶ if (memcmp(h->pos + (size_t)i * (size_t)h->pts, packed, (size_t)h->pts) == 0)
Branch: 1 branch
BranchTrueFalseTotal
if (memcmp(h->pos + (size_t)i * (size_t)h->pts, packed, (size_t)h->pts) == 0) 4 0 4
573 4 return 1;
574 }
575 0 return 0;
576 }
577  
578 2 static int go_hist_has(const struct go_hist *h, const struct go_board *b)
579 {
580 unsigned char packed[GO_MAX_PTS];
581 2 ▶ if (!h || !b) return 0;
Branch: 2 branches
BranchTrueFalseTotal
if (!h || !b) return 0; 2 0 2
if (!h || !b) return 0; 0 2 2
582 2 (void)go_pack(b, packed);
583 2 return hist_seen(h, b->hash, packed);
584 }
585  
586 /* ------------------------------------------------------------ would it? -----
587 *
588 * An enemy chain adjacent to an empty point pt is captured by a play at pt if
589 * and only if its liberty count is exactly 1. It needs no search for WHICH
590 * liberty: pt is empty and adjacent to that chain, so pt is one of its
591 * liberties, and if it has only one then pt is it.
592 */
593 175738090 static int dies_to(const struct go_board *b, int q)
594 {
595 175738090 return b->chain_libs[b->chain_root[q]] == 1;
596 }
597  
598 /* The hash the position WOULD have, without touching the board. */
599 35245 static unsigned long long go_hash_after(const struct go_board *b, int pt, int colour)
600 {
601 unsigned long long hsh;
602 int roots[4];
603 35245 int nroots = 0;
604 int i, j, cur, them;
605  
606 35245 ▶ if (!b || pt < 0 || pt >= b->pts) return 0;
Branch: 3 branches
BranchTrueFalseTotal
if (!b || pt < 0 || pt >= b->pts) return 0; 35245 0 35245
if (!b || pt < 0 || pt >= b->pts) return 0; 35245 0 35245
if (!b || pt < 0 || pt >= b->pts) return 0; 0 35245 35245
607 35245 ▶ if (colour != GO_BLACK && colour != GO_WHITE) return 0;
Branch: 2 branches
BranchTrueFalseTotal
if (colour != GO_BLACK && colour != GO_WHITE) return 0; 18100 17145 35245
if (colour != GO_BLACK && colour != GO_WHITE) return 0; 0 18100 18100
608  
609 35245 ▶ them = GO_OTHER(colour);
Branch: 1 branch
BranchTrueFalseTotal
them = GO_OTHER(colour); 17145 18100 35245
610 35245 hsh = b->hash ^ zob(colour, pt);
611  
612 176225 ▶ for (i = 0; i < 4; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < 4; i++) { 140980 35245 176225
613 140980 int q = pt + b->nbr[i];
614 140980 int r, seen = 0;
615 140980 ▶ if (b->colour[q] != them) continue;
Branch: 1 branch
BranchTrueFalseTotal
if (b->colour[q] != them) continue; 128331 12649 140980
616 12649 ▶ if (!dies_to(b, q)) continue;
Branch: 1 branch
BranchTrueFalseTotal
if (!dies_to(b, q)) continue; 11186 1463 12649
617 1463 r = b->chain_root[q];
618 1531 ▶ for (j = 0; j < nroots; j++) if (roots[j] == r) { seen = 1; break; }
Branch: 2 branches
BranchTrueFalseTotal
for (j = 0; j < nroots; j++) if (roots[j] == r) { seen = 1; break; } 117 68 185
for (j = 0; j < nroots; j++) if (roots[j] == r) { seen = 1; break; } 185 1346 1531
619 1463 ▶ if (seen) continue;
Branch: 1 branch
BranchTrueFalseTotal
if (seen) continue; 117 1346 1463
620 1346 roots[nroots++] = r;
621 1346 cur = r;
622 3064 ▶ do { hsh ^= zob(them, cur); cur = b->chain_next[cur]; } while (cur != r);
Branch: 1 branch
BranchTrueFalseTotal
do { hsh ^= zob(them, cur); cur = b->chain_next[cur]; } while (cur != r); 1718 1346 3064
623 }
624 35245 return hsh;
625 }
626  
627 /* The packed position the board WOULD have: pack what is there, then patch the
628 * played point and the captured stones. Cheaper than copying the board, and
629 * only ever reached on a hash hit. */
630 2 static void packed_after(const struct go_board *b, int pt, int colour, unsigned char *buf)
631 {
632 int roots[4];
633 2 int nroots = 0;
634 int i, j, cur, them, ix;
635  
636 2 (void)go_pack(b, buf);
637 2 ix = buf_index(b, pt);
638 2 ▶ if (ix >= 0) buf[ix] = (unsigned char)colour;
Branch: 1 branch
BranchTrueFalseTotal
if (ix >= 0) buf[ix] = (unsigned char)colour; 2 0 2
639  
640 2 ▶ them = GO_OTHER(colour);
Branch: 1 branch
BranchTrueFalseTotal
them = GO_OTHER(colour); 0 2 2
641 10 ▶ for (i = 0; i < 4; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < 4; i++) { 8 2 10
642 8 int q = pt + b->nbr[i];
643 8 int r, seen = 0;
644 8 ▶ if (b->colour[q] != them) continue;
Branch: 1 branch
BranchTrueFalseTotal
if (b->colour[q] != them) continue; 0 8 8
645 8 ▶ if (!dies_to(b, q)) continue;
Branch: 1 branch
BranchTrueFalseTotal
if (!dies_to(b, q)) continue; 6 2 8
646 2 r = b->chain_root[q];
647 2 ▶ for (j = 0; j < nroots; j++) if (roots[j] == r) { seen = 1; break; }
Branch: 2 branches
BranchTrueFalseTotal
for (j = 0; j < nroots; j++) if (roots[j] == r) { seen = 1; break; } 0 0 0
for (j = 0; j < nroots; j++) if (roots[j] == r) { seen = 1; break; } 0 2 2
648 2 ▶ if (seen) continue;
Branch: 1 branch
BranchTrueFalseTotal
if (seen) continue; 0 2 2
649 2 roots[nroots++] = r;
650 2 cur = r;
651 do {
652 2 ix = buf_index(b, cur);
653 2 ▶ if (ix >= 0) buf[ix] = GO_EMPTY;
Branch: 1 branch
BranchTrueFalseTotal
if (ix >= 0) buf[ix] = GO_EMPTY; 2 0 2
654 2 cur = b->chain_next[cur];
655 2 ▶ } while (cur != r);
Branch: 1 branch
BranchTrueFalseTotal
} while (cur != r); 0 2 2
656 }
657 2 }
658  
659 /* ---------------------------------------------------------------- legal ----- */
660  
661 /* THE FIVE STEPS, IN ORDER, AND THE ORDER IS THE RULE.
662 *
663 * 1. the point is on the board and empty -> GO_ILL_OFF / GO_ILL_TAKEN
664 * 2. it is not the ko point -> GO_ILL_KO
665 * 3. the capture is accounted for FIRST
666 * 4. only then, has the played chain a liberty -> GO_ILL_SUICIDE
667 * 5. the resulting position is new -> GO_ILL_REPEAT
668 *
669 * Article 5 puts 3 before 4: "the player must remove all these opposing
670 * stones ... the move is completed when the stones have been removed." So A
671 * MOVE THAT CAPTURES IS NEVER SUICIDE. Testing suicide before capture refuses
672 * every capture of a surrounded group, and does it in the way that is hardest
673 * to notice: a suite of capture-the-lone-stone tests still passes, because a
674 * lone stone leaves an empty point behind it, and only captures into a filled
675 * shape fail.
676 *
677 * NOTHING HERE MUTATES AND NOTHING HERE ALLOCATES, except a stack buffer on a
678 * superko hash hit. Steps 3 and 4 are folded into one pass over the four
679 * neighbours, which computes the same answer the place-then-clear-then-check
680 * procedure would: the played chain has a liberty if any neighbour is empty, or
681 * any adjacent enemy chain dies (freeing a point next to pt), or any adjacent
682 * friendly chain has a liberty that is not pt. legal_moves calls this up to 361
683 * times per node and a playout calls legal_moves per move, so a board copy here
684 * would be the cost of the whole search.
685 */
686 206281414 static int go_legal(const struct go_board *b, const struct go_hist *h, int pt, int colour)
687 {
688 206281414 int i, breathes = 0;
689  
690 206281414 ▶ if (!b) return GO_ILL_OFF;
Branch: 1 branch
BranchTrueFalseTotal
if (!b) return GO_ILL_OFF; 0 206281414 206281414
691 206281414 ▶ if (colour != GO_BLACK && colour != GO_WHITE) return GO_ILL_COLOUR;
Branch: 2 branches
BranchTrueFalseTotal
if (colour != GO_BLACK && colour != GO_WHITE) return GO_ILL_COLOUR; 103495957 102785457 206281414
if (colour != GO_BLACK && colour != GO_WHITE) return GO_ILL_COLOUR; 0 103495957 103495957
692 206281414 ▶ if (pt < 0 || pt >= b->pts) return GO_ILL_OFF;
Branch: 2 branches
BranchTrueFalseTotal
if (pt < 0 || pt >= b->pts) return GO_ILL_OFF; 206281414 0 206281414
if (pt < 0 || pt >= b->pts) return GO_ILL_OFF; 1 206281413 206281414
693 206281413 ▶ if (b->colour[pt] == GO_BORDER) return GO_ILL_OFF;
Branch: 1 branch
BranchTrueFalseTotal
if (b->colour[pt] == GO_BORDER) return GO_ILL_OFF; 0 206281413 206281413
694 206281413 ▶ if (b->colour[pt] != GO_EMPTY) return GO_ILL_TAKEN;
Branch: 1 branch
BranchTrueFalseTotal
if (b->colour[pt] != GO_EMPTY) return GO_ILL_TAKEN; 17 206281396 206281413
695 206281396 ▶ if (pt == b->ko_point && colour == b->ko_colour) return GO_ILL_KO;
Branch: 2 branches
BranchTrueFalseTotal
if (pt == b->ko_point && colour == b->ko_colour) return GO_ILL_KO; 39370 206242026 206281396
if (pt == b->ko_point && colour == b->ko_colour) return GO_ILL_KO; 39368 2 39370
696  
697 1031210140 ▶ for (i = 0; i < 4; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < 4; i++) { 824968112 206242028 1031210140
698 824968112 int q = pt + b->nbr[i];
699 824968112 int c = b->colour[q];
700 824968112 ▶ if (c == GO_EMPTY) {
Branch: 1 branch
BranchTrueFalseTotal
if (c == GO_EMPTY) { 398562948 426405164 824968112
701 398562948 breathes = 1;
702 426405164 ▶ } else if (c == GO_OTHER(colour)) {
Branch: 2 branches
BranchTrueFalseTotal
} else if (c == GO_OTHER(colour)) { 213319250 213085914 426405164
} else if (c == GO_OTHER(colour)) { 175725433 250679731 426405164
703 175725433 ▶ if (dies_to(b, q)) breathes = 1; /* step 3, before step 4 */
Branch: 1 branch
BranchTrueFalseTotal
if (dies_to(b, q)) breathes = 1; /* step 3, before step 4 */ 11615598 164109835 175725433
704 250679731 ▶ } else if (c == colour) {
Branch: 1 branch
BranchTrueFalseTotal
} else if (c == colour) { 172060439 78619292 250679731
705 172060439 ▶ if (b->chain_libs[b->chain_root[q]] > 1) breathes = 1;
Branch: 1 branch
BranchTrueFalseTotal
if (b->chain_libs[b->chain_root[q]] > 1) breathes = 1; 161377496 10682943 172060439
706 }
707 }
708 206242028 ▶ if (!breathes) return GO_ILL_SUICIDE;
Branch: 1 branch
BranchTrueFalseTotal
if (!breathes) return GO_ILL_SUICIDE; 15057317 191184711 206242028
709  
710 191184711 ▶ if (h && b->superko_on) {
Branch: 2 branches
BranchTrueFalseTotal
if (h && b->superko_on) { 35421 191149290 191184711
if (h && b->superko_on) { 35244 177 35421
711 unsigned char packed[GO_MAX_PTS];
712 35244 unsigned long long after = go_hash_after(b, pt, colour);
713 int i2;
714 1062608 ▶ for (i2 = 0; i2 < h->n; i2++) {
Branch: 1 branch
BranchTrueFalseTotal
for (i2 = 0; i2 < h->n; i2++) { 1027366 35242 1062608
715 1027366 ▶ if (h->hash[i2] != after) continue;
Branch: 1 branch
BranchTrueFalseTotal
if (h->hash[i2] != after) continue; 1027364 2 1027366
716 2 packed_after(b, pt, colour, packed);
717 2 ▶ if (hist_seen(h, after, packed)) return GO_ILL_REPEAT;
Branch: 1 branch
BranchTrueFalseTotal
if (hist_seen(h, after, packed)) return GO_ILL_REPEAT; 2 0 2
718 0 break;
719 }
720 }
721 191184709 return GO_OK;
722 }
723  
724 890 static int go_legal_moves(const struct go_board *b, const struct go_hist *h,
725 int colour, int *out)
726 {
727 890 int r, c, n = 0;
728 890 ▶ if (!b) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (!b) return 0; 0 890 890
729 8977 ▶ for (r = 0; r < b->size; r++) {
Branch: 1 branch
BranchTrueFalseTotal
for (r = 0; r < b->size; r++) { 8087 890 8977
730 82308 ▶ for (c = 0; c < b->size; c++) {
Branch: 1 branch
BranchTrueFalseTotal
for (c = 0; c < b->size; c++) { 74221 8087 82308
731 74221 int pt = (r + 1) * b->stride + (c + 1);
732 74221 ▶ if (b->colour[pt] != GO_EMPTY) continue; /* the cheap test first */
Branch: 1 branch
BranchTrueFalseTotal
if (b->colour[pt] != GO_EMPTY) continue; /* the cheap test first */ 40915 33306 74221
733 33306 ▶ if (go_legal(b, h, pt, colour) != GO_OK) continue;
Branch: 1 branch
BranchTrueFalseTotal
if (go_legal(b, h, pt, colour) != GO_OK) continue; 1365 31941 33306
734 31941 ▶ if (out) out[n] = pt;
Branch: 1 branch
BranchTrueFalseTotal
if (out) out[n] = pt; 31941 0 31941
735 31941 n++;
736 }
737 }
738 890 return n;
739 }
740  
741 /* ------------------------------------------------------------------ ko ------ */
742  
743 /* ARTICLE 6'S SHAPE, AND ALL THREE CLAUSES ARE LOAD-BEARING.
744 *
745 * Article 6 describes a shape rather than a procedure: "A shape in which the
746 * players can alternately capture and recapture one opposing stone is called a
747 * 'ko'." So the test is whether THIS move created that shape, and it did only
748 * if all three hold. Each comment says what breaks without its clause. */
749 4574945 static void ko_set(struct go_board *b, int pt, int ncaps, int captured, int colour)
750 {
751 4574945 b->ko_point = -1;
752 4574945 b->ko_colour = GO_EMPTY;
753  
754 /* Without this, a capture of two or more stones sets a phantom ko and the
755 * opponent is refused a point Article 6 says nothing about. */
756 4574945 ▶ if (ncaps != 1) return;
Branch: 1 branch
BranchTrueFalseTotal
if (ncaps != 1) return; 4125650 449295 4574945
757  
758 /* Without this, a stone that joins a larger group AND captures one stone
759 * sets a ko. Article 6 does not create one: the recapture would not be of
760 * a single stone in a shape that can repeat. */
761 449295 ▶ if (b->chain_size[b->chain_root[pt]] != 1) return;
Branch: 1 branch
BranchTrueFalseTotal
if (b->chain_size[b->chain_root[pt]] != 1) return; 372535 76760 449295
762  
763 /* Without this, a capture that leaves the capturing stone with room sets a
764 * ko where no recapture was possible anyway. The symptom is the worst of
765 * the three: a legal move refused somewhere apparently unrelated, three
766 * moves later. */
767 76760 ▶ if (b->chain_libs[b->chain_root[pt]] != 1) return;
Branch: 1 branch
BranchTrueFalseTotal
if (b->chain_libs[b->chain_root[pt]] != 1) return; 37388 39372 76760
768  
769 39372 b->ko_point = captured;
770  
771 /* AND THE COLOUR IT IS FORBIDDEN TO, which is the player whose stone was
772 * just taken. Article 6 names one player: "A player whose stone has been
773 * captured in a ko cannot recapture in that ko on the next move." The
774 * capturer is not restricted, and on a filled board sometimes wants to
775 * play the point to connect. Refusing both colours is the easy version and
776 * it refuses a legal move. */
777 39372 ▶ b->ko_colour = GO_OTHER(colour);
Branch: 1 branch
BranchTrueFalseTotal
b->ko_colour = GO_OTHER(colour); 17075 22297 39372
778 }
779  
780 13 ▶static int go_ko_point(const struct go_board *b) { return b ? b->ko_point : -1; }
Branch: 1 branch
BranchTrueFalseTotal
static int go_ko_point(const struct go_board *b) { return b ? b->ko_point : -1; } 13 0 13
781 2 ▶static int go_ko_colour(const struct go_board *b) { return b ? b->ko_colour : GO_EMPTY; }
Branch: 1 branch
BranchTrueFalseTotal
static int go_ko_colour(const struct go_board *b) { return b ? b->ko_colour : GO_EMPTY; } 2 0 2
782 28 ▶static int go_superko_on(const struct go_board *b) { return b ? b->superko_on : 0; }
Branch: 1 branch
BranchTrueFalseTotal
static int go_superko_on(const struct go_board *b) { return b ? b->superko_on : 0; } 28 0 28
783  
784 28 static void go_set_superko(struct go_board *b, int on)
785 {
786 28 ▶ if (b) b->superko_on = on ? 1 : 0;
Branch: 1 branch
BranchTrueFalseTotal
if (b) b->superko_on = on ? 1 : 0; 28 0 28
787 28 }
788  
789 /* ============================================================== the scorers ===
790 *
791 * Two of them over ONE flood fill, because both ask the same question of the
792 * empty points and differ only in what they do with the answer.
793 *
794 * Japanese territory: an empty region reaching only one colour is that
795 * colour's, a region reaching both is dame, and a region the players agreed
796 * is seki counts for nobody.
797 * Tromp-Taylor area: the same classification, plus your stones on the board.
798 *
799 * The second is here for two reasons. It needs nobody's agreement, so it is
800 * what a game whose players cannot agree falls through to; and the two must
801 * agree under a published condition, which is the only differential test this
802 * distribution can have, since the XS-only decision left one implementation of
803 * everything else.
804 */
805  
806 /* One pass over the empty points. Fills the eye counts, the dame count, the
807 * stone counts and the area scores; the caller applies prisoners and komi. */
808 static void analyse_map(const struct go_board *b, const int *seki, int nseki,
809 struct go_score *out, signed char *owner);
810  
811 55076 static void analyse(const struct go_board *b, const int *seki, int nseki,
812 struct go_score *out)
813 {
814 55076 analyse_map(b, seki, nseki, out, NULL);
815 55076 }
816  
817 /* The one classification. `owner`, when given, gets one value per padded point:
818 * the colour whose territory it is, or GO_EMPTY for dame, for an agreed seki,
819 * and for anything holding a stone.
820 *
821 * It is the same walk that produces the score because a SECOND implementation
822 * of this is a second thing to get wrong, and the way it goes wrong is subtle:
823 * territory is a property of a REGION, so an empty point beside one black stone
824 * on an otherwise open board belongs to NOBODY. A per-point version of this
825 * gave a nearly empty board eight points of territory where the scorer, quite
826 * rightly, gave it none. */
827 56397 static void analyse_map(const struct go_board *b, const int *seki, int nseki,
828 struct go_score *out, signed char *owner)
829 {
830 int seen[GO_MAX_PTS];
831 int stack[GO_MAX_PTS];
832 int region[GO_MAX_PTS];
833 int r, c, i, k, sp, n;
834  
835 56397 out->eyes_b = out->eyes_w = 0;
836 56397 out->territory_b = out->territory_w = 0;
837 56397 out->dame = 0;
838 56397 out->area_b = out->area_w = 0;
839 56397 out->stones_b = b->stones[GO_BLACK];
840 56397 out->stones_w = b->stones[GO_WHITE];
841  
842 7422962 ▶ for (i = 0; i < b->pts; i++) seen[i] = 0;
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < b->pts; i++) seen[i] = 0; 7366565 56397 7422962
843  
844 582778 ▶ for (r = 0; r < b->size; r++) {
Branch: 1 branch
BranchTrueFalseTotal
for (r = 0; r < b->size; r++) { 526381 56397 582778
845 5561834 ▶ for (c = 0; c < b->size; c++) {
Branch: 1 branch
BranchTrueFalseTotal
for (c = 0; c < b->size; c++) { 5035453 526381 5561834
846 5035453 int p = (r + 1) * b->stride + (c + 1);
847 5035453 int touches_b = 0, touches_w = 0, is_seki = 0;
848  
849 5035453 ▶ if (b->colour[p] != GO_EMPTY || seen[p]) continue;
Branch: 2 branches
BranchTrueFalseTotal
if (b->colour[p] != GO_EMPTY || seen[p]) continue; 590536 4444917 5035453
if (b->colour[p] != GO_EMPTY || seen[p]) continue; 4648 585888 590536
850  
851 /* the region, and which colours it reaches */
852 585888 n = 0;
853 585888 sp = 0;
854 585888 stack[sp++] = p;
855 585888 seen[p] = 1;
856 1176424 ▶ while (sp > 0) {
Branch: 1 branch
BranchTrueFalseTotal
while (sp > 0) { 590536 585888 1176424
857 590536 int cur = stack[--sp];
858 590536 region[n++] = cur;
859 2952680 ▶ for (k = 0; k < 4; k++) {
Branch: 1 branch
BranchTrueFalseTotal
for (k = 0; k < 4; k++) { 2362144 590536 2952680
860 2362144 int q = cur + b->nbr[k];
861 2362144 ▶ if (b->colour[q] == GO_BLACK) { touches_b = 1; continue; }
Branch: 1 branch
BranchTrueFalseTotal
if (b->colour[q] == GO_BLACK) { touches_b = 1; continue; } 1262665 1099479 2362144
862 1099479 ▶ if (b->colour[q] == GO_WHITE) { touches_w = 1; continue; }
Branch: 1 branch
BranchTrueFalseTotal
if (b->colour[q] == GO_WHITE) { touches_w = 1; continue; } 763468 336011 1099479
863 336011 ▶ if (b->colour[q] != GO_EMPTY) continue; /* the ring */
Branch: 1 branch
BranchTrueFalseTotal
if (b->colour[q] != GO_EMPTY) continue; /* the ring */ 320521 15490 336011
864 15490 ▶ if (seen[q]) continue;
Branch: 1 branch
BranchTrueFalseTotal
if (seen[q]) continue; 10842 4648 15490
865 4648 seen[q] = 1;
866 4648 stack[sp++] = q;
867 }
868 }
869  
870 /* agreed seki: any listed point taints the whole region it is in */
871 585905 ▶ for (i = 0; i < nseki && !is_seki; i++)
Branch: 2 branches
BranchTrueFalseTotal
for (i = 0; i < nseki && !is_seki; i++) 18 585887 585905
for (i = 0; i < nseki && !is_seki; i++) 17 1 18
872 233 ▶ for (k = 0; k < n; k++)
Branch: 1 branch
BranchTrueFalseTotal
for (k = 0; k < n; k++) 221 12 233
873 221 ▶ if (region[k] == seki[i]) { is_seki = 1; break; }
Branch: 1 branch
BranchTrueFalseTotal
if (region[k] == seki[i]) { is_seki = 1; break; } 5 216 221
874  
875 585888 ▶ if (touches_b && !touches_w) {
Branch: 2 branches
BranchTrueFalseTotal
if (touches_b && !touches_w) { 361513 224375 585888
if (touches_b && !touches_w) { 361435 78 361513
876 361435 out->eyes_b += n;
877 361435 out->area_b += n;
878 361435 ▶ if (!is_seki) out->territory_b += n;
Branch: 1 branch
BranchTrueFalseTotal
if (!is_seki) out->territory_b += n; 361430 5 361435
879 361435 ▶ if (owner && !is_seki)
Branch: 2 branches
BranchTrueFalseTotal
if (owner && !is_seki) 5740 355695 361435
if (owner && !is_seki) 5740 0 5740
880 11480 ▶ for (k = 0; k < n; k++) owner[region[k]] = GO_BLACK;
Branch: 1 branch
BranchTrueFalseTotal
for (k = 0; k < n; k++) owner[region[k]] = GO_BLACK; 5740 5740 11480
881 224453 ▶ } else if (touches_w && !touches_b) {
Branch: 2 branches
BranchTrueFalseTotal
} else if (touches_w && !touches_b) { 224452 1 224453
} else if (touches_w && !touches_b) { 224374 78 224452
882 224374 out->eyes_w += n;
883 224374 out->area_w += n;
884 224374 ▶ if (!is_seki) out->territory_w += n;
Branch: 1 branch
BranchTrueFalseTotal
if (!is_seki) out->territory_w += n; 224374 0 224374
885 224374 ▶ if (owner && !is_seki)
Branch: 2 branches
BranchTrueFalseTotal
if (owner && !is_seki) 3373 221001 224374
if (owner && !is_seki) 3373 0 3373
886 6746 ▶ for (k = 0; k < n; k++) owner[region[k]] = GO_WHITE;
Branch: 1 branch
BranchTrueFalseTotal
for (k = 0; k < n; k++) owner[region[k]] = GO_WHITE; 3373 3373 6746
887 } else {
888 /* reaching both colours, or neither on an empty board */
889 79 out->dame += n;
890 }
891 }
892 }
893  
894 56397 out->area_b += out->stones_b;
895 56397 out->area_w += out->stones_w;
896 56397 }
897  
898 /* The same five steps score_jp takes, stopping after the classification. Dead
899 * stones come off on a copy first, because a point a dead stone was standing on
900 * is territory once it is gone. */
901 1321 static void go_territory(const struct go_board *b,
902 const int *dead, int ndead,
903 const int *seki, int nseki,
904 signed char *out)
905 {
906 struct go_board *work;
907 struct go_score s;
908 int i;
909  
910 1321 ▶ if (!b || !out) return;
Branch: 2 branches
BranchTrueFalseTotal
if (!b || !out) return; 1321 0 1321
if (!b || !out) return; 0 1321 1321
911 161162 ▶ for (i = 0; i < b->pts; i++) out[i] = GO_EMPTY;
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < b->pts; i++) out[i] = GO_EMPTY; 159841 1321 161162
912  
913 1321 work = go_board_copy(b);
914 1321 ▶ if (!work) return;
Branch: 1 branch
BranchTrueFalseTotal
if (!work) return; 0 1321 1321
915  
916 1321 ▶ for (i = 0; i < ndead; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < ndead; i++) { 0 1321 1321
917 0 int pt = dead[i];
918 0 ▶ if (pt < 0 || pt >= work->pts) continue;
Branch: 2 branches
BranchTrueFalseTotal
if (pt < 0 || pt >= work->pts) continue; 0 0 0
if (pt < 0 || pt >= work->pts) continue; 0 0 0
919 0 ▶ if (work->colour[pt] != GO_BLACK && work->colour[pt] != GO_WHITE) continue;
Branch: 2 branches
BranchTrueFalseTotal
if (work->colour[pt] != GO_BLACK && work->colour[pt] != GO_WHITE) continue; 0 0 0
if (work->colour[pt] != GO_BLACK && work->colour[pt] != GO_WHITE) continue; 0 0 0
920 0 (void)go_lift(work, pt);
921 }
922  
923 1321 analyse_map(work, seki, nseki, &s, out);
924 1321 go_board_drop(work);
925 }
926  
927 55012 static void go_score_area(const struct go_board *b, struct go_score *out)
928 {
929 55012 ▶ if (!b || !out) return;
Branch: 2 branches
BranchTrueFalseTotal
if (!b || !out) return; 55012 0 55012
if (!b || !out) return; 0 55012 55012
930 55012 analyse(b, NULL, 0, out);
931 55012 out->prisoners_b = out->prisoners_w = 0;
932 55012 out->score_b = out->score_w = 0;
933 }
934  
935 64 static void go_score_jp(const struct go_board *b,
936 const int *dead, int ndead,
937 const int *seki, int nseki,
938 int prisoners_b, int prisoners_w,
939 int komi_tenths,
940 struct go_score *out)
941 {
942 struct go_board *work;
943 int i;
944  
945 64 ▶ if (!b || !out) return;
Branch: 2 branches
BranchTrueFalseTotal
if (!b || !out) return; 64 0 64
if (!b || !out) return; 0 64 64
946  
947 /* Step 1. The dead come off, and each stone goes to the player who did NOT
948 * own it. Done on a COPY, because scoring a position must not change it:
949 * the site scores a game and then goes on serving the same board to a
950 * spectator. */
951 64 work = go_board_copy(b);
952 64 ▶ if (!work) return;
Branch: 1 branch
BranchTrueFalseTotal
if (!work) return; 0 64 64
953  
954 71 ▶ for (i = 0; i < ndead; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < ndead; i++) { 7 64 71
955 7 int pt = dead[i];
956 int colour, gone;
957 7 ▶ if (pt < 0 || pt >= work->pts) continue;
Branch: 2 branches
BranchTrueFalseTotal
if (pt < 0 || pt >= work->pts) continue; 7 0 7
if (pt < 0 || pt >= work->pts) continue; 0 7 7
958 7 colour = work->colour[pt];
959 7 ▶ if (colour != GO_BLACK && colour != GO_WHITE) continue;
Branch: 2 branches
BranchTrueFalseTotal
if (colour != GO_BLACK && colour != GO_WHITE) continue; 6 1 7
if (colour != GO_BLACK && colour != GO_WHITE) continue; 0 6 6
960 7 gone = go_lift(work, pt);
961 7 ▶ if (colour == GO_BLACK) prisoners_w += gone; /* black stones, white holds them */
Branch: 1 branch
BranchTrueFalseTotal
if (colour == GO_BLACK) prisoners_w += gone; /* black stones, white holds them */ 1 6 7
962 6 else prisoners_b += gone;
963 }
964  
965 /* Steps 2 to 4. */
966 64 analyse(work, seki, nseki, out);
967  
968 64 out->prisoners_b = prisoners_b;
969 64 out->prisoners_w = prisoners_w;
970  
971 /* Step 5, and the direction of it is the rule. Article 10.2 fills each
972 * player's prisoners INTO THE OPPONENT'S TERRITORY, so they come off the
973 * opponent rather than going on to your own. */
974 64 out->score_b = (out->territory_b - prisoners_w) * 10;
975 64 out->score_w = (out->territory_w - prisoners_b) * 10 + komi_tenths;
976  
977 64 go_board_drop(work);
978 }
979  
980 /* ====================================================== Benson's algorithm ===
981 *
982 * D. B. Benson, "Life in the Game of Go", Information Sciences 10 (1976).
983 *
984 * The chains that are UNCONDITIONALLY ALIVE: alive even if their owner never
985 * answers another move, whatever the opponent does. It is the only part of life
986 * and death that is decidable without search, and this engine claims to know
987 * nothing else about it.
988 *
989 * The algorithm, so the code below can be read against it:
990 *
991 * X = every chain of the colour
992 * R = every region: a maximal connected set of points NOT of the colour
993 *
994 * repeat until nothing is removed:
995 * remove from X every chain with fewer than TWO VITAL regions in R,
996 * where a region is vital to a chain when EVERY EMPTY POINT in it is
997 * adjacent to that chain
998 * remove from R every region that touches a chain no longer in X
999 *
1000 * what remains in X is unconditionally alive
1001 *
1002 * TWO VITAL REGIONS, NOT TWO EYE POINTS, and the difference is the thing this
1003 * gets right that a count of eyes does not. A group around a single two-point
1004 * eye has two eye points and ONE vital region, and it is not unconditionally
1005 * alive. t/10-benson.t has that position.
1006 */
1007  
1008 /* Every empty point of the region is a liberty of the chain. */
1009 111 static int region_is_vital(const struct go_board *b, int root,
1010 const int *pts, int from, int len)
1011 {
1012 int i, k;
1013 364 ▶ for (i = from; i < from + len; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (i = from; i < from + len; i++) { 317 47 364
1014 317 int p = pts[i];
1015 317 int touches = 0;
1016 317 ▶ if (b->colour[p] != GO_EMPTY) continue; /* opponent stones do not count */
Branch: 1 branch
BranchTrueFalseTotal
if (b->colour[p] != GO_EMPTY) continue; /* opponent stones do not count */ 132 185 317
1017 507 ▶ for (k = 0; k < 4; k++) {
Branch: 1 branch
BranchTrueFalseTotal
for (k = 0; k < 4; k++) { 443 64 507
1018 443 int q = p + b->nbr[k];
1019 443 ▶ if (b->chain_root[q] == root && b->colour[q] != GO_EMPTY) { touches = 1; break; }
Branch: 2 branches
BranchTrueFalseTotal
if (b->chain_root[q] == root && b->colour[q] != GO_EMPTY) { touches = 1; break; } 121 322 443
if (b->chain_root[q] == root && b->colour[q] != GO_EMPTY) { touches = 1; break; } 121 0 121
1020 }
1021 185 ▶ if (!touches) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (!touches) return 0; 64 121 185
1022 }
1023 47 return 1;
1024 }
1025  
1026 70 static int go_alive(const struct go_board *b, int colour, int *out)
1027 {
1028 int region_of[GO_MAX_PTS]; /* which region a point is in, or -1 */
1029 int pts[GO_MAX_PTS]; /* every region's points, laid end to end */
1030 int rstart[GO_MAX_PTS];
1031 int rlen[GO_MAX_PTS];
1032 int stack[GO_MAX_PTS];
1033 int live[GO_MAX_PTS]; /* by chain ROOT: is it still a candidate */
1034 int rlive[GO_MAX_PTS]; /* by region: is it still a candidate */
1035 70 int nregions = 0, npts = 0, n = 0;
1036 int r, c, i, k, sp, changed;
1037  
1038 70 ▶ if (!b || (colour != GO_BLACK && colour != GO_WHITE)) return 0;
Branch: 3 branches
BranchTrueFalseTotal
if (!b || (colour != GO_BLACK && colour != GO_WHITE)) return 0; 70 0 70
if (!b || (colour != GO_BLACK && colour != GO_WHITE)) return 0; 44 26 70
if (!b || (colour != GO_BLACK && colour != GO_WHITE)) return 0; 1 43 44
1039  
1040 8418 ▶ for (i = 0; i < b->pts; i++) { region_of[i] = -1; live[i] = 0; }
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < b->pts; i++) { region_of[i] = -1; live[i] = 0; } 8349 69 8418
1041  
1042 /* X starts as every chain of the colour. `live` is indexed by root, so a
1043 * point that is not a root simply never gets looked at. */
1044 690 ▶ for (r = 0; r < b->size; r++)
Branch: 1 branch
BranchTrueFalseTotal
for (r = 0; r < b->size; r++) 621 69 690
1045 6210 ▶ for (c = 0; c < b->size; c++) {
Branch: 1 branch
BranchTrueFalseTotal
for (c = 0; c < b->size; c++) { 5589 621 6210
1046 5589 int p = (r + 1) * b->stride + (c + 1);
1047 5589 ▶ if (b->colour[p] == colour) live[b->chain_root[p]] = 1;
Branch: 1 branch
BranchTrueFalseTotal
if (b->colour[p] == colour) live[b->chain_root[p]] = 1; 617 4972 5589
1048 }
1049  
1050 /* R starts as every maximal connected set of points that are NOT the
1051 * colour. The sentinel ring is not a point, so it bounds the fill. */
1052 690 ▶ for (r = 0; r < b->size; r++) {
Branch: 1 branch
BranchTrueFalseTotal
for (r = 0; r < b->size; r++) { 621 69 690
1053 6210 ▶ for (c = 0; c < b->size; c++) {
Branch: 1 branch
BranchTrueFalseTotal
for (c = 0; c < b->size; c++) { 5589 621 6210
1054 5589 int p = (r + 1) * b->stride + (c + 1);
1055 5589 ▶ if (b->colour[p] == colour || region_of[p] >= 0) continue;
Branch: 2 branches
BranchTrueFalseTotal
if (b->colour[p] == colour || region_of[p] >= 0) continue; 4972 617 5589
if (b->colour[p] == colour || region_of[p] >= 0) continue; 4852 120 4972
1056  
1057 120 rstart[nregions] = npts;
1058 120 sp = 0;
1059 120 stack[sp++] = p;
1060 120 region_of[p] = nregions;
1061 5092 ▶ while (sp > 0) {
Branch: 1 branch
BranchTrueFalseTotal
while (sp > 0) { 4972 120 5092
1062 4972 int cur = stack[--sp];
1063 4972 pts[npts++] = cur;
1064 24860 ▶ for (k = 0; k < 4; k++) {
Branch: 1 branch
BranchTrueFalseTotal
for (k = 0; k < 4; k++) { 19888 4972 24860
1065 19888 int q = cur + b->nbr[k];
1066 19888 ▶ if (b->colour[q] == GO_BORDER) continue;
Branch: 1 branch
BranchTrueFalseTotal
if (b->colour[q] == GO_BORDER) continue; 2232 17656 19888
1067 17656 ▶ if (b->colour[q] == colour) continue;
Branch: 1 branch
BranchTrueFalseTotal
if (b->colour[q] == colour) continue; 602 17054 17656
1068 17054 ▶ if (region_of[q] >= 0) continue;
Branch: 1 branch
BranchTrueFalseTotal
if (region_of[q] >= 0) continue; 12202 4852 17054
1069 4852 region_of[q] = nregions;
1070 4852 stack[sp++] = q;
1071 }
1072 }
1073 120 rlen[nregions] = npts - rstart[nregions];
1074 120 rlive[nregions] = 1;
1075 120 nregions++;
1076 }
1077 }
1078  
1079 /* The two removals, alternating until neither fires. */
1080 do {
1081 114 changed = 0;
1082  
1083 /* a chain with fewer than two vital candidate regions goes */
1084 1140 ▶ for (r = 0; r < b->size; r++) {
Branch: 1 branch
BranchTrueFalseTotal
for (r = 0; r < b->size; r++) { 1026 114 1140
1085 10260 ▶ for (c = 0; c < b->size; c++) {
Branch: 1 branch
BranchTrueFalseTotal
for (c = 0; c < b->size; c++) { 9234 1026 10260
1086 9234 int p = (r + 1) * b->stride + (c + 1);
1087 9234 int root, vital = 0, seen[4], nseen = 0;
1088 9908 ▶ if (b->colour[p] != colour) continue;
Branch: 1 branch
BranchTrueFalseTotal
if (b->colour[p] != colour) continue; 8490 744 9234
1089 744 root = b->chain_root[p];
1090 744 ▶ if (p != root || !live[root]) continue;
Branch: 2 branches
BranchTrueFalseTotal
if (p != root || !live[root]) continue; 120 624 744
if (p != root || !live[root]) continue; 50 70 120
1091  
1092 /* count the distinct candidate regions adjacent to this chain
1093 * that are vital to it. Walk the chain's stones; a region can
1094 * touch a chain at many points and counts once. */
1095 {
1096 70 int cur = root;
1097 do {
1098 870 ▶ for (k = 0; k < 4; k++) {
Branch: 1 branch
BranchTrueFalseTotal
for (k = 0; k < 4; k++) { 696 174 870
1099 696 int q = cur + b->nbr[k];
1100 696 int reg, j, dup = 0;
1101 696 ▶ if (b->colour[q] == GO_BORDER) continue;
Branch: 1 branch
BranchTrueFalseTotal
if (b->colour[q] == GO_BORDER) continue; 69 627 696
1102 627 reg = region_of[q];
1103 627 ▶ if (reg < 0 || !rlive[reg]) continue;
Branch: 2 branches
BranchTrueFalseTotal
if (reg < 0 || !rlive[reg]) continue; 381 246 627
if (reg < 0 || !rlive[reg]) continue; 0 381 381
1104 506 ▶ for (j = 0; j < nseen; j++) if (seen[j] == reg) { dup = 1; break; }
Branch: 2 branches
BranchTrueFalseTotal
for (j = 0; j < nseen; j++) if (seen[j] == reg) { dup = 1; break; } 270 125 395
for (j = 0; j < nseen; j++) if (seen[j] == reg) { dup = 1; break; } 395 111 506
1105 381 ▶ if (dup) continue;
Branch: 1 branch
BranchTrueFalseTotal
if (dup) continue; 270 111 381
1106 111 ▶ if (nseen < 4) seen[nseen++] = reg; /* two is all we need */
Branch: 1 branch
BranchTrueFalseTotal
if (nseen < 4) seen[nseen++] = reg; /* two is all we need */ 111 0 111
1107 111 ▶ if (region_is_vital(b, root, pts, rstart[reg], rlen[reg]))
Branch: 1 branch
BranchTrueFalseTotal
if (region_is_vital(b, root, pts, rstart[reg], rlen[reg])) 47 64 111
1108 47 vital++;
1109 }
1110 174 cur = b->chain_next[cur];
1111 174 ▶ } while (cur != root && vital < 2);
Branch: 2 branches
BranchTrueFalseTotal
} while (cur != root && vital < 2); 119 55 174
} while (cur != root && vital < 2); 104 15 119
1112 }
1113  
1114 70 ▶ if (vital < 2) { live[root] = 0; changed = 1; }
Branch: 1 branch
BranchTrueFalseTotal
if (vital < 2) { live[root] = 0; changed = 1; } 50 20 70
1115 }
1116 }
1117  
1118 /* a region touching a chain that has gone goes too */
1119 285 ▶ for (i = 0; i < nregions; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < nregions; i++) { 171 114 285
1120 int j;
1121 171 ▶ if (!rlive[i]) continue;
Branch: 1 branch
BranchTrueFalseTotal
if (!rlive[i]) continue; 51 120 171
1122 2725 ▶ for (j = rstart[i]; j < rstart[i] + rlen[i]; j++) {
Branch: 1 branch
BranchTrueFalseTotal
for (j = rstart[i]; j < rstart[i] + rlen[i]; j++) { 2656 69 2725
1123 2656 int p = pts[j];
1124 13123 ▶ for (k = 0; k < 4; k++) {
Branch: 1 branch
BranchTrueFalseTotal
for (k = 0; k < 4; k++) { 10518 2605 13123
1125 10518 int q = p + b->nbr[k];
1126 10518 ▶ if (b->colour[q] != colour) continue;
Branch: 1 branch
BranchTrueFalseTotal
if (b->colour[q] != colour) continue; 10167 351 10518
1127 351 ▶ if (!live[b->chain_root[q]]) { rlive[i] = 0; changed = 1; break; }
Branch: 1 branch
BranchTrueFalseTotal
if (!live[b->chain_root[q]]) { rlive[i] = 0; changed = 1; break; } 51 300 351
1128 }
1129 2656 ▶ if (!rlive[i]) break;
Branch: 1 branch
BranchTrueFalseTotal
if (!rlive[i]) break; 51 2605 2656
1130 }
1131 }
1132 114 ▶ } while (changed);
Branch: 1 branch
BranchTrueFalseTotal
} while (changed); 45 69 114
1133  
1134 /* what survived, as points */
1135 690 ▶ for (r = 0; r < b->size; r++)
Branch: 1 branch
BranchTrueFalseTotal
for (r = 0; r < b->size; r++) 621 69 690
1136 6210 ▶ for (c = 0; c < b->size; c++) {
Branch: 1 branch
BranchTrueFalseTotal
for (c = 0; c < b->size; c++) { 5589 621 6210
1137 5589 int p = (r + 1) * b->stride + (c + 1);
1138 5589 ▶ if (b->colour[p] != colour) continue;
Branch: 1 branch
BranchTrueFalseTotal
if (b->colour[p] != colour) continue; 4972 617 5589
1139 617 ▶ if (!live[b->chain_root[p]]) continue;
Branch: 1 branch
BranchTrueFalseTotal
if (!live[b->chain_root[p]]) continue; 127 490 617
1140 490 ▶ if (out) out[n] = p;
Branch: 1 branch
BranchTrueFalseTotal
if (out) out[n] = p; 490 0 490
1141 490 n++;
1142 }
1143  
1144 69 return n;
1145 }
1146  
1147 /* ---------------------------------------------------------------- play ------ */
1148  
1149 4574968 static void go_play(struct go_board *b, struct go_hist *h, int pt, int colour,
1150 struct go_played *out)
1151 {
1152 4574968 int i, j, code, nroots = 0;
1153 int roots[4];
1154  
1155 4574991 ▶ if (!out) return;
Branch: 1 branch
BranchTrueFalseTotal
if (!out) return; 0 4574968 4574968
1156 4574968 out->code = GO_ILL_OFF;
1157 4574968 out->ncaps = 0;
1158 4574968 out->ko_point = -1;
1159 4574968 ▶ if (!b) return;
Branch: 1 branch
BranchTrueFalseTotal
if (!b) return; 0 4574968 4574968
1160  
1161 /* Refuse BEFORE touching anything, so a refused play leaves the board
1162 * exactly as it was and a caller can offer the reason and try again. */
1163 4574968 code = go_legal(b, h, pt, colour);
1164 4574968 out->code = code;
1165 4574968 out->ko_point = b->ko_point;
1166 4574968 ▶ if (code != GO_OK) return;
Branch: 1 branch
BranchTrueFalseTotal
if (code != GO_OK) return; 23 4574945 4574968
1167  
1168 4574945 go_put(b, pt, colour);
1169  
1170 /* Article 5: the opposing stones come off, and the move is completed when
1171 * they have. An adjacent enemy chain is captured exactly when go_put's
1172 * recount has left it at zero. */
1173 22874725 ▶ for (i = 0; i < 4; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < 4; i++) { 18299780 4574945 22874725
1174 18299780 int q = pt + b->nbr[i];
1175 18299780 int r, seen = 0, cur;
1176 18299780 ▶ if (b->colour[q] != GO_OTHER(colour)) continue;
Branch: 2 branches
BranchTrueFalseTotal
if (b->colour[q] != GO_OTHER(colour)) continue; 9314028 8985752 18299780
if (b->colour[q] != GO_OTHER(colour)) continue; 13630633 4669147 18299780
1177 4669147 ▶ if (b->chain_libs[b->chain_root[q]] != 0) continue;
Branch: 1 branch
BranchTrueFalseTotal
if (b->chain_libs[b->chain_root[q]] != 0) continue; 3723525 945622 4669147
1178 945622 r = b->chain_root[q];
1179 1068170 ▶ for (j = 0; j < nroots; j++) if (roots[j] == r) { seen = 1; break; }
Branch: 2 branches
BranchTrueFalseTotal
for (j = 0; j < nroots; j++) if (roots[j] == r) { seen = 1; break; } 0 122548 122548
for (j = 0; j < nroots; j++) if (roots[j] == r) { seen = 1; break; } 122548 945622 1068170
1180 945622 ▶ if (seen) continue;
Branch: 1 branch
BranchTrueFalseTotal
if (seen) continue; 0 945622 945622
1181 945622 roots[nroots++] = r;
1182  
1183 /* record the stones before they go, because after go_lift the chain
1184 * that named them does not exist */
1185 945622 cur = r;
1186 2179499 ▶ do { out->caps[out->ncaps++] = cur; cur = b->chain_next[cur]; } while (cur != r);
Branch: 1 branch
BranchTrueFalseTotal
do { out->caps[out->ncaps++] = cur; cur = b->chain_next[cur]; } while (cur != r); 1233877 945622 2179499
1187 945622 (void)go_lift(b, r);
1188 }
1189  
1190 4574945 ▶ ko_set(b, pt, out->ncaps, out->ncaps == 1 ? out->caps[0] : -1, colour);
Branch: 1 branch
BranchTrueFalseTotal
ko_set(b, pt, out->ncaps, out->ncaps == 1 ? out->caps[0] : -1, colour); 449295 4125650 4574945
1191 4574945 out->ko_point = b->ko_point;
1192  
1193 4574945 ▶ if (h) (void)go_hist_push(h, b);
Branch: 1 branch
BranchTrueFalseTotal
if (h) (void)go_hist_push(h, b); 3393 4571552 4574945
1194 }
1195  
1196 /* A pass clears the ko point, because Article 6 forbids the recapture on the
1197 * NEXT move only: after a pass, the recapture is the move after that.
1198 *
1199 * It pushes nothing onto the history. A pass changes no colouring, so the
1200 * colouring is already there from the move that made it, and pushing it again
1201 * would be a duplicate at best. The direction that actually bites is the other
1202 * one: an engine that treats a pass as a position-producing event and pushes
1203 * can end up refusing the next real move that returns to a colouring, for a
1204 * reason no player could ever see. */
1205 294485 static void go_pass(struct go_board *b, int colour)
1206 {
1207 (void)colour;
1208 294485 ▶ if (!b) return;
Branch: 1 branch
BranchTrueFalseTotal
if (!b) return; 0 294485 294485
1209 294485 b->ko_point = -1;
1210 294485 b->ko_colour = GO_EMPTY;
1211 }
1212  
1213 /* ------------------------------------------------------------- the table ----- */
1214  
1215 /* NAMED ASSIGNMENT, NOT A POSITIONAL INITIALISER, and not a designated one
1216 * either. A positional list silently binds the wrong function to a member the
1217 * day somebody reorders the struct, and the symptom is a call through a
1218 * plausible-looking pointer. A designated initialiser would fix that and would
1219 * also put a C99-only construct in a file that has to build under old MSVC.
1220 * So the table is filled in by name, once, here. The writes are identical on
1221 * every call, so the benign race costs nothing. */
1222  
1223 static struct go_abi GO_TABLE;
1224 static int GO_TABLE_READY = 0;
1225  
1226 /* go_search.c fills in its own four members. Declared here rather than in
1227 * go_abi.h because it is not part of the published ABI: a consumer reaches the
1228 * search through the table like everything else.
1229 *
1230 * The two files call into each other, and it terminates: go_abi_table calls
1231 * this while building the table, and go_search.c only calls go_abi_table from
1232 * inside a search, which is long after the table is ready. */
1233 void go_search_install(struct go_abi *t);
1234  
1235 35 const struct go_abi *go_abi_table(void)
1236 {
1237 35 ▶ if (!GO_TABLE_READY) {
Branch: 1 branch
BranchTrueFalseTotal
if (!GO_TABLE_READY) { 26 9 35
1238 26 GO_TABLE.abi_version = GO_ABI_VERSION;
1239  
1240 26 GO_TABLE.board_new = go_board_new;
1241 26 GO_TABLE.board_drop = go_board_drop;
1242 26 GO_TABLE.board_copy = go_board_copy;
1243  
1244 26 GO_TABLE.at = go_at;
1245 26 GO_TABLE.libs = go_libs;
1246 26 GO_TABLE.chain_at = go_chain_at;
1247 26 GO_TABLE.chain_size = go_chain_size;
1248 26 GO_TABLE.pack = go_pack;
1249 26 GO_TABLE.hash = go_hash;
1250 26 GO_TABLE.stones = go_stones;
1251  
1252 26 GO_TABLE.point_of = go_point_of;
1253 26 GO_TABLE.col_of = go_col_of;
1254 26 GO_TABLE.row_of = go_row_of;
1255 26 GO_TABLE.size_of = go_size_of;
1256 26 GO_TABLE.stride_of = go_stride_of;
1257  
1258 26 GO_TABLE.put = go_put;
1259 26 GO_TABLE.lift = go_lift;
1260  
1261 26 GO_TABLE.zobrist = go_zobrist;
1262  
1263 /* appended at version 2. Nothing above this line moved. */
1264 26 GO_TABLE.hist_new = go_hist_new;
1265 26 GO_TABLE.hist_drop = go_hist_drop;
1266 26 GO_TABLE.hist_copy = go_hist_copy;
1267 26 GO_TABLE.hist_len = go_hist_len;
1268 26 GO_TABLE.hist_clear = go_hist_clear;
1269 26 GO_TABLE.hist_push = go_hist_push;
1270 26 GO_TABLE.hist_has = go_hist_has;
1271  
1272 26 GO_TABLE.legal = go_legal;
1273 26 GO_TABLE.legal_moves = go_legal_moves;
1274 26 GO_TABLE.play = go_play;
1275 26 GO_TABLE.pass = go_pass;
1276  
1277 26 GO_TABLE.ko_point = go_ko_point;
1278 26 GO_TABLE.ko_colour = go_ko_colour;
1279 26 GO_TABLE.set_superko = go_set_superko;
1280 26 GO_TABLE.superko_on = go_superko_on;
1281 26 GO_TABLE.hash_after = go_hash_after;
1282  
1283 /* appended at version 3 */
1284 26 GO_TABLE.alive = go_alive;
1285  
1286 /* appended at version 4 */
1287 26 GO_TABLE.score_jp = go_score_jp;
1288 26 GO_TABLE.score_area = go_score_area;
1289  
1290 /* appended at version 5 */
1291 26 GO_TABLE.territory = go_territory;
1292  
1293 /* appended at version 6, from go_search.c */
1294 26 go_search_install(&GO_TABLE);
1295  
1296 26 GO_TABLE_READY = 1;
1297 }
1298 35 return &GO_TABLE;
1299 }
« Go.xs ↑ Summary go_search.c »