Stable negamax-alpha-beta fail-soft

1 files changed, 42 insertions, 18 deletions

diff --git a/include/negamax.c b/include/negamax.c
index db5d39b..856f3fc 100644
--- a/include/negamax.c
+++ b/include/negamax.c
@@ -93,6 +93,19 @@ negamax_free(void) {
 	zobrist_free();
 }
 
+static enum WIN_TYPE w;
+
+static inline float
+negamax_evaluate_terminal(const float colour) {
+	if (ply >= 2*board_size - 2 && (w = check_win()) < 0xFF) {
+		// Check win if far enough into the game
+		if (w == WIN_ROAD_BLACK || w == WIN_FLAT_BLACK) return colour*infty;
+		else if (w == WIN_DRAW) return 0; // Draw is fixed at neutral
+		else return -colour*infty;
+	} else {
+		return colour * cnn1986_evaluate_black_win();
+	}
+}
 
 float
 negamax_generate(void) {
@@ -109,7 +122,7 @@ negamax_generate(void) {
 	return result;
 }
 
-static enum WIN_TYPE w;
+static enum TT_FLAG flag;
 
 static float
 negamax(const uint8_t cur_depth, float alpha, float beta,
@@ -120,7 +133,7 @@ negamax(const uint8_t cur_depth, float alpha, float beta,
 	 * tt_entry_t *entry = tt_seek(hash);
 	 * const float alpha_orig = alpha;
 	 *
-	 * if (entry != NULL && entry->depth >= cur_depth) {
+	 * if (entry != NULL && entry->depth == cur_depth) {
 	 *	if (entry->flag == TT_EXACT) {
 	 *		return entry->value;
 	 *	} else if (entry->flag == TT_LOWERBOUND) {
@@ -128,15 +141,24 @@ negamax(const uint8_t cur_depth, float alpha, float beta,
 	 *	} else if (entry->flag == TT_UPPERBOUND) {
 	 *		beta = fmin(beta, entry->value);
 	 *	}
-	 *	if (alpha >= beta) return entry->value;
+	 *	if (alpha >= beta) {
+	 *		if (cur_depth == negamax_search_depth)
+	 *			action_to_ptn(entry->action, negamax_ptn);
+	 *		return entry->value;
+	 *	}
 	 * }
 	 */
 
-	float value = -infty;
+	action_list_t *list;
+	if ((list = action_list_generate()) == NULL)
+		return alpha; // should never happen!
+
 
-	action_list_t *list = action_list_generate();
-	if (list == NULL) return value; // ???
+	/*
+	 * action_node_t *best = NULL;
+	 */
 
+	float value = -infty;
 	for (action_node_t *node=list->head; node!=NULL; node=node->next) {
 
 		action_take(node);
@@ -147,42 +169,44 @@ negamax(const uint8_t cur_depth, float alpha, float beta,
 			node_value = -colour*infty;
 			// Check win if far enough into the game
 			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 > 0) {
-			// If nobody won, or too early, recurse if not a leaf
+			else if (w == WIN_DRAW) node_value = 0; // Draw is neutral
+		} else if (cur_depth > 1) {
+			// If nobody won, or too early and not leaf, recurse
 			node_value = -negamax(cur_depth - 1, -beta, -alpha, -colour);
 		} else {
-			// Recursion would take us to a leaf, evaluate
 			node_value = colour * cnn1986_evaluate_black_win();
 		}
-
-		value = fmax(value, node_value);
-
 		action_undo(node);
 
 		negamax_display_progress(cur_depth, list->length);
 
-		if (value > alpha) {
-			alpha = value;
+		if (node_value > value) {
+			value = node_value;
 			if (cur_depth == negamax_search_depth)
 				action_to_ptn(node, negamax_ptn);
-			if (alpha >= beta) break;
 		}
+
+		alpha = fmax(value, alpha);
+		if (alpha >= beta) break;
 	}
 
 	action_list_free(list);
 
 	/*
-	 * enum TT_FLAG flag = TT_EXACT;
+	 * flag = TT_EXACT;
 	 * if (value <= alpha_orig) flag = TT_UPPERBOUND;
 	 * else if (value >= beta) flag = TT_UPPERBOUND;
 	 *
 	 * if (entry == NULL) {
 	 *	tt_insert(hash, flag, cur_depth, value);
-	 * } else {
+	 * }
+	 */
+	/*
+	 * else {
 	 *	entry->flag = flag;
 	 *	entry->value = value;
 	 *	entry->depth = cur_depth;
+	 *	entry->action = best;
 	 * }
 	 */