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