Trying caching to speed things up

7 files changed, 305 insertions, 212 deletions

diff --git a/include/cnn1986_cache.c b/include/cnn1986_cache.c
new file mode 100644
index 0000000..d9545ac
--- /dev/null
+++ b/include/cnn1986_cache.c
@@ -0,0 +1,98 @@
+#include "cnn1986_cache.h"
+
+#define DATA_STONE_SHIFT 6
+#define DATA_COUNT_SHIFT (DATA_STONE_SHIFT+2)
+#define COLOUR_MASK      0x3F // 0b00111111
+
+uint32_t cnn1986_num_cached, cnn1986_max_num_cached;
+node_t *head = NULL, *tail = NULL;
+
+void cnn1986_cache_free(void) {
+	node_t *c = head, *n;
+	while (c) {
+		n = c->next;
+		free(c);
+		c = n;
+	}
+	head = NULL;
+	tail = NULL;
+}
+
+int cnn1986_cache_seek(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;
+				}
+			}
+		} 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;
+				if (c->next) c->next->prev = c->prev;
+				c->prev->next = c->next;
+				c->prev = NULL;
+				c->next = head;
+				head->prev = c;
+				head = c;
+			}
+
+			return EXIT_SUCCESS;
+		}
+	} while (c);
+
+	// Failed to find it
+	return EXIT_FAILURE;
+}
+
+int cnn1986_cache_insert(float in_result) {
+	node_t *new = malloc(sizeof(node_t));
+	if (new == NULL) return EXIT_FAILURE;
+	// TODO: check errno
+	new->prev = NULL;
+	new->next = head;
+	if (head) head->prev = new;
+	head = new;
+	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++;
+
+	if (cnn1986_num_cached > cnn1986_max_num_cached) {
+		tail = tail->prev;
+		free(tail->next);
+		tail->next = NULL;
+		cnn1986_num_cached--;
+	}
+
+	return EXIT_SUCCESS;
+}
diff --git a/include/cnn1986_cache.h b/include/cnn1986_cache.h
new file mode 100644
index 0000000..8d82ee9
--- /dev/null
+++ b/include/cnn1986_cache.h
@@ -0,0 +1,18 @@
+#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;
+	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);
diff --git a/include/lcdlib.c b/include/lcdlib.c
index ea47062..0933b2c 100644
--- a/include/lcdlib.c
+++ b/include/lcdlib.c
@@ -1,15 +1,10 @@
 #include "lcdlib.h"
 
-// ===================================================================
-// Globals
-// ===================================================================
-
 static char previous_lines[LCD_HEIGHT][LCD_WIDTH+1];
+static const char* esc = "\x1B[L";
 static FILE *lcd = NULL;
 static int line_idx;
 
-static const char* esc = "\x1B[L";
-
 int
 lcd_begin(void) {
 	lcd = fopen("/dev/lcd", "w");
diff --git a/include/negamax_cnn1986.c b/include/negamax_cnn1986.c
index 3aa282f..b9d618d 100644
--- a/include/negamax_cnn1986.c
+++ b/include/negamax_cnn1986.c
@@ -7,6 +7,7 @@
 const float infty = 3.0;
 char negamax_cnn1986_ptn[9];
 uint8_t negamax_cnn1986_search_depth = 3;
+uint8_t negamax_cnn1986_cache_threshold = 3;
 
 // ===================================================================
 // Implementation of a small convolutional neural network
@@ -192,234 +193,203 @@ 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) {
-	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 < 5; row++) {
-		for (uint8_t col = 0; col < 5; 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);
-			// 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?
+	if (cnn1986_cache_seek(&alpha)) {
+		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));
 
