Merge branch 'negamax'

5 files changed, 123 insertions, 123 deletions

diff --git a/include/minimax_cnn1986.h b/include/minimax_cnn1986.h
deleted file mode 100644
index 3bc3301..0000000
--- a/include/minimax_cnn1986.h
+++ /dev/null
@@ -1,19 +0,0 @@
-#include <stdint.h>
-#include "tak.h"
-#include "weights.h"
-
-extern const float infty;
-extern char ct1986_ptn[9];
-extern inline void ct1986_display_progress(const uint8_t);
-
-float
-ct1986_evaluate_black_win(void);
-
-// Generate PTN of the ````best'''' action and store it in ct1986_ptn,
-// along with its value as the return. The ct1986_display_progress
-// function pointer is called on every new square.
-
-float ct1986_generate(const uint8_t max_depth);
-
-extern char ct1986_ptn[9];
-extern float ct1986_optimal;
diff --git a/include/minimax_cnn1986.c b/include/negamax_cnn1986.c
index fed30e2..fafb38c 100644
--- a/include/minimax_cnn1986.c
+++ b/include/negamax_cnn1986.c
@@ -1,4 +1,4 @@
-#include "minimax_cnn1986.h"
+#include "negamax_cnn1986.h"
 
 // ===================================================================
 // Globals
@@ -6,6 +6,7 @@
 
 const float infty = 3.0;
 char ct1986_ptn[9];
+uint8_t ct1986_search_depth = 3;
 
 // ===================================================================
 // Implementation of a small convolutional neural network
@@ -114,14 +115,17 @@ ct1986_evaluate_black_win(void) {
 	DOXORSHIFT;
 	output += fudge.f;
 #endif
-	if (output > 1.0) return 1.0;
-	else if (output < 0.0) return 0.0;
-
-	return output;
+	if (output > 1.0) {
+		return 1.0;
+	}
+	else if (output < 0.0) {
+		return -1.0;
+	}
+	return 2*output-1.0;
 }
 
 // ===================================================================
-// α-β minimax using the above evaluator
+// α-β negamax using the above evaluator
 // ===================================================================
 
 static void
@@ -135,63 +139,61 @@ 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) {
+	colours[location]  = (colours[location] << count) | new_colours;
+	celldat[location]  = top_stone
+		| ((celldat[location] + ((count << NUM_SHIFT))) & NUM_MASK);
+}
+
 static float val;
 static enum WIN_TYPE w;
 
-#define WIN_EVALUATE_OR_RECURSE(store) {		\
+// 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 - 2) w = check_win(); \
 		if (w < 0xFF) { \
-			/* Somebody won, assign weights accordingly */ \
-			if (min == 0) { \
-				if (w == WIN_ROAD_BLACK || w == WIN_FLAT_BLACK) \
-					val = infty; \
-				else val = -infty; \
-			} else { \
-				if (w == WIN_ROAD_WHITE || w == WIN_FLAT_WHITE) \
-					val = -infty; \
-				else val = infty; \
-			} \
-		} else if (cur_depth == max_depth) { \
+			/* 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 = infty/2.0; \
+			else val = -infty; \
+			val *= colour; \
+		} else if (cur_depth == ct1986_search_depth) { \
 			/* We're at the bottom, evaluate */ \
-			val = ct1986_evaluate_black_win(); \
-			if ((ply & 1) == 0) val = 1.0 - 2*val; \
-			if (min) val *= -1; \
+			val = colour * ct1986_evaluate_black_win(); \
 		} else { \
 			/* We're not at the bottom, recurse first */ \
 			next_ply(); \
-			val = ct1986_minimax(cur_depth + 1, max_depth, 1-min, alpha, beta); \
+			val = -ct1986_negamax(cur_depth + 1, -beta, -alpha, -colour); \
 			previous_ply(); \
 		} \
-		/* Update the optimal value */ \
-		if (((min > 0) && (val <= optimal)) \
-				|| ((min == 0) && (val >= optimal))) { \
-			optimal = val; \
-			if (cur_depth == 0) (store); \
-		} \
-		/* Update alpha and beta */ \
-		if (min) { \
-			if (optimal < beta) beta = optimal; \
-		} else { \
-			if (optimal > alpha) alpha = optimal; \
+		{ reset }; \
+		/* Prune */ \
+		if (val >= beta) return beta; \
+		/* Update the optimal value, which alpha carries */ \
+		if (val > alpha) { \
+			alpha = val; \
+			if (cur_depth == 0) { store }; \
 		} \
 	}
 
