RE: [computer-go] Chains and liberties

["Mark Boon" <tesuji@xxxxxxxxx>]

> -----Original Message-----
> From: computer-go-bounces@xxxxxxxxxxxxxxxxx
> [mailto:computer-go-bounces@xxxxxxxxxxxxxxxxx]On Behalf Of Gunnar
> Farnebdck
> Sent: Saturday, November 13, 2004 17:14
> To: computer-go
> Subject: Re: [computer-go] Chains and liberties
>
>
> > Adding all the stones and marking the Chain object in the chain
> array takes
> > O(n) where n is the total number of stones involved.
>
> It might not fit into this approach but merging stone lists can always
> be done in constant time if the strings are represented as cyclic
> lists in a board array.

Yes, I can see how that is possible, I'll think about that. But you will
still need to process all the stones of the newly merged group to set the
pointer to the Chain datastructure in the chain array for all the points,
no? Unless you're having a totally different data-representation I suppose,
and you never need to know the chain at random position x,y.

>
> > This can be done in constant time at the cost of using
> > considerably more memory per chain. Would that be worth it?
> Theoretically a
> > chain can have up to 229 liberties, but in practice the average
> is probably
> > more in the neighbourhood of 4.
>
> I doubt that it's worth it, with cache misses and what not.

I suppose cache-misses do affect performance, but I find it too hard to take
them into account when I'm thinking about algorithms. If someone can show me
that a less efficient algorithm runs faster than a more efficient, more
memory-hungry one, in real-life circumstances, *then* I'll believe it, and
no sooner. I'm talking about 450 bytes more per chain, is that going to make
all the difference?

> > If we use Davids method of sorted liberty lists, making the new
> > liberty-list also takes O(n) where n is the cumulative liberty count
> > of the chains involved. If we use the more memory intensive solution
> > I have in mind, it also takes O(n) but probably with less code (and
> > therefore faster?).
>
> I never understood the point of having sorted liberty lists. Merging
> lists can be done in O(n) with only a marginal memory overhead.

Yes, that is correct, no need for sorting actually.

> > Now taking back a move. We can distinguish the same three cases as with
> > playing a move.
>
> Keeping a change stack that can be unwinded to perform undo is way
> easier. It has been described here before how GNU Go does that, but
> since it relies heavily on pointers to arbitrary board data it's maybe
> not feasible in Java.

Well, keeping the chains and liberty-lists for reversal is kind of the same
as keeping a change-stack I suppose.

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