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

[Jason House <jhouse@xxxxxxxxx>]

I think I'm going to abandon pseudo-liberties in favor of a slightly 
more complex form of localized liberty counting that can still be done 
incrementally.

I've come to two useful conclusions about liberty approximations.

1. Only large chains can exhibit unfavorable shapes, and even then the 
pathological cases can only be a small fraction of a group or force two 
eyes to form.  Of course, once a group has two or more eyes, I stop 
caring about that exception.

2. Careful (but localized) tracking of open triangle shapes within a 
group can eliminate most cases of miscounting.  An 8 stone square is the 
smallest group where a simple tracking of open triangles would break 
down, but a bit more care solves that too.


  Actually, with open triangle tracking, no exceptions can occur with 
less than 7 stones.  At 7 stones, a U with sides of 3 would cause a 
miscount by one liberty.  For every two stones added to the U, the 
miscount increases by one.
  Since I've already used the term pseudo-liberties for something else, 
I'll just call this liberty estimate localized liberties.
  The worst case for local liberties is double counting.  The only way 
to count a single liberty 3 or 4 times is to form two eyes and is 
therefore a don't care scenario.  Since 2:1 is the worst case, 4 real 
liberties exist if there are at least 7 local liberties.
  The table below summarizes the liberty bounds

stones(N)  min local liberties to guarantee liberties >= 4
    1       4
    2       4
    3       4
    4       4
    5       4
    6       4
    7       5  (N+3)/2
    8       5  (N+3)/2
    9       6  (N+3)/2
   10       6  (N+3)/2
   11+      7


I think this approach should be a far more acceptable liberty approximation.

_______________________________________________
computer-go mailing list
computer-go@xxxxxxxxxxxxxxxxx
http://www.computer-go.org/mailman/listinfo/computer-go/