Hash collisions

9 files changed, 95 insertions, 80 deletions

diff --git a/Makefile b/Makefile
index 82b04c1..3ed8067 100644
--- a/Makefile
+++ b/Makefile
@@ -1,9 +1,9 @@
 IDIR=include
 DEFINES=-DDETERMINISTIC
-CFLAGS=-O3 -Wall -Wextra -Wpedantic -std=c99 -D_DEFAULT_SOURCE $(DEFINES) -I$(IDIR)
+CFLAGS=-g -Wall -Wextra -Wpedantic -std=c99 -D_DEFAULT_SOURCE $(DEFINES) -I$(IDIR)
 LIBS=
 
-SRCS=include/tak.c include/xorshift64.c include/negamax.c include/weights.c include/cnn1986.c include/lcdlib.c include/cnn1986_treap_cache.c
+SRCS=include/tak.c include/xorshift64.c include/negamax.c include/weights.c include/cnn1986.c include/lcdlib.c include/cnn1986_cache.c
 OBJS=$(SRCS:.c=.o)
 
 BUILDROOT_DIR=buildroot-2020.11.1
diff --git a/include/cnn1986_cache.c b/include/cnn1986_cache.c
index d9545ac..692920a 100644
--- a/include/cnn1986_cache.c
+++ b/include/cnn1986_cache.c
@@ -4,9 +4,11 @@
 #define DATA_COUNT_SHIFT (DATA_STONE_SHIFT+2)
 #define COLOUR_MASK      0x3F // 0b00111111
 
-uint32_t cnn1986_num_cached, cnn1986_max_num_cached;
+uint32_t cnn1986_num_cached, cnn1986_max_num_cached = 1000000;
 node_t *head = NULL, *tail = NULL;
 
