Re: [computer-go] Hardware-Instruction.

[Peter Seibel <peter@xxxxxxxxxxxxxx>]

John Tromp <John.Tromp@xxxxxxxxxxxxxxxxx> writes:

> 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.

>> Huh? I must not be understanding you. Take this position:
>>
>>   + O O O
>>   O + @ O
>>   O @ + O
>>   + O + +
>>
>> I'd say there are two one-stone groups of @'s each with two
>> liberties. And each with two liberty edges. (?) But if a @ is
>> played to connect the two stones, after subtracting the one liberty
>> taken up by the new stone, the group has only one liberty not 1 + 1
>> = 2. Or am I not understanding what a "liberty edge" is?
>
> Your arithmetic is a little off:-) Let us show the liberty edges of
> the central 2x2 points in detail:
>
>     +  --a--  @
>
>     |         |
>     b         c
>     |         |
>
>     @  --d--  +
>
> Clearly, both @ have 2 adjacent liberty edges. Playing a @ at the top left
> connects both @, but takes away TWO liberty edges in doing so.

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
 | + + + + + +

Or am I still spacing on something?

-Peter

-- 
Peter Seibel                                      peter@xxxxxxxxxxxxxxxxx

         Lisp is the red pill. -- John Fraser, comp.lang.lisp
_______________________________________________
computer-go mailing list
computer-go@xxxxxxxxxxxxxxxxx
http://www.computer-go.org/mailman/listinfo/computer-go/