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 Paul Pogonyshev
> Sent: Monday, November 15, 2004 12:02
> To: computer-go
> Subject: Re: [computer-go] Chains and liberties
>
>
> I'm a little late into this discussion, but I'd like to point out
> a few uses of board code that frequently occur in GNU Go.
>
> We have approxlib() and accuratelib() functions that predict the
> number of liberties a player gains after a given move.  The
> difference between them is that approxlib() ignores captures
> (hence it is "approximate".)  In principle, accuratelib() is
> identical to (in pseudocode)
>
> 	play_move (pos, color);
> 	result = count_liberties (pos);
> 	undo_move ();
>
> 	return result;
>
> (Actually this is how it was implemented earlier.)  However, in
> GNU Go these functions don't alter the board (i.e. they don't play
> the move.)  This is a speed optimization that makes the functions
> several times faster (at the cost of code complication of course.)
> We also find that "approximate" result of approxlib() is very often
> good enough, so the faster approxlib() is used more often than
> accuratelib().
>
> We also have a family of chainlinks*() functions that find opponent's
> string adjacent to given string, possibly with restriction on the
> number of liberties.  This is what we track neighbours while playing
> moves for.  chainlinks*() are very useful in tactical reading.
>

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. I also pass a 'maximum', so
it stops as soon as it finds more than the required amount. This uses the
flood-fill principle discussed earlier. There's also a getRlib(), wich takes
captures into account, similar to your accuratelib().

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. It's also data that's very
fast and easy to generate while you're at it, and can be useful for tactical
search. I haven't found a clever reversal yet though... so the reversal
slows down the chain module a bit at the moment and I didn't think the speed
was great to begin with. So until I find a faster reversal I've separated it
out by conditional compilation. It depends also how generally useful it is.
Sometimes it's more efficient to do just-in-time computations instead of
preparing all in advance.

I have a few more days left to play around...

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