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 struct pattern3s {
  15         /* Hashtable: 2*8 bits (ignore middle point, 2 bits per intersection) */
  16         /* Value: 0: no pattern, 1: black pattern,
  17          * 2: white pattern, 3: both patterns */
  18         char hash[65536];
  19 };
  20
  21 /* XXX: See <board.h> for hash3_t typedef. */
  22
  23 /* Source pattern encoding:
  24  * X: black;  O: white;  .: empty;  #: edge
  25  * x: !black; o: !white; ?: any
  26  *
  27  * extra X: pattern valid only for one side;
  28  * middle point ignored. */
  29
  30 void pattern3s_init(struct pattern3s *p, char src[][11], int src_n);
  31
  32 /* Compute pattern3 hash at local position. */
  33 static hash3_t pattern3_hash(struct board *b, coord_t c);
  34
  35 /* Check if we match any 3x3 pattern centered on given move. */
  36 static bool pattern3_move_here(struct pattern3s *p, struct board *b, struct move *m);
  37
  38 /* Generate all transpositions of given pattern, stored in an
  39  * hash3_t[8] array. */
  40 void pattern3_transpose(hash3_t pat, hash3_t (*transp)[8]);
  41
  42 /* Reverse pattern to opposite color assignment. */
  43 static hash3_t pattern3_reverse(hash3_t pat);
  44
  45
  46 static inline hash3_t
  47 pattern3_hash(struct board *b, coord_t c)
  48 {
  49         hash3_t pat = 0;
  50         int x = coord_x(c, b), y = coord_y(c, b);
  51         pat |= (board_atxy(b, x - 1, y - 1) << 14)
  52                 | (board_atxy(b, x, y - 1) << 12)
  53                 | (board_atxy(b, x + 1, y - 1) << 10);
  54         pat |= (board_atxy(b, x - 1, y) << 8)
  55                 | (board_atxy(b, x + 1, y) << 6);
  56         pat |= (board_atxy(b, x - 1, y + 1) << 4)
  57                 | (board_atxy(b, x, y + 1) << 2)
  58                 | (board_atxy(b, x + 1, y + 1));
  59         return pat;
  60 }
  61
  62 static inline bool
  63 pattern3_move_here(struct pattern3s *p, struct board *b, struct move *m)
  64 {
  65 #ifdef BOARD_PAT3
  66         hash3_t pat = b->pat3[m->coord];
  67 #else
  68         hash3_t pat = pattern3_hash(b, m->coord);
  69 #endif
  70         return (p->hash[pat] & m->color);
  71 }
  72
  73 static inline hash3_t
  74 pattern3_reverse(hash3_t pat)
  75 {
  76         /* Reverse color assignment - achieved by swapping odd and even bits */
  77         return ((pat >> 1) & 0x5555) | ((pat & 0x5555) << 1);
  78 }
  79
  80 #endif