[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [computer-go] Chains and liberties
On Saturday, November 13, 2004, at 11:14 AM, Gunnar Farnebäck wrote:
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? :-)
I love doing this -- it's a very fun data structures problem.
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.
Can you say more about this? Orego currently uses bit vectors (one
32-bit int for each row on the board) to represent blocks. Is it worth
using an array (with fill pointer) or linked list of points instead?
Has anyone compared these implementations empirically?
The bit vector representation does allow for efficient representation
of mathematical morphology operations. Specifically, to find the
liberties of a block, we just:
1) Find the set of points adjacent to the block (with shift
operations), then,
2) Take the intersection of this set with the set of vacant points
(with bitwise AND operations).
This takes time independent of the number of stones in the block.
I never understood the point of having sorted liberty lists. Merging
lists can be done in O(n) with only a marginal memory overhead.
I guess sorted lists would be easier to test for equality...
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.
I don't think this would be a problem in Java. Java has pointers, you
just can't do arithmetic on them -- and you don't have to worry about
dangling pointers, memory leaks, etc.
Peter Drake
Assistant Professor of Computer Science
Lewis & Clark College
http://www.lclark.edu/~drake/
_______________________________________________
computer-go mailing list
computer-go@xxxxxxxxxxxxxxxxx
http://www.computer-go.org/mailman/listinfo/computer-go/