[computer-go] State of the art of pattern matching

[Jacques Basaldúa]

Mark Boon wrote:

> Sorry, without a bit more explanation, the assembler code is very  
> hard to understand. What exactly does it do?

The first source code was just an example to see what kind of code
is generated. The second is useful, if you understand asm you should 
understand it. The board has 4 modes, as far as patterns are concerned.
So the following applies for each mode and for each possible mapping 
scheme. When 40 neighbors are used, (i.e. Manhattan distance 4) there 
are 81 possible situations (all the cells of a 9x9 board are different 
as far as board limits are concerned). On bigger boards, each cell maps 
one of the 81 possible 9x9 cells. The board system cannot play on less 
than 9x9. And for each of these 4x(maximum)81 (some board modes have 
smaller distance) the generator writes 2 functions: one for creating 
the mask/hash from scratch and an other to update all masks/hashes 
in the neighborhood of a new stone.


> Does it relate to a pattern? 

Yes the complete pattern is:

                +---+
                | 4 |
            +---+---+---+
            | 4 | 3 | 4 |
        +---+---+---+---+---+
        | 4 | 3 | 2 | 3 | 4 |
    +---+---+---+---+---+---+---+
    | 4 | 3 | 2 | 1 | 2 | 3 | 4 |
+---+---+---+---+---+---+---+---+---+
| 4 | 3 | 2 | 1 | · | 1 | 2 | 3 | 4 |
+---+---+---+---+---+---+---+---+---+
    | 4 | 3 | 2 | 1 | 2 | 3 | 4 |
    +---+---+---+---+---+---+---+
        | 4 | 3 | 2 | 3 | 4 |
        +---+---+---+---+---+
            | 4 | 3 | 4 |
            +---+---+---+
                | 4 |
                +---+

Justification of this shape:

1. It includes all standard nobi, iken tobi, niken tobi, kosumi, 
keima & ogeima relations (+ double iken tobi + double kosumi)
2. It detects if a pattern is at the 4-th line or the 4x4 corner 
(and below obviously). Less than that is too small.
The 4-th line is too different from the center. 
3. It is a nested structure, {dist12, dist12 + dist3} are both usable.
4. It has reasonable size for the information it contains.
5. The bit arrangement is optimized for 90 deg rotation.

Additionally, I keep urgency information for: normal, the pattern
shows up for the first time and urgency in a ko.


> Did you write a paper or post explaining this in more detail?

Not yet.


> Do I understand correctly that you generate this code automatically?

Yes. It would be a nightmare to write about 70K lines by hand and 
debugging would be hard as well. Although what the functions do is
simple enough to create a test that verifies 100% of the cases.
 

> You are talking about updating 40 hashes. Does it mean your patterns  
have fixed size? 

Yes. 3 sizes: Manhattan distance 2, 3 and 4


> In the 500 nanoseconds, how many patterns do you compare? 

That was updating (max) 40 hashes in the neighborhood of a newly 
placed stone. The precise number of hashes depends on the board
coordinate and the surrounding stones although that is achieved 
without a single conditional jump. (It is a very conservative 
estimation for approx 140 instructions in a jump free sequence. 
The typical case is probably more like half of that.) But, as 
mentioned, it does not include neither the board logic nor the
search that translates hash -> urgency.


> How about rotations and color inversions? 

In the slowest mode the pattern is rotated using macros like this 
one (that rotates a 40 neighbor pattern)

    asm
        mov edx, eax        // @jm
        mov eax, [edx + 8]  // jm.mask4
        rol eax, 8
        mov [edx + 8], eax  // jm.mask4

        mov eax, [edx + 4]  // jm.mask3
        shl eax, 6
        mov ecx, eax
        and eax, 0ffFFFFh
        rol ecx, 8
        or  al, cl
        mov [edx + 4], eax  // jm.mask3

        mov eax, [edx]      // jm.msk12
        mov ecx, eax
        shl eax, 4
        rol cl, 2
        mov al, cl
        mov ecx, eax
        shr ecx, 16
        and eax, 0ffF0FFh
        and ecx, 0000F00h
        or  eax, ecx
        mov [edx], eax      // jm.msk12
    end

and converted to canonical. Color inversion is automatic
because the pattern is own/opponent instead of black/white.

In the fastest mode, the hash table has x8 size and includes
the hashes of the rotated patterns.


Jacques.