Tried some naive iterative deepening. Work on TEI interface next

If TEI is implemented, then i could make use of Morten's
racetrack (https://github.com/MortenLohne/racetrack) and develop a
quantitative measure of the bot's performance. This is the current
priority.

2 files changed, 26 insertions, 10 deletions

diff --git a/include/negamax.c b/include/negamax.c
index 44deea9..f5bbf02 100644
--- a/include/negamax.c
+++ b/include/negamax.c
@@ -24,12 +24,14 @@
 const float infty = 3.0;
 char negamax_ptn[9];
 uint8_t negamax_search_depth = 3;
+static uint64_t negamax_best_action;
 
 // ===================================================================
 // Helper declarations
 // ===================================================================
 
-static float negamax(const uint8_t cur_depth, float alpha, float beta,
+static float negamax(const uint8_t cur_depth, const uint8_t init_depth,
+										 float alpha, float beta,
 										 const float colour, const uint64_t hash);
 
 // ===================================================================
@@ -51,25 +53,31 @@ float negamax_generate(void) {
 	// We need to start with something outside of [-∞,∞] because those
 	// values are wins
 	const float safe_infty = infty + 1;
+	float result = -infty;
+
+	negamax_best_action = -1;
 
 	tt_init();
-	float result =
-		negamax(negamax_search_depth, -safe_infty, safe_infty,
-						(ply & 1) ? +1.0 : -1.0, zobrist_compute());
+	for (int d = 1; d <= negamax_search_depth; d++) {
+		result = negamax(d, d, -safe_infty, safe_infty,
+										 (ply & 1) ? +1.0 : -1.0, zobrist_compute());
+	}
 	tt_free();
 
 	return result;
 }
 
 // ===================================================================
-// α-β negamax using the cnn1986 evaluation function and transposition
-// tables using Zobrist hasing and a chaining hash table
+// α-β negamax with iterative deepening, using the cnn1986 evaluation
+// function and transposition tables using Zobrist hasing and a
+// chaining hash table
 // ===================================================================
 
 static enum TT_FLAG flag;
 static enum WIN_TYPE w;
 
-static float negamax(const uint8_t cur_depth, float alpha, float beta,
+static float negamax(const uint8_t cur_depth, const uint8_t init_depth,
+										 float alpha, float beta,
 										 const float colour, const uint64_t hash) {
 
 	tt_entry_t *entry = tt_seek(hash);
@@ -94,12 +102,16 @@ static float negamax(const uint8_t cur_depth, float alpha, float beta,
 		action_move_to_front(entry->action, list);
 	}
 
+	if (init_depth > 1 && cur_depth == init_depth) {
+		action_move_to_front(negamax_best_action, list);
+	}
+
 	// TODO: what to do if this is never written to?
 	action_t best_action = list->head->action;
 	float best_value = -infty;
 
 	for (action_node_t *node=list->head; node!=NULL; node=node->next) {
-		negamax_display_progress(cur_depth, list->length);
+		negamax_display_progress(cur_depth, init_depth, list->length);
 
 		action_take(node->action);
 
@@ -115,7 +127,8 @@ static float negamax(const uint8_t cur_depth, float alpha, float beta,
 			}
 		} else if (cur_depth > 1) {
 			// If nobody won, or too early and not leaf, recurse
-			node_value = -negamax(cur_depth - 1, -beta, -alpha,
+			node_value = -negamax(cur_depth - 1, init_depth,
+														-beta, -alpha,
 														-colour, zobrist_compute());
 		} else {
 			node_value = colour * cnn1986_evaluate_black_win();
@@ -125,8 +138,10 @@ static float negamax(const uint8_t cur_depth, float alpha, float beta,
 		if (node_value > best_value) {
 			best_value = node_value;
 			best_action = node->action;
-			if (cur_depth == negamax_search_depth)
+			if (cur_depth == init_depth) {
 				action_to_ptn(node->action, negamax_ptn);
+				negamax_best_action = best_action;
+			}
 		}
 
 		if (best_value > alpha) alpha = best_value;
diff --git a/include/negamax.h b/include/negamax.h
index 77461b8..b3dec75 100644
--- a/include/negamax.h
+++ b/include/negamax.h
@@ -33,6 +33,7 @@ extern char negamax_ptn[9];
 extern uint8_t negamax_search_depth;
 
 extern void negamax_display_progress(const uint8_t cur_depth,
+																		 const uint8_t init_depth,
 																		 const uint32_t length);
 
 // ===================================================================