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


GNU Go Documentation

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

12.14 Implementation Details

  1. An entry in the pattern header states whether the anchor is an `X' or an `O'. This helps performance, since all transformations can be rejected at once if the anchor stone does not match. (Ideally, we could just define that the anchor is always `O' or always `X', but some patterns contain no `O' and some contain no `X'.)

  2. The pattern header contains the size of the pattern (ie the co-ordinates of the top left and bottom right elements) relative to the anchor. This allows the pattern can be rejected quickly if there is not room for the pattern to fit around the anchor stone in a given orientation (ie it is too near the edge of the board). The bounding box information must first be transformed like the elements before it can be tested, and after transforming, we need to work out where the top-left and bottom-right corners are.

  3. The edge constraints are implemented by notionally padding the pattern with rows or columns of `?' until it is exactly 19 (or whatever the current board size is) elements wide or high. Then the pattern is quickly rejected by (ii) above if it is not at the edge. So the example pattern above is compiled as if it was written

     
    "example"
    .OO????????????????
    *XX????????????????
    o??????????????????
    :8,80
    
    

  4. The elements in a pattern are sorted so that non-space elements are checked before space elements. It is hoped that, for most of the game, more squares are empty, and so the pattern can be more quickly rejected doing it this way.

  5. The actual tests are performed using an 'and-compare' sequence. Each board position is a 2-bit quantity. %00 for empty, %01 for `O', %10 for `X'. We can test for an exact match by and-ing with %11 (no-op), then comparing with 0, 1 or 2. The test for `o' is the same as a test for 'not-X', ie not %10. So and with %01 should give 0 if it matches. Similarly `x' is a test that bit 0 is not set.


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

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