[computer-go] Rotate the dog or the tail?

[David Fotland]

Spelling error.  Decision tree.  Just a bunch of nested if statements.

I don't do any shifting.  My patterns are 8x8.  I keep 32 copies of the
board bitmap (4 orientations, and 8 shifts).  I select an 8x8 pattern from
these board to match by selecting the proper bytes, in the proper order.  I
handle all 8 orientations because top to bottom reversal is just selecting
the bytes in a different order.

When a stone is added or removed from the board I have to set or clear 32
bits in the board bitmaps.  Very fast.

The pattern database is hashed to 8 bits, with a linked list of patterns on
each of 256 chains.  I have don't cares, so I don't want a big hash since
there is too much duplication.  The 8-bit hash gets me about 100x speedup
over a linear search, which is enough.  I chose the 8 bits in the patterns
that are least frequently don't care for the hash.  I have about 2000
patterns.

David

unsigned char bdw[4][8][4][32];  /* bit vectors for the board 19 + 7 + 6
(for overlap)  (white, empty, black bits) */
unsigned char bde[4][8][4][32];  /* 4 orientations.  corner matches left */
unsigned char bdb[4][8][4][32];  /* edge rows 7-25 across top filled with
off board */
								 /* left
edge of board is one byte in from left */
								 /* right
edge has only 5 points off board, so don't try to match too close */
/* 0 - bits left to right (bytes top to bottom) */
/* 1 - bits right to left (bytes top to bottom) */
/* 2 - bits top to bottom (bytes left to right) */
/* 3 - bits bottom to top (bytes left to right) */
/* 4 orient, 8 shifts, 4 wide, 32 tall */

> -----Original Message-----
> From: computer-go-bounces at computer-go.org 
> [mailto:computer-go-bounces at computer-go.org] On Behalf Of Chrilly
> Sent: Saturday, June 17, 2006 9:47 PM
> To: computer-go
> Subject: Re: [computer-go] Rotate the dog or the tail?
> 
> 
> 
> 
> Many faces spends very little time on pattern matching, 
> perhaps 2 percent, since it is only used for full board move 
> generation.  Tactical move generation is all hand crafted C 
> decagons trees.
> 
> What is a decagons tree?
> 
> When the pattern code was written the whole program still had 
> to fit in 600 KB to run under DOS, before Windows 95 existed 
> :(  So memory usage for patterns was critical.  That's why 
> the joseki database was encoded in about 10 bits per move.
> 
> It was even worse. One had 600KB, but a single data entity 
> had to be smaller 
> than 64KB.  There was no cache, no super-pipeline.... The 
> rules of the 
> programming game were different.
> I would also not change a running pattern-code, because it is 
> a lot of work 
> and any change introduces new bugs. But if one designs from 
> scratch one 
> should start from todays hardware resources.
> 
> I don't lose any performance for being memory efficient.  It 
> just means keeping 8 copies of the board bitmap.  Updating 
> the board bitmap when a move is made takes no time.
> 
> But then you have to build up the pattern-area around a point 
> from these 
> bitmaps.
> Something like:
> Shft=ShiftValue[point];
> Pattern=((BitMap[BitVectorIndex[point]]>>Shft)&PATTERNMSK) |(( 
> (BitMap[BitVectorIndex[point+ROW_OFFSET]>>Shift)&PATTERNMSK)<<
> ROW1_SHFT).....
> 
> 
> Mark Boon did a different approach. He maintained for every 
> point the 3x25 
> area. In this case updating the info is not for free. One saves the 
> operation above - unless there is a clever trick to avoid this.
> 
> Chrilly
> 
> _______________________________________________
> computer-go mailing list
> computer-go at computer-go.org 
> http://www.computer-go.org/mailman/listinfo/computer-go/
>