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 19:05
> To: computer-go
> Subject: Re: [computer-go] Chains and liberties
>
>
> Mark wrote:
> > 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?
>
> Yes. (To be perfectly honest I had forgot about this little detail
> when I wrote the previous message, but the cyclic lists are still a
> nice idea and a space-effective way to store some of the information.)
>
> > Well, keeping the chains and liberty-lists for reversal is kind
> of the same
> > as keeping a change-stack I suppose.
>
> Not from my point of view. I would rather say that it's a way to
> reduce the size of the change-stack.

I've done a quick implementation along the lines I described. I found that
along with the marking of the merged chain in the chain array, all I need to
do is adding those same points to an array of integers. Although it has to
do this for all stones in the chain, I don't see how keeping cyclic lists is
going to beat that. I may be wrong of course. (And I have somehow gotten to
hate making linked-lists, so I suppose I'm a bit biased here.)

Taking back a move takes just moving around a few pointers. Except when
splitting chains, in which case it needs to mark all the stones involved in
the chain-array again.

I'm not too enthousiastic about the speed. A quick test seemed to point to a
little over 0.5 million moves per second, including taking back those same
moves. 2 uSec per move doesn't compare too well with my ladder-module, which
is more than twice the speed and does a whole lot more. So using it for
ladders is not an option. But maybe for the other tactial readers and
life-and-death it is, provided I can optimize the current implementation
still.

My implementation also feels rather OO. That means lots of function-calls.
I'm not sure to what extent they are inlined and optimized by the compiler.
The profiler I have is lousy and shows considerable time spent on
function-calls, even though I know most of them should have been compiled
out. I've been out of this kind of programming too long, it will take me a
little time to automatically know what's fast and what's not.

The other thing with OO in Java is the collections. Since Java 1.4 it
doesn't have type-safe collections, I need to do a cast in a few places. But
casts are very expensive. In Java 1.5, which I don't use yet, there are
type-safe collections, but I understand from the documentation it just does
the cast under the hood. (Swept under the carpet I call that.)

Thirdly, my object pools are standard Stack objects. Since Stack is
synchronized, this involves a considerable performance-hit as well. But it
seemed to me for the future it's wise to keep these thread-safe. Again, I
wish I had a better profiler.

Some more work and investigation maybe necessary. Hopefully this can be used
as a point of reference for faster methods or some clever optimization. At
least I think the implementation *looks* pleasant and clean, something that
may disappear with optimizations.

David Weiss said he probably won't be able to finish his flat-file
implementation for the pattern matcher before next week. I also didn't get
aproved by SourceForge yet, so it may take a little more before I'm going to
publish this all. In the meantime I hope I'll have some more spare time to
tinker with the chain administration.



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