| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| if (ZOB_READY) return; |
6795576 |
25 |
6795601 |
|
| 144 |
75 |
▶ | for (colour = GO_BLACK; colour <= GO_WHITE; colour++) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (colour = GO_BLACK; colour <= GO_WHITE; colour++) { |
50 |
25 |
75 |
|
| 145 |
22100 |
▶ | for (pt = 0; pt < GO_MAX_PTS; pt++) { |
Branch: 1 branch
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| for (r = 0; r < b->stride; r++) { |
5930 |
492 |
6422 |
|
| 197 |
81844 |
▶ | for (c = 0; c < b->stride; c++) { |
Branch: 1 branch
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| } 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| for (i = 0; i < n; i++) { |
2179598 |
945710 |
3125308 |
|
| 339 |
10897990 |
▶ | for (k = 0; k < 4; k++) { |
Branch: 1 branch
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| if (!seen) roots[nroots++] = r; |
1478082 |
3242468 |
4720550 |
|
| 345 |
|
| } |
| 346 |
|
| } |
| 347 |
|
| } |
| 348 |
|
| |
| 349 |
3125308 |
▶ | for (i = 0; i < n; i++) { |
Branch: 1 branch
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| for (r = 0; r < b->size; r++) |
36348 |
3930 |
40278 |
|
| 403 |
381842 |
▶ | for (c = 0; c < b->size; c++) |
Branch: 1 branch
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| if (h->hash) free(h->hash); |
0 |
0 |
0 |
|
| 482 |
0 |
▶ | if (h->pos) free(h->pos); |
Branch: 1 branch
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| if (!h) return; |
0 |
487 |
487 |
|
| 492 |
487 |
▶ | if (h->hash) free(h->hash); |
Branch: 1 branch
| Branch | True | False | Total |
| if (h->hash) free(h->hash); |
487 |
0 |
487 |
|
| 493 |
487 |
▶ | if (h->pos) free(h->pos); |
Branch: 1 branch
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| if (n->hash) free(n->hash); |
0 |
0 |
0 |
|
| 516 |
0 |
▶ | if (n->pos) free(n->pos); |
Branch: 1 branch
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| if (!h) return 0; |
0 |
4 |
4 |
|
| 570 |
8 |
▶ | for (i = 0; i < h->n; i++) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (i = 0; i < h->n; i++) { |
8 |
0 |
8 |
|
| 571 |
8 |
▶ | if (h->hash[i] != hash) continue; |
Branch: 1 branch
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| if (b->colour[q] != them) continue; |
128331 |
12649 |
140980 |
|
| 616 |
12649 |
▶ | if (!dies_to(b, q)) continue; |
Branch: 1 branch
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| if (ix >= 0) buf[ix] = (unsigned char)colour; |
2 |
0 |
2 |
|
| 639 |
|
| |
| 640 |
2 |
▶ | them = GO_OTHER(colour); |
Branch: 1 branch
| Branch | True | False | Total |
| them = GO_OTHER(colour); |
0 |
2 |
2 |
|
| 641 |
10 |
▶ | for (i = 0; i < 4; i++) { |
Branch: 1 branch
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| if (b->colour[q] != them) continue; |
0 |
8 |
8 |
|
| 645 |
8 |
▶ | if (!dies_to(b, q)) continue; |
Branch: 1 branch
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| } 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| if (c == GO_EMPTY) { |
398562948 |
426405164 |
824968112 |
|
| 701 |
398562948 |
| breathes = 1; |
| 702 |
426405164 |
▶ | } else if (c == GO_OTHER(colour)) { |
Branch: 2 branches
| Branch | True | False | Total |
| } 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
| Branch | True | False | Total |
| if (dies_to(b, q)) breathes = 1; /* step 3, before step 4 */ |
11615598 |
164109835 |
175725433 |
|
| 704 |
250679731 |
▶ | } else if (c == colour) { |
Branch: 1 branch
| Branch | True | False | Total |
| } else if (c == colour) { |
172060439 |
78619292 |
250679731 |
|
| 705 |
172060439 |
▶ | if (b->chain_libs[b->chain_root[q]] > 1) breathes = 1; |
Branch: 1 branch
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| if (!breathes) return GO_ILL_SUICIDE; |
15057317 |
191184711 |
206242028 |
|
| 709 |
|
| |
| 710 |
191184711 |
▶ | if (h && b->superko_on) { |
Branch: 2 branches
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| for (i2 = 0; i2 < h->n; i2++) { |
1027366 |
35242 |
1062608 |
|
| 715 |
1027366 |
▶ | if (h->hash[i2] != after) continue; |
Branch: 1 branch
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| if (!b) return 0; |
0 |
890 |
890 |
|
| 729 |
8977 |
▶ | for (r = 0; r < b->size; r++) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (r = 0; r < b->size; r++) { |
8087 |
890 |
8977 |
|
| 730 |
82308 |
▶ | for (c = 0; c < b->size; c++) { |
Branch: 1 branch
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| if (go_legal(b, h, pt, colour) != GO_OK) continue; |
1365 |
31941 |
33306 |
|
| 734 |
31941 |
▶ | if (out) out[n] = pt; |
Branch: 1 branch
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| for (r = 0; r < b->size; r++) { |
526381 |
56397 |
582778 |
|
| 845 |
5561834 |
▶ | for (c = 0; c < b->size; c++) { |
Branch: 1 branch
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| if (b->colour[q] != GO_EMPTY) continue; /* the ring */ |
320521 |
15490 |
336011 |
|
| 864 |
15490 |
▶ | if (seen[q]) continue; |
Branch: 1 branch
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| for (k = 0; k < n; k++) |
221 |
12 |
233 |
|
| 873 |
221 |
▶ | if (region[k] == seki[i]) { is_seki = 1; break; } |
Branch: 1 branch
| Branch | True | False | Total |
| if (region[k] == seki[i]) { is_seki = 1; break; } |
5 |
216 |
221 |
|
| 874 |
|
| |
| 875 |
585888 |
▶ | if (touches_b && !touches_w) { |
Branch: 2 branches
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| if (!is_seki) out->territory_b += n; |
361430 |
5 |
361435 |
|
| 879 |
361435 |
▶ | if (owner && !is_seki) |
Branch: 2 branches
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| } 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
| Branch | True | False | Total |
| if (!is_seki) out->territory_w += n; |
224374 |
0 |
224374 |
|
| 885 |
224374 |
▶ | if (owner && !is_seki) |
Branch: 2 branches
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| if (!work) return; |
0 |
1321 |
1321 |
|
| 915 |
|
| |
| 916 |
1321 |
▶ | for (i = 0; i < ndead; i++) { |
Branch: 1 branch
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| if (!work) return; |
0 |
64 |
64 |
|
| 953 |
|
| |
| 954 |
71 |
▶ | for (i = 0; i < ndead; i++) { |
Branch: 1 branch
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| for (r = 0; r < b->size; r++) |
621 |
69 |
690 |
|
| 1045 |
6210 |
▶ | for (c = 0; c < b->size; c++) { |
Branch: 1 branch
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| for (r = 0; r < b->size; r++) { |
621 |
69 |
690 |
|
| 1053 |
6210 |
▶ | for (c = 0; c < b->size; c++) { |
Branch: 1 branch
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| if (b->colour[q] == GO_BORDER) continue; |
2232 |
17656 |
19888 |
|
| 1067 |
17656 |
▶ | if (b->colour[q] == colour) continue; |
Branch: 1 branch
| Branch | True | False | Total |
| if (b->colour[q] == colour) continue; |
602 |
17054 |
17656 |
|
| 1068 |
17054 |
▶ | if (region_of[q] >= 0) continue; |
Branch: 1 branch
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| for (r = 0; r < b->size; r++) { |
1026 |
114 |
1140 |
|
| 1085 |
10260 |
▶ | for (c = 0; c < b->size; c++) { |
Branch: 1 branch
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| if (dup) continue; |
270 |
111 |
381 |
|
| 1106 |
111 |
▶ | if (nseen < 4) seen[nseen++] = reg; /* two is all we need */ |
Branch: 1 branch
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| } 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| for (i = 0; i < nregions; i++) { |
171 |
114 |
285 |
|
| 1120 |
|
| int j; |
| 1121 |
171 |
▶ | if (!rlive[i]) continue; |
Branch: 1 branch
| Branch | True | False | Total |
| if (!rlive[i]) continue; |
51 |
120 |
171 |
|
| 1122 |
2725 |
▶ | for (j = rstart[i]; j < rstart[i] + rlen[i]; j++) { |
Branch: 1 branch
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| if (!rlive[i]) break; |
51 |
2605 |
2656 |
|
| 1130 |
|
| } |
| 1131 |
|
| } |
| 1132 |
114 |
▶ | } while (changed); |
Branch: 1 branch
| Branch | True | False | Total |
| } while (changed); |
45 |
69 |
114 |
|
| 1133 |
|
| |
| 1134 |
|
| /* what survived, as points */ |
| 1135 |
690 |
▶ | for (r = 0; r < b->size; r++) |
Branch: 1 branch
| Branch | True | False | Total |
| for (r = 0; r < b->size; r++) |
621 |
69 |
690 |
|
| 1136 |
6210 |
▶ | for (c = 0; c < b->size; c++) { |
Branch: 1 branch
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| if (b->colour[p] != colour) continue; |
4972 |
617 |
5589 |
|
| 1139 |
617 |
▶ | if (!live[b->chain_root[p]]) continue; |
Branch: 1 branch
| Branch | True | False | Total |
| if (!live[b->chain_root[p]]) continue; |
127 |
490 |
617 |
|
| 1140 |
490 |
▶ | if (out) out[n] = p; |
Branch: 1 branch
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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 |
|
| } |