Still trying

|

8 files changed, 300 insertions, 289 deletions

diff --git a/include/cnn1986.c b/include/cnn1986.c
index 039dddd..17d4e84 100644
--- a/include/cnn1986.c
+++ b/include/cnn1986.c
@@ -100,10 +100,12 @@ float cnn1986_evaluate_black_win(void) {
 	}
 	// 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
+/*
+ * #ifndef DETERMINISTIC
+ *	RANDF;
+ *	output += fudge.f;
+ * #endif
+ */
 	if (output > 1.0) {
 		return 1.0;
 	}
diff --git a/include/cnn1986_cache.c b/include/cnn1986_cache.c
index 692920a..303ef57 100644
--- a/include/cnn1986_cache.c
+++ b/include/cnn1986_cache.c
@@ -32,7 +32,7 @@ int cnn1986_cache_seek(const uint64_t key[4],
 			}
 		}
 
-		if (fail) {
+		if (fail == 1) {
 			c = c->next;
 		} else {
 			*out_result = c->result;
diff --git a/include/cnn1986_treap_cache.h b/include/cnn1986_treap_cache.h
deleted file mode 100644
index 20b2fbc..0000000
--- a/include/cnn1986_treap_cache.h
+++ /dev/null
@@ -1,17 +0,0 @@
-#include <stdlib.h>
-#include <stdint.h>
-#include <tak.h>
-#include <xorshift64.h>
-
-extern uint32_t cnn1986_num_cached;
-
-int cnn1986_cache_init(void);
-void cnn1986_cache_free(void);
-
-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 3e57165..3e3a209 100644
--- a/include/negamax.c
+++ b/include/negamax.c
@@ -14,34 +14,27 @@ uint32_t cache_fails = 0;
 // Zobrist hashing
 // ===================================================================
 
-uint64_t *zobrist[4];
-uint64_t *zobrist_empty[4];
+uint64_t *zobrist[15];
 
 static int negamax_init_zobrist(void) {
-	for (int k=0; k<4; k++) {
+
+	for (int k=0; k<15; 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++) {
+	for (int j=0; j<15; j++) {
+		zobrist[j] = malloc(sizeof(uint64_t)*board_size*board_size*(2*3+1));
+		for (int k=0; k<board_size*board_size*(2*3+1); 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) {
-	for (int k=0; k<4; k++) {
+	for (int k=0; k<15; k++) {
 		if (zobrist[k] != NULL) {
 			free(zobrist[k]);
 			zobrist[k] = NULL;
@@ -49,21 +42,20 @@ static void negamax_free_zobrist(void) {
 	}
 }
 
-void negamax_compute_zobrist(uint64_t *hash) {
-	for (int k=0; k<4; k++) hash[k] = 0;
+uint64_t negamax_compute_zobrist(void) {
+	uint64_t hash = 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);
-		if (count) {
-			const enum STONE_VARIANT s = STONE_AT(l);
-			colour_stack_t c = colours[l];
-			for (uint8_t h=0; h<count; h++) {
-				for (int k=0; k<4; k++) {
-					hash[k] ^= zobrist[k][l*16*3*2 + h*3*2 + (c&1)*3 + s];
-				}
+		enum STONE_VARIANT s = STONE_AT(l);
+		for (uint8_t h=0; h<15; h++) {
+			if (h<count) {
+				hash ^= zobrist[h][l*(2*3+1)+(c&1)*3+s];
 				c >>= 1;
 			}
 		}
 	}
+	return hash;
 }
 
 // ===================================================================
@@ -144,220 +136,229 @@ static enum WIN_TYPE w;
 float negamax(const uint8_t cur_depth, float alpha, float beta,
 							const float colour) {
 
-	uint64_t hash[4];
-	negamax_compute_zobrist(hash);
-
-	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,
-			cap = (ply > 2 && (material & 128)),
-			standing = (ply > 2 && (material & 127));
-
-		// Step across the board
-		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) > board_size) ? board_size : COUNT_AT(loc);
-				// Only try moves after CPS
-				if (count && ((colours[loc] & 1) == current_colour) && ply>2) {
-					// 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] = (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] = (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 < board_size-1; d++){
-						end_stops[d][1] = 1;
-						const uint8_t stop = end_stops[d][0];
-						end_stops[d][0] = 0;
-						for (uint8_t k = 1; k <= stop; k++) {
-							const uint8_t stone = STONE_AT(loc+k*deltas[d]);
-							if (stone == STONE_STANDING) {
-								if (cap_top) {
-									end_stops[d][1] = 0;
-									end_stops[d][0]++;
-								}
-								break;
-							} else if (stone == STONE_CAPSTONE) {
-								break;
+	uint64_t hash = negamax_compute_zobrist();
+	tt_entry_t *entry = tt_seek(hash);
+	const float alpha_orig = alpha;
+
+	if (entry != NULL && entry -> depth <= cur_depth) {
+		if (entry->flag == TT_EXACT) {
+			return entry->value;
+		} else if (entry->flag == TT_LOWERBOUND) {
+			if (entry->value > alpha) alpha = entry->value;
+		} else if (entry->flag == TT_UPPERBOUND) {
+			if (entry->value < beta) beta = entry->value;
+		}
+		if (alpha >= beta) return entry->value;
+	}
+
+	const uint8_t black = (ply & 1),
+		material = (black) ? black_count : white_count,
+		flat = material & 127,
+		cap = (ply > 2 && (material & 128)),
+		standing = (ply > 2 && (material & 127));
+
+	// Step across the board
+	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) > board_size) ? board_size : COUNT_AT(loc);
+			// Only try moves after CPS
+			if (count && ((colours[loc] & 1) == current_colour) && ply>2) {
+				// 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] = (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] = (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 < board_size-1; d++){
+					end_stops[d][1] = 1;
+					const uint8_t stop = end_stops[d][0];
+					end_stops[d][0] = 0;
+					for (uint8_t k = 1; k <= stop; k++) {
+						const uint8_t stone = STONE_AT(loc+k*deltas[d]);
+						if (stone == STONE_STANDING) {
+							if (cap_top) {
+								end_stops[d][1] = 0;
+								end_stops[d][0]++;
 							}
-							end_stops[d][0]++;
+							break;
+						} else if (stone == STONE_CAPSTONE) {
+							break;
 						}
+						end_stops[d][0]++;
 					}
+				}
 
-					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 (*)
+				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)];
-					}
+				//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)];
+				}
 
-					// I'm not a huge fan of looping through enums, but it's
-					// better than manually unrolling this. Sufficiently smart
-					// compilers?
-					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 < board_size; x++) {
-								colours_backup[x] = colours[THE_COORDS(x, row)];
-								celldat_backup[x] = celldat[THE_COORDS(x, row)];
-							}
+				// I'm not a huge fan of looping through enums, but it's
+				// better than manually unrolling this. Sufficiently smart
+				// compilers?
+				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 < board_size; x++) {
+							colours_backup[x] = colours[THE_COORDS(x, row)];
+							celldat_backup[x] = celldat[THE_COORDS(x, row)];
 						}
-						/*
-						 * We don't do anything terribly efficient here just try
-						 * all the ordered partitions of num ∈ {1 … end_stop}, and
-						 * skip the partition if it calls for multiple stones at
-						 * the end with a crush.
-						 */
-						uint8_t gaps, t, idx, mask;
-						for (uint8_t num = 1; num <= count; num++) {
-							for (uint8_t steps = 1;
-									 steps <= end_stops[dir][0] && steps <= num;
-									 steps++) {
-								// 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;
-									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; // (*) no bounds check
-											} else {
-												drops[idx] += 1;
-											}
-											mask <<= 1;
-										}
-										// Do it, and manually check for win if it's valid
-										uint8_t j = num;
-										for (uint8_t k = 0; k < steps; k++) {
-											j -= drops[k];
-											push_stones(loc+(k+1)*deltas[dir],
-																	drops[k],
-																	(colours[loc] >> j) & (0xFFFF >> (0x10 - drops[k])),
-																	(k == steps - 1) ? STONE_AT(loc) : STONE_FLAT);
+					}
+					/*
+					 * We don't do anything terribly efficient here just try
+					 * all the ordered partitions of num ∈ {1 … end_stop}, and
+					 * skip the partition if it calls for multiple stones at
+					 * the end with a crush.
+					 */
+					uint8_t gaps, t, idx, mask;
+					for (uint8_t num = 1; num <= count; num++) {
+						for (uint8_t steps = 1;
+								 steps <= end_stops[dir][0] && steps <= num;
+								 steps++) {
+							// 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;
+								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; // (*) no bounds check
+										} else {
+											drops[idx] += 1;
 										}
-										// Then we drop them from the source
-										colours[loc] >>= num;
-										const uint8_t dec_count = celldat[loc] - (num << NUM_SHIFT);
-										celldat[loc] = dec_count & NUM_MASK;
-
-										// First check for wins, if we're at the bottom
-										// evaluate, otherwise recurse
-										WIN_EVALUATE_OR_RECURSE({
-												// If we did update the optimal value, store
-												// this move
-												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 < 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 < board_size; x++) {
-														colours[THE_COORDS(x, row)] = colours_backup[x];
-														celldat[THE_COORDS(x, row)] = celldat_backup[x];
-													}
-												}
-											});
+										mask <<= 1;
 									}
-									/*
-									 * With thanks to
-									 * https://graphics.stanford.edu/~seander/bithacks.html#NextBitPermutation
-									 * we have the following magic to generate the next
-									 * permutation of steps-many set bits
-									 */
-									t = (gaps | (gaps - 1));
-									gaps = (t + 1) | (((~t & -~t) - 1) >> (__builtin_ctz(gaps) + 1));
-								} while (gaps && (gaps + 1 <= (1<<(num-1))));
-							}
+									// Do it, and manually check for win if it's valid
+									uint8_t j = num;
+									for (uint8_t k = 0; k < steps; k++) {
+										j -= drops[k];
+										push_stones(loc+(k+1)*deltas[dir],
+																drops[k],
+																(colours[loc] >> j) & (0xFFFF >> (0x10 - drops[k])),
+																(k == steps - 1) ? STONE_AT(loc) : STONE_FLAT);
+									}
+									// Then we drop them from the source
+									colours[loc] >>= num;
+									const uint8_t dec_count = celldat[loc] - (num << NUM_SHIFT);
+									celldat[loc] = dec_count & NUM_MASK;
+
+									// First check for wins, if we're at the bottom
+									// evaluate, otherwise recurse
+									WIN_EVALUATE_OR_RECURSE({
+											// If we did update the optimal value, store
+											// this move
+											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 < 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 < board_size; x++) {
+													colours[THE_COORDS(x, row)] = colours_backup[x];
+													celldat[THE_COORDS(x, row)] = celldat_backup[x];
+												}
+											}
+										});
+								}
+								/*
+								 * With thanks to
+								 * https://graphics.stanford.edu/~seander/bithacks.html#NextBitPermutation
+								 * we have the following magic to generate the next
+								 * permutation of steps-many set bits
+								 */
+								t = (gaps | (gaps - 1));
+								gaps = (t + 1) | (((~t & -~t) - 1) >> (__builtin_ctz(gaps) + 1));
+							} while (gaps && (gaps + 1 <= (1<<(num-1))));
 						}
 					}
