From 06f3ee1c56f1c47c6d9cd6bfca81e6635df0e497 Mon Sep 17 00:00:00 2001
From: Petr Baudis <pasky@ucw.cz>
Date: Fri, 3 Dec 2010 04:19:05 +0100
Subject: [PATCH] fbook: Deal with conflicts properly, make the hash size
 smaller

---
 fbook.c | 21 ++++++++++++++++++---
 fbook.h |  3 ++-
 gtp.c   | 12 ++++++++++--
 3 files changed, 30 insertions(+), 6 deletions(-)

diff --git a/fbook.c b/fbook.c
index dbe10ed..4731eeb 100644
--- a/fbook.c
+++ b/fbook.c
@@ -86,11 +86,26 @@ fbook_init(char *filename, struct board *b)
 		coord_t *c = str2coord(line, fbook->bsize);
 		for (int i = 0; i < 8; i++) {
 #if 0
-			fprintf(stderr, "%c %"PRIhash" (<%d> %s)\n",
-			        is_pass(fbook->moves[bs[i]->hash & fbook_hash_mask]) ? '+' : 'C',
+			char conflict = is_pass(fbook->moves[bs[i]->hash & fbook_hash_mask]) ? '+' : 'C';
+			if (conflict == 'C')
+				for (int j = 0; j < i; j++)
+					if (bs[i]->hash == bs[j]->hash)
+						conflict = '+';
+			if (conflict == 'C') {
+				hash_t hi = bs[i]->hash;
+				while (!is_pass(fbook->moves[hi & fbook_hash_mask]) && fbook->hashes[hi & fbook_hash_mask] != bs[i]->hash)
+					hi++;
+				if (fbook->hashes[hi & fbook_hash_mask] == bs[i]->hash)
+					hi = 'c';
+			}
+			fprintf(stderr, "%c %"PRIhash" (<%d> %s)\n", conflict,
 			        bs[i]->hash & fbook_hash_mask, i, linebuf);
 #endif
-			fbook->moves[bs[i]->hash & fbook_hash_mask] = *c;
+			hash_t hi = bs[i]->hash;
+			while (!is_pass(fbook->moves[hi & fbook_hash_mask]) && fbook->hashes[hi & fbook_hash_mask] != bs[i]->hash)
+				hi++;
+			fbook->moves[hi & fbook_hash_mask] = *c;
+			fbook->hashes[hi & fbook_hash_mask] = bs[i]->hash;
 		}
 		coord_done(c);
 	}
diff --git a/fbook.h b/fbook.h
index e344be5..734251a 100644
--- a/fbook.h
+++ b/fbook.h
@@ -12,10 +12,11 @@ struct fbook {
 	int bsize;
 	int handicap;
 
-#define fbook_hash_bits 19 // 4M w/ 32-bit coord_t
+#define fbook_hash_bits 16 // 1M w/ 32-bit coord_t
 #define fbook_hash_mask ((1 << fbook_hash_bits) - 1)
 	/* pass == no move in this position */
 	coord_t moves[1<<fbook_hash_bits];
+	hash_t hashes[1<<fbook_hash_bits];
 };
 
 struct fbook *fbook_init(char *filename, struct board *b);
diff --git a/gtp.c b/gtp.c
index 15de4ef..66b591c 100644
--- a/gtp.c
+++ b/gtp.c
@@ -279,10 +279,18 @@ gtp_parse(struct board *board, struct engine *engine, struct time_info *ti, char
 		if (board->fbook) {
 			/* We have an fbook, check if we cannot make
 			 * a move along it right away. */
-			coord_t cf = board->fbook->moves[board->hash & fbook_hash_mask];
+			hash_t hi = board->hash;
+			coord_t cf = pass;
+			while (!is_pass(board->fbook->moves[hi & fbook_hash_mask])) {
+				if (board->fbook->hashes[hi & fbook_hash_mask] == board->hash) {
+					cf = board->fbook->moves[hi & fbook_hash_mask];
+					break;
+				}
+				hi++;
+			}
 			if (!is_pass(cf)) {
 				if (DEBUGL(1))
-					fprintf(stderr, "fbook match\n");
+					fprintf(stderr, "fbook match %"PRIhash":%"PRIhash"\n", board->hash, board->hash & fbook_hash_mask);
 				c = coord_copy(cf);
 			} else {
 				/* No match, also prevent further fbook usage
-- 
2.11.4.GIT