# Board Here, the goal is to implement the [Game rules](https://en.wikipedia.org/wiki/Rules_of_Go). Tasks remaining: - ✓ capture - ✓ suicide - ✓ ko - ✓ pass - ✓ handicap - ✓ count score Related projects: - [jgoboard](https://github.com/jokkebk/jgoboard) (see [website](http://jgoboard.com)) - [WGo.js](http://wgo.waltheri.net) available on [GitHub](https://github.com/waltheri/wgo.js) - [Go libraries](https://github.com/waltheri/go-libraries) ## Capture and suicide 1. Compute the set of black and white chains. 2. Count the liberties of each chain. 3. If a chain of the opponent's color has none, remove it and its stones, and go back to 1. 4. If a chain of the player's color has none, this is a suicide: refuse the move. *Jan's optimized suggestion, if we don't keep track of groups/liberties over time:* 1. Look what's adjacent to the targeted intersection: 2. If there is a stone of the player's color, remember it for later. 3. If there is a stone of an opponent's color, compute its group until we find the first liberty (if we compute the whole group with no liberty, capture it) 4. If there is an empty intersection, we know it's not a suicide. 5. If there was no empty intersection, and no opponent group was captured, compute adjacent groups until the first liberty (if there is none, refuse the suicide) ## Ko Compute Zobrist hashing of boards. It supports positional superko, and can be updated fast. Ignore the possibility that equal hashes may result from distinct positions. ## Score 1. Compute the set of chains into three groups: empty, black, white. 2. For each empty chain, mark it as black, resp. white, if it is only connected to black, resp. white, chains. 3. Black score: number of stones from black chains, plus captures. White score: same, plus komi. --- # Bots - Communicate to the WebWorker bot with [GTP]. - Get [SGF] examples (eg. [AlphaGo vs. Ke Jie]). There are [SGF databases]. - Compute the accuracy / time ratio over a corpus of high-level matches. [GTP]: https://www.lysator.liu.se/~gunnar/gtp/gtp2-spec-draft2/gtp2-spec.html [SGF]: https://en.wikipedia.org/wiki/Smart_Game_Format [AlphaGo vs. Ke Jie]: https://events.google.com/alphago2017/sgf/alphago20170523_en.sgf [SGF databases]: http://senseis.xmp.net/?SGFArchives ## Probaduk We define a set of masks relative to an intersection that allow matching up to twelve intersections. Each intersection is either outside, empty, of the same color as the current player, or of a different color.

Fulfill from existing master playouts, a hash table indicating the number of occurrences (in total and when placing a stone) given a match of a mask. When guessing a spot, pick the spot with the largest probability, computed like this: Score(intersection, mask) = Wilson score (# matches among moves, # matches) Pr(intersection) = max[mask] Score(intersection, mask) Assuming a packing of 7 bytes per match (3 for the match, 2 for the move count, 2 for the total count), the level 2 mask information weighs 3¹²×7 = 3.7 MB. (It can be divided by eight by removing symmetries, though.) Generate one level 2 mask for every level 1 match, and so on with further levels. To trim them down, only generate a level `l+1` for the `sqrt(n)` top level `l` matches, and only keep `sqrt(n)` of them, with `n` the number of level `l` matches. That way, the total number of stored matches is `n × l`, with `n` the number of level 1 matches, and `l` the number of levels. Ideally, you want `l = 4`, to detect the board edge on 4-4 points for the purpose of Josekis. With `n = 10000`, level 4 has `10000^(1/(2^4)) = 1` matches. ## Gonvnet Use a *convolutional neural network* as a move guesser: it computes the probability of a move on a board. You can also add a CNN win guesser (computing the probability of winning), which you can use to evaluate nodes in a *Monte-Carlo Tree Search*, in which you select promising nodes from the average between the most probable move and the node with best quality (bootstrapped by the win guesser). You perform the rollout to the end of the game only from the move guesser; then the quality of the leaf node is set to the average of the win guesser on the node's board and of the rollout success, and the quality of the node's ancestor is updated to the average of the qualities of its children.