Re: [computer-go] Chains and liberties

[Peter Drake <drake@xxxxxxxxxx>]

On Saturday, November 13, 2004, at 01:06  PM, Don Dailey wrote:

> Peter,
>
> > 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).
> If 32-bits for each row,  you are not explaining how you get liberties
> above and below the block, only to the right and left.   (I assume you
> do it the most obvious way.)
A block is represented as an array of ints, each of which represents a 
row.  To shift left or right, I shift the bits within each int.  To 
shift up or down, I shift the ints within the array.

> For fast tactical searching, you  also want to know how many liberties
> are involved and have a very fast  way to identify them, one at a time
> (not just as another bit vector.)
>
> You can get a set of ALL liberties this way, but how do you get just a
> set of liberties for a specified block without a lot of dilate type of
> calculations?  In other words, can you quickly get a bit vector of all
> 2 liberty or less groups?  Do you maintain a separate list of vectors,
> one for each block?
Yes (to the last question).

Traversing a block (or set of liberties, or other region) involves 
"unpacking" the bit vectors.  I'm beginning to suspect that it's not 
worth the effort.

> I find that I'm always wanting to know:
>
>   1. Where each group is.
Generate a region containing just the stone in question.  Dilate and 
then bitwise AND with the set of points of that color, repeating this 
until there is no change.

>   2. How many liberties each group has.
Take the block, find its neighbors (by shifting in all four 
directions), and AND this with the set of vacant points.

>   3. How many stones in each group.
Unpack it and counts.

> How do you do these things?
I'm beginning to see the error of my ways.  I was about to ask about 
pattern matching, but the spiral sequence described in the GNU Go DFA 
paper would probably be easier without the bit vectors.

Rotation could easily be accommodated without the bit vectors.  If I 
define four int constants NORTH, SOUTH, EAST, and WEST, then I can ask 
for something like

stone.getNeighbor(NORTH)

or

stone.getNeighbor(rotate(rotate(reflect(NORTH))));

As a sometime Schemer, I love the parentheses.  :-)

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/