-// UP DOWN LEFT RIGHT
-static const int8_t deltas[4] = { +5, -5, -1, +1};
-
 float
-ct1986_minimax(const uint8_t cur_depth, const uint8_t max_depth,
-							 const uint8_t min, float alpha, float beta) {
+ct1986_negamax(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));
 
-	// 1.0 is a `certain' black win, -1.0 is a `certain' white win.
-	float optimal = (min) ? infty : -infty;
-
 	// Step across the board
 	for (uint8_t row = 0; row < 5; row++) {
 		for (uint8_t col = 0; col < 5; col++) {
@@ -263,56 +265,55 @@ ct1986_minimax(const uint8_t cur_depth, const uint8_t max_depth,
 								 steps++) {
 							gaps = 0b00000111 >> (4-steps);
 							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;
+									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;
-								}
-								// TODO: Work out what this should be before partition
-
-								// Ensure legal move if we have to crush
-								if (end_stops[dir][1] || drops[steps-1] <= 1) {
-									// Try it, and manually check for win if it's valid
+									// Do it, and manually check for win if it's valid
 									uint8_t j = num;
 									for (uint8_t k = 0; k < steps; k++) {
-										// Dear future me, i'm sorry
 										j -= drops[k];
-										colours[loc+(k+1)*deltas[dir]]  = (colours[loc+(k+1)*deltas[dir]] << drops[k])
-											| ((colours[loc] >> j) & (0xFFFF >> (0x10 - drops[k])));
-										celldat[loc+(k+1)*deltas[dir]]  = (k == steps - 1) ? STONE_AT(loc) : STONE_FLAT
-											| ((celldat[loc+(k+1)*deltas[dir]] + ((drops[k] << NUM_SHIFT))) & NUM_MASK);
+										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, ct1986_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];
+												}
+											}
 										});
