BinMatrix

Table of contents Rules Benson Pass Alive

Table of diagrams Black's next move will be on the marked spot B W P.copy(B).set(pos) S.none().set(pos) S.neighbors4() S.and(W) N.copy(S.expandTo(W)) N.neighbors4() N.minus(P) N.neighbors4() N.and(S) N.expandTo(S) N.xor(S) Unconditionally Alive? Black stones only Liberties of black stones (L) Potential regions are liberties plus adjacent white stones (P) Error liberties (E) Error potential regions Reduced potential regions (R) First region (F) Opposit set of first region (R.clone().xor(F)) Surrounding black stones Opposit set of black stone

BinaryMatrix? Binary Matrix LogicMatrix? Logic Matrix

I (Kjeld Petersen) have been working on a library implementation of a 19x19 binary matrix, to implement the game rules by simple matrix calculations. You are free to use the method, but please give credits if used. BinMatrix is implemented with 19 integers (32 bits). At the end of this page is a list of operations that can be performed on BinMatrix'es.

I have also implemented the Benson Pass Alive algorithm with BinMatrix'es, and I will document that when I get the time to do so. But basicly I just extends black's groups to include liberties, and then the adjacent white groups to that. That must be the potential regions. But if there are any liberties to that it's a bad region. Next I mask the remaining region out 1 at the time, and if there is any black stone with no remaining region in the vicinity it must be removed from the potential pass alive pool.

NB: There could be some benefit in implementing a lowestRowWithBitSet and highestRowWithBitSet, that should keep track of how many of the 19 integers actually should be compared in all methods. I need to perform some speed testing, to see if this would benefit the overall algorithm. But in general only few lines are used when doing this algorithm. And it is not that often that a capture is spread across the hole board.

Rules

Implementing the game rules can be done with:

BinMatrix B,W,oldB,oldW,P,S,N
int bScore,wScore
Player turn = BLACK

In the move method I do the below checking. Particular line 4 and 5 are important. 4) Checks if there are any surrounding opponent groups. 5) Expand the surrounding group and find the groups with no liberties, and count the possible captured stones. Line 6+7 checks, if none is captured, that it is not suicide. If only 1 stone is captured it may be a KO, so line 9 checks for that. The rest is just copying the new positions, and removing the captured stones by a simple XOR.

 1: if( B.is(pos) || W.is(pos) ) return OCCUPIED
 2: if( turn == BLACK )
 3:     P.copy(B).set(pos)
 4:     capture = ( S.none().set(pos).neighbors4().and(W).equals(false) )
 5:         ? 0 : N.copy( S.expandTo(W) ).neighbors4().minus(P).neighbors4().and(S).expandTo(S).xor(S).count()
 6:     if( capture == 0 )
 7:         if( S.none().set(pos).expandTo(P).neighbors4().minus(W).equals(false) ) return SUICIDE
 8:     else
 9:         if( capture == 1 && P.equals(oldB) ) return KO
10:         bScore += capture
11:         oldW.copy(W)
12:         W.xor(N)
13:     oldB.copy(B)
14:     B.set(pos)
15: else
16:     P.copy(W).set(pos)
17:     capture = ( S.none().set(pos).neighbors4().and(B).equals(false) )
18:         ? 0 : N.copy( S.expandTo(B) ).neighbors4().minus(P).neighbors4().and(S).expandTo(S).xor(S).count()
19:     if( capture == 0 )
20:         if( S.none().set(pos).expandTo(P).neighbors4().minus(B).equals(false) ) return SUICIDE
21:     else
22:         if( capture == 1 && P.equals(oldW) ) return KO
23:         wScore += capture
24:         oldB.copy(B)
25:         B.xor(N)
26:     oldW.copy(W)
27:     W.set(pos)
28: turn = opponent(turn)
29: return APPROVED

Here is how it works:

Black's next move will be on the marked spot  

B  

The BinMatrix B holds the black stones

W  

The BinMatrix W holds the white stones

P.copy(B).set(pos)  

The BinMatrix P holds the black stone and the next stone he wants to play

S.none().set(pos)  

The BinMatrix S is cleared and the new stone to be played is marked

S.neighbors4()  

Find the neighbors of the new stone.

S.and(W)  

Mask the neighbors with the white stones. The test S.equals(false) will now give false, so capture should be calculated

N.copy(S.expandTo(W))  

Expand S so it covers the connected stone, with a series of grow() + and(W) until no there are no more changes. We now have a BinMatrix S with the surrounding white stones to the new stone. The BinMatrix N is simply a copy of S

N.neighbors4()  

Find the neighbor points of the surrounding white stones.

N.minus(P)  

Remove all the markings where there are black stones. So that must be the liberties of the surrounding white stones. Here I could test if N.equals(false) to see if all surrounding stones should be captured, and calculate capture=N.copy(S).count(). But I need to perform some speed test to see if this would benefit the whole algorithm. It depends on what is more common. If we capture, then it is a full capture, where the played stone has no opponent stones as neighbor after the capture. Or it is more common it does have some neighbor stones after any capture. N.neighbors4().and(S).expandTo(S).xor(S) does have some costly operations. Particular expandTo(S).

