pattern3.h

   1 #ifndef ZZGO_PATTERN3_H
   2 #define ZZGO_PATTERN3_H
   3
   4 /* Fast matching of simple 3x3 patterns. */
   5
   6 #include "board.h"
   7
   8 /* (Note that this is completely independent from the general pattern
   9  * matching infrastructure in pattern.[ch]. This is fast and simple.) */
  10
  11 struct board;
  12 struct move;
  13
  14 /* hash3_t pattern: 8*2 bits
  15  * (ignore middle point, 2 bits (color) per intersection) */
  16 /* Value bit 0: black pattern; bit 1: white pattern */
  17
  18 /* XXX: See <board.h> for hash3_t typedef. */
  19
  20 struct pattern2p {
  21         hash3_t pattern;
  22         char value;
  23 };
  24
  25 struct pattern3s {
  26         /* Right now, the hash is of just the right size, but this
  27          * is going to change very soon! */
  28         /* In case of a collision, following hash entries are
  29          * used. value==0 indicated an unoccupied hash entry. */
  30 #define pattern3_hash_bits 16
  31 #define pattern3_hash_size (1 << pattern3_hash_bits)
  32 #define pattern3_hash_mask (pattern3_hash_size - 1)
  33         struct pattern2p hash[pattern3_hash_size];
  34 };
  35
  36 /* Source pattern encoding:
  37  * X: black;  O: white;  .: empty;  #: edge
  38  * x: !black; o: !white; ?: any
  39  *
  40  * extra X: pattern valid only for one side;
  41  * middle point ignored. */
  42
  43 void pattern3s_init(struct pattern3s *p, char src[][11], int src_n);
  44
  45 /* Compute pattern3 hash at local position. */
  46 static hash3_t pattern3_hash(struct board *b, coord_t c);
  47
  48 /* Check if we match any 3x3 pattern centered on given move. */
  49 static bool pattern3_move_here(struct pattern3s *p, struct board *b, struct move *m);
  50
  51 /* Generate all transpositions of given pattern, stored in an
  52  * hash3_t[8] array. */
  53 void pattern3_transpose(hash3_t pat, hash3_t (*transp)[8]);
  54
  55 /* Reverse pattern to opposite color assignment. */
  56 static hash3_t pattern3_reverse(hash3_t pat);
  57
  58
  59 static inline hash3_t
  60 pattern3_hash(struct board *b, coord_t c)
  61 {
  62         hash3_t pat = 0;
  63         int x = coord_x(c, b), y = coord_y(c, b);
  64         pat |= (board_atxy(b, x - 1, y - 1) << 14)
  65                 | (board_atxy(b, x, y - 1) << 12)
  66                 | (board_atxy(b, x + 1, y - 1) << 10);
  67         pat |= (board_atxy(b, x - 1, y) << 8)
  68                 | (board_atxy(b, x + 1, y) << 6);
  69         pat |= (board_atxy(b, x - 1, y + 1) << 4)
  70                 | (board_atxy(b, x, y + 1) << 2)
  71                 | (board_atxy(b, x + 1, y + 1));
  72         return pat;
  73 }
  74
  75 static inline bool
  76 pattern3_move_here(struct pattern3s *p, struct board *b, struct move *m)
  77 {
  78 #ifdef BOARD_PAT3
  79         hash3_t pat = b->pat3[m->coord];
  80 #else
  81         hash3_t pat = pattern3_hash(b, m->coord);
  82 #endif
  83         while (p->hash[pat & pattern3_hash_mask].pattern != pat
  84                && p->hash[pat & pattern3_hash_mask].value != 0)
  85                 pat++;
  86         return (p->hash[pat & pattern3_hash_mask].value & m->color);
  87 }
  88
  89 static inline hash3_t
  90 pattern3_reverse(hash3_t pat)
  91 {
  92         /* Reverse color assignment - achieved by swapping odd and even bits */
  93         return ((pat >> 1) & 0x5555) | ((pat & 0x5555) << 1);
  94 }
  95
  96 #endif