Trying alpha-beta pruning. There's a bug somewhere ...

1 files changed, 18 insertions, 5 deletions

diff --git a/include/ct1986.c b/include/ct1986.c
index bc48110..706640e 100644
--- a/include/ct1986.c
+++ b/include/ct1986.c
@@ -121,12 +121,12 @@ previous_ply(void) {
 		if ((min == 0) && (w == WIN_ROAD_BLACK \
 											 || w == WIN_FLAT_BLACK \
 											 || w == WIN_DRAGON)) { \
-			this = +2; \
+			this = +3; \
 		} else if ((min > 0) \
 							 && (w == WIN_ROAD_WHITE \
 									 || w == WIN_FLAT_WHITE \
 									 || w == WIN_DRAGON)) { \
-			this = -2; \
+			this = -3; \
 		}	/* Otherwise decide what to do based on our depth  */ \
 	} else if (cur_depth == max_depth) { \
 		/* We're at the bottom, evaluate */ \
@@ -134,20 +134,24 @@ previous_ply(void) {
 	} else { \
 		/* We're not at the bottom, recurse first */ \
 		next_ply(); \
-		this = ct1986_minimax(cur_depth + 1, max_depth, 1-min); \
+		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; }; \
 	} \
 	}
 
-
 float
 ct1986_minimax(const uint8_t cur_depth, const uint8_t max_depth,
-							 const uint8_t min) {
+							 const uint8_t min, float alpha, float beta) {
 	enum E_RESULT r;
 	enum WIN_TYPE w;
 	uint16_t colours_backup[board_size];
@@ -227,6 +231,8 @@ ct1986_minimax(const uint8_t cur_depth, const uint8_t max_depth,
 										}
 									}
 								}
+								// Prune
+								if (alpha >= beta) return optimal;
 							}
 						}
 					}
@@ -250,6 +256,8 @@ ct1986_minimax(const uint8_t cur_depth, const uint8_t max_depth,
 						celldat[loc] = 0;
 						white_count = white_count_backup;
 						black_count = black_count_backup;
+						// Prune
+						if (alpha >= beta) return optimal;
 					}
 				}
 			}
@@ -258,3 +266,8 @@ ct1986_minimax(const uint8_t cur_depth, const uint8_t max_depth,
 	}
 	return optimal;
 }
+
+inline float
+ct1986_generate(const uint8_t max_depth) {
+	return ct1986_minimax(0, max_depth, 0, -10, 10);
+}