There was a bug in the minimax!

1 files changed, 46 insertions, 41 deletions

diff --git a/include/ct1986.c b/include/ct1986.c
index 5b3125f..4e081d1 100644
--- a/include/ct1986.c
+++ b/include/ct1986.c
@@ -115,54 +115,61 @@ previous_ply(void) {
 	}
 }
 
-#define WIN_EVALUATE_OR_RECURSE(store)		\
-	{ w = 0xFF; \
-	if (ply >= 2*board_size - 2) w = check_win(); \
-	if (w < 0xFF) { \
-		if ((min == 0) && (w == WIN_ROAD_BLACK \
-											 || w == WIN_FLAT_BLACK \
-											 || w == WIN_DRAGON)) { \
-			this = infty; \
-		} else if ((min > 0) \
-							 && (w == WIN_ROAD_WHITE \
-									 || w == WIN_FLAT_WHITE \
-									 || w == WIN_DRAGON)) { \
-			this = -infty; \
-		}	/* Otherwise decide what to do based on our depth  */ \
-	} else if (cur_depth == max_depth) { \
-		/* We're at the bottom, evaluate */ \
-		this = ct1986_evaluate_black_win(); \
-		if ((ply & 1) == 0) this = this - 1.0; \
-	} else { \
-		/* We're not at the bottom, recurse first */ \
-		next_ply(); \
-		this = ct1986_minimax(cur_depth + 1, max_depth, 1-min, alpha, beta); \
-		previous_ply(); \
-	} \
-	if ( (min && (this < optimal)) \
-			 || ((min==0) && (this > optimal))) { \
-		optimal = this; \
-		if (min) { \
-			if (this < beta) beta = this; \
-		} else { \
-			if (this > alpha) alpha = this; \
-		} \
-		if (cur_depth == 0) { store; }; \
-	} \
+static inline int
+win_evaluate_or_recurse(const uint8_t cur_depth,
+												const uint8_t max_depth, const uint8_t min,
+												float* alpha, float* beta, float *optimal) {
+	float this;
+	enum WIN_TYPE w = 0xFF;
+	if (ply >= 2*board_size - 2) w = check_win();
+	if (w < 0xFF) {
+		/* Somebody won, assign weights accordingly */
+		if (min == 0) {
+			if (w == WIN_ROAD_BLACK || w == WIN_FLAT_BLACK || w == WIN_DRAGON)
+				this = infty;
+			else this = -infty;
+		} else {
+			if (w == WIN_ROAD_WHITE || w == WIN_FLAT_WHITE || w == WIN_DRAGON)
+				this = -infty;
+			else this = infty;
+		}
+	} else if (cur_depth == max_depth) {
+		/* We're at the bottom, evaluate */
+		this = ct1986_evaluate_black_win();
+		if ((ply & 1) == 0) this = this - 1.0;
+	} else {
+		/* We're not at the bottom, recurse first */
+		next_ply();
+		this = ct1986_minimax(cur_depth + 1, max_depth, 1-min, *alpha, *beta);
+		previous_ply();
+	}
+	/* Update alpha and beta */
+	if (min) {
+		if (this < *beta) *beta = this;
+	} else {
+		if (this > *alpha) *alpha = this;
+	}
+	/* Update the optimal value */
+	if (((min > 0) && (this < *optimal))
+			|| ((min == 0) && (this > *optimal))) {
+		*optimal = this;
+		/* If we're at the top, store the PTN of the winning turn */
+		if (cur_depth == 0) { return 1; };
 	}
+	return 0;
+}
 
 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;
-	enum WIN_TYPE w;
 	uint16_t colours_backup[board_size];
 	uint8_t celldat_backup[board_size], drops[board_size];
 	const uint8_t white_count_backup = white_count,
 		black_count_backup = black_count;
 
 	// 1.0 is a `certain' black win, -1.0 is a `certain' white win.
-	float this = 0, optimal = (min) ? infty : -infty;
+	float optimal = (min) ? infty : -infty;
 
 	// Step across the board
 	for (uint8_t row = 0; row < board_size; row++) {
@@ -217,9 +224,8 @@ ct1986_minimax(const uint8_t cur_depth, const uint8_t max_depth,
 								if (r == ACT_OK) {
 									// First check for wins, if we're at the bottom
 									// evaluate, otherwise recurse
-									WIN_EVALUATE_OR_RECURSE({
-											generate_move(loc, dir, steps, drops, ct1986_ptn);
-										});
+									if (win_evaluate_or_recurse(cur_depth, max_depth, min, &alpha, &beta, &optimal))
+										generate_move(loc, dir, steps, drops, ct1986_ptn);
 									// Reset the board data
 									if (dir <= M_DOWN) {
 										for (uint8_t y = 0; y < board_size; y++) {
@@ -251,9 +257,8 @@ ct1986_minimax(const uint8_t cur_depth, const uint8_t max_depth,
 					if (r == ACT_OK) {
 						// First check for wins, if we're at the bottom
 						// evaluate, otherwise recurse
-						WIN_EVALUATE_OR_RECURSE({
+						if (win_evaluate_or_recurse(cur_depth, max_depth, min, &alpha, &beta, &optimal))
 								generate_place(loc, stone, ct1986_ptn);
-							});
 						// Reset the state
 						celldat[loc] = 0;
 						white_count = white_count_backup;