Stable negamax-alpha-beta fail-soft

4 files changed, 101 insertions, 34 deletions

diff --git a/include/action_list.c b/include/action_list.c
index 9ddd74b..30ca918 100644
--- a/include/action_list.c
+++ b/include/action_list.c
@@ -9,10 +9,9 @@
 #define CLR_STONE NUM_MASK
 
 static inline void
-action_list_prepend(action_list_t *list, const enum A_TYPE type,
-										const int8_t loc, const uint8_t data0,
-										const uint8_t data1);
-
+action_list_append(action_list_t *list, const enum A_TYPE type,
+									 const int8_t loc, const uint8_t data0,
+									 const uint8_t data1);
 static inline void
 inline_next_ply(void);
 
@@ -24,6 +23,30 @@ inline_prev_ply(void);
 // Exported method implementations
 // ===================================================================
 
+/*
+ * void action_list_ensure_at_front(const action_node_t *action,
+ *																 const action_list_t *list) {
+ *	action_node_t *copy = action_copy(action), *n = list->head, *nn;
+ *	// ensure it's not there already
+ *	while (n) {
+ *		nn = n->next;
+ *	}
+ *
+ *	copy->next = list->head;
+ * }
+ */
+
+action_node_t *action_copy(const action_node_t *action) {
+	action_node_t *copy = malloc(sizeof(struct action_node_s));
+	// TODO: trap
+	copy->data0 = action->data0;
+	copy->data1 = action->data1;
+	copy->loc = action->loc;
+	copy->type = action->type;
+	copy->next = NULL;
+	return copy;
+}
+
 void action_list_free(action_list_t *list) {
 	if (list) {
 		action_node_t *n = list->head, *nn;
@@ -64,9 +87,9 @@ action_list_t *action_list_generate(void) {
 		cap = ((ply >= 2) && (material & 0x80)),
 		standing = ((ply >= 2) && flat);
 
-	// Step across the board, reversed because we prepend to the list
-	for (int row = board_size - 1; row >= 0; row--) {
-		for (int col = board_size - 1; col >= 0; col--) {
+	// Step across the board
+	for (int row = 0; row < board_size; row++) {
+		for (int col = 0; col < board_size; col++) {
 			// We'll need these at various points: the location of this
 			// square and the maximum number of stones we could pick up
 			const int loc = THE_COORDS(col, row);
@@ -132,7 +155,8 @@ action_list_t *action_list_generate(void) {
 										const uint8_t crush =
 											(steps == end_stops[dir]) && crushes[dir];
 										// Store the move
-										action_list_prepend(list, A_MOVE, loc,
+
+										action_list_append(list, A_MOVE, loc,
 																				(crush << 7) | gaps,
 																				(dir<<4) | num);
 									}
@@ -154,12 +178,12 @@ action_list_t *action_list_generate(void) {
 			else if (material) {
 				// Empty square, generate placements
 				if (flat) {
-					action_list_prepend(list, A_PLACE, loc, STONE_FLAT, 0);
+					action_list_append(list, A_PLACE, loc, STONE_FLAT, 0);
 					if (standing)
-						action_list_prepend(list, A_PLACE, loc, STONE_STANDING,0);
+						action_list_append(list, A_PLACE, loc, STONE_STANDING,0);
 				}
 				if (cap)
-					action_list_prepend(list, A_PLACE, loc, STONE_CAPSTONE, 0);
+					action_list_append(list, A_PLACE, loc, STONE_CAPSTONE, 0);
 			}
 		}
 	}
@@ -333,18 +357,27 @@ void action_to_ptn(action_node_t* action, char* out_ptn) {
 // ===================================================================
 
 static inline void
-action_list_prepend(action_list_t *list, const enum A_TYPE type,
+action_list_append(action_list_t *list, const enum A_TYPE type,
 										const int8_t loc, const uint8_t data0,
 										const uint8_t data1) {
 	action_node_t *new = malloc(sizeof(action_list_t));
 	// TODO: trap errno
-	list->length++;
+
 	new->loc = loc;
 	new->type = type;
 	new->data0 = data0;
 	new->data1 = data1;
-	new->next = list->head;
-	list->head = new;
+	new->next = NULL;
+
+	if (list->length) {
+		list->tail->next = new;
+		list->tail = new;
+	} else {
+		list->head = new;
+		list->tail = new;
+	}
+
+	list->length++;
 }
 
 static inline void
diff --git a/include/action_list.h b/include/action_list.h
index 14c733f..b6fd13a 100644
--- a/include/action_list.h
+++ b/include/action_list.h
@@ -3,6 +3,9 @@
 
 #include <tak.h>
 
+#ifndef ACTION_LIST_H
+#define ACTION_LIST_H
+
 enum A_TYPE { A_PLACE, A_MOVE };
 
 typedef struct action_node_s {
@@ -14,15 +17,18 @@ typedef struct action_node_s {
 } action_node_t;
 
 typedef struct action_list_s {
-	struct action_node_s *head;
+	struct action_node_s *head, *tail;
 	uint32_t length;
 } action_list_t;
 
 void action_list_init(void);
 void action_list_free(action_list_t *list);
 action_list_t *action_list_generate(void);
+action_node_t *action_copy(const action_node_t* action);
 
 void action_take(action_node_t *action);
 void action_undo(action_node_t *action);
 
 void action_to_ptn(action_node_t* action, char* out_ptn);
+
+#endif
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;
 	 * }
 	 */
 
diff --git a/include/tt_treap.h b/include/tt_treap.h
index 793d536..1a15e1b 100644
--- a/include/tt_treap.h
+++ b/include/tt_treap.h
@@ -1,5 +1,6 @@
 #include <stdlib.h>
 #include <stdint.h>
+#include <action_list.h>
 #include <xorshift64.h>
 
 #ifndef TT_TREAP_H
@@ -18,6 +19,7 @@ typedef struct treap_node_s {
 	enum TT_FLAG flag;
 	uint8_t depth;
 	float value;
+	action_node_t *action;
 } tt_entry_t;
 
 // ===================================================================
@@ -34,7 +36,9 @@ int tt_init(void);
 void tt_free(void);
 
 tt_entry_t *tt_seek(uint64_t key);
+
 int tt_insert(const uint64_t key, const enum TT_FLAG flag,
 							const uint8_t depth, const float value);
+							//							const action_node_t* action);
 
 #endif