RE: [computer-go] Chains and liberties - performance

["Mark Boon" <tesuji@xxxxxxxxx>]

> -----Original Message-----
> From: computer-go-bounces@xxxxxxxxxxxxxxxxx
> [mailto:computer-go-bounces@xxxxxxxxxxxxxxxxx]On Behalf Of Gunnar
> Farnebdck
> Sent: Monday, November 15, 2004 21:16
> To: computer-go
> Subject: Re: [computer-go] Chains and liberties - performance
>
>
> Anders wrote:
> > As far as I understand, GNU Go only keeps track of the liberties up to a
> > certain number, not the theoretical maximum possible. Why?
> You'll have to
> > test for the upper limit in a number of places, and recompute
> the liberties
> > if you ever get blocks with more liberties. Is the reduced
> memory usage seen
> > as more important than a small speedup?
>
> Yes, it's a memory consideration. When the code was implemented it
> made a difference of 650 kB, which I didn't think was justified to
> spend. Now it's four and a half years later, GNU Go's memory footprint
> is larger anyway, and the difference has shrunk to 210 kB. It may be
> time to revise that decision.
>

Goliath simply used an unchecked maximum of 40 liberties. So in theory it's
easy to cause a problem by creating a large chain. In practice I don't think
it has ever happened... :-)

I was thinking: 650Kb? But when I look at the chain datastructure I have now
with liberty-lists, stone-lists and neighbours, it's probably 5Kb a piece.
So in an average game it can easily spend 1Mb just on chains. I suppose it
becomes clear why in Goliath I never considered using anything but the
'on-demand' functions, as it allowed it to run in about 1Mb, code and data
together.

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