Peter Seibel wrote:
John Tromp <John.Tromp@xxxxxxxxxxxxxxxxx> writes:Simply finding the connected components in Go can be done very fast asymptotically (between O(log n) and O(1)), using a so called union-find algorithm. Instead of liberties, one counts liberty-edges, i.e. the edges which connect a liberty to a stone of the group. When joining strings together these counts can simply be added.
Duh. I get it. So there's no necessary relation between the number of liberty edges and the actual number of liberties except that the number of liberty-edges is always >= the number of liberties? So when liberty-edges = 0, liberties = 0. For example both groups of @ below have four liberty edges but the group in the corner has three liberties while the other group has four: .------------ | + @ + + + + | @ @ O + + + | + O + + + + | + + O @ @ O | + + + + + +
Correct; in fact #libs <= #lib-edges <= 4 *libs The upper bound is also achievable, as in @ @ @ O . @ . @ O O @ @ . @ O O @ @ @ O O O O O O where @ has 2 liberties and 8 liberty edges. regards, -John _______________________________________________ computer-go mailing list computer-go@xxxxxxxxxxxxxxxxx http://www.computer-go.org/mailman/listinfo/computer-go/