Pattern Matching
How to build a pattern database:
The size of the pattern has influence on how big the database will become. I will try to describe my idea of a pattern database with a 4x4 sized pattern.
This 4x4 pattern can be representet by a 32 bit variable.
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
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.)