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

Re: [computer-go] Hardware-Instruction.

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.
So the resulting group has liberty edges {b,d} plus {a,c} minus {a,b} = {c,d}.

regards,
-John

main=mapM_(print.g 2)[0..]where
g b 0=b;g b n=g c$s 0n-1where s _ 0=0;s e n=mod n b*c^s 0e+s(e+1)(div n b);c=b+1

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