New optional fast_alloc mode, allocating all nodes at once. See tree.h for overview.
[pachi.git] / pattern3.h
blob6f236b62fa1063eb8e239adc142150330df8ff76
1 #ifndef ZZGO_PATTERN3_H
2 #define ZZGO_PATTERN3_H
4 /* Fast matching of simple 3x3 patterns. */
6 #include "board.h"
7 #include "tactics.h"
9 /* (Note that this is completely independent from the general pattern
10 * matching infrastructure in pattern.[ch]. This is fast and simple.) */
12 struct board;
13 struct move;
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];
22 /* Source pattern encoding:
23 * X: black; O: white; .: empty; #: edge
24 * x: !black; o: !white; ?: any
26 * extra X: pattern valid only for one side;
27 * middle point ignored. */
29 void pattern3s_init(struct pattern3s *p, char src[][11], int src_n);
31 /* Compute pattern3 hash at local position. */
32 static int pattern3_hash(struct board *b, coord_t c);
34 /* Check if we match any pattern centered on given move; includes
35 * self-atari test. */
36 static bool test_pattern3_here(struct pattern3s *p, struct board *b, struct move *m);
38 /* Generate all transpositions of given pattern, stored in an
39 * int[8] array. */
40 void pattern3_transpose(int pat, int (*transp)[8]);
42 /* Reverse pattern to opposite color assignment. */
43 static int pattern3_reverse(int pat);
46 static inline int
47 pattern3_hash(struct board *b, coord_t c)
49 int 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;
62 /* TODO: Make use of the incremental spatial matching infrastructure
63 * in board.h? */
64 static inline bool
65 test_pattern3_here(struct pattern3s *p, struct board *b, struct move *m)
67 #ifdef BOARD_PAT3
68 int pat = b->pat3[m->coord];
69 #else
70 int pat = pattern3_hash(b, m->coord);
71 #endif
72 //fprintf(stderr, "(%d,%d) hashtable[%04x] = %d\n", x, y, pat, p->hash[pat]);
73 return (p->hash[pat] & m->color) && !is_bad_selfatari(b, m->color, m->coord);
76 static inline int
77 pattern3_reverse(int pat)
79 /* Reverse color assignment - achieved by swapping odd and even bits */
80 return ((pat >> 1) & 0x5555) | ((pat & 0x5555) << 1);
83 #endif