Merge branch 'pi'

4 files changed, 109 insertions, 84 deletions

diff --git a/include/ct1986.c b/include/minimax_cnn1986.c
index 24c9c64..e89e5a6 100644
--- a/include/ct1986.c
+++ b/include/minimax_cnn1986.c
@@ -1,4 +1,4 @@
-#include "ct1986.h"
+#include "minimax_cnn1986.h"
 
 // ===================================================================
 // Globals
@@ -6,7 +6,6 @@
 
 const float infty = 3.0;
 char ct1986_ptn[9];
-void (*ct1986_display_progress)(const uint8_t);
 
 // ===================================================================
 // Implementation of a small convolutional neural network
@@ -25,13 +24,13 @@ union u_f {
 static uint32_t state = 1;
 static union u_f fudge;
 
-#define DOXORSHIFT { \
+#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))
@@ -139,49 +138,50 @@ previous_ply(void) {
 static float val;
 static enum WIN_TYPE w;
 
-#define WIN_EVALUATE_OR_RECURSE(store) { \
-	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; \
+#define WIN_EVALUATE_OR_RECURSE(store) {		\
+		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) { \
+			/* We're at the bottom, evaluate */ \
+			val = ct1986_evaluate_black_win(); \
+			if ((ply & 1) == 0) val = val - 1.0; \
 		} else { \
-			if (w == WIN_ROAD_WHITE || w == WIN_FLAT_WHITE) \
-				val = -infty; \
-			else val = infty; \
+			/* We're not at the bottom, recurse first */ \
+			next_ply(); \
+			val = ct1986_minimax(cur_depth + 1, max_depth, 1-min, alpha, beta); \
+			previous_ply(); \
 		} \
-	} else if (cur_depth == max_depth) { \
-		/* We're at the bottom, evaluate */ \
-		val = ct1986_evaluate_black_win(); \
-		if ((ply & 1) == 0) val = val - 1.0; \
-	} else { \
-		/* We're not at the bottom, recurse first */ \
-		next_ply(); \
-		val = ct1986_minimax(cur_depth + 1, max_depth, 1-min, alpha, beta); \
-		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; \
-	} \
-}
+		/* 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; \
+		} \
+	}
+
+// 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) {
-
-	enum E_RESULT r;
 	const uint8_t black = (ply & 1),
 		material = (black) ? black_count : white_count,
 		flat = material & 127,
@@ -200,19 +200,47 @@ ct1986_minimax(const uint8_t cur_depth, const uint8_t max_depth,
 			// 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?
-				// I'm not a huge fan of looping through enums, but it's
-				// better than manually unrolling this. Sufficiently smart
-				// compilers?
+
+				// 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;
+						}
+						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 (*)
+				// 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) {
@@ -221,35 +249,17 @@ ct1986_minimax(const uint8_t cur_depth, const uint8_t max_depth,
 							celldat_backup[x] = celldat[THE_COORDS(x, row)];
 						}
 					}
-					 /*
-						* We don't do anything terribly efficient or smart here,
-						* just try all the ordered partitions of num ∈ {1,…,count}
-						* that will fit on the board in the current direction.
-						* Recall that count = max(stack height, carry limit).
-						*/
-					uint8_t upper;
-					switch (dir) {
-						case M_UP:    {
-							upper = (4-row > count) ? count : 4-row;
-							break;
-						}
-						case M_DOWN:  {
-							upper = (row > count) ? count : row;
-							break;
-						}
-						case M_LEFT:   {
-							upper = (col > count) ? count : col;
-							break;
-						}
-						case M_RIGHT: // fall through
-						default: {
-							upper = (4-col > count) ? count : 4-col;
-							break;
-						}
-					}
+					/*
+					 * 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 <= upper && steps <= num; steps++) {
+						for (uint8_t steps = 1;
+								 steps <= end_stops[dir][0] && steps <= num;
+								 steps++) {
 							gaps = 0b00000111 >> (4-steps);
 							do  {
 								// Translate to a drop sequence
@@ -263,9 +273,24 @@ ct1986_minimax(const uint8_t cur_depth, const uint8_t max_depth,
 									}
 									mask <<= 1;
 								}
-								// Try it, and manually check for win if it's valid
-								r = try_move(loc, dir, steps, drops);
-								if (r == ACT_OK) {
+								// 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
+									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);
+									}
+									// 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({
@@ -285,9 +310,9 @@ ct1986_minimax(const uint8_t cur_depth, const uint8_t max_depth,
 											celldat[THE_COORDS(x, row)] = celldat_backup[x];
 										}
 									}
+									// Prune
+									if (alpha >= beta) return optimal;
 								}
-								// Prune
-								if (alpha >= beta) return optimal;
 								/*
 								 * With thanks to
 								 * https://graphics.stanford.edu/~seander/bithacks.html#NextBitPermutation
@@ -310,9 +335,9 @@ ct1986_minimax(const uint8_t cur_depth, const uint8_t max_depth,
 					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, ct1986_ptn);
-							});
+							// 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++;
@@ -359,5 +384,5 @@ ct1986_minimax(const uint8_t cur_depth, const uint8_t max_depth,
 
 inline float
 ct1986_generate(const uint8_t max_depth) {
-	return ct1986_minimax(0, max_depth, (ply & 1) ? 0 : 1, -infty, infty);
+	return ct1986_minimax(0, 1+2*max_depth, (ply & 1) ? 0 : 1, -infty, infty);
 }
diff --git a/include/ct1986.h b/include/minimax_cnn1986.h
index 3f2568d..3ccc004 100644
--- a/include/ct1986.h
+++ b/include/minimax_cnn1986.h
@@ -4,7 +4,7 @@
 
 extern const float infty;
 extern char ct1986_ptn[9];
-extern void (*ct1986_display_progress)(const uint8_t);
+extern inline void ct1986_display_progress(const uint8_t);
 
 float
 ct1986_evaluate_black_win(void);
diff --git a/include/tak.c b/include/tak.c
index 3d3ba0f..a748555 100644
--- a/include/tak.c
+++ b/include/tak.c
@@ -15,7 +15,6 @@ uint8_t white_count, black_count, ply;
 // Helpers
 // ===================================================================
 
-#define NUM_MASK      (0xF<<NUM_SHIFT) // 0b11110000
 #define DFS_MASK      0b00001100
 #define NOT_DFS_MASK  0b11110011
 
diff --git a/include/tak.h b/include/tak.h
index 0a97c2d..1d49720 100644
--- a/include/tak.h
+++ b/include/tak.h
@@ -20,6 +20,7 @@ typedef uint8_t data_t;
 typedef uint16_t colour_stack_t;
 
 #define NUM_SHIFT           4
+#define NUM_MASK            (0xF<<NUM_SHIFT) // 0b11110000
 #define NUM_INC             (0x1<<NUM_SHIFT) // 0b00010000
 #define STONE_MASK          0b00000011
 #define STONE_AT(l)         (celldat[(l)] & STONE_MASK)