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: ignore middle point, 2 bits per intersection (color)
  15  * plus 1 bit per each direct neighbor => 8*2 + 4 bits. Bitmap point order:
  16  * 7 6 5    b
  17  * 4   3  a   9
  18  * 2 1 0    8   */
  19 /* Value bit 0: black pattern; bit 1: white pattern */
  20
  21 /* XXX: See <board.h> for hash3_t typedef. */
  22
  23 struct pattern2p {
  24         hash3_t pattern;
  25         char value;
  26 };
  27
  28 struct pattern3s {
  29         /* In case of a collision, following hash entries are
  30          * used. value==0 indicates an unoccupied hash entry. */
  31         /* The hash indices are zobrist hashes based on p3hashes. */
  32 #define pattern3_hash_bits 19
  33 #define pattern3_hash_size (1 << pattern3_hash_bits)
  34 #define pattern3_hash_mask (pattern3_hash_size - 1)
  35         struct pattern2p hash[pattern3_hash_size];
  36 };
  37
  38 /* Zobrist hashes for the various 3x3 points. */
  39 /* [point][is_atari][color] */
  40 hash_t p3hashes[8][2][S_MAX];
  41
  42 /* Source pattern encoding:
  43  * X: black;  O: white;  .: empty;  #: edge
  44  * x: !black; o: !white; ?: any
  45  *
  46  * |/=: black in atari/anything but black in atari
  47  * @/0: white in atari
  48  * Y/y: black notin atari; Q/q: white notin atari
  49  *
  50  * extra X: pattern valid only for one side;
  51  * middle point ignored. */
  52
  53 void pattern3s_init(struct pattern3s *p, char src[][11], int src_n);
  54
  55 /* Compute pattern3 hash at local position. */
  56 static hash3_t pattern3_hash(struct board *b, coord_t c);
  57
  58 /* Check if we match any 3x3 pattern centered on given move. */
  59 static bool pattern3_move_here(struct pattern3s *p, struct board *b, struct move *m);
  60
  61 /* Generate all transpositions of given pattern, stored in an
  62  * hash3_t[8] array. */
  63 void pattern3_transpose(hash3_t pat, hash3_t (*transp)[8]);
  64
  65 /* Reverse pattern to opposite color assignment. */
  66 static hash3_t pattern3_reverse(hash3_t pat);
  67
  68
  69 static inline hash3_t
  70 pattern3_hash(struct board *b, coord_t c)
  71 {
  72         hash3_t pat = 0;
  73         int x = coord_x(c, b), y = coord_y(c, b);
  74         /* Stone info. */
  75         pat |= (board_atxy(b, x - 1, y - 1) << 14)
  76                 | (board_atxy(b, x, y - 1) << 12)
  77                 | (board_atxy(b, x + 1, y - 1) << 10);
  78         pat |= (board_atxy(b, x - 1, y) << 8)
  79                 | (board_atxy(b, x + 1, y) << 6);
  80         pat |= (board_atxy(b, x - 1, y + 1) << 4)
  81                 | (board_atxy(b, x, y + 1) << 2)
  82                 | (board_atxy(b, x + 1, y + 1));
  83         /* Atari info. */
  84 #define atari_atxy(b, x, y) (group_atxy(b, x, y) && board_group_info(b, group_atxy(b, x, y)).libs == 1)
  85         pat |= (atari_atxy(b, x, y - 1) << 19);
  86         pat |= (atari_atxy(b, x - 1, y) << 18)
  87                 | (atari_atxy(b, x + 1, y) << 17);
  88         pat |= (atari_atxy(b, x, y + 1) << 16);
  89 #undef atari_atxy
  90         return pat;
  91 }
  92
  93 static inline __attribute__((const)) hash_t
  94 hash3_to_hash(hash3_t pat)
  95 {
  96         hash_t h = 0;
  97         static const int ataribits[8] = { -1, 0, -1, 1, 2, -1, 3, -1 };
  98         for (int i = 0; i < 8; i++) {
  99                 h ^= p3hashes[i][ataribits[i] >= 0 ? (pat >> (16 + ataribits[i])) & 1 : 0][(pat >> (i*2)) & 3];
 100         }
 101         return h;
 102 }
 103
 104 static inline bool
 105 pattern3_move_here(struct pattern3s *p, struct board *b, struct move *m)
 106 {
 107 #ifdef BOARD_PAT3
 108         hash3_t pat = b->pat3[m->coord];
 109 #else
 110         hash3_t pat = pattern3_hash(b, m->coord);
 111 #endif
 112         hash_t h = hash3_to_hash(pat);
 113         while (p->hash[h & pattern3_hash_mask].pattern != pat
 114                && p->hash[h & pattern3_hash_mask].value != 0)
 115                 h++;
 116         return (p->hash[h & pattern3_hash_mask].value & m->color);
 117 }
 118
 119 static inline hash3_t
 120 pattern3_reverse(hash3_t pat)
 121 {
 122         /* Reverse color assignment - achieved by swapping odd and even bits */
 123         return ((pat >> 1) & 0x5555) | ((pat & 0x5555) << 1) | (pat & 0xf0000);
 124 }
 125
 126 #endif