Re: [computer-go] Chains and liberties

[Gunnar Farnebäck <gunnar@xxxxxxxxxxxxxx>]

Mark wrote:
> Now several ideas have past by in this list to address this issue. It's such
> a basic thing that every Go program needs it. It's also one of those things
> that are simple enough to 'solve' once and for all, make a basic reference
> implementation and be done with it.

What, taking away the fun for all future go programmers? :-)

> Let's first look at playing a move. I distinguish three possible cases:
> 1) playing a single stone that results in a new chain, with one stone in it
> and up to four liberties.
> 2) adding a stone to an existing chain, increasing the stone list by one. It
> could reduce the number of liberties by one, or increase by up to two.
> 3) merging two or more existing chains.

This makes perfect sense and is probably unavoidable. GNU Go makes the
same case distinctions.

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

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

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

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

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