-				// 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[1][0] = (row > count) ? count : row;
-				end_stops[2][0] = (col > count) ? count : col;
-				end_stops[3][0] = (4-col > count) ? count : 4-col;
-				const uint8_t cap_top = STONE_AT(loc) == STONE_CAPSTONE;
-				for (uint8_t d = 0; d < 4; 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]++;
+		// Step across the board
+		for (uint8_t row = 0; row < 5; row++) {
+			for (uint8_t col = 0; col < 5; 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);
+				// 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?
+
+					// 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[1][0] = (row > count) ? count : row;
+					end_stops[2][0] = (col > count) ? count : col;
+					end_stops[3][0] = (4-col > count) ? count : 4-col;
+					const uint8_t cap_top = STONE_AT(loc) == STONE_CAPSTONE;
+					for (uint8_t d = 0; d < 4; 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;
 							}
-							break;
-						} else if (stone == STONE_CAPSTONE) {
-							break;
+							end_stops[d][0]++;
 						}
-						end_stops[d][0]++;
 					}
-				}
 
-				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++) {
-					colours_backup[y] = colours[THE_COORDS(col, y)];
-					celldat_backup[y] = celldat[THE_COORDS(col, y)];
-				}
+					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++) {
+						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 < 5; 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 < 5; 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++) {
-							gaps = 0x07 >> (4-steps); // 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; // (*) we don't need to bounds check
-										} else {
-											drops[idx] += 1;
+						/*
+						 * 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++) {
+								gaps = 0x07 >> (4-steps); // 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; // (*) we don't need to bounds check
+											} else {
+												drops[idx] += 1;
+											}
+											mask <<= 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);
-									}
-									// 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;
+										// 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_cnn1986_ptn);
-										},{
-											// Reset the board data after recursing or
-											// before returning
-											if (dir <= M_DOWN) {
-												for (uint8_t y = 0; y < 5; 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++) {
-													colours[THE_COORDS(x, row)] = colours_backup[x];
-													celldat[THE_COORDS(x, row)] = celldat_backup[x];
+										// 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_cnn1986_ptn);
+											},{
+												// Reset the board data after recursing or
+												// before returning
+												if (dir <= M_DOWN) {
+													for (uint8_t y = 0; y < 5; 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++) {
+														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))));
+											});
+									}
+									/*
+									 * 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
+				} 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;
-					/*
-					 * w = 0xFF;
-					 * if (ply >= 2*5 - 3) w = check_win();
-					 * if (w < 0xFF) {
-					 *	/\* Somebody won, assign weights accordingly. Note in particular
-					 *		 that draws are only worth ∞/2 ;)
-					 *	*\/
-					 *	if (w == WIN_ROAD_BLACK || w == WIN_FLAT_BLACK)
-					 *		val = infty;
-					 *	else if (w == WIN_DRAW) val = 0;
-					 *	else val = -infty;
-					 *	val *= colour;
-					 * } else if (cur_depth == negamax_cnn1986_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);
-					 *	previous_ply();
-					 * }
-					 * celldat[loc] = 0;
-					 * if (black) black_count++;
-					 * else white_count++;
-					 * /\* Prune *\/
-					 * if (val >= beta) return beta;
-					 * /\* Update the optimal value, which alpha carries *\/
-					 * if (val > alpha) {
-					 *	alpha = val;
-					 *	if (cur_depth == 0) {
-					 *		generate_place(loc, STONE_FLAT, negamax_cnn1986_ptn);
-					 *		/\* Did we win? *\/
-					 *		if (alpha >= infty && w < 0xFF)
-					 *			return alpha;
-					 *	};
-					 * }
-					 */
-					WIN_EVALUATE_OR_RECURSE({
-							// If we did update the optimal value, store
-							generate_place(loc, STONE_FLAT, negamax_cnn1986_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 (flat) {
+						// Generate the placement
 						if (black) black_count--;
 						else white_count--;
 						colours[loc] = current_colour;
-						celldat[loc] = NUM_INC | STONE_STANDING;
+						celldat[loc] = NUM_INC | STONE_FLAT;
 						WIN_EVALUATE_OR_RECURSE({
-								generate_place(loc, STONE_STANDING, negamax_cnn1986_ptn);
+								// If we did update the optimal value, store
+								generate_place(loc, STONE_FLAT, negamax_cnn1986_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_cnn1986_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_cnn1986_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_cnn1986_ptn);
+							},{
+								celldat[loc] = 0;
+								if (black) black_count |= 128;
+								else white_count |= 128;
+							});
+					}
 				}
+				negamax_cnn1986_display_progress(cur_depth);
 			}
-			negamax_cnn1986_display_progress(cur_depth);
 		}
+		// Insert into the cache if we're not too deep
+		if (cur_depth < negamax_cnn1986_cache_threshold)
+			cnn1986_cache_insert(alpha);
 	}
 	return alpha;
 }
