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

[Jason House <jhouse@xxxxxxxxx>]

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?
  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/