From 0b04bccf70a1a5b3aa5927726a3d62c9168352bd Mon Sep 17 00:00:00 2001
From: Petr Baudis <pasky@ucw.cz>
Date: Sat, 23 Oct 2010 02:45:59 +0200
Subject: [PATCH] Pattern3: Use zobrist hash of the 3x3 area for indexing

---
 pattern3.c | 33 +++++++++++++++++++++++++++------
 pattern3.h | 29 ++++++++++++++++++++++-------
 2 files changed, 49 insertions(+), 13 deletions(-)

diff --git a/pattern3.c b/pattern3.c
index cf68fd0..1736421 100644
--- a/pattern3.c
+++ b/pattern3.c
@@ -11,12 +11,16 @@
 static void
 pattern_record(struct pattern3s *p, char *str, hash3_t pat, int fixed_color)
 {
-	hash3_t hpat = pat;
-	while (p->hash[hpat & pattern3_hash_mask].pattern != pat
-	       && p->hash[hpat & pattern3_hash_mask].value != 0)
-		hpat++;
-	p->hash[hpat & pattern3_hash_mask].pattern = pat;
-	p->hash[hpat & pattern3_hash_mask].value = fixed_color ? fixed_color : 3;
+	hash_t h = hash3_to_hash(pat);
+	while (p->hash[h & pattern3_hash_mask].pattern != pat
+	       && p->hash[h & pattern3_hash_mask].value != 0)
+		h++;
+#if 0
+	if (h != hash3_to_hash(pat) && p->hash[h & pattern3_hash_mask].pattern != pat)
+		fprintf(stderr, "collision of %06x: %llx(%x)\n", pat, hash3_to_hash(pat)&pattern3_hash_mask, p->hash[hash3_to_hash(pat)&pattern3_hash_mask].pattern);
+#endif
+	p->hash[h & pattern3_hash_mask].pattern = pat;
+	p->hash[h & pattern3_hash_mask].value = fixed_color ? fixed_color : 3;
 	//fprintf(stderr, "[%s] %04x %d\n", str, pat, fixed_color);
 }
 
@@ -249,3 +253,20 @@ pattern3s_init(struct pattern3s *p, char src[][11], int src_n)
 
 	patterns_gen(p, nsrc, src_n);
 }
+
+
+static __attribute__((constructor)) void
+p3hashes_init(void)
+{
+	/* tuned for 11482 collisions */
+	/* XXX: tune better */
+	hash_t h = 0x35373c;
+	for (int i = 0; i < 8; i++) {
+		for (int a = 0; a < 2; a++) {
+			p3hashes[i][a][S_NONE] = (h = h * 16803-7);
+			p3hashes[i][a][S_BLACK] = (h = h * 16805-2);
+			p3hashes[i][a][S_WHITE] = (h = h * 16807-11);
+			p3hashes[i][a][S_OFFBOARD] = (h = h * 16809+7);
+		}
+	}
+}
diff --git a/pattern3.h b/pattern3.h
index a76a647..8a1daf4 100644
--- a/pattern3.h
+++ b/pattern3.h
@@ -26,16 +26,19 @@ struct pattern2p {
 };
 
 struct pattern3s {
-	/* Right now, the hash is of just the right size, but this
-	 * is going to change very soon! */
 	/* In case of a collision, following hash entries are
-	 * used. value==0 indicated an unoccupied hash entry. */
+	 * used. value==0 indicates an unoccupied hash entry. */
+	/* The hash indices are zobrist hashes based on p3hashes. */
 #define pattern3_hash_bits 19
 #define pattern3_hash_size (1 << pattern3_hash_bits)
 #define pattern3_hash_mask (pattern3_hash_size - 1)
 	struct pattern2p hash[pattern3_hash_size];
 };
 
+/* Zobrist hashes for the various 3x3 points. */
+/* [point][is_atari][color] */
+hash_t p3hashes[8][2][S_MAX];
+
 /* Source pattern encoding:
  * X: black;  O: white;  .: empty;  #: edge
  * x: !black; o: !white; ?: any
@@ -87,6 +90,17 @@ pattern3_hash(struct board *b, coord_t c)
 	return pat;
 }
 
+static inline __attribute__((const)) hash_t
+hash3_to_hash(hash3_t pat)
+{
+	hash_t h = 0;
+	static const int ataribits[8] = { -1, 0, -1, 1, 2, -1, 3, -1 };
+	for (int i = 0; i < 8; i++) {
+		h ^= p3hashes[i][ataribits[i] >= 0 ? (pat >> (16 + ataribits[i])) & 1 : 0][(pat >> (i*2)) & 3];
+	}
+	return h;
+}
+
 static inline bool
 pattern3_move_here(struct pattern3s *p, struct board *b, struct move *m)
 {
@@ -95,10 +109,11 @@ pattern3_move_here(struct pattern3s *p, struct board *b, struct move *m)
 #else
 	hash3_t pat = pattern3_hash(b, m->coord);
 #endif
-	while (p->hash[pat & pattern3_hash_mask].pattern != pat
-	       && p->hash[pat & pattern3_hash_mask].value != 0)
-		pat++;
-	return (p->hash[pat & pattern3_hash_mask].value & m->color);
+	hash_t h = hash3_to_hash(pat);
+	while (p->hash[h & pattern3_hash_mask].pattern != pat
+	       && p->hash[h & pattern3_hash_mask].value != 0)
+		h++;
+	return (p->hash[h & pattern3_hash_mask].value & m->color);
 }
 
 static inline hash3_t
-- 
2.11.4.GIT