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

[Mark Boon <tesuji@xxxxxxxxx>]

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
computer-go@xxxxxxxxxxxxxxxxx
http://www.computer-go.org/mailman/listinfo/computer-go/