Finally fixed move generation

1 files changed, 72 insertions, 36 deletions

diff --git a/include/ct1986.c b/include/ct1986.c
index d5325be..ec73f7c 100644
--- a/include/ct1986.c
+++ b/include/ct1986.c
@@ -17,9 +17,21 @@ static float dense1[DENSE1_NUM];
 static float dense2[DENSE2_NUM];
 
 #ifndef DETERMINISTIC
-static uint32_t x = 1;
-#define DOXORSHIFT { x ^= x << 13; x ^= x >> 17; x ^= x << 5; }
-#define FUDGE (((float)(x&255))/255.0-0.5)*0.2
+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))
@@ -101,7 +113,7 @@ ct1986_evaluate_black_win(void) {
 	output = (12.0+output+50.0*output/(output*output+10.0))/24.0;
 #ifndef DETERMINISTIC
 	DOXORSHIFT;
-	output += FUDGE;
+	output += fudge.f;
 #endif
 	if (output > 1.0) return 1.0;
 	else if (output < 0.0) return 0.0;
@@ -152,8 +164,8 @@ static enum WIN_TYPE w;
 		previous_ply(); \
 	} \
 	/* Update the optimal value */ \
-	if (((min > 0) && (val < optimal)) \
-			|| ((min == 0) && (val > optimal))) { \
+	if (((min > 0) && (val <= optimal)) \
+			|| ((min == 0) && (val >= optimal))) { \
 		optimal = val; \
 		if (cur_depth == 0) (store); \
 	} \
@@ -184,7 +196,7 @@ ct1986_minimax(const uint8_t cur_depth, const uint8_t max_depth,
 		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);
+			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?
@@ -193,7 +205,9 @@ ct1986_minimax(const uint8_t cur_depth, const uint8_t max_depth,
 				// compilers?
 
 				uint16_t colours_backup[5];
-				uint8_t celldat_backup[5], drops[5-1];
+				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)];
@@ -207,34 +221,48 @@ 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 everything...
-
-					// For every number of steps
-					for (uint8_t steps = 1; steps < 5 && steps <= count; steps++) {
-						uint8_t idx, carry;
-						for (idx = 0; idx < steps; idx++) drops[idx]=0;
-						idx = 0;
-						while (idx < steps) {
-							// Increment the drop sequence
-							carry = 0;
-							drops[idx]++;
-							do {
-								if (carry) {
-									idx++;
-									if (idx >= steps) break;
-									drops[idx]++;
-									carry = 0;
-								}
-								if (drops[idx] > count || drops[idx] > 5) {
-									drops[idx] = 1; carry = 1;
+					 /*
+						* 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:  {
+							upper = (4-col > count) ? count : 4-col;
+							break;
+						}
+					}
+					uint8_t gaps, t, idx, mask;
+					for (uint8_t num = 1; num <= count; num++) {
+						for (uint8_t steps = 1; steps <= upper && steps <= num; steps++) {
+							gaps = 0b00000111 >> (4-steps);
+							do  {
+								// 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;
 								}
-							} while (carry && idx < steps);
-							// If carry is still set here we're done
-							if (carry == 0) {
-								// Try it, and note that try_move will never return
-								// GAME_END. It does not check for winners, but we do
-								// manually.
+								// Try it, and manually check for win if it's valid
 								r = try_move(loc, dir, steps, drops);
 								if (r == ACT_OK) {
 									// First check for wins, if we're at the bottom
@@ -259,7 +287,15 @@ ct1986_minimax(const uint8_t cur_depth, const uint8_t max_depth,
 								}
 								// Prune
 								if (alpha >= beta) return optimal;
-							}
+								/*
+								 * 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))));
 						}
 					}
 				}