-									// Reset the board data
-									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];
-										}
-									}
-									// Prune
-									if (alpha >= beta) return optimal;
 								}
 								/*
 								 * With thanks to
@@ -338,13 +339,12 @@ ct1986_minimax(const uint8_t cur_depth, const uint8_t max_depth,
 					WIN_EVALUATE_OR_RECURSE({
 							// If we did update the optimal value, store
 							generate_place(loc, STONE_FLAT, ct1986_ptn);
+						},{
+							// Reset the state
+							celldat[loc] = 0;
+							if (black) black_count++;
+							else white_count++;
 						});
-					// Reset the state
-					celldat[loc] = 0;
-					if (black) black_count++;
-					else white_count++;
-					// Prune
-					if (alpha >= beta) return optimal;
 
 					// Do the same for walls, can't happen without flats
 					if (standing) {
@@ -354,11 +354,11 @@ ct1986_minimax(const uint8_t cur_depth, const uint8_t max_depth,
 						celldat[loc] = NUM_INC | STONE_STANDING;
 						WIN_EVALUATE_OR_RECURSE({
 								generate_place(loc, STONE_STANDING, ct1986_ptn);
+							},{
+								celldat[loc] = 0;
+								if (black) black_count++;
+								else white_count++;
 							});
-						celldat[loc] = 0;
-						if (black) black_count++;
-						else white_count++;
-						if (alpha >= beta) return optimal;
 					}
 				}
 
@@ -370,20 +370,20 @@ ct1986_minimax(const uint8_t cur_depth, const uint8_t max_depth,
 					celldat[loc] = NUM_INC | STONE_CAPSTONE;
 					WIN_EVALUATE_OR_RECURSE({
 							generate_place(loc, STONE_CAPSTONE, ct1986_ptn);
+						},{
+							celldat[loc] = 0;
+							if (black) black_count |= 128;
+							else white_count |= 128;
 						});
-					celldat[loc] = 0;
-					if (black) black_count |= 128;
-					else white_count |= 128;
-					if (alpha >= beta) return optimal;
 				}
 			}
 			ct1986_display_progress(cur_depth);
 		}
 	}
-	return optimal;
+	return alpha;
 }
 
 inline float
-ct1986_generate(const uint8_t max_depth) {
-	return ct1986_minimax(0, 1+2*max_depth, (ply & 1) ? 0 : 1, -infty, infty);
+ct1986_generate(void) {
+	return ct1986_negamax(0, -infty, infty, (ply&1)?1.0:-1.0);
 }
diff --git a/include/negamax_cnn1986.h b/include/negamax_cnn1986.h
new file mode 100644
index 0000000..411d877
--- /dev/null
+++ b/include/negamax_cnn1986.h
@@ -0,0 +1,18 @@
+#include <stdint.h>
+#include "tak.h"
+#include "weights.h"
+
+extern const float infty;
+extern char ct1986_ptn[9];
+extern uint8_t ct1986_search_depth;
+extern inline void ct1986_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 ct1986_generate(void);
+
+// Internal utility function
+float
+ct1986_evaluate_black_win(void);
diff --git a/include/tak.c b/include/tak.c
index a748555..e400578 100644
--- a/include/tak.c
+++ b/include/tak.c
@@ -109,7 +109,7 @@ try_place(const int8_t location, const enum COLOUR colour,
 // Moving stacks
 // ===================================================================
 
-static 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) {
diff --git a/src/ctaklm.c b/src/ctaklm.c
index a7c299d..a1ca69d 100644
--- a/src/ctaklm.c
+++ b/src/ctaklm.c
@@ -3,7 +3,7 @@
 #include <string.h>
 
 #include <tak.h>
-#include <minimax_cnn1986.h>
+#include <negamax_cnn1986.h>
 
 static const char *blk = "\033[41m", *wht = "\033[44m";
 static const char *und = "\033[4m",  *rst = "\033[0m";
@@ -151,9 +151,9 @@ print_info(void) {
 				 blk, black_count & 127, black_count >> 7, rst);
 }
 
+static int human;
 static char *gamelog = 0;
 static uint8_t auto_board = 0xFF, auto_info = 0xFF;
-static int human, search_depth;
 
 static void
 append_to_gamelog(const char *line, const uint8_t win_line) {
@@ -234,8 +234,8 @@ handle_turn(char *line) {
 static void
 new_game(uint8_t size) {
 	reset_state(size);
-	printf("New %dx%d game! ct1986 at search_depth %d.\n",
-				 size, size, search_depth);
+	printf("New %dx%d game! ct1986 at search depth %d.\n",
+				 size, size, ct1986_search_depth);
 	if (gamelog) gamelog = realloc(gamelog, sizeof(char));
 	else gamelog = malloc(sizeof(char));
 	gamelog[0] = 0;
@@ -308,7 +308,7 @@ ct1986_display_progress(const uint8_t depth) {
 }
 
 static int
-ct1986_turn(const uint8_t search_depth) {
+ct1986_turn(void) {
 	if (won == 0xFF) {
 		// Prepare progress bar
 		fputs("Computing [", stdout);
@@ -317,7 +317,7 @@ ct1986_turn(const uint8_t search_depth) {
 		fflush(stdout);
 		// Run the minimax
 		sum_depth = 0; num_check = 0;
-		float minimax = ct1986_generate(search_depth);
+		float minimax = ct1986_generate();
 		fputs("\033[1C ", stdout);
 		// Failed to find a move?
 		if (minimax <= -infty) {
@@ -353,18 +353,19 @@ info, load, log, new, play (b|w), self-play, square <col><row>, <PTN>.");
 						 blk, eval, rst);
 		} else {
 			printf("White heruistic chance: %s%.2f%s\n",
-						 wht, 100-eval, rst);
+						 wht, -eval, rst);
 		}
 	} else if (!strcmp(line,"log")) {
 		puts(gamelog);
 	} else if (!strcmp(line,"new")) {
 		new_game(5);
 	} else if (!strcmp(line,"self-play")) {
-		while (ct1986_turn(search_depth) == 0);
+		while (ct1986_turn() == 0);
 	} else if (!strncmp(line,"depth",5)) {
 		if (strnlen(line,7) == 7 && line[6] >= '0' && line[6] <= '9') {
-			search_depth = line[6] - '0';
-			printf("New search depth: %d.\n",search_depth);
+			ct1986_search_depth = line[6] - '0';
+			printf("New search depth: %d.\n",
+						 ct1986_search_depth);
 		} else {
 			puts("Usage: depth [0-9].");
 		}
@@ -418,7 +419,7 @@ main(int argc, char **argv) {
 	(void)(argv);
 
 	human = 0;
-	search_depth = 1;
+	ct1986_search_depth = 3;
 	new_game(5);
 
 	char *line = NULL;
@@ -446,7 +447,7 @@ main(int argc, char **argv) {
 		if (read == -1) {
 			playing = 0;
 		} else {
-			ct1986_turn(search_depth);
+			ct1986_turn();
 			human = 0;
 		}
 	}