N.neighbors4()  

Find the neighbors to the liberties.

N.and(S)  

Mask this with the surrounding white stones again. So this "group" should NOT be captured, since it have some liberties.

N.expandTo(S)  

Expand so we have the white group(s) that should NOT be captured.

N.xor(S)  

We can now switch over from the stones that should NOT be captured, to the stones that SHOULD be captured with a simple xor. Now calculate capture = N.count(). And remove the captured stones from the white stones with W.xor(N)

[edit]

Benson Pass Alive

Sorry, I have to re-think this algoritm, because of the example below. I will return with a solution, when ready. Right now the algoritm is semi correct. The potential region c is not valid, but will not be detected by my algoritm. The problem is that all points in the c region has a neighboring black stone, but from different chains. The long chain only supports 3 of the points in c, and the short chain (a single stone) only supports 2 of the points in c.

Unconditionally Alive?  

BinMatrix B, W, L, P, E, R, N, M, C, F

 1: L.copy(B).neighbors4().minus(W)       // Liberties to black, X.
 2: P.copy(L).expandTo( W.clone().or(L) )  // Potential regions, X. or X.O or XO
 3: E.copy(P).neighbors4().minus(B)       // Error liberties, X.. or XO. or X.O.
 4: R.copy(E).grow4().expandTo(P).xor(P)  // Reduced potential regions
 5: N.none()
 6: M.none()
 7: do
 8:     C.copy(R)                                                      // Region counter
 9:     while( ! C.equals(false) )                                     // continue until all regions are removed
10:         F.copy(C).first().expandTo(R)                              // find first region
11:         N.or( R.clone().xor(F).neighbors4().expandTo(B).xor(B) )   // Without first region, include black, swapped over to the not included black stones. That is black with only 1 potentinal region
12:         C.xor(F)                                                   // remove the first region from the region counter
13:     M.copy(N).neighbors4().expandTo(R)                             // Region(s) next to black stones with only 1 potential region
14:     R.minus(M)                                                     // Remove region from the region pool, so stones with semi pass alive groups will be removed in the next iteration
15: while( ! M.equals(false) )
16: return B.clone().xor(N)                                            // return only pass alive black stones

Black stones only  

Liberties of black stones (L)  

Potential regions are liberties plus adjacent white stones (P)  

In this case no change, since there are no white stones

Error liberties (E)  

If the liberties or the adjacent white stones have extra liberties, that are then error liberties

Error potential regions  

E.grow4().expandTo(P)

Regions next to the error liberties

Reduced potential regions (R)  

The first operations is done, to reduce the number of iterations. I have not testet if this is actually good or bad.

First region (F)  

Well this is not the first region, but the serie of diagrams would become to long if I should explain all iterations.

Opposit set of first region (R.clone().xor(F))  

Surrounding black stones  

(R.clone().xor(F).neighbors4().expandTo(B)). Since I have removed 1 of the potential regions, then stones that does not have a region now did only have the regions that was masked out. So those stones are not pass alive.

Opposit set of black stone  

This set of black stones are moved (added) to N. N.or(R.clone().xor(F).neighbors4().expandTo(B).xor(B)). At the end N holds all the non-pass-alive black stones

My BinMatrix class have the following function:

Constructors

• BinMatrix()
• BinMatrix(boolean)
• BinMatrix(other)

Manipulators

• set(position) // a[pos/19] |= 1<<(pos%19)
• clear(position) // a[pos/19] &= ~(1<<(pos%19))
• toogle(position) // a[pos/19] ^= 1<<(pos%19)
• all() // set all bits to 1
• none() // clear all bits (0's)
• copy() // deep copy
• clone() // creates a clone to work on

Binary operators

• and(other) // A&B
• or(other) // A|B
• xor(other) // A^B
• minus(other) // A&~B
• expandTo(other) // a while loop that repeats grow4() + and(other) until there are no changes

Unary operators

• inverse() // ~A
• increment() // A++, regards the matrix as an 361 bits int. Increment the first (a[0]) integer, if it turns into 19 zero's (7FFFF+1 = 80000), then clear the integer (a[0]=0), and repeat for the next integer, otherwise break the loop.
• decrement() // A--, regards the matrix as an 361 bits int
• twoComplement() // -A = (~A)++
• first() // this and twoComplement(this), A&-A
• firstChain() // this.clone().first().expandTo(this)
• withoutFirst()
• randomFree() // while loop trying random position until a free is found.
• down() // shift rows down, filling the top with 0's
• up() // shift row up, filling the bottom with 0,s
• left() // shift columns left, filling the right with 0's
• right() // shift columns right, filling the left with 0´s
• explode4() // up() or down() or left() or right()
• explode8() // First up() or down(), then right() or left(), then or with explode4() for single stones
• grow4() // explode4() or this
• grow8() // explode8() or this
• neighbors4() // explode4() and not(this)
• neighbors8() // explode8() and not(this)

Testing

• is(position)
• equals(other) // compare 2 BinMatrix
• equals(boolean) // tests if all are true or false
• count()

If you have any comments, to the algorithm, I would be pleased to read them: Please make comments here below: