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

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

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