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

4 files changed, 36 insertions, 15 deletions

diff --git a/Makefile b/Makefile
index 7819070..1f472ed 100644
--- a/Makefile
+++ b/Makefile
@@ -1,6 +1,6 @@
 IDIR=include
 TPDIR=3rd-party
-CFLAGS=-Os -Wall -Wextra -std=c99 -D_DEFAULT_SOURCE -I$(IDIR) -I$(TPDIR)
+CFLAGS=-O3 -Wall -Wextra -std=c99 -D_DEFAULT_SOURCE -I$(IDIR) -I$(TPDIR)
 LIBS=
 
 SRCS=$(wildcard include/*.c) $(wildcard 3rd-party/*.c)
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);
+}
diff --git a/include/ct1986.h b/include/ct1986.h
index 877c301..ef56c1f 100644
--- a/include/ct1986.h
+++ b/include/ct1986.h
@@ -11,9 +11,13 @@ ct1986_evaluate_black_win(void);
 // Generate PTN of the ````best'''' action and store it in ct1986_ptn,
 // along with its value as the return. The ct1986_display_progress
 // function pointer is called on every new square.
+
+float ct1986_generate(const uint8_t max_depth);
+
+// Access to the internal method
 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);
 
 extern char ct1986_ptn[9];
 extern float ct1986_optimal;
diff --git a/src/ctaklm.c b/src/ctaklm.c
index 7d6cedd..e7d9960 100644
--- a/src/ctaklm.c
+++ b/src/ctaklm.c
@@ -153,8 +153,6 @@ print_info(void) {
 	printf("Caps remaining:   %s%d%s,  %s%d%s\n",
 				 wht,white_count >> 7,rst,
 				 blk,black_count >> 7,rst);
-	printf("Valuation: %s%.6f%s\n",
-				 blk, ct1986_evaluate_black_win(), rst);
 }
 
 char *gamelog = 0;
@@ -325,7 +323,8 @@ main(int argc, char **argv) {
 		} else if (!strncmp(line,"info",5)) {
 			print_info();
 		} else if (!strncmp(line,"eval",5)) {
-			printf("Valuation: %.6f\n", ct1986_evaluate_black_win());
+			printf("Valuation: %s%.6f%s\n",
+						 blk, ct1986_evaluate_black_win(), rst);
 		} else if (!strncmp(line,"log",3)) {
 			puts(gamelog);
 		} else if (!strncmp(line,"load",4)) {
@@ -369,12 +368,17 @@ main(int argc, char **argv) {
 				fputs("Computing [", stdout);
 				for (int k = 0; k < board_size * board_size; k++) putchar(' ');
 				fputs("]\033[26D",stdout);
+				fflush(stdout);
 				// Run the minimax
-				float minimax = ct1986_minimax(0, 2, 0);
-				printf("] Result: %s (%.3f)\n",
-							 ct1986_ptn,
-							 minimax*100.0);
-				handle_turn(ct1986_ptn);
+				float minimax = ct1986_minimax(0, 3, 0, -10, 10);
+				if (minimax < 0 || minimax > 1) {
+					puts("] Opponent concedes!");
+				} else {
+					printf("] Result: %s (%.3f)\n",
+								 ct1986_ptn,
+								 minimax*100.0);
+					handle_turn(ct1986_ptn);
+				}
 			}
 		}