-				} else if (material && count == 0) {
-					// Empty square, try placements
-
-					if (flat) {
-						// Generate the placement
+				}
+			} else if (material && count == 0) {
+				// Empty square, try placements
+
+				if (flat) {
+					// Generate the placement
+					if (black) black_count--;
+					else white_count--;
+					colours[loc] = current_colour;
+					celldat[loc] = NUM_INC | STONE_FLAT;
+					WIN_EVALUATE_OR_RECURSE({
+							// If we did update the optimal value, store
+							generate_place(loc, STONE_FLAT, negamax_ptn);
+						},{
+							// Reset the state
+							celldat[loc] = 0;
+							if (black) black_count++;
+							else white_count++;
+						});
+					// Do the same for walls, can't happen without flats
+					if (standing) {
 						if (black) black_count--;
 						else white_count--;
 						colours[loc] = current_colour;
-						celldat[loc] = NUM_INC | STONE_FLAT;
+						celldat[loc] = NUM_INC | STONE_STANDING;
 						WIN_EVALUATE_OR_RECURSE({
-								// If we did update the optimal value, store
-								generate_place(loc, STONE_FLAT, negamax_ptn);
+								generate_place(loc, STONE_STANDING, negamax_ptn);
 							},{
-								// Reset the state
 								celldat[loc] = 0;
 								if (black) black_count++;
 								else white_count++;
 							});
-						// Do the same for walls, can't happen without flats
-						if (standing) {
-							if (black) black_count--;
-							else white_count--;
-							colours[loc] = current_colour;
-							celldat[loc] = NUM_INC | STONE_STANDING;
-							WIN_EVALUATE_OR_RECURSE({
-									generate_place(loc, STONE_STANDING, negamax_ptn);
-								},{
-									celldat[loc] = 0;
-									if (black) black_count++;
-									else white_count++;
-								});
-						}
 					}
+				}
 
-					// and for caps
-					if (cap) {
-						if (black) black_count &= 127;
-						else white_count &= 127;
-						colours[loc] = current_colour;
-						celldat[loc] = NUM_INC | STONE_CAPSTONE;
-						WIN_EVALUATE_OR_RECURSE({
-								generate_place(loc, STONE_CAPSTONE, negamax_ptn);
-							},{
-								celldat[loc] = 0;
-								if (black) black_count |= 128;
-								else white_count |= 128;
-							});
-					}
+				// and for caps
+				if (cap) {
+					if (black) black_count &= 127;
+					else white_count &= 127;
+					colours[loc] = current_colour;
+					celldat[loc] = NUM_INC | STONE_CAPSTONE;
+					WIN_EVALUATE_OR_RECURSE({
+							generate_place(loc, STONE_CAPSTONE, negamax_ptn);
+						},{
+							celldat[loc] = 0;
+							if (black) black_count |= 128;
+							else white_count |= 128;
+						});
 				}
-				negamax_display_progress(cur_depth);
 			}