+int cnn1986_cache_init(void) { return EXIT_SUCCESS; }
+
 void cnn1986_cache_free(void) {
 	node_t *c = head, *n;
 	while (c) {
@@ -18,37 +20,22 @@ void cnn1986_cache_free(void) {
 	tail = NULL;
 }
 
-int cnn1986_cache_seek(float *out_result) {
+int cnn1986_cache_seek(const uint64_t key[4],
+											 float *out_result) {
 	node_t *c = head;
-
-	if (c == NULL) return EXIT_FAILURE;
-
-	uint8_t comp_data[25], fail;
-	for (int k=0; k<25; k++) {
-		comp_data[k] = (colours[k] & COLOUR_MASK)
-			| (STONE_AT(k) << DATA_STONE_SHIFT)
-			| (COUNT_AT(k) << DATA_COUNT_SHIFT);
-	}
-
-	// We've checked c = head already, so uncoditionally test it
-	do {
-		// Compare
-		fail = 0;
-		if (c->black_count == black_count && c->white_count == white_count) {
-			for (int k=0; k<25; k++) {
-				if (comp_data[k] != c->data[k]) {
-					fail = 1;
-					break;
-				}
+	while (c != NULL) {
+		// Either seek next or move to front and return
+		uint8_t fail = 0;
+		for (int k=0; k<4; k++) {
+			if (c->key[k] != key[k]) {
+				fail = 1; break;
 			}
-		} else { fail = 1; }
+		}
 
-		// Either seek next or move to front and return
 		if (fail) {
 			c = c->next;
 		} else {
 			*out_result = c->result;
-
 			// Move to front
 			if (c != head) {
 				if (tail == c) tail=c->prev;
@@ -59,16 +46,14 @@ int cnn1986_cache_seek(float *out_result) {
 				head->prev = c;
 				head = c;
 			}
-
 			return EXIT_SUCCESS;
 		}
-	} while (c);
-
+	}
 	// Failed to find it
 	return EXIT_FAILURE;
 }
 
-int cnn1986_cache_insert(float in_result) {
+int cnn1986_cache_insert(const uint64_t key[4], float in_result) {
 	node_t *new = malloc(sizeof(node_t));
 	if (new == NULL) return EXIT_FAILURE;
 	// TODO: check errno
@@ -76,14 +61,8 @@ int cnn1986_cache_insert(float in_result) {
 	new->next = head;
 	if (head) head->prev = new;
 	head = new;
+	for (int k=0; k<4; k++) new->key[k] = key[k];
 	new->result = in_result;
-	new->white_count = white_count;
-	new->black_count = black_count;
-	for (int k=0; k<25; k++) {
-		new->data[k] = (colours[k] & COLOUR_MASK)
-			| (STONE_AT(k) << DATA_STONE_SHIFT)
-			| (COUNT_AT(k) << DATA_COUNT_SHIFT);
-	}
 	if (cnn1986_num_cached == 0) tail = new;
 	cnn1986_num_cached++;
 
diff --git a/include/cnn1986_cache.h b/include/cnn1986_cache.h
index 8d82ee9..14a894d 100644
--- a/include/cnn1986_cache.h
+++ b/include/cnn1986_cache.h
@@ -1,18 +1,19 @@
 #include <stdlib.h>
 #include <tak.h>
 
-#define MAX_NUM_CACHED 123
-
 extern uint32_t cnn1986_num_cached, cnn1986_max_num_cached;
 
 typedef struct node_s {
 	struct node_s *next, *prev;
-	uint16_t data[25], white_count, black_count;
+	uint64_t key[4];
 	float result;
 } node_t;
 
 int cnn1986_cache_init(void);
 void cnn1986_cache_free(void);
 
-int cnn1986_cache_seek(float *out_result);
-int cnn1986_cache_insert(float in_result);
+int cnn1986_cache_seek(const uint64_t key[4],
+											 float *out_result);
+
+int cnn1986_cache_insert(const uint64_t key[4],
+												 const float in_result);
diff --git a/include/cnn1986_treap_cache.h b/include/cnn1986_treap_cache.h
index 92208b2..20b2fbc 100644
--- a/include/cnn1986_treap_cache.h
+++ b/include/cnn1986_treap_cache.h
@@ -8,5 +8,10 @@ extern uint32_t cnn1986_num_cached;
 int cnn1986_cache_init(void);
 void cnn1986_cache_free(void);
 
-int cnn1986_cache_seek(const uint64_t key, float *out_result);
-int cnn1986_cache_insert(const uint64_t key, const float in_result);
+int cnn1986_cache_seek(const uint64_t key_lo,
+											 const uint64_t key_hi,
+											 float *out_result);
+
+int cnn1986_cache_insert(const uint64_t key_lo,
+												 const uint64_t key_hi,
+												 const float in_result);
diff --git a/include/negamax.c b/include/negamax.c
index e1c2991..3e57165 100644
--- a/include/negamax.c
+++ b/include/negamax.c
@@ -8,44 +8,62 @@ const float infty = 3.0;
 char negamax_ptn[9];
 uint8_t negamax_search_depth = 3;
 
+uint32_t cache_fails = 0;
+
 // ===================================================================
 // Zobrist hashing
 // ===================================================================
 
-uint64_t *zobrist = NULL;
+uint64_t *zobrist[4];
+uint64_t *zobrist_empty[4];
 
 static int negamax_init_zobrist(void) {
-	if (zobrist != NULL) return EXIT_FAILURE;
-	zobrist = malloc(sizeof(uint64_t)*board_size*board_size*16*3*2);
-	for (int k=0; k<board_size*board_size*16*3*2; k++) {
-		XORSHIFT64;
-		zobrist[k] = RANDOM64;
+	for (int k=0; k<4; k++) {
+		if (zobrist[k] != NULL) return EXIT_FAILURE;
+		if (zobrist_empty[k] != NULL) return EXIT_FAILURE;
 	}
+
+	for (int j=0; j<4; j++) {
+		zobrist[j] = malloc(sizeof(uint64_t)*board_size*board_size*15*3*2);
+		zobrist_empty[j] = malloc(sizeof(uint64_t)*board_size*board_size);
+		// TODO: trap errno
+		for (int k=0; k<board_size*board_size*15*3*2; k++) {
+			XORSHIFT64;
+			zobrist[j][k] = RANDOM64;
+		}
+		for (int k=0; k<board_size*board_size; k++) {
+			XORSHIFT64;
+			zobrist_empty[j][k] = RANDOM64;
+		}
+	}
+
 	return EXIT_SUCCESS;
 }
 
 static void negamax_free_zobrist(void) {
-	if (zobrist != NULL) {
-		free(zobrist);
-		zobrist = NULL;
+	for (int k=0; k<4; k++) {
+		if (zobrist[k] != NULL) {
+			free(zobrist[k]);
+			zobrist[k] = NULL;
+		}
 	}
 }
 
-uint64_t negamax_compute_zobrist(void) {
-	uint64_t result = 0;
+void negamax_compute_zobrist(uint64_t *hash) {
+	for (int k=0; k<4; k++) hash[k] = 0;
 	for (uint8_t l=0; l<board_size*board_size; l++) {
 		const uint8_t count = COUNT_AT(l);
 		if (count) {
+			const enum STONE_VARIANT s = STONE_AT(l);
 			colour_stack_t c = colours[l];
-			enum STONE_VARIANT s = STONE_AT(l);
 			for (uint8_t h=0; h<count; h++) {
-				result ^= zobrist[l*16*2*3 + h*3*2 + (c&1)*3 + s];
-				s = STONE_FLAT;
+				for (int k=0; k<4; k++) {
+					hash[k] ^= zobrist[k][l*16*3*2 + h*3*2 + (c&1)*3 + s];
+				}
 				c >>= 1;
 			}
 		}
 	}
-	return result;
 }
 
 // ===================================================================
@@ -126,9 +144,15 @@ static enum WIN_TYPE w;
 float negamax(const uint8_t cur_depth, float alpha, float beta,
 							const float colour) {
 
-	uint64_t hash = negamax_compute_zobrist();
+	uint64_t hash[4];
+	negamax_compute_zobrist(hash);
 
-	if (cnn1986_cache_seek(hash, &alpha) == EXIT_FAILURE) {
+	float stored_alpha;
+	int lookup = cnn1986_cache_seek(hash, &stored_alpha);
+
+	/*
+	 * if (cnn1986_cache_seek(hash, &alpha) == EXIT_FAILURE) {
+	 */
 		const uint8_t black = (ply & 1),
 			material = (black) ? black_count : white_count,
 			flat = material & 127,
@@ -323,10 +347,17 @@ float negamax(const uint8_t cur_depth, float alpha, float beta,
 				}
 				negamax_display_progress(cur_depth);
 			}
-		}
+		/*
+		 * }
+		 */
 		// Insert into the cache
-		cnn1986_cache_insert(hash, alpha);
 	}
+		if (lookup == EXIT_FAILURE)
+			cnn1986_cache_insert(hash, alpha);
+		else {
+			if (stored_alpha != alpha)
+				cache_fails++;
+		}
 	return alpha;
 }
 
@@ -336,6 +367,9 @@ negamax_generate(void) {
 	// values are wins
 	const float safe_infty = infty + 1;
 
+
+	cache_fails=0;
+
 	cnn1986_cache_init();
 	float result = negamax(0, -safe_infty, safe_infty, (ply&1)?1.0:-1.0);
 	cnn1986_cache_free();
diff --git a/include/negamax.h b/include/negamax.h
index d00780d..52a8fd2 100644
--- a/include/negamax.h
+++ b/include/negamax.h
@@ -2,15 +2,16 @@
 #include <tak.h>
 #include <xorshift64.h>
 #include <cnn1986.h>
-#include <cnn1986_treap_cache.h>
+#include <cnn1986_cache.h>
 
 extern const float infty;
 extern char negamax_ptn[9];
 extern uint8_t negamax_search_depth;
+extern uint32_t cache_fails;
 extern inline void negamax_display_progress(const uint8_t);
 
 void negamax_init(const uint8_t new_board_size);
-uint64_t negamax_compute_zobrist(void);
+void negamax_compute_zobrist(uint64_t hash[4]);
 
 // Do negamax to depth negamax_search_depth and return PTN of best move
 // in negamax_ptn, along with its value as the return. The
diff --git a/include/xorshift64.c b/include/xorshift64.c
index 04d5cfe..516218a 100644
--- a/include/xorshift64.c
+++ b/include/xorshift64.c
@@ -1,3 +1,3 @@
 #include "xorshift64.h"
 
-uint64_t xors = (uint64_t)0xFEEDCAFEF00DDDDD;
+uint64_t xors = (uint64_t)0xBF58476D1CE4E5B9;
diff --git a/include/xorshift64.h b/include/xorshift64.h
index ee41abc..62a0a4e 100644
--- a/include/xorshift64.h
+++ b/include/xorshift64.h
@@ -9,10 +9,9 @@ extern uint64_t xors;
 		xors ^= xors >> 12; \
 		xors ^= xors << 25; \
 		xors ^= xors >> 27; \
-		xors *= 0x2545F4914F6CDD1D; \
 	}
 
-#define RANDOM64 (xors)
-#define RANDOM32 ((uint32_t)xors)
+#define RANDOM64 (xors*0x2545F4914F6CDD1D)
+#define RANDOM32 ((uint32_t)RANDOM64)
 
 #endif
diff --git a/src/ctaklm.c b/src/ctaklm.c
index f7a58d9..2232bc4 100644
--- a/src/ctaklm.c
+++ b/src/ctaklm.c
@@ -317,7 +317,7 @@ negamax_turn(void) {
 		// Run the minimax
 		sum_depth = 0; num_check = 0; progress = 0;
 		float minimax = negamax_generate();
-		printf(" [%d]\n", cnn1986_num_cached);
+		printf(" [%d] <%d>\n", cnn1986_num_cached, cache_fails);
 		// Failed to find a move?
 		if (minimax < -infty) {
 			puts("Opponent failed to find a move!");
@@ -416,19 +416,15 @@ main(int argc, char **argv) {
 	(void)(argc);
 	(void)(argv);
 
-	/*
-	 * cnn1986_max_num_cached = 500;
-	 * negamax_search_depth = 3;
-	 * negamax_cache_threshold = 3;
-	 * new_game(5);
-	 */
-
 	// Test harness
 	negamax_search_depth = 5;
 	new_game(5);
 	negamax_init(5);
-	for (int k=0; k<2; k++) negamax_turn();
-	return 0;
+	/*
+	 * load_ptn("data/0.ptn");
+	 * for (int k=0; k<2; k++) negamax_turn();
+	 * return 0;
+	 */
 	// Test harness
 
 	char *line = NULL;