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

[Mark Boon]

Jacques,

Yes, I do an incremental update so the board-size should be almost  
irrelevant. I'm not sure why I see any difference between 9x9 and  
19x19 but it may have to do with the fact that the edge cuts a lot of  
pattern seach short.


On 27-mrt-08, at 10:13, Santiago Basaldúa wrote:

> Mark Boon wrote:
>
>> What I have now takes 10-15 microseconds on a 2Ghz Intel computer  
>> to  find all the patterns on a board (on average for 9x9, for  
>> 19x19 it's  more like 15-20 usec)
>
>> From your difference between 9x9 and 19x19 I assume that you are  
>> updating
> the patterns of the cells after a stone was placed, (else the  
> difference should be 361/81 times) not a computation from scratch.  
> I make this sure so that we compare apples to apples. As far as the  
> patterns computing is
> concerned, (i.e. excluding the board part verifying captures, etc.)  
> for
> a pattern of 40 neighbors I get times easily below 500 nanoseconds  
> (even on an old P4 3.4 GHz) for updating 40 hashes. I explained  
> that about
> June last year, when I wrote it. Since it passed my tests (June 07)  
> I have never changed a character in the code that writes the 67090 asm
> lines. It is just a black box, that works 100%. Each board cell has  
> an updating function that knows where the board limits are, the  
> resulting
> code (for hash 32 bit mode) is something like an endless:
>
>           lea     ebx, [edx + ecx*2 - SizeOf_bccCell]
>           mov     eax, 0967f6762h
>           bt      dword ptr [ebx], bidx_StoneBit
>           cmovc   eax, esi
>           xor     [ebx + 4], eax
>           lea     ebx, [edx + ecx*2]
>           mov     eax, 0d83b6518h
>           bt      dword ptr [ebx], bidx_StoneBit
>           cmovc   eax, esi
>           xor     [ebx + 4], eax
>           lea     ebx, [edx + ecx*2 + SizeOf_bccCell]
>           mov     eax, 0121001f7h
>           bt      dword ptr [ebx], bidx_StoneBit
>           cmovc   eax, esi
>           xor     [ebx + 4], eax
>

Sorry, without a bit more explanation, the assembler code is very  
hard to understand. What exactly does it do? Does it relate to a  
pattern? Did you write a paper or post explaining this in more detail?

Do I understand correctly that you generate this code automatically?  
I believe David Fotland does something similiarly. I have thought  
about that but I wasn't sure if that was really much faster.

You are talking about updating 40 hashes. Does it mean your patterns  
have fixed size? In the 500 nanoseconds, how many patterns do you  
compare? One? A thousand? A million? How about rotations and color  
inversions? To make it really an apples to apples comparison I'd like  
to make sure we're talking about the same thing.

Mark