Re: [computer-go] Chains and liberties

[Don Dailey <drd@xxxxxxx>]

>  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 have  found that  no matter what  representation you use,  there are
some things you  can't do as well as you would  like, and other things
that are really easy.

The bit  vector approach tries to  do many things in  parallel, at the
expense of decoding issues.   I think it's probably very fast at doing
some common things,  maybe a bit slow in others.

It may be that you can discover liberties one at a time and postpone a
lot of the logical operations until you know they are needed.  This is
common in alpha/beta  searching where you don't do  any work until you
know it  is absolutely  needed.  Moving to  a liberty, in  a searching
program, might create  a cutoff, in which case it  would not have been
very useful  finding ALL  the liberties first  (unless you  must count
them.)

If performance is the overriding issue, I think you have to figure out
exactly what  your program needs to  do, and then  determine what data
structure you need to support speed.

- Don






   Date: Sun, 14 Nov 2004 14:09:39 -0800
   From: Peter Drake <drake@xxxxxxxxxxxxxxxxx>
   X-Scanned-By: MIMEDefang 2.42

   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/