Hash collisions

1 files changed, 53 insertions, 19 deletions

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();