Merge branch 'master' of ssh://repo.or.cz/srv/git/pachi
[pachi/nmclean.git] / pattern3.h
blobf456d5467f47f86c480370803abe473b94ef3cb2
1 #ifndef PACHI_PATTERN3_H
2 #define PACHI_PATTERN3_H
4 /* Fast matching of simple 3x3 patterns. */
6 #include "board.h"
8 /* (Note that this is completely independent from the general pattern
9 * matching infrastructure in pattern.[ch]. This is fast and simple.) */
11 struct board;
12 struct move;
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 */
21 /* XXX: See <board.h> for hash3_t typedef. */
23 struct pattern2p {
24 hash3_t pattern;
25 char value;
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];
38 /* Zobrist hashes for the various 3x3 points. */
39 /* [point][is_atari][color] */
40 hash_t p3hashes[8][2][S_MAX];
42 /* Source pattern encoding:
43 * X: black; O: white; .: empty; #: edge
44 * x: !black; o: !white; ?: any
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
50 * extra X: pattern valid only for one side;
51 * middle point ignored. */
53 void pattern3s_init(struct pattern3s *p, char src[][11], int src_n);
55 /* Compute pattern3 hash at local position. */
56 static hash3_t pattern3_hash(struct board *b, coord_t c);
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);
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]);
65 /* Reverse pattern to opposite color assignment. */
66 static hash3_t pattern3_reverse(hash3_t pat);
69 static inline hash3_t
70 pattern3_hash(struct board *b, coord_t c)
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;
93 static inline __attribute__((const)) hash_t
94 hash3_to_hash(hash3_t pat)
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];
101 return h;
104 static inline bool
105 pattern3_move_here(struct pattern3s *p, struct board *b, struct move *m)
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);
119 static inline hash3_t
120 pattern3_reverse(hash3_t pat)
122 /* Reverse color assignment - achieved by swapping odd and even bits */
123 return ((pat >> 1) & 0x5555) | ((pat & 0x5555) << 1) | (pat & 0xf0000);
126 #endif