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.
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:
The BinMatrix B holds the black stones
The BinMatrix W holds the white stones
The BinMatrix P holds the black stone and the next stone he wants to play
The BinMatrix S is cleared and the new stone to be played is marked
Mask the neighbors with the white stones. The test S.equals(false) will now give false, so capture should be calculated
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
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).
Mask this with the surrounding white stones again. So this "group" should NOT be captured, since it have some liberties.
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)
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.
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
The first operations is done, to reduce the number of iterations. I have not testet if this is actually good or bad.
Well this is not the first region, but the serie of diagrams would become to long if I should explain all iterations.
(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.
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:
- 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
- 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
- inverse() // ~A
- increment() // A++, regards the matrix as an 361 bits int. Increment the first (a) integer, if it turns into 19 zero's (7FFFF+1 = 80000), then clear the integer (a=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)
- 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)
- equals(other) // compare 2 BinMatrix
- equals(boolean) // tests if all are true or false
If you have any comments, to the algorithm, I would be pleased to read them: Please make comments here below: