There is still a bug, it doesn't appear to be checking enough

4 files changed, 135 insertions, 128 deletions

diff --git a/include/action_list.c b/include/action_list.c
index c407ae9..9ddd74b 100644
--- a/include/action_list.c
+++ b/include/action_list.c
@@ -13,6 +13,13 @@ action_list_prepend(action_list_t *list, const enum A_TYPE type,
 										const int8_t loc, const uint8_t data0,
 										const uint8_t data1);
 
+static inline void
+inline_next_ply(void);
+
+static inline void
+inline_prev_ply(void);
+
+
 // ===================================================================
 // Exported method implementations
 // ===================================================================
@@ -40,114 +47,123 @@ void action_list_init(void) {
 }
 
 action_list_t *action_list_generate(void) {
-	action_list_t *result = malloc(sizeof(struct action_list_s));
+	action_list_t *list = malloc(sizeof(struct action_list_s));
 	// TODO: trap errno
-	result->length = 0;
-	result->head = NULL;
+	list->length = 0;
+	list->head = NULL;
+
+	/*
+	 * The check for whether it's a black piece to be played is actually
+	 *     black = (ply < 2) ? (ply==1) : (ply & 1),
+	 * but material will always be sufficient in ply < 2 so we might as
+	 * well save on the conditional.
+	 */
 
-	const uint8_t black = (ply < 2) ? (ply==1) : (ply & 1),
-		material = (black) ? black_count : white_count,
+	const uint8_t material = (ply & 1) ? black_count : white_count,
 		flat = material & 0x7F,
-		cap = (ply >= 2 && (material & 0x80)),
-		standing = (ply >= 2 && flat);
+		cap = ((ply >= 2) && (material & 0x80)),
+		standing = ((ply >= 2) && flat);
 
 	// Step across the board, reversed because we prepend to the list
-	for (int8_t row = board_size - 1; row >= 0; row--) {
-		for (int8_t col = board_size - 1; col >= 0; col--) {
+	for (int row = board_size - 1; row >= 0; row--) {
+		for (int col = board_size - 1; col >= 0; col--) {
 			// We'll need these at various points: the location of this
 			// square and the maximum number of stones we could pick up
-			const int8_t loc = THE_COORDS(col, row);
+			const int loc = THE_COORDS(col, row);
 			const uint8_t count = DANGER_MIN(COUNT_AT(loc), board_size);
-			// Only try moves after CPS
-			if (ply >= 2 && count && ((colours[loc] & 1) == current_colour)) {
-				// There are stones, let's try moving them
-
-				// Pre-compute end-stops and crushes
-				uint8_t end_stops[4], crushes[4] = {0, 0, 0, 0};
-
-				// These are upper bounds, not counting walls and such. UP DOWN LEFT RIGHT
-				end_stops[0] = DANGER_MIN(board_size - row - 1, count);
-				end_stops[1] = DANGER_MIN(row, count);
-				end_stops[2] = DANGER_MIN(col, count);
-				end_stops[3] = DANGER_MIN(board_size - col - 1, count);
-
-				// Now we check for caps and walls
-				const uint8_t cap_top = STONE_AT(loc) == STONE_CAPSTONE;
-				for (uint8_t d = 0; d < 4; d++){
-					const int8_t delta = deltas[d];
-					const uint8_t stop = end_stops[d];
-					end_stops[d] = 0;
-					for (uint8_t k = 1; k <= stop; k++) {
-						const enum STONE_VARIANT stone = STONE_AT(loc+k*delta);
-						if (stone == STONE_STANDING) {
-							if (cap_top) {
-								crushes[d] = 0xFF;
-								end_stops[d]++;
+
+			// Only try moves after CPS and if the colour is correct
+			if (count) {
+				if (ply >= 2 && ((colours[loc] & 1) == current_colour)) {
+
+					// Pre-compute end-stops and crushes
+					uint8_t end_stops[4], crushes[4] = {0, 0, 0, 0};
+
+					// These are upper bounds, not counting walls and such.
+					// UP DOWN LEFT RIGHT
+					end_stops[0] = DANGER_MIN(board_size - row - 1, count);
+					end_stops[1] = DANGER_MIN(row, count);
+					end_stops[2] = DANGER_MIN(col, count);
+					end_stops[3] = DANGER_MIN(board_size - col - 1, count);
+
+					// Now we check for caps and walls
+					const uint8_t cap_top = STONE_AT(loc) == STONE_CAPSTONE;
+					for (int d = 0; d < 4; d++){
+						const int delta = deltas[d];
+						const int stop = end_stops[d];
+						end_stops[d] = 0;
+						for (int k = 1; k <= stop; k++) {
+							const enum STONE_VARIANT stone = STONE_AT(loc+k*delta);
+							if (stone == STONE_STANDING) {
+								if (cap_top) {
+									crushes[d] = 0xFF;
+									end_stops[d]++;
+								}
+								break;
+							} else if (stone == STONE_CAPSTONE) {
+								break;
 							}
-							break;
-						} else if (stone == STONE_CAPSTONE) {
-							break;
+							end_stops[d]++;
 						}
-						end_stops[d]++;
 					}
-				}
-				/*
-				 * For each direction, generate all possible ordered integer
-				 * partitions of 1 ≤ num ≤ count whose number of summands is
-				 * exactly 1 ≤ summands ≤ min(end_stops[dir], num) -- we write
-				 * summands as steps
-				 */
-				for (enum MOVE_DIRECTION dir = M_UP; dir <= M_RIGHT; dir++) {
-					for (uint8_t num = 1; num <= count; num++) {
-						for (uint8_t steps = 1;
-								 steps <= end_stops[dir] && steps <= num;
-								 steps++) {
-							// TODO: Generalise to board_size!
-							uint8_t gaps = 0x07 >> (board_size-steps-1);
-							// 0b0000[0111] because 4-1=3 and 5-1=4
-							do  {
-								/*
-								 * We skip the partition if it calls for multiple stones at
-								 * the end with a crush.
-								 */
-								const uint8_t last_drop_check =
-									(num > 1) ? (gaps & 1<<(num - 2)) : 1;
-								if (crushes[dir] == 0 || last_drop_check) {
-									// We have to record a crush!
-									// THIS IS WHERE THE PROBLEM IS
-									const uint8_t crush = (steps == end_stops[dir]) && crushes[dir];
-									action_list_prepend(result, A_MOVE, loc,
-																			(crush << 7) | gaps,
-																			(dir<<4) | num);
-								}
-								/*
-								 * 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
-								 */
-								uint8_t t = (gaps | (gaps - 1));
-								gaps = (t + 1) | (((~t & -~t) - 1) >> (__builtin_ctz(gaps) + 1));
-							} while (gaps && (gaps + 1 <= (1<<(num-1))));
+					/*
+					 * For each direction, generate all possible ordered integer
+					 * partitions of 1 ≤ num ≤ count whose number of summands is
+					 * exactly 1 ≤ summands ≤ min(end_stops[dir], num) -- we
+					 * write summands as steps
+					 */
+					for (enum MOVE_DIRECTION dir=M_UP; dir<=M_RIGHT; dir++) {
+						for (uint8_t num = 1; num <= count; num++) {
+							for (uint8_t steps = 1;
+									 steps <= end_stops[dir] && steps <= num;
+									 steps++) {
+								// TODO: Generalise to board_size!
+								uint8_t gaps = 0x07 >> (board_size-steps-1);
+								// 0b0000[0111] because 4-1=3 and 5-1=4
+								do  {
+									/*
+									 * We skip the partition if it calls for multiple
+									 * stones at the end with a crush.
+									 */
+									const uint8_t last_drop_check =
+										(num > 1) ? (gaps & (1 << (num - 2))) : 1;
+									if (crushes[dir] == 0 || last_drop_check) {
+										// We have to record a crush!
+										const uint8_t crush =
+											(steps == end_stops[dir]) && crushes[dir];
+										// Store the move
+										action_list_prepend(list, A_MOVE, loc,
+																				(crush << 7) | gaps,
+																				(dir<<4) | num);
+									}
+									/*
+									 * 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
+									 */
+									uint8_t t = (gaps | (gaps - 1));
+									gaps = (t + 1)
+										| (((~t & -~t) - 1) >> (__builtin_ctz(gaps) + 1));
+								} while (gaps && (gaps + 1 <= (1 << (num - 1))));
+							}
 						}
 					}
 				}
-			} else if (count == 0 && material) {
+			} // end of if (count) { ... }
+			else if (material) {
 				// Empty square, generate placements
 				if (flat) {
-					action_list_prepend(result, A_PLACE, loc,
-															STONE_FLAT, 0);
+					action_list_prepend(list, A_PLACE, loc, STONE_FLAT, 0);
 					if (standing)
-						action_list_prepend(result, A_PLACE, loc,
-																STONE_STANDING, 0);
+						action_list_prepend(list, A_PLACE, loc, STONE_STANDING,0);
 				}
 				if (cap)
-					action_list_prepend(result, A_PLACE, loc,
-															STONE_CAPSTONE, 0);
+					action_list_prepend(list, A_PLACE, loc, STONE_CAPSTONE, 0);
 			}
 		}
 	}
-	return result;
+	return list;
 }
 
 void action_take(action_node_t *action) {
@@ -227,24 +243,12 @@ void action_take(action_node_t *action) {
 		celldat[loc] -= total*NUM_INC;
 	}
 	// Next ply
-	ply++;
-	if (ply == 2) {
-		current_colour = C_WHITE;
-	} else {
-		if (current_colour == C_BLACK) current_colour = C_WHITE;
-		else current_colour = C_BLACK;
-	}
+	inline_next_ply();
 }
 
 void action_undo(action_node_t *action) {
 	// Previous ply
-	if (ply>0) ply--;
-	if (ply == 1) {
-		current_colour = C_WHITE;
-	} else {
-		if (current_colour == C_BLACK) current_colour = C_WHITE;
-		else current_colour = C_BLACK;
-	}
+	inline_prev_ply();
 
 	const int8_t loc = action->loc;
 	if (action->type == A_PLACE) {
@@ -342,3 +346,25 @@ action_list_prepend(action_list_t *list, const enum A_TYPE type,
 	new->next = list->head;
 	list->head = new;
 }
+
+static inline void
+inline_next_ply(void) {
+	ply++;
+	if (ply == 2) {
+		current_colour = C_WHITE;
+	} else {
+		if (current_colour == C_BLACK) current_colour = C_WHITE;
+		else current_colour = C_BLACK;
+	}
+}
+
+static inline void
+inline_prev_ply(void) {
+	if (ply>0) ply--;
+	if (ply == 1) {
+		current_colour = C_WHITE;
+	} else {
+		if (current_colour == C_BLACK) current_colour = C_WHITE;
+		else current_colour = C_BLACK;
+	}
+}
diff --git a/include/cnn1986.c b/include/cnn1986.c
index 17d4e84..ada1766 100644
--- a/include/cnn1986.c
+++ b/include/cnn1986.c
@@ -9,21 +9,6 @@ static float flattened[CONV_NUM+2];
 static float dense1[DENSE1_NUM];
 static float dense2[DENSE2_NUM];
 
-#ifndef DETERMINISTIC
-union u_f {
-	uint32_t u;
-	float f;
-};
-
-static union u_f fudge;
-
-#define RANDF { \
-	XORSHIFT; \
-	fudge.u = 0x3f800000 | RANDOM32 >> 10; \
-	fudge.f = (fudge.f - 1.5) * 0.01; \
-	}
-#endif
-
 #define RELU(x) ((x) = ((x)<0)?0:(x))
 
 float cnn1986_evaluate_black_win(void) {
@@ -100,12 +85,6 @@ 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
- */
 	if (output > 1.0) {
 		return 1.0;
 	}
diff --git a/include/negamax.c b/include/negamax.c
index 912705d..8b7345f 100644
--- a/include/negamax.c
+++ b/include/negamax.c
@@ -123,20 +123,22 @@ negamax(const uint8_t cur_depth, float alpha, float beta,
 		action_take(node);
 
 		// Compute the value of the node
+		float node_value;
 		if (ply >= 2*board_size - 2 && (w = check_win()) < 0xFF) {
-			float winnings = -colour*infty;
+			node_value = -colour*infty;
 			// Check win if far enough into the game
-			if (w == WIN_ROAD_BLACK || w == WIN_FLAT_BLACK) winnings = colour*infty;
-			else if (w == WIN_DRAW) winnings = 0; // Draw is fixed at neutral
-			value = fmax(value, winnings);
+			if (w == WIN_ROAD_BLACK || w == WIN_FLAT_BLACK) node_value = colour*infty;
+			else if (w == WIN_DRAW) node_value = 0; // Draw is fixed at neutral
 		} else if (cur_depth > 1) {
 			// If nobody won, or too early, recurse if not a leaf
-			value = fmax(value, -negamax(cur_depth - 1, -beta, -alpha, -colour));
+			node_value = -negamax(cur_depth - 1, -beta, -alpha, -colour);
 		} else {
 			// Recursion would take us to a leaf, evaluate
-			value = fmax(value, colour*cnn1986_evaluate_black_win());
+			node_value = colour * cnn1986_evaluate_black_win();
 		}
 
+		value = fmax(value, node_value);
+
 		action_undo(node);
 
 		negamax_display_progress(cur_depth, list->length);
diff --git a/src/ctaklm.c b/src/ctaklm.c
index dda6eb1..a3685db 100644
--- a/src/ctaklm.c
+++ b/src/ctaklm.c
@@ -416,7 +416,7 @@ main(int argc, char **argv) {
 	(void)(argc);
 	(void)(argv);
 
-	negamax_search_depth = 5;
+	negamax_search_depth = 4;
 	new_game(5);
 	negamax_init(5);
 	tt_init();