www.delorie.com/gnu/docs/gnugo/gnugo_157.html   search  
 
Buy GNU books!


GNU Go Documentation

[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Index] [ ? ]

12.15 The "Grid" Optimization

The comparisons between pattern and board are performed as 2-bit bitwise operations. Therefore they can be performed in parallel, 16-at-a-time on a 32-bit machine.

Suppose the board is layed out as follows :

 
 .X.O....OO
 XXXXO.....
 .X..OOOOOO
 X.X.......
 ....X...O.

which is internally stored internally in a 2d array (binary)

 
 00 10 00 01 00 00 00 00 01 01
 10 10 10 10 01 00 00 00 00 00
 00 10 00 00 01 01 01 01 01 01
 10 00 10 00 00 00 00 00 00 00
 00 00 00 00 10 00 00 00 01 00

we can compile this to a composite array in which each element stores the state of a 4x4 grid of squares :

 
 ????????  ????????  ???????? ...
 ??001000  00100001  10000100
 ??101010  10101010  10101001
 ??001000  00100000  10000001

 ??001000  00100001  ...
 ??101010  10101010
 ??001000  00100000
 ??001000  10001000 

...

 ??100010  ...
 ??000000
 ????????
 ????????

Where '??' is off the board.

We can store these 32-bit composites in a 2d merged-board array, substituting the illegal value %11 for '??'.

Similarly, for each pattern, mkpat produces appropriate 32-bit and-value masks for the pattern elements near the anchor. It is a simple matter to test the pattern with a similar test to (5) above, but for 32-bits at a time.


  webmaster     delorie software   privacy  
  Copyright 2003   by The Free Software Foundation     Updated Jun 2003