[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [computer-go] Groups, liberties, and such

Jason House wrote:

Mark Boon wrote:

In my opinion pseudo-liberties are next to useless. When you put the limit too high you end up doing liberty calculation for the majority of the chains anyway so you gain almost nothing. If you put it too low you'll run into too situations where you make a terrible mistake.

What would you recommend instead of pseudo-liberties as a liberty calculation metric? # of stones? # of distinct touching enemy stones? Recognized shapes? Some combination of those?
About a year ago I started a discussion in this group what it would take to make something that keeps liberties of chains and update them incrementally after every move as efficiently as possible. An implementation in Java ended up in the library I mentioned. Gnu Go has something similar in C I believe. Liberties are too important a concept in go to use any method to estimate them. Moreover, it's not that expensive to calculate compared to any other known method. (At least that I know of.)

The distinct feature of the number of touching stones can actually become a complex operation since it essentially requires iterating over all touching white stones.
When I actually thought this out in more detail, the actual threshold would be <= 10 pseudo_liberties rather than <10. The reasoning is at the bottom of this e-mail.

From the algorithmic standpoint, pseudo-liberties are a valid metric for computing stone captures. When placing an enemy stone, for each touching stone of opposing color, decrement a pseudo liberty from whichever group the stone is part of.
As discussed originally, the pseudo-liberty calculation can be done locally for any merger of stones, and always O(1) operations. Since liberty calculation can be O(# of stones), I wanted to avoid them if possible.

For those interested in the <=10 threshold:
There's no way for a chain to have less than 2 eyes, less than 4 liberties, and more than 10 pseudo-liberties.
A fully enclosed single point eye is 1 liberty but 4 pseudo liberties.
A non-eye liberty is capped at 3 pseudo-liberties (a friendly stone on 3 of 4 sides). Therefore, for a group to not be unconditionally alive and have less than N liberties, it's pseudo-liberties can be no higher than 3*N-2. For N=4, this comes out to 10.
As just a point of reference, without touching enemy stones, the liberty count would always for all 3 stone (or shorter) chains and never occur for 5 stone (or longer) chains. If there are enemy stones touching, the pseudo-liberties approach will slowly start extending these limits to larger chains.
computer-go mailing list