Re: computer-go: Sharing Go modules

["Richard Brown" <rbrown@xxxxxxxx>]

Well, just to add my voice to the noise about 1-D vs. 2-D arrays,
let me share with you an approach that I use in some parts of my
program, a hybrid of Java and native C code.  (Guess which part is
the legacy code.)

Feel free to use or modify the Java class below, if you find it
useful.  It's only twelve lines of code.

To represent board state, I use three bitmaps, each comprising a
1-D array of 32 ints.  But 32 ints, times 32 bits each, gives a
2-D bitmap.

[In Java, an int is always 32 bits.  And, as a primitive, it's
alloc'ed on the stack, not on the heap, so it's faster than the
creation of non-primitive objects.]

One bitmap indicates whether the point is "on the board" or not.
This automatically accomodates different sizes -- and even different
shapes -- of boards.  (Up to a 30x30 board, if you also want an
invisible edge row around the board.)

Another bitmap indicates whether a point is "stoned" or not.  (That
is, occupied.)  Of course, any bits set here comprise a strict subset
of the points that are on the board.

The third indicates, for occupied points on the board, whether they
are black or white.

[For unoccupied points, this third bitmap can also serve double duty:
To indicate, for example, whether the vacant point is a legal move or
not (consider suicide, and ko).  Or perhaps to mark it as "visited"
already in some algorithm.]

Each bitmap is declared and instantiated as an instance of the Java
class below, which has one field, one constructor, and two methods.

import java.awt.Point;

public class BoardBits {

  int bb[];	//	Field.

  public BoardBits() {	//	Constructor.
    bb = new int[32];
  }

/*	That gives us, for each BoardBits object, 32 ints (of 32 bits).
	A 1-dimensional array of ints, but a 2-dimensional bitmap.

Now, masking the int that corresponds to the Y coordinate, we left-
shift a 1 by the value of the X coordinate, and we can do:	*/

  private void setBit(Point myPoint) {
    this.bb[myPoint.y] |= ( 1 << myPoint.x );
  }

//	And:

  public boolean getBit(Point myPoint) {
    return( ( this.bb[myPoint.y] & ( 1 << myPoint.x )) != 0 );
  }
}

That's the whole class.  The setBit() method does a left-shift and
an OR, to set 1 bit, while the getBit() method does a left-shift,
an AND, and a compare with zero, and returns either true or false.

So, with only three of these bitmaps, we can do stuff like:

	++myPoint.y;	// Look at my northern neighbor.
	if( bitMap[ONBOARD].getBit(myPoint)
	&& !bitMap[STONED].getBit(myPoint) ) {
		// Then it's a liberty.
		...
	}

And so on.

Additional instances are handy for storing the answers to all sorts
of yes/no questions about the points on the board.

And without any multiply, or address arithmetic, I think...  I'm not
sure what looking at the assembler output would show about this sort
of scheme -- and I don't know how to do that for the JVM anyway --
any thoughts on this?  I have found it to be very convenient.

There's a little bit of wasted space in each bitmap, unless you're
playing on a 30x30 board. (And 4 bits are wasted even if you are!)
Does anyone think that this wasted space will cause performance
difficulties that will outweigh the convenience of this class?

Comments welcome.

-- 
Richard L. Brown       Office of Information Services
Unix Guy               University of Wisconsin System Administration
                       780 Regent St., Rm. 246
rbrown@xxxxxxxxxxxxxxxxx        Madison, WI  53715