Re: [computer-go] Chains and liberties

[Gunnar Farnebäck <gunnar@xxxxxxxxxxxxxx>]

Mark wrote:
> GNU Go's approxlib() seems similar to my getNLib() function. getNlib()
> actually gets the number of liberties and their locations of a stone (or
> stones) when passed a coordinate where there's a stone, otherwise the number
> of liberties when a stone would be played there.

GNU Go has different functions for those cases. I won't say it makes a
big difference but the assertions about whether there should be a
stone or not has helped catch some bugs in other code.

> I also pass a 'maximum', so it stops as soon as it finds more than
> the required amount.

GNU Go does too.

> This uses the flood-fill principle discussed earlier.

We use the liberty lists for existing nearby strings to find
liberties. Only when MAX_LIBERTIES is exceeded both for requested
liberties and some of the nearby strings (very rare) do we have to
traverse the nearby strings to look for liberties, but the traversal
is through the cyclic lists rather than flood-filling of course.

> Isn't your chainlinks*() already held by 'neighborlist' in your chain
> structure, as Arend Bayer showed? It seems natural, if the chain
> datastructure already contains liberty-lists and stone-lists,
> neighbour-lists seems a very natural extension.

Yes, chainlinks() only translates from string numbers to the "origin"
(one of the stones) of each neighbor string. Chainlinks2() and
chainlinks3() additionally filter with respect to the number of
liberties in two different ways.

> It's also data that's very fast and easy to generate while you're at
> it, and can be useful for tactical search.

Indeed. It can also be used for some optimizations in updating liberty
lists when a string is captured.

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