diff --git a/include/negamax_cnn1986.h b/include/negamax_cnn1986.h
index 799ca4c..3002837 100644
--- a/include/negamax_cnn1986.h
+++ b/include/negamax_cnn1986.h
@@ -1,10 +1,12 @@
 #include <stdint.h>
-#include "tak.h"
+#include <tak.h>
+#include <cnn1986_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
diff --git a/src/ct1986.c b/src/ct1986.c
index 40943db..e440255 100644
--- a/src/ct1986.c
+++ b/src/ct1986.c
@@ -145,14 +145,18 @@ main(int argc, char **argv) {
 	if (lcd_begin() != EXIT_SUCCESS)
 		return EXIT_FAILURE;
 
-	human = 0;
+	cnn1986_max_num_cached = 500;
+	negamax_cnn1986_search_depth = 3;
+	negamax_cnn1986_cache_threshold = 2;
 	negamax_cnn1986_search_depth = 3;
+
 	new_game(5);
 
 	char *line = NULL;
 	ssize_t read;
 	size_t alloc_size;
 
+	human = 0;
 	for (int playing = 1; playing;) {
 		while (human == 0) {
 			if (ply & 1) lcd_put_line(L_SCROLL, "Black: ");
@@ -177,6 +181,7 @@ main(int argc, char **argv) {
 		}
 	}
 
+	cnn1986_cache_free();
 	lcd_end();
 	return EXIT_SUCCESS;
 }
diff --git a/src/ctaklm.c b/src/ctaklm.c
index 805e54d..44428c8 100644
--- a/src/ctaklm.c
+++ b/src/ctaklm.c
@@ -214,7 +214,7 @@ handle_turn(char *line) {
 					case WIN_ROAD_WHITE: { end_game(line,"R-0");     break; }
 				}
 			}
-			puts("Game over, enter `new' to play again.");
+			puts("Enter `new' to play again.");
 			if (! new_win) return EXIT_FAILURE;
 			break;
 		}
@@ -317,7 +317,7 @@ negamax_cnn1986_turn(void) {
 		// Run the minimax
 		sum_depth = 0; num_check = 0; progress = 0;
 		float minimax = negamax_cnn1986_generate();
-		putchar('\n');
+		printf(" [%d]\n", cnn1986_num_cached);
 		// Failed to find a move?
 		if (minimax < -infty) {
 			puts("Opponent failed to find a move!");
@@ -416,14 +416,16 @@ main(int argc, char **argv) {
 	(void)(argc);
 	(void)(argv);
 
-	human = 0;
+	cnn1986_max_num_cached = 500;
 	negamax_cnn1986_search_depth = 3;
+	negamax_cnn1986_cache_threshold = 3;
 	new_game(5);
 
 	char *line = NULL;
 	ssize_t read = -1;
 	size_t alloc_size;
 
+	human = 0;
 	for (int playing = 1; playing;) {
 		while (human == 0) {
 			fputs("ctaklm> ", stdout);
@@ -447,5 +449,8 @@ main(int argc, char **argv) {
 			human = 0;
 		}
 	}
-	return 0;
+
+	cnn1986_cache_free();
+
+	return EXIT_SUCCESS;
 }