Still bugs...

3 files changed, 119 insertions, 65 deletions

diff --git a/include/action_list.c b/include/action_list.c
index b338627..b11bae7 100644
--- a/include/action_list.c
+++ b/include/action_list.c
@@ -4,6 +4,8 @@
 // Helper method declarations
 // ===================================================================
 
+#define DANGER_MIN(a,b) (((a)<(b))?(a):(b))
+
 #define CLR_STONE NUM_MASK
 
 static inline void
@@ -45,9 +47,9 @@ action_list_t *action_list_generate(void) {
 
 	const uint8_t black = (ply < 2) ? (ply==1) : (ply & 1),
 		material = (black) ? black_count : white_count,
-		flat = material & 127,
-		cap = (ply >= 2 && (material & 128)),
-		standing = (ply >= 2 && (material & 127));
+		flat = material & 0x7F,
+		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--) {
@@ -55,39 +57,38 @@ action_list_t *action_list_generate(void) {
 			// 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 uint8_t count = (COUNT_AT(loc) > board_size) ? board_size : COUNT_AT(loc);
+			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
-				uint8_t end_stops[4][2]; // (end, not_crush)
+				// 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][0] = (board_size - row - 1 > count) ? count : board_size - row - 1;
-				end_stops[1][0] = (row > count) ? count : row;
-				end_stops[2][0] = (col > count) ? count : col;
-				end_stops[3][0] = (board_size - col - 1 > count) ? count : board_size - col - 1;
+				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];
-					end_stops[d][1] = 1;
-					const uint8_t stop = end_stops[d][0];
-					end_stops[d][0] = 0;
+					const uint8_t stop = end_stops[d];
+					end_stops[d] = 0;
 					for (uint8_t k = 1; k <= stop; k++) {
-						const uint8_t stone = STONE_AT(loc+k*delta);
+						const enum STONE_VARIANT stone = STONE_AT(loc+k*delta);
 						if (stone == STONE_STANDING) {
 							if (cap_top) {
-								end_stops[d][1] = 0;
-								end_stops[d][0]++;
+								crushes[d] = 0xFF;
+								end_stops[d]++;
 							}
 							break;
 						} else if (stone == STONE_CAPSTONE) {
 							break;
 						}
-						end_stops[d][0]++;
+						end_stops[d]++;
 					}
 				}
 				/*
@@ -99,7 +100,7 @@ action_list_t *action_list_generate(void) {
 				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][0] && steps <= num;
+								 steps <= end_stops[dir] && steps <= num;
 								 steps++) {
 							// TODO: Generalise to board_size!
 							uint8_t gaps = 0x07 >> (board_size-steps-1);
@@ -111,8 +112,14 @@ action_list_t *action_list_generate(void) {
 								 */
 								const uint8_t last_drop_check =
 									(num > 1) ? (gaps & 1<<(num - 2)) : 1;
