A-1 A-2 A-3 A-4
B-1 B-2 B-3 B-4
C-1 C-2 C-3 C-4
D-1 D-2 D-3 D-4

A-1 A-2 A-3 A-4 B-1 B-2 B-3 B-4 C-1 C-2 C-3 C-4 D-1 D-2 D-3 D-4

We need 2 bit per position (A-1 ...) in the pattern because we need at least 3 different status per position. And 4 if we want to have edge as an status also.

00 = Empty
01 = Black
10 = White
11 = Edge

So the following 32 bit stream would be this pattern:

0000 0000 0000 0000 0000 0000 0000 0000 bin

0100 1000 0110 0000 0000 0000 0000 0101 bin

Manipulate

But we need to be able to manipulate the patterns, so it is not always practical to represent the pattern in the way discribes above. What we need is a simple way to rotate, invert and mirror the patterns.

So by placing the position in this way this will be much easier to manipulate the patterns:

A-1 A-2  B-3 B-1
A-3 A-4  B-4 B-2

D-2 D-4  C-4 C-3
D-1 D-3  C-2 C-1

A-1 A-2 A-3 A-4 B-1 B-2 B-3 B-4 C-1 C-2 C-3 C-4 D-1 D-2 D-3 D-4

A rotation of the pattern would simply be a shift operation.

A-1 A-2 A-3 A-4 B-1 B-2 B-3 B-4 C-1 C-2 C-3 C-4 D-1 D-2 D-3 D-4

shiftet 8 bit

B-1 B-2 B-3 B-4 C-1 C-2 C-3 C-4 D-1 D-2 D-3 D-4 A-1 A-2 A-3 A-4

The inversion of patterns changes

Empty -> Empty (00->00)
Black -> White (01->10)
White -> Black (10->01)
Edge -> Edge   (11->11)

C++ code:
#define rotate(p)
    ( ( ( p&0x000000FF )<<24 ) | ( ( p&0xFFFFFF00 )>>8 ) )
#define antirotate(p)
    ( ( ( p&0xFF000000 )>>24 ) | ( ( p&0x00FFFFFF )<<8 ) )
#define invert(p)
    ( ( ( p&0xAAAAAAAA )>>1  ) | ( ( p&0x55555555 )<<1 ) )
#define shift(p)
     ( ( ( p&0x30303030 )>>2  ) | ( ( p&0x0C0C0C0C )<<2 ) |
       ( p&0xC3C3C3C3 ) )
#define mirror(p)
    ( ( shift( p )&0xFF00FF00 )>>8 ) |
      ( shift( p )&0x00FF00FF )<<8 ) )

So the previus pattern is now:

0100 1000 0110 0000 0000 0000 0000 0101 bin

Database

From all initial patterns there is also a resulting pattern. So a hash table could be build with input and output pattern. The problem is only that some pattern on a real board are larger than other. The patterns are more "empty" in the beginning of the game. Later on when there are more stones on the board, it is not nessesary to consider so widely.

So I define some surrounding patterns. That also can be representet by some 32 bit variables. The patterns starts at level 1 and continue until they meet some requirements.

Stop

The end of the patterns is determind by how many stones there are in the surrounding. As one example: When there has been 4 or more stone (or edge) in the surrounding, we have a stop.

Tables

A pattern on level 0 is P0. A pattern on level 1 is S1. The resulting pattern is R. A hash table with all patterns on level 0 is set up. From this table there is a pointer to a tree structure containing the surrounding patterns (S1-S16 and resulting (R) patterns.

Hash   Tree
P0---->S1,S2,S3,S4,R
P0---->S1,S2,S3,S4,S5,R
P0---->S1,S2,R
P0---->S1,S2,S3,S4,S5,R

Every surrounding pattern also contains a pointer to a different surrounding pattern, but still with the same pattern on level 0.

Hash   Tree
P0---->S1,S2,S3,S4,R
       |  |  |  |
       |  |  |  v
       |  |  v  S4,R
       |  v  S3,S4,S5,S6,R
       |  S2,R
       |  |
       |  v
       v  S2,S3,S4,S5,R
       S1,R

The patterns are rotated, mirrored and inverted, so only the smallest (in value) pattern is stored. This also concern the surrounding. So we need to be able to rotate, mirror and invert the surrounding patterns also.

The surrounding patterns are there fore arranged as:

    A-1 A-3 A-4 A-2
D-2                 B-1
D-4                 B-3
D-3                 B-4
D-1                 B-2
    C-2 C-4 C-3 C-1

A rotation and inverting is still the same, but mirror need some special care. First a swap is performed, where all X-1 is swaped with X-2 and X-3 with X-4. Then only B-@ and D-@ is interchanged by a rotation.

C++ code
#define swap(p)
  ( ( ( p&0xCCCCCCCC )>>2 ) | ( ( p&0x33333333 )<<2 ) )
#define mirror(p)
  ( ( ( swap( p )&0x00FF0000 )>>16 ) |
    ( ( swap( p )&0x000000FF )<<16 ) |
    ( swap( p )&0xFF00FF00 ) )

Resulting patterns

Now we can store patterns in a database, where we have a center 4 by 4 pattern and some surrounding pattern to assist in the choise of the resulting pattern. When a user plays a move on the board, the move is marked in a resulting pattern. Again we need 2 bit per position, as both players can make a move on a certain position.

00 - None of the players have made this move
01 - only black has made this move
10 - only white has made this move
11 - both black and white have made this move.

Finding suggestions

We can now store moves in a database, and find sugestions to any board position. Ex:

Would be converted into: (with a stop on 3 surrounding stones or edge)

P0: 0000 0001 0000 0000 0000 0000 0000 0000 ('a' marking with 1 black stone)
S1: 0000 0000 0000 0000 0000 0000 0000 0000 ('b' marking)
S2: 0000 0000 0000 0000 0000 0000 0000 0000 ('c' marking)
S3: 1111 1111 0000 0000 0000 0000 1111 1111 ('d' marking,
                                             NB: Edge)
S4: 1111 1111 0000 0000 0000 0000 1111 1111 ('e' Marking,
                                             NB: Edge repeated)
S5: 1111 1111 0000 0000 0001 0000 1111 1111 ('f' marking,
                                            NB: the black stone)
R : 0000 0000 1000 0000 0000 0000 0000 0000 (This white move
                                             is stored)

lowest pattern

The pattern is rotated, inverted and mirrored to find the lowest value of the pattern before it is stored. This makes it easier to find a sugestion for a move in a new board position, and there is a reuse of position when they are rotated, mirrored, and inverted.

Good and bad things

The good this about this pattern database, is that it can store opening position (fuseki), corner position (joseki) but also endgame position in 1 and the same database. The only differens in the patterns is the size of the surrounding patterns. The bad thing about this database, is that only moves made by a user prevously can be return as a sugestion for a position. So when there is only 1 stone that changes in the surrounding patterns, there will be no resulting pattern stored. Or not all marked. Also if there is a ladder breaker or not is not stored in the patterns.

Use

This database can only give some suggestions for some moves. We still need to perform a MiniMax or Playout analysis to find the best of the suggestions.

Ideas

I also have some ideas beside the described methode. Level 4 of the surrounding patterns could be choosed like this instead, and level 5 continues in the same way as before. (I have not design the rotation and mirror function yet, but setup of the bit pairs could be as in the main pattern.)