Attempting Zobrist hashing

9 files changed, 282 insertions, 242 deletions

diff --git a/include/cnn1986.c b/include/cnn1986.c
new file mode 100644
index 0000000..039dddd
--- /dev/null
+++ b/include/cnn1986.c
@@ -0,0 +1,114 @@
+#include "cnn1986.h"
+#include "weights.h"
+
+// ===================================================================
+// Implementation of a small convolutional neural network
+// ===================================================================
+
+static float flattened[CONV_NUM+2];
+static float dense1[DENSE1_NUM];
+static float dense2[DENSE2_NUM];
+
+#ifndef DETERMINISTIC
+union u_f {
+	uint32_t u;
+	float f;
+};
+
+static union u_f fudge;
+
+#define RANDF { \
+	XORSHIFT; \
+	fudge.u = 0x3f800000 | RANDOM32 >> 10; \
+	fudge.f = (fudge.f - 1.5) * 0.01; \
+	}
+#endif
+
+#define RELU(x) ((x) = ((x)<0)?0:(x))
+
+float cnn1986_evaluate_black_win(void) {
+	/* ------------------ *
+	 *  Convolution layer *
+	 * ------------------ */
+	// for each kernel
+	for (uint8_t kern = 0; kern < KERN_NUM; kern++) {
+		// the stride is 1, march across the board
+		for (uint8_t bx = 0; bx < KERN_OSIZE; bx++) {
+			for (uint8_t by = 0; by < KERN_OSIZE; by++) {
+				flattened[kern+KERN_NUM*(bx+by*KERN_OSIZE)] =
+					conv2d_biases[kern];
+				// Compute the convolution for this position
+				for (uint8_t ky = 0; ky < KERN_SIZE; ky++) {
+					for (uint8_t kx = 0; kx < KERN_SIZE; kx++) {
+						for (uint8_t c = 0; c < KERN_CHAN; c++) {
+							// Where we are on the board
+							const uint8_t loc = kx+bx+(ky+by)*5;
+							// Look up what's on the board at this location, and
+							// multiply it. For c=0 we have to do some extra work
+							float lookup = 0;
+							if (COUNT_AT(loc)>c) {
+								if (c==0) {
+									if (STONE_AT(loc) == STONE_STANDING) {
+										lookup = (colours[loc] & 1) ? +0.25 : -0.25;
+									} else if (STONE_AT(loc) == STONE_CAPSTONE) {
+										lookup = (colours[loc] & 1) ? +1.00 : -1.00;
+									} else {
+										lookup = (colours[loc] & 1) ? +0.50 : -0.50;
+									}
+								} else {
+									lookup = (colours[loc] & (1<<c)) ? +0.50 : -0.50;
+								}
+							}
+							flattened[kern+KERN_NUM*(bx+by*KERN_OSIZE)]
+								+= lookup*conv2d_weights[kern][ky][kx][c];
+						}
+					}
+				}
+				RELU(flattened[kern+KERN_NUM*(bx+by*KERN_OSIZE)]);
+			}
+		}
+	}
+	// Add input of flat counts
+	flattened[CONV_NUM]   = (float)(white_count & 127)/21.0;
+	flattened[CONV_NUM+1] = (float)(black_count & 127)/21.0;
+	/* ------------------ *
+	 *  First dense layer *
+	 * ------------------ */
+	for (uint8_t d1 = 0; d1 < DENSE1_NUM; d1++) {
+		dense1[d1] = dense1_biases[d1];
+		for (uint8_t fl = 0; fl < CONV_NUM+2; fl++) {
+			dense1[d1] += flattened[fl]*dense1_weights[d1][fl];
+		}
+		RELU(dense1[d1]);
+	}
+	/* ------------------- *
+	 *  Second dense layer *
+	 * ------------------- */
+	for (uint8_t d2 = 0; d2 < DENSE2_NUM; d2++) {
+		dense2[d2] = dense2_biases[d2];
+		for (uint8_t d1 = 0; d1 < DENSE1_NUM; d1++) {
+			dense2[d2] += dense1[d1]*dense2_weights[d2][d1];
+		}
+		RELU(dense2[d2]);
+	}
+	/* ------------- *
+	 *  Output layer *
+	 * ------------- */
+	float output = output_bias;
+	for (uint8_t d2 = 0; d2 < DENSE2_NUM; d2++) {
+		output += dense2[d2]*output_weights[d2];
+	}
+	// Truncated Pade approximant of logistic function
+	output = (12.0+output+50.0*output/(output*output+10.0))/24.0;
+#ifndef DETERMINISTIC
+	RANDF;
+	output += fudge.f;
+#endif
+	if (output > 1.0) {
+		return 1.0;
+	}
+	else if (output < 0.0) {
+		return -1.0;
+	}
+	return 2*output-1.0;
+}
diff --git a/include/cnn1986.h b/include/cnn1986.h
new file mode 100644
index 0000000..c04a04e
--- /dev/null
+++ b/include/cnn1986.h
@@ -0,0 +1,3 @@
+#include <tak.h>
+
+float cnn1986_evaluate_black_win(void);
diff --git a/include/cnn1986_treap_cache.c b/include/cnn1986_treap_cache.c
index 06553c1..94eda58 100644
--- a/include/cnn1986_treap_cache.c
+++ b/include/cnn1986_treap_cache.c
@@ -5,36 +5,31 @@
 // ===================================================================
 
 typedef struct treap_node_s {
+	uint64_t key;
 	uint32_t weight;
 	struct treap_node_s *left, *right, *parent;
-	colour_stack_t colours[25];
-	data_t celldat[25];
-	uint8_t white_count, black_count;
+	/*
+	 * colour_stack_t colours[25];
+	 * data_t celldat[25];
+	 * uint8_t white_count, black_count;
+	 */
 	float result;
 } * TreapNode;
 