-								if (end_stops[dir][1] || last_drop_check)
-									action_list_prepend(result, A_MOVE, loc, gaps, (dir<<4) | num);
+								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
@@ -163,15 +170,22 @@ void action_take(action_node_t *action) {
 				break;
 			}
 			default: {
-				if (black) black_count &= 127;
-				else white_count &= 127;
+				if (black) black_count &= 0x7F;
+				else white_count &= 0x7F;
 				colours[loc] = current_colour;
 				celldat[loc] = NUM_INC | STONE_CAPSTONE;
 				break;
 			}
 		}
 	} else {
-		const uint8_t gaps = action->data0,
+		const uint8_t gaps = action->data0 & 0x7F, // not interested in
+																							// whether we crushed,
+																							// it will work out by
+																							// anyway because we
+																							// overwrite the top
+																							// stone type. See (*)
+																							// later for when we do
+																							// need to know.
 			num = action->data1 & 0x0F, // unpack
 			dir = action->data1 >> 4;
 		int8_t delta = deltas[dir];
@@ -186,11 +200,11 @@ void action_take(action_node_t *action) {
 		celldat[loc] &= CLR_STONE;
 		celldat[loc] |= STONE_FLAT; // should be optimised out
 
-		uint8_t gap_bit = 0, total = 1;
-		// num == 1 is a special case
-		if (num > 1) {
-			gap_bit = 1 << (num - 2);
-		}
+		uint8_t total = 1, gap_bit = 1 << (num - 2); // it's not important
+																								 // what negative
+																								 // shifts do here, we
+																								 // don't use gap_bit
+																								 // if num < 2
 		// move stuff starting at destination
 		for (uint8_t d = 1; d < num; d++, total++, gap_bit >>= 1) {
 			// We took a step, move everything over so far
@@ -237,22 +251,24 @@ void action_undo(action_node_t *action) {
 		const uint8_t black = (current_colour == C_BLACK);
 		celldat[loc] = 0;
 		if (action->data0 == STONE_CAPSTONE) {
-			if (black) black_count |= 128;
-			else white_count |= 128;
+			if (black) black_count |= 0x80;
+			else white_count |= 0x80;
 		} else {
 			if (black) black_count++;
 			else white_count++;
 		}
 	} else {
-		// See action_take for comments, this is the time reversal
-		const uint8_t gaps = action->data0,
+		// See action_take for comments, this is the time reversal, but
+		// there is one caveat -- undoing a crush! (*)
+		const uint8_t gaps = action->data0 & 0x75,
+			crush = action->data0 & 0x80,
 			num = action->data1 & 0x0F,
 			dir = action->data1 >> 4;
 		const int8_t delta = deltas[dir];
 
 		int8_t steps = 1;
 		uint8_t gap_bit = 1, total = 1;
-		for (uint8_t d = 1; d < num; d++, total++, gap_bit <<= 1) {
+		for (int8_t d = 1; d < num; d++, total++, gap_bit <<= 1) {
 			if (gaps & gap_bit) {
 				colours[loc] <<= total;
 				colours[loc] |= colours[loc+steps*delta] & ((1 << total) - 1);
@@ -266,13 +282,17 @@ void action_undo(action_node_t *action) {
 		colours[loc] <<= total;
 		colours[loc] |= colours[loc+steps*delta] & ((1 << total) - 1);
 		colours[loc+steps*delta] >>= total;
-		// celldat[loc] &= CLR_STONE; is not necessary, as STONE_FLAT == 0
+
 		celldat[loc] += total*NUM_INC;
-		celldat[loc+steps*delta] -= total*NUM_INC;
-		// Top stone type
+		// celldat[loc] &= CLR_STONE; is not necessary, as STONE_FLAT == 0
 		celldat[loc] |= STONE_AT(loc+steps*delta);
+		celldat[loc+steps*delta] -= total*NUM_INC;
 		celldat[loc+steps*delta] &= CLR_STONE;
-		celldat[loc+steps*delta] |= STONE_FLAT; // should be optimised out
+		if (crush) {
+			celldat[loc+steps*delta] |= STONE_STANDING;
+		} else {
+			celldat[loc+steps*delta] |= STONE_FLAT; // should be optimised out
+		}
 	}
 }
 
@@ -281,20 +301,20 @@ void action_to_ptn(action_node_t* action, char* out_ptn) {
 	if (action->type == A_PLACE) {
 		generate_place(loc, action->data0, out_ptn);
 	} else {
-		const uint8_t gaps = action->data0,
+		const uint8_t gaps = action->data0 & 0x7F,
 			num = action->data1 & 0x0F, // unpack
 			dir = action->data1 >> 4;
 
 		uint8_t drops[board_size]; // we only ever need board_size-1 in
 															 // drops actually, the last spot is to
-															 // skip a bounds check at (*)
+															 // skip a bounds check at (**)
 		uint8_t mask = 1, steps = 0;
 		// Translate to a drop sequence
 		drops[0] = 1; mask = 1;
 		for (uint8_t d = 1; d < num; d++) {
 			if (gaps & mask) {
 				steps++;
-				drops[steps] = 1; // (*) no bounds check
+				drops[steps] = 1; // (**) no bounds check
 			} else {
 				drops[steps] += 1;
 			}
diff --git a/include/negamax.c b/include/negamax.c
index 43fa5f6..abb4e27 100644
--- a/include/negamax.c
+++ b/include/negamax.c
@@ -113,35 +113,61 @@ static enum WIN_TYPE w;
 static float
 negamax(const uint8_t cur_depth, float alpha, float beta,
 				const float colour) {
+	float value = -infty;
 
-	if (cur_depth == 0) return colour*cnn1986_evaluate_black_win();
 
-	float value = -infty;
+	data_t bd[5*5];
+	colour_stack_t bc[25];
 
 	action_list_t *list = action_list_generate();
 	if (list == NULL) return value; // ???
 
 	for (action_node_t *node=list->head; node!=NULL; node=node->next) {
+
+		for (int k=0; k<25; k++) { bd[k]=celldat[k]; bc[k]=colours[k]; }
 		action_take(node);
 
-		// Somebody won?
+		// Compute the value of the node
 		if (ply >= 2*board_size - 2 && (w = check_win()) < 0xFF) {
-			if (w == WIN_ROAD_BLACK || w == WIN_FLAT_BLACK) value = colour*infty;
-			else if (w == WIN_DRAW) value = 0; // Draw is fixed at neutral
-			else value = -colour*infty;
-			if (value > 0) {
-				// Always take the win for ourselves
-				action_undo(node);
-				if (cur_depth == negamax_search_depth) {
-					action_to_ptn(node, negamax_ptn);
-				}
-				goto prune;
-			}
-		} else {
+			float winnings = -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);
+		} 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));
+		} else {
+			// Recursion would take us to a leaf, evaluate
+			value = fmax(value, colour*cnn1986_evaluate_black_win());
 		}
 
 		action_undo(node);
+		for (int k=0; k<25; k++) {
+			if (bd[k]!=celldat[k]) {
+				printf("Depth %d %.3f %.3f %d: { .type = %s, .loc = 0x%02X, .data0 = 0x%02X, .data1 = 0x%02X} DIFF 0x%02X \n",
+							 cur_depth,
+							 alpha,
+							 beta,
+							 ply,
+							 (node->type == A_PLACE) ? "A_PLACE" : "A_MOVE",
+							 node->loc,
+							 node->data0,
+							 node->data1,
+							 k);
+				puts("Before:");
+				for (int j=0; j<25;j++) printf("0x%02X ",bd[j]);
+				putchar('\n');
+				for (int j=0; j<25;j++) printf("0x%02X ",bc[j]);
+				putchar('\n');
+				puts("After:");
+				for (int j=0; j<25;j++) printf("0x%02X ",celldat[j]);
+				putchar('\n');
+				for (int j=0; j<25;j++) printf("0x%02X ",colours[j]);
+				putchar('\n');
+				exit(1);
+			}
+		}
 
 		negamax_display_progress(cur_depth, list->length);
 
diff --git a/src/ctaklm.c b/src/ctaklm.c
index 5dd4164..c395c29 100644
--- a/src/ctaklm.c
+++ b/src/ctaklm.c
@@ -421,17 +421,25 @@ main(int argc, char **argv) {
 	negamax_init(5);
 	tt_init();
 
+	auto_board = 1;
+	auto_info = 0;
+	negamax_search_depth = 4;
+	for (int k=0; k<10; k++) negamax_turn();
+	return 0;
+
+	ply = 7; current_colour=C_BLACK;
+	celldat[0x00]=0x22; colours[0x00]=0x05;
+	celldat[0x01]=0x10; colours[0x01]=0x00;
+	celldat[0x02]=0x11; colours[0x02]=0x00;
+	print_board();
 
-	/*
-	 * celldat[0x16]=0x30;
-	 * colours[0x16]=4;
-	 * print_board();
-	 *
-	 * action_list_t a = {.next = NULL, .type = A_MOVE, .loc = 0x16, .data0 = 0x1, .data1 = 0x12};
-	 * action_take(&a); print_board();
-	 * action_undo(&a); print_board();
-	 * return 0;
-	 */
+	action_list_t *list = action_list_generate();
+
+
+	action_node_t a = {.next = NULL, .type = A_MOVE, .loc = 0x0, .data0 = 0x80, .data1 = 0x31};
+	action_take(&a); print_board();
+	action_undo(&a); print_board();
+	return 0;
 
 
 	// Test harness