Re: [computer-go] Hardware-Instruction.

[Peter Seibel <peter@xxxxxxxxxxxxxx>]

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?

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