-enum E_CMP { EQ, GT, LT };
-
 // ===================================================================
 // Variables
 // ===================================================================
 
 uint32_t cnn1986_num_cached;
-uint32_t cnn1986_max_num_cached; // TODO
 static TreapNode root;
-static uint64_t xors = (uint64_t)123134124234879;
 
 // ===================================================================
 // Helper declarations
 // ===================================================================
 
-enum E_CMP compare_data(TreapNode n);
-void recurse_tree(TreapNode n);
-TreapNode new_treap_node(float in_result);
-void bubble_up(TreapNode n);
-
-#define XORSHIFT { xors ^= xors >> 12; xors ^= xors << 25; xors ^= xors >> 27; }
-#define RANDOM (xors *= 0x2545F4914F6CDD1D)
+void recurse_tree(const TreapNode n);
+TreapNode new_treap_node(const float in_result, const uint64_t key);
+void bubble_up(const TreapNode n);
 
 // ===================================================================
 // Exported functions
@@ -51,13 +46,12 @@ void cnn1986_cache_free(void) {
 	return;
 }
 
-int cnn1986_cache_seek(float *out_result) {
+int cnn1986_cache_seek(const uint64_t key, float *out_result) {
 	if (root == NULL) return EXIT_FAILURE;
 	TreapNode n = root;
-	enum E_CMP e;
-	e = compare_data(n);
-	while (n != NULL && e != EQ) {
-		if (e == GT) n = n->right;
+
+	while (n != NULL && n->key != key) {
+		if (n->key > key) n = n->right;
 		else n = n->left;
 	}
 	if (n == NULL) return EXIT_FAILURE;
@@ -65,24 +59,22 @@ int cnn1986_cache_seek(float *out_result) {
 	return EXIT_SUCCESS;
 }
 
-int cnn1986_cache_insert(float in_result) {
+int cnn1986_cache_insert(const uint64_t key, const float in_result) {
 	if (root == NULL) {
-		root = new_treap_node(in_result);
+		root = new_treap_node(in_result, key);
 		cnn1986_num_cached = 1;
 		return EXIT_SUCCESS;
 	}
-	TreapNode s = root, n = root, m = new_treap_node(in_result);
+	TreapNode s = root, n = root,
+		m = new_treap_node(in_result, key);
 	// Find the correct position by doing a BST traversal
-	enum E_CMP e;
 	while (n!=NULL) {
 		s = n;
-		e = compare_data(n);
-		if (e == LT) n = n->left;
-		else n = n->right;
+		if (n->key >= key) n = n->right;
+		else n = n->left;
 	}
 	// Make it a leaf
-	e = compare_data(s);
-	if (e == GT) s->right = m;
+	if (s->key > key) s->right = m;
 	else s->left = m;
 	m->parent = s;
 	// Now bubble upward to satisfy the heap property
@@ -95,26 +87,6 @@ int cnn1986_cache_insert(float in_result) {
 // Helper implementations
 // ===================================================================
 
-enum E_CMP compare_data(TreapNode n) {
-	if (n->white_count < white_count) return LT;
-	else if (n->white_count > white_count) return GT;
-
-	if (n->black_count < black_count) return LT;
-	else if (n->black_count > black_count) return GT;
-
-	for (int k = 0; k<25; k++) {
-		if (n->colours[k] < colours[k]) return LT;
-		if (n->colours[k] > colours[k]) return GT;
-	}
-
-	for (int k = 0; k<25; k++) {
-		if (n->celldat[k] < celldat[k]) return LT;
-		if (n->celldat[k] > celldat[k]) return GT;
-	}
-
-	return EQ;
-}
-
 void recurse_tree(TreapNode n) {
 	if (n==NULL) return;
 	if (n->left != NULL) recurse_tree(n->left);
@@ -122,20 +94,15 @@ void recurse_tree(TreapNode n) {
 	free(n);
 }
 
-TreapNode new_treap_node(float in_result) {
+TreapNode new_treap_node(const float in_result, const uint64_t key) {
 	TreapNode n = malloc(sizeof(struct treap_node_s));
 	// TODO: trap
+	n->key = key;
 	n->left = NULL;
 	n->right = NULL;
 	n->parent = NULL;
-	XORSHIFT; n->weight = RANDOM;
-	// Set key
-	for (int k = 0; k<25; k++) {
-		n->celldat[k] = celldat[k];
-		n->colours[k] = colours[k];
-	}
-	n->black_count = black_count;
-	n->white_count = white_count;
+	n->weight = RANDOM32;
+	XORSHIFT;
 	// Set value
 	n->result = in_result;
 	return n;
diff --git a/include/cnn1986_treap_cache.h b/include/cnn1986_treap_cache.h
index 292e9c5..92208b2 100644
--- a/include/cnn1986_treap_cache.h
+++ b/include/cnn1986_treap_cache.h
@@ -1,12 +1,12 @@
 #include <stdlib.h>
 #include <stdint.h>
 #include <tak.h>
+#include <xorshift64.h>
 
 extern uint32_t cnn1986_num_cached;
-extern uint32_t cnn1986_max_num_cached;
 
 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, float *out_result);
+int cnn1986_cache_insert(const uint64_t key, const float in_result);
diff --git a/include/negamax_cnn1986.c b/include/negamax.c
index 1dd0e72..bc912ad 100644
--- a/include/negamax_cnn1986.c
+++ b/include/negamax.c
@@ -1,136 +1,76 @@
-#include "negamax_cnn1986.h"
+#include "negamax.h"
 
 // ===================================================================
 // Globals
 // ===================================================================
 
 const float infty = 3.0;
-char negamax_cnn1986_ptn[9];
-uint8_t negamax_cnn1986_search_depth = 3;
-uint8_t negamax_cnn1986_cache_threshold = 3;
+char negamax_ptn[9];
+uint8_t negamax_search_depth = 3;
 
 // ===================================================================
-// Implementation of a small convolutional neural network
+// Zobrist hashing
 // ===================================================================
 
-static float flattened[CONV_NUM+2];
-static float dense1[DENSE1_NUM];
-static float dense2[DENSE2_NUM];
+uint64_t *zobrist = NULL;
 
-#ifndef DETERMINISTIC
-union u_f {
-	uint32_t u;
-	float f;
-};
-
-static uint32_t state = 1;
-static union u_f fudge;
-
-#define DOXORSHIFT {		\
-		state ^= state << 13; \
-		state ^= state >> 17; \
-		state ^= state << 5; \
-		fudge.u = 0x3f800000 | state >> 10; \
-		fudge.f = (fudge.f - 1.5) * 0.01; \
-	}
-#endif
-
-#define RELU(x) ((x) = ((x)<0)?0:(x))
-
-float
-cnn1986_evaluate_black_win(void) {
-	/* ------------------ *
-	 *  Convolution layer *
-	 * ------------------ */
-	// for each kernel
-	for (uint8_t kern = 0; kern < KERN_NUM; kern++) {
-		// the stride is 1, march across the board
-		for (uint8_t bx = 0; bx < KERN_OSIZE; bx++) {
-			for (uint8_t by = 0; by < KERN_OSIZE; by++) {
-				flattened[kern+KERN_NUM*(bx+by*KERN_OSIZE)] =
-					conv2d_biases[kern];
-				// Compute the convolution for this position
-				for (uint8_t ky = 0; ky < KERN_SIZE; ky++) {
-					for (uint8_t kx = 0; kx < KERN_SIZE; kx++) {
-						for (uint8_t c = 0; c < KERN_CHAN; c++) {
-							// Where we are on the board
-							const uint8_t loc = kx+bx+(ky+by)*5;
-							// Look up what's on the board at this location, and
-							// multiply it. For c=0 we have to do some extra work
-							float lookup = 0;
-							if (COUNT_AT(loc)>c) {
-								if (c==0) {
-									if (STONE_AT(loc) == STONE_STANDING) {
-										lookup = (colours[loc] & 1) ? +0.25 : -0.25;
-									} else if (STONE_AT(loc) == STONE_CAPSTONE) {
-										lookup = (colours[loc] & 1) ? +1.00 : -1.00;
-									} else {
-										lookup = (colours[loc] & 1) ? +0.50 : -0.50;
-									}
-								} else {
-									lookup = (colours[loc] & (1<<c)) ? +0.50 : -0.50;
-								}
-							}
-							flattened[kern+KERN_NUM*(bx+by*KERN_OSIZE)]
-								+= lookup*conv2d_weights[kern][ky][kx][c];
-						}
-					}
+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 l=0; l<board_size*board_size; l++) {
+		for (int h=0; h<16; h++) {
+			for (int c=0; c<2; c++) {
+				for (int s=0; s<3; s++) {
+					XORSHIFT;
+					zobrist[l*board_size*board_size+h*16+c*2+s] = RANDOM64;
 				}
-				RELU(flattened[kern+KERN_NUM*(bx+by*KERN_OSIZE)]);
 			}
 		}
 	}
-	// Add input of flat counts
-	flattened[CONV_NUM]   = (float)(white_count & 127)/21.0;
-	flattened[CONV_NUM+1] = (float)(black_count & 127)/21.0;
-	/* ------------------ *
-	 *  First dense layer *
-	 * ------------------ */
-	for (uint8_t d1 = 0; d1 < DENSE1_NUM; d1++) {
-		dense1[d1] = dense1_biases[d1];
-		for (uint8_t fl = 0; fl < CONV_NUM+2; fl++) {
-			dense1[d1] += flattened[fl]*dense1_weights[d1][fl];
-		}
-		RELU(dense1[d1]);
+	return EXIT_SUCCESS;
+}
+
+static void negamax_free_zobrist(void) {
+	if (zobrist != NULL) {
+		free(zobrist);
+		zobrist = NULL;
 	}
-	/* ------------------- *
-	 *  Second dense layer *
-	 * ------------------- */
-	for (uint8_t d2 = 0; d2 < DENSE2_NUM; d2++) {
-		dense2[d2] = dense2_biases[d2];
-		for (uint8_t d1 = 0; d1 < DENSE1_NUM; d1++) {
-			dense2[d2] += dense1[d1]*dense2_weights[d2][d1];
+}
+
+uint64_t negamax_compute_zobrist(void) {
+	uint64_t result = 0;
+	for (uint8_t l=0; l<board_size*board_size; l++) {
+		colour_stack_t c = colours[l];
+		const uint8_t count = COUNT_AT(l);
+		enum STONE_VARIANT s = STONE_AT(l);
+		for (uint8_t h=0; h<count; h++) {
+			result ^= zobrist[l*board_size*board_size
+												+h*16 +(c&1)*2 +s];
+			s = STONE_FLAT;
+			c >>= 1;
 		}
-		RELU(dense2[d2]);
 	}
-	/* ------------- *
-	 *  Output layer *
-	 * ------------- */
-	float output = output_bias;
-	for (uint8_t d2 = 0; d2 < DENSE2_NUM; d2++) {
-		output += dense2[d2]*output_weights[d2];
-	}
-	// Truncated Pade approximant of logistic function
-	output = (12.0+output+50.0*output/(output*output+10.0))/24.0;
-#ifndef DETERMINISTIC
-	DOXORSHIFT;
-	output += fudge.f;
-#endif
-	if (output > 1.0) {
-		return 1.0;
-	}
-	else if (output < 0.0) {
-		return -1.0;
-	}
-	return 2*output-1.0;
+	return result;
 }
 
 // ===================================================================
-// α-β negamax using the above evaluator
+// α-β negamax using the cnn1986 evaluation function
 // ===================================================================
 
-static void
-previous_ply(void) {
+
+// Movement steps, orderd with the enum: UP DOWN LEFT RIGHT
+static int8_t deltas[4];
+
+void negamax_init_size(void) {
+	deltas[0] = +board_size;
+	deltas[1] = -board_size;
+	deltas[2] = -1;
+	deltas[3] = +1;
+	negamax_free_zobrist();
+	negamax_init_zobrist();
+}
+
+static void previous_ply(void) {
 	if (ply>0) ply--;
 	if (ply == 1) {
 		current_colour = C_WHITE;
@@ -140,10 +80,10 @@ previous_ply(void) {
 	}
 }
 
-static inline void
-push_stones(const int8_t location, const uint8_t count,
-						const uint8_t new_colours,
-						const enum STONE_VARIANT top_stone) {
+static void push_stones(const int8_t location,
+												const uint8_t count,
+												const uint8_t new_colours,
+												const enum STONE_VARIANT top_stone) {
 	colours[location]  = (colours[location] << count) | new_colours;
 	celldat[location]  = top_stone
 		| ((celldat[location] + ((count << NUM_SHIFT))) & NUM_MASK);
@@ -152,12 +92,9 @@ push_stones(const int8_t location, const uint8_t count,
 static float val;
 static enum WIN_TYPE w;
 
-// UP DOWN LEFT RIGHT
-static const int8_t deltas[4] = { +5, -5, -1, +1};
-
 #define WIN_EVALUATE_OR_RECURSE(store,reset) {		\
 		w = 0xFF; \
-		if (ply >= 2*5 - 3) w = check_win(); \
+		if (ply >= 2*board_size - 3) w = check_win(); \
 		if (w < 0xFF) { \
 			/* Somebody won, assign weights accordingly. */ \
 			if (w == WIN_ROAD_BLACK || w == WIN_FLAT_BLACK) { \
@@ -171,13 +108,13 @@ static const int8_t deltas[4] = { +5, -5, -1, +1};
 				/* Fix draw value to be completely neutral */ \
 			} else if (w == WIN_DRAW) val = 0; \
 			else val = -colour*infty; \
-		} else if (cur_depth == negamax_cnn1986_search_depth) { \
+		} else if (cur_depth == negamax_search_depth) { \
 			/* We're at the bottom, evaluate */ \
 			val = colour * cnn1986_evaluate_black_win(); \
 		} else { \
 			/* We're not at the bottom, recurse first */ \
 			next_ply(); \
-			val = -negamax_cnn1986(cur_depth + 1, -beta, -alpha, -colour); \
+			val = -negamax(cur_depth + 1, -beta, -alpha, -colour); \
 			previous_ply(); \
 		} \
 		{ reset }; \
@@ -190,15 +127,10 @@ static const int8_t deltas[4] = { +5, -5, -1, +1};
 		} \
 	}
 
-float
-negamax_cnn1986(const uint8_t cur_depth, float alpha, float beta,
-								const float colour) {
-
-	int sought = EXIT_FAILURE;
-	if (cur_depth < negamax_cnn1986_cache_threshold) {
-		sought = cnn1986_cache_seek(&alpha);
-	}
-	if (sought) {
+float negamax(const uint8_t cur_depth, float alpha, float beta,
+							const float colour) {
+	uint64_t hash = negamax_compute_zobrist();
+	if (cnn1986_cache_seek(hash, &alpha) == EXIT_FAILURE) {
 		const uint8_t black = (ply & 1),
 			material = (black) ? black_count : white_count,
 			flat = material & 127,
@@ -206,24 +138,24 @@ negamax_cnn1986(const uint8_t cur_depth, float alpha, float beta,
 			standing = (ply > 2 && (material & 127));
 
 		// Step across the board
-		for (uint8_t row = 0; row < 5; row++) {
-			for (uint8_t col = 0; col < 5; col++) {
+		for (uint8_t row = 0; row < board_size; row++) {
+			for (uint8_t col = 0; col < board_size; col++) {
 				// Try all valid actions for this square. Is it empty?
 				const uint8_t loc = THE_COORDS(col, row);
-				const uint8_t count = (COUNT_AT(loc) > 5) ? 5 : COUNT_AT(loc);
+				const uint8_t count = (COUNT_AT(loc) > board_size) ? board_size : COUNT_AT(loc);
 				// Only try moves after CPS
 				if (count && ((colours[loc] & 1) == current_colour) && ply>2) {
-					// There are stones, can we move them in a given direction?
+					// There are stones, let's try moving them
 
 					// Pre-compute end-stops
 					uint8_t end_stops[4][2]; // (end, not_crush)
 					// UP DOWN LEFT RIGHT
-					end_stops[0][0] = (4-row > count) ? count : 4-row;
+					end_stops[0][0] = (board_size - row - 1 > count) ? count : board_size - row - 1;
 					end_stops[1][0] = (row > count) ? count : row;
 					end_stops[2][0] = (col > count) ? count : col;
-					end_stops[3][0] = (4-col > count) ? count : 4-col;
+					end_stops[3][0] = (board_size - col - 1 > count) ? count : board_size - col - 1;
 					const uint8_t cap_top = STONE_AT(loc) == STONE_CAPSTONE;
-					for (uint8_t d = 0; d < 4; d++){
+					for (uint8_t d = 0; d < board_size-1; d++){
 						end_stops[d][1] = 1;
 						const uint8_t stop = end_stops[d][0];
 						end_stops[d][0] = 0;
@@ -242,12 +174,13 @@ negamax_cnn1986(const uint8_t cur_depth, float alpha, float beta,
 						}
 					}
 
-					uint16_t colours_backup[5];
-					uint8_t celldat_backup[5], drops[5]; // we only use 4, the
-					// fifth is to skip a
-					// bounds check at (*)
-					// Back up the row of the board
-					for (uint8_t y = 0; y < 5; y++) {
+					uint16_t colours_backup[board_size];
+					uint8_t celldat_backup[board_size], drops[board_size];
+					// we only ever need board_size-1 in drops actually, the
+					// last spot is to skip a bounds check at (*)
+
+					//Back up the rows of the board
+					for (uint8_t y = 0; y < board_size; y++) {
 						colours_backup[y] = colours[THE_COORDS(col, y)];
 						celldat_backup[y] = celldat[THE_COORDS(col, y)];
 					}
@@ -258,7 +191,7 @@ negamax_cnn1986(const uint8_t cur_depth, float alpha, float beta,
 					for (enum MOVE_DIRECTION dir = M_UP; dir <= M_RIGHT; dir++) {
 						// Back-up the column once we start looking horizontally
 						if (dir == M_LEFT) {
-							for (uint8_t x = 0; x < 5; x++) {
+							for (uint8_t x = 0; x < board_size; x++) {
 								colours_backup[x] = colours[THE_COORDS(x, row)];
 								celldat_backup[x] = celldat[THE_COORDS(x, row)];
 							}
@@ -274,18 +207,20 @@ negamax_cnn1986(const uint8_t cur_depth, float alpha, float beta,
 							for (uint8_t steps = 1;
 									 steps <= end_stops[dir][0] && steps <= num;
 									 steps++) {
-								gaps = 0x07 >> (4-steps); // 0b0000[0111] because 4-1=3
-								// and 5-1=4
+								// TODO: Generalise to board_size!
+								gaps = 0x07 >> (board_size-steps-1);
+								// 0b0000[0111] because 4-1=3 and 5-1=4
 								do  {
 									// Ensure legal move if we have to crush
-									const uint8_t last_drop_check = (num > 1) ? (gaps & 1<<(num - 2)) : 1;
+									const uint8_t last_drop_check =
+										(num > 1) ? (gaps & 1<<(num - 2)) : 1;
 									if (end_stops[dir][1] || last_drop_check) {
 										// Translate to a drop sequence
 										drops[0] = 1; mask = 1; idx = 0;
 										for (uint8_t d = 0; d + 1 < num; d++) {
 											if (gaps & mask) {
 												idx++;
-												drops[idx] = 1; // (*) we don't need to bounds check
+												drops[idx] = 1; // (*) no bounds check
 											} else {
 												drops[idx] += 1;
 											}
@@ -310,17 +245,17 @@ negamax_cnn1986(const uint8_t cur_depth, float alpha, float beta,
 										WIN_EVALUATE_OR_RECURSE({
 												// If we did update the optimal value, store
 												// this move
-												generate_move(loc, dir, steps, drops, negamax_cnn1986_ptn);
+												generate_move(loc, dir, steps, drops, negamax_ptn);
 											},{
 												// Reset the board data after recursing or
 												// before returning
 												if (dir <= M_DOWN) {
-													for (uint8_t y = 0; y < 5; y++) {
+													for (uint8_t y = 0; y < board_size; y++) {
 														colours[THE_COORDS(col, y)] = colours_backup[y];
 														celldat[THE_COORDS(col, y)] = celldat_backup[y];
 													}
 												} else {
-													for (uint8_t x = 0; x < 5; x++) {
+													for (uint8_t x = 0; x < board_size; x++) {
 														colours[THE_COORDS(x, row)] = colours_backup[x];
 														celldat[THE_COORDS(x, row)] = celldat_backup[x];
 													}
@@ -350,7 +285,7 @@ negamax_cnn1986(const uint8_t cur_depth, float alpha, float beta,
 						celldat[loc] = NUM_INC | STONE_FLAT;
 						WIN_EVALUATE_OR_RECURSE({
 								// If we did update the optimal value, store
-								generate_place(loc, STONE_FLAT, negamax_cnn1986_ptn);
+								generate_place(loc, STONE_FLAT, negamax_ptn);
 							},{
 								// Reset the state
 								celldat[loc] = 0;
@@ -364,7 +299,7 @@ negamax_cnn1986(const uint8_t cur_depth, float alpha, float beta,
 							colours[loc] = current_colour;
 							celldat[loc] = NUM_INC | STONE_STANDING;
 							WIN_EVALUATE_OR_RECURSE({
-									generate_place(loc, STONE_STANDING, negamax_cnn1986_ptn);
+									generate_place(loc, STONE_STANDING, negamax_ptn);
 								},{
 									celldat[loc] = 0;
 									if (black) black_count++;
@@ -380,7 +315,7 @@ negamax_cnn1986(const uint8_t cur_depth, float alpha, float beta,
 						colours[loc] = current_colour;
 						celldat[loc] = NUM_INC | STONE_CAPSTONE;
 						WIN_EVALUATE_OR_RECURSE({
-								generate_place(loc, STONE_CAPSTONE, negamax_cnn1986_ptn);
+								generate_place(loc, STONE_CAPSTONE, negamax_ptn);
 							},{
 								celldat[loc] = 0;
 								if (black) black_count |= 128;
@@ -388,24 +323,24 @@ negamax_cnn1986(const uint8_t cur_depth, float alpha, float beta,
 							});
 					}
 				}
-				negamax_cnn1986_display_progress(cur_depth);
+				negamax_display_progress(cur_depth);
 			}
 		}
-		// Insert into the cache if we're not too deep, and make it
-		// useable for both min and max (colour * colour == 1)
-		if (cur_depth < negamax_cnn1986_cache_threshold)
-			cnn1986_cache_insert(colour*alpha);
-	} else {
-		// Impose the colour
-		alpha *= colour;
+		// Insert into the cache
+		cnn1986_cache_insert(hash, alpha);
 	}
 	return alpha;
 }
 
 inline float
-negamax_cnn1986_generate(void) {
+negamax_generate(void) {
 	// We need to start with something outside of [-∞,∞] because those
 	// values are wins
 	const float safe_infty = infty + 1;
-	return negamax_cnn1986(0, -safe_infty, safe_infty, (ply&1)?1.0:-1.0);
+
+	cnn1986_cache_init();
+	float result = negamax(0, -safe_infty, safe_infty, (ply&1)?1.0:-1.0);
+	cnn1986_cache_free();
+
+	return result;
 }
diff --git a/include/negamax.h b/include/negamax.h
new file mode 100644
index 0000000..fbdf8da
--- /dev/null
+++ b/include/negamax.h
@@ -0,0 +1,19 @@
+#include <stdint.h>
+#include <tak.h>
+#include <xorshift64.h>
+#include <cnn1986.h>
+#include <cnn1986_treap_cache.h>
+
+extern const float infty;
+extern char negamax_ptn[9];
+extern uint8_t negamax_search_depth;
+extern inline void negamax_display_progress(const uint8_t);
+
+void negamax_init_size(void);
+uint64_t negamax_compute_zobrist(void);
+
+// Do negamax to depth negamax_search_depth and return PTN of best move
+// in negamax_ptn, along with its value as the return. The
+// negamax_display_progress function is called on every new square at
+// the top level.
+float negamax_generate(void);
diff --git a/include/negamax_cnn1986.h b/include/negamax_cnn1986.h
deleted file mode 100644
index fc0d5f2..0000000
--- a/include/negamax_cnn1986.h
+++ /dev/null
@@ -1,19 +0,0 @@
-#include <stdint.h>
-#include <tak.h>
-#include <cnn1986_treap_cache.h>
-#include "weights.h"
-
-extern const float infty;
-extern char negamax_cnn1986_ptn[9];
-extern uint8_t negamax_cnn1986_search_depth;
-extern uint8_t negamax_cnn1986_cache_threshold;
-extern inline void negamax_cnn1986_display_progress(const uint8_t);
-
-// Do negamax to depth ct1986_search_depth and return PTN of best move
-// in ct1986_ptn, along with its value as the return. The
-// ct1986_display_progress function is called on every new square at
-// the top level.
-float negamax_cnn1986_generate(void);
-
-// Internal utility function
-float cnn1986_evaluate_black_win(void);
diff --git a/include/xorshift64.c b/include/xorshift64.c
new file mode 100644
index 0000000..04d5cfe
--- /dev/null
+++ b/include/xorshift64.c
@@ -0,0 +1,3 @@
+#include "xorshift64.h"
+
+uint64_t xors = (uint64_t)0xFEEDCAFEF00DDDDD;
diff --git a/include/xorshift64.h b/include/xorshift64.h
new file mode 100644
index 0000000..a12a38d
--- /dev/null
+++ b/include/xorshift64.h
@@ -0,0 +1,18 @@
+#include <stdint.h>
+
+#ifndef XORSHIFT_H
+#define XORSHIFT_H
+
+extern uint64_t xors;
+
+#define XORSHIFT { \
+		xors ^= xors >> 12; \
+		xors ^= xors << 25; \
+		xors ^= xors >> 27; \
+		xors *= 0x2545F4914F6CDD1D; \
+	}
+
+#define RANDOM64 (xors)
+#define RANDOM32 ((uint32_t)xors)
+
+#endif