-		/*
-		 * }
-		 */
-		// Insert into the cache
-	}
-		if (lookup == EXIT_FAILURE)
-			cnn1986_cache_insert(hash, alpha);
-		else {
-			if (stored_alpha != alpha)
-				cache_fails++;
+			negamax_display_progress(cur_depth);
 		}
+	}
+
+	enum TT_FLAG flag = TT_EXACT;
+	if (alpha <= alpha_orig) flag = TT_UPPERBOUND;
+	else if (alpha >= beta) flag = TT_UPPERBOUND;
+
+	if (entry == NULL) {
+		tt_insert(hash, flag, cur_depth, alpha);
+	} else {
+		entry->flag = flag;
+		entry->value = alpha;
+		entry->depth = cur_depth;
+	}
+
 	return alpha;
 }
 
@@ -367,12 +368,9 @@ negamax_generate(void) {
 	// values are wins
 	const float safe_infty = infty + 1;
 
-
-	cache_fails=0;
-
-	cnn1986_cache_init();
+	tt_init();
 	float result = negamax(0, -safe_infty, safe_infty, (ply&1)?1.0:-1.0);
-	cnn1986_cache_free();
+	tt_free();
 
 	return result;
 }
diff --git a/include/negamax.h b/include/negamax.h
index 52a8fd2..f3a0a6c 100644
--- a/include/negamax.h
+++ b/include/negamax.h
@@ -2,16 +2,15 @@
 #include <tak.h>
 #include <xorshift64.h>
 #include <cnn1986.h>
