[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [computer-go] Groups, liberties, and such
I tried to explain why a localized liberty correction would not workin
my original (long) post. Consider stones in the shape of an uppercase U
where there one stone in the bottom is the newly added stone, and the
sides of the U are one stone apart. The U can be made arbitrarily tall
to invalidate local liberty corrections. See the picture below. The
X's are pre-existing stones and the + is the new stone.
PS: In theory, the stones could separate from each other local to the
connection but then come close to each other further on in each of the
When a move connects 2 strings, isn't it easy and fast to calculate
the liberty count of the newly combined string?
new_count = old_string_A_count + old_string_B_count - 1 + LNC.
LNC means Liberties Not in Common. For the newly placed stone (that does
the connecting), we look at the 4 neighbor points. If they are empty,
we tally 1 if they are not liberties of EITHER of the OLD strings.
This idea is easily extended for connections of 3 or 4 groups.
When connecting 2 groups, you would have to look at 6 points at most,
the 2 possible new liberties, and the 3 possible points around these new
liberties to check if they touch the old group.
Compared to other more complicated schemes, this is fast. What little
extra time this takes is very tiny when amortized over all the moves
your program will be making.
Am I understanding the problem correctly or am I confused about your
If the new connection is also a capture, this doesn't work, but that's
a problem for any of the incremental liberty calculations, not just the
computer-go mailing list