Hi everyone. I am still a beginner at the game of go, and I am also a programmer. I am currently writing an easy-to-use software for playing go either online or offline. However, the algorithm I am using to detect captured stones are very slow. I thought of an enhancement, but I am not sure if my assumption is correct.

If a stone is played which would capture one or more stones, is it safe to assume that at least one of the captured stones will be touching the played stone? Or is it possible to capture stones with a play which does not touch any of the captured stones?

Thanks!

Yes, because the played stone must by definition remove the last liberty of the group captured.Impossible, same reason.

In order to capture, you have to remove a liberty from a group of stones, so by necessity, your move must be adjacent to at least one of the stones in the group you are capturing.

Stones can be dead and still be on the board, because the opponent can capture them at will, but I gather that's not what you're looking for here.

That's what I indeed thought, thanks for confirming!

Just for fun: (long nerdy programming post follows)

If you only want to implement a go board data structure for a server GUI or for an SGF editor, then the following is almost certainly overkill. But if you want speed/efficiency, you can do much better if you track and incrementally update information about the groups on the board, rather than repeatedly running floodfill-like algorithms to count things like liberties.

A not-the-most-optimized but still quite fast implementation is for each group, to store the number of stones in the group, its "pseudoliberty" count, and a circular doubly linked list of all the stones in that group, with each node in the list also storing the group index for the group it belongs to. (The "pseudoliberties" of a group are the same as its liberties except that you count an empty spot multiple times if it's bordered by that group from multiple directions). Importantly, the linked list nodes don't need to be allocated dynamically. Just have a fixed flat array of nodes, one for each location on the board, and the "next" and "prev" pointers can also just be integers, indicating the location of the stone/node next or previous in the list, assuming a location is a single integer array index.

To play a stone at a location:
1. For each stone adjacent, regardless of color, decrement its group's pseudoliberty count by 1. (A group bordering that location from multiple sides will get decremented multiple times.)

2. If all adjacent groups of the opposing color still have one or more pseudoliberties (the move doesn't capture anything) and all adjacent groups of the same color now have zero pseudoliberties, and there are no empty spaces immediately adjacent to the location for the new stone, then the move is an illegal suicide - undo step 1 and return.

3. Otherwise, create a group for the new stone with an initial stone count of 1 and an initial pseudoliberty count of the number of empty spaces immediately adjacent.

4. Then, for each adjacent stone of the same color, perform a merge of that stone's group with the group of the new stone newly played, unless they are the same group already (the group of the new stone will be continually changing as it merges with each group around it and may already be merged if the group around it borders from multiple directions).

4a. To perform a merge of two groups, add the smaller group's pseudoliberty and stone counts to those of the larger group, then iterate through the smaller group's stones and update the group index of each to be the index of the larger group, and then concatenate the two groups' lists of stones together. Except for the iterating, this is all constant time, and in the vast majority of cases, the iterating will also be only over a single stone because the smaller group in the merge will only have one stone.

5. For each adjacent stone of the opposing color whose group has zero pseudoliberties, capture that group, adding pseudoliberties to the appropriate adjacent groups as each stone is removed.

Except for large captures (rare), and large merges when a new stone links two or existing large groups together (fairly rare), every step in the above is constant time and extremely fast. Notably, adding a stone to or filling a liberty of an existing large group does not iterate over the stones or liberties of the large group.

@ lightvector

Verrry interesting! Thanks.

That is basically the approach I took with my first go program many moons ago. I did not think of the pseudo-liberty idea, though. Nor did I use doubly-linked lists. I wrote the program in Smalltalk, and just used sets and set union.

However, to my surprise, the last time I dabbled with writing a go playing program, it was faster over a playout to handle captures by not joining stones into strings and doing a brute force search for a liberty as necessary. I suspect that at some point in the game, as a play becomes more likely to touch an opposing stone, and as the search for a liberty becomes deeper on average, the more sophisticated approach would become faster. Language probably matters. This was in NetLogo, which has a built-in data structure I used for adjacent points on the board. (Obviously I was not trying to write a competitive program in either language. )

_________________
The Adkins Principle:
At some point, doesn't thinking have to go on?
— Winona Adkins

Visualize whirled peas.

Everything with love. Stay safe.

Cool. I think the incremental approach indeed mainly pays off near the end of the game, particularly if you're writing a more dumb bot or playout logic that doesn't pass until the board is tiled with single-point eyes. Possibly if you only stop at the normal point where most people would pass, an efficient brute-force-style implementation might do similarly well.

I never went that deep into it myself, but from what I recall, if you're actually serious about writing a bot, it actually pays to go one step further and store the true liberty count, not the pseudoliberty count, even though incrementally updating efficiently this is much harder and more costly. The reason is then it becomes extremely fast to figure out all the moves on the board that will capture anything, and you can use the liberty count as an input to various capturing race or tactical routines or even pattern-matching routines. And of course, once the liberty count is an input to everything, incremental updating is a necessity, since recomputing it every time would be horrible.

Many years ago, just for the learning experience, I implemented the approach I described above in C++, except with some extra complexity to do true liberty counts rather than pseudoliberties, and without overall trying too hard, managed something around 7k playouts per second on 19x19, which although several times smaller than some published numbers I've heard, is still quite decent.

Right. If play stops at move 450, there have been a whole lot of captures.



Good points. Going way back, Wilcox obviously used the liberty count in tactical fights, hence his "five alive" heuristic. In my Smalltalk program for each set of connected stones I kept a set of its liberties. Obviously, the liberty count was the cardinality of that set.

I wonder about using bitmaps to implement sets of stones and liberties. Surely someone has tried that.

_________________
The Adkins Principle:
At some point, doesn't thinking have to go on?
— Winona Adkins

Visualize whirled peas.

Everything with love. Stay safe.