-#include <cnn1986_cache.h>
+#include <tt_treap.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);
-void negamax_compute_zobrist(uint64_t hash[4]);
+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
diff --git a/include/tak.c b/include/tak.c
index 964225e..6d07ea0 100644
--- a/include/tak.c
+++ b/include/tak.c
@@ -329,6 +329,9 @@ check_win(void) {
 	enum WIN_TYPE rb, rw;
 	rb = check_road_colour(C_BLACK);
 	rw = check_road_colour(C_WHITE);
+	for (uint8_t k=0; k<NUM_SQUARES; k++)
+		celldat[k] &= NOT_DFS_MASK;
+
 
 	if (rb == WIN_ROAD_BLACK && rw == WIN_ROAD_WHITE) {
 		return (ply & 1) ? rb : rw; // Dragons
diff --git a/include/cnn1986_treap_cache.c b/include/tt_treap.c
index 941ec1c..b48ffd4 100644
--- a/include/cnn1986_treap_cache.c
+++ b/include/tt_treap.c
@@ -1,72 +1,56 @@
-#include "cnn1986_treap_cache.h"
-
-// ===================================================================
-// Types
-// ===================================================================
-
-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;
-	 */
-	float result;
-} * TreapNode;
+#include "tt_treap.h"
 
 // ===================================================================
 // Variables
 // ===================================================================
 
-uint32_t cnn1986_num_cached;
-static TreapNode root;
+uint32_t tt_num_cached;
+static tt_entry_t * root;
 
 // ===================================================================
 // Helper declarations
 // ===================================================================
 
-void recurse_tree(const TreapNode n);
-TreapNode new_treap_node(const float in_result, const uint64_t key);
-void bubble_up(const TreapNode n);
+void recurse_tree(tt_entry_t *n);
+tt_entry_t *new_treap_node(const uint64_t key, const enum TT_FLAG flag,
+													 const uint8_t depth, const float value);
+void bubble_up(tt_entry_t *n);
 
 // ===================================================================
 // Exported functions
 // ===================================================================
 
-int cnn1986_cache_init(void) {
+int tt_init(void) {
 	root = NULL;
-	cnn1986_num_cached = 0;
+	tt_num_cached = 0;
 	return EXIT_SUCCESS;
 }
 
-void cnn1986_cache_free(void) {
+void tt_free(void) {
 	recurse_tree(root);
 	return;
 }
 
-int cnn1986_cache_seek(const uint64_t key, float *out_result) {
-	if (root == NULL) return EXIT_FAILURE;
-	TreapNode n = root;
+tt_entry_t *tt_seek(const uint64_t key) {
+	if (root == NULL) return NULL;
+	tt_entry_t * n = root;
 
 	while (n != NULL && n->key != key) {
 		if (n->key > key) n = n->right;
 		else n = n->left;
 	}
-	if (n == NULL) return EXIT_FAILURE;
-	*out_result = n->result;
-	return EXIT_SUCCESS;
+	return n;
 }
 
-int cnn1986_cache_insert(const uint64_t key, const float in_result) {
+int tt_insert(const uint64_t key, const enum TT_FLAG flag,
+										const uint8_t depth, const float value) {
+	tt_entry_t *m = new_treap_node(key, flag, depth, value);
 	if (root == NULL) {
-		root = new_treap_node(in_result, key);
-		cnn1986_num_cached = 1;
+		root = m;
+		tt_num_cached = 1;
 		return EXIT_SUCCESS;
 	}
-	TreapNode s = root, n = root,
-		m = new_treap_node(in_result, key);
+	tt_entry_t *s = root, *n = root;
 	// Find the correct position by doing a BST traversal
 	while (n!=NULL) {
 		s = n;
@@ -79,7 +63,7 @@ int cnn1986_cache_insert(const uint64_t key, const float in_result) {
 	m->parent = s;
 	// Now bubble upward to satisfy the heap property
 	bubble_up(m);
-	cnn1986_num_cached++;
+	tt_num_cached++;
 	return EXIT_SUCCESS;
 }
 
@@ -87,28 +71,30 @@ int cnn1986_cache_insert(const uint64_t key, const float in_result) {
 // Helper implementations
 // ===================================================================
 
-void recurse_tree(TreapNode n) {
+void recurse_tree(tt_entry_t *n) {
 	if (n==NULL) return;
 	if (n->left != NULL) recurse_tree(n->left);
 	if (n->right != NULL) recurse_tree(n->right);
 	free(n);
 }
 
-TreapNode new_treap_node(const float in_result, const uint64_t key) {
-	TreapNode n = malloc(sizeof(struct treap_node_s));
+tt_entry_t *new_treap_node(const uint64_t key, const enum TT_FLAG flag,
+													 const uint8_t depth, const float value) {
+	tt_entry_t *n = malloc(sizeof(struct treap_node_s));
 	// TODO: trap
 	n->key = key;
+	n->flag = flag;
+	n->depth = depth;
+	n->value = value;
 	n->left = NULL;
 	n->right = NULL;
 	n->parent = NULL;
 	XORSHIFT64; n->weight = RANDOM32;
-	// Set value
-	n->result = in_result;
 	return n;
 }
 
-void rotate_left(TreapNode n) {
-	TreapNode a = n->parent, b = a->left, c = n->left;
+void rotate_left(tt_entry_t *n) {
+	tt_entry_t *a = n->parent, *b = a->left, *c = n->left;
 	/*
 		We are the right child, so do this
 					 a           n
@@ -129,8 +115,8 @@ void rotate_left(TreapNode n) {
 	a->right = c; if (c!=NULL) c->parent = a;
 }
 
-void rotate_right(TreapNode n) {
-	TreapNode a = n->parent, b = a->right, d = n->right;
+void rotate_right(tt_entry_t *n) {
+	tt_entry_t *a = n->parent, *b = a->right, *d = n->right;
 	 /*
 		 We are the left child, so do this
 				 a           n
@@ -152,7 +138,7 @@ void rotate_right(TreapNode n) {
 }
 
 //This preserves the BST quality of the treap
-void bubble_up(TreapNode n) {
+void bubble_up(tt_entry_t *n) {
 	// Nothing to be done in this case
 	if (n==NULL || n->parent == NULL) return;
 	// Bubble until the treap invariants are satisfied
diff --git a/include/tt_treap.h b/include/tt_treap.h
new file mode 100644
index 0000000..793d536
--- /dev/null
+++ b/include/tt_treap.h
@@ -0,0 +1,40 @@
+#include <stdlib.h>
+#include <stdint.h>
+#include <xorshift64.h>
+
+#ifndef TT_TREAP_H
+#define TT_TREAP_H
+
+// ===================================================================
+// Types
+// ===================================================================
+
+enum TT_FLAG { TT_EXACT, TT_LOWERBOUND, TT_UPPERBOUND };
+
+typedef struct treap_node_s {
+	uint64_t key;
+	uint32_t weight;
+	struct treap_node_s *left, *right, *parent;
+	enum TT_FLAG flag;
+	uint8_t depth;
+	float value;
+} tt_entry_t;
+
+// ===================================================================
+// Globals
+// ===================================================================
+
+extern uint32_t tt_num_cached;
+
+// ===================================================================
+// Methods
+// ===================================================================
+
+int tt_init(void);
+void tt_free(void);
+
+tt_entry_t *tt_seek(uint64_t key);
+int tt_insert(const uint64_t key, const enum TT_FLAG flag,
+							const uint8_t depth, const float value);
+
+#endif