Storing best moves!

6 files changed, 115 insertions, 103 deletions

diff --git a/include/action_list.c b/include/actions.c
index 30ca918..9b3534b 100644
--- a/include/action_list.c
+++ b/include/actions.c
@@ -1,4 +1,4 @@
-#include "action_list.h"
+#include "actions.h"
 
 // ===================================================================
 // Helper method declarations
@@ -8,45 +8,50 @@
 
 #define CLR_STONE NUM_MASK
 
+#define TYPE_SHIFT  24
+#define LOC_SHIFT   16
+#define DATA0_SHIFT  8
+
+#define GET_TYPE(a)  (enum A_TYPE)((a)>>TYPE_SHIFT)
+#define GET_LOC(a)   (int8_t)(((a)>>LOC_SHIFT) & 0xFF)
+#define GET_DATA0(a) (uint8_t)(((a)>>DATA0_SHIFT) & 0xFF)
+#define GET_DATA1(a) (uint8_t)((a) & 0xFF)
+
 static inline void
-action_list_append(action_list_t *list, const enum A_TYPE type,
-									 const int8_t loc, const uint8_t data0,
-									 const uint8_t data1);
+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);
 
 static inline void
 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;
+int action_move_to_front(const action_t action,
+												 action_list_t *list) {
+	action_node_t *n = list->head;
+
+	// TODO: what if it's not in the list?
+
+	while (n) {
+		if (n->action == action) {
+			const action_t t = list->head->action;
+			list->head->action = action;
+			n->action = t;
+			return EXIT_SUCCESS;
+		}
+		n = n->next;
+	}
+
+	return EXIT_FAILURE;
 }
 
+
 void action_list_free(action_list_t *list) {
 	if (list) {
 		action_node_t *n = list->head, *nn;
@@ -156,9 +161,9 @@ action_list_t *action_list_generate(void) {
 											(steps == end_stops[dir]) && crushes[dir];
 										// Store the move
 
-										action_list_append(list, A_MOVE, loc,
-																				(crush << 7) | gaps,
-																				(dir<<4) | num);
+										list_append(list, A_MOVE, loc,
+																(crush << 7) | gaps,
+																(dir<<4) | num);
 									}
 									/*
 									 * With thanks to
@@ -178,23 +183,23 @@ action_list_t *action_list_generate(void) {
 			else if (material) {
 				// Empty square, generate placements
 				if (flat) {
-					action_list_append(list, A_PLACE, loc, STONE_FLAT, 0);
+					list_append(list, A_PLACE, loc, STONE_FLAT, 0);
 					if (standing)
-						action_list_append(list, A_PLACE, loc, STONE_STANDING,0);
+						list_append(list, A_PLACE, loc, STONE_STANDING,0);
 				}
 				if (cap)
-					action_list_append(list, A_PLACE, loc, STONE_CAPSTONE, 0);
+					list_append(list, A_PLACE, loc, STONE_CAPSTONE, 0);
 			}
 		}
 	}
 	return list;
 }
 
-void action_take(action_node_t *action) {
-	const int8_t loc = action->loc;
-	if (action->type == A_PLACE) {
+void action_take(const action_t action) {
+	const int8_t loc = GET_LOC(action);
+	if (GET_TYPE(action) == A_PLACE) {
 		const uint8_t black = (current_colour == C_BLACK);
-		switch (action->data0) {
+		switch (GET_DATA0(action)) {
 			case STONE_FLAT: {
 				if (black) black_count--;
 				else white_count--;
@@ -218,16 +223,12 @@ void action_take(action_node_t *action) {
 			}
 		}
 	} else {
-		const uint8_t gaps = action->data0 & 0x7F, // not interested in
-																							// whether we crushed,
-																							// it will work out by
-																							// anyway because we
-																							// overwrite the top
-																							// stone type. See (*)
-																							// later for when we do
-																							// need to know.
-			num = action->data1 & 0x0F, // unpack
-			dir = action->data1 >> 4;
+		 // not interested in whether we crushed, it will work out by
+		 // anyway because we overwrite the top stone type. See (*) later
+		 // for when we do need to know.
+		const uint8_t gaps = GET_DATA0(action) & 0x7F,
+			num = GET_DATA1(action) & 0x0F, // unpack
+			dir = GET_DATA1(action) >> 4;
 		int8_t delta = deltas[dir];
 
 		// Use the Kernighan method to count the set bits
@@ -270,15 +271,15 @@ void action_take(action_node_t *action) {
 	inline_next_ply();
 }
 
-void action_undo(action_node_t *action) {
+void action_undo(const action_t action) {
 	// Previous ply
 	inline_prev_ply();
 
-	const int8_t loc = action->loc;
-	if (action->type == A_PLACE) {
+	const int8_t loc = GET_LOC(action);
+	if (GET_TYPE(action) == A_PLACE) {
 		const uint8_t black = (current_colour == C_BLACK);
 		celldat[loc] = 0;
-		if (action->data0 == STONE_CAPSTONE) {
+		if (GET_DATA0(action) == STONE_CAPSTONE) {
 			if (black) black_count |= 0x80;
 			else white_count |= 0x80;
 		} else {
@@ -288,10 +289,10 @@ void action_undo(action_node_t *action) {
 	} else {
 		// See action_take for comments, this is the time reversal, but
 		// there is one caveat -- undoing a crush! (*)
-		const uint8_t gaps = action->data0 & 0x7F,
-			crush = action->data0 & 0x80,
-			num = action->data1 & 0x0F,
-			dir = action->data1 >> 4;
+		const uint8_t gaps = GET_DATA0(action) & 0x7F,
+			crush = GET_DATA0(action) & 0x80,
+			num = GET_DATA1(action) & 0x0F,
+			dir = GET_DATA1(action) >> 4;
 		const int8_t delta = deltas[dir];
 
 		int8_t steps = 1;
@@ -324,14 +325,14 @@ void action_undo(action_node_t *action) {
 	}
 }
 
-void action_to_ptn(action_node_t* action, char* out_ptn) {
-	const int8_t loc = action->loc;
-	if (action->type == A_PLACE) {
-		generate_place(loc, action->data0, out_ptn);
+void action_to_ptn(const action_t action, char* out_ptn) {
+	const int8_t loc = GET_LOC(action);
+	if (GET_TYPE(action) == A_PLACE) {
+		generate_place(loc, GET_DATA0(action), out_ptn);
 	} else {
-		const uint8_t gaps = action->data0 & 0x7F,
-			num = action->data1 & 0x0F, // unpack
-			dir = action->data1 >> 4;
+		const uint8_t gaps = GET_DATA0(action) & 0x7F,
+			num = GET_DATA1(action) & 0x0F, // unpack
+			dir = GET_DATA1(action) >> 4;
 
 		uint8_t drops[board_size]; // we only ever need board_size-1 in
 															 // drops actually, the last spot is to
@@ -357,17 +358,17 @@ void action_to_ptn(action_node_t* action, char* out_ptn) {
 // ===================================================================
 
 static inline void
-action_list_append(action_list_t *list, const enum A_TYPE type,
-										const int8_t loc, const uint8_t data0,
-										const uint8_t data1) {
+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
 
-	new->loc = loc;
-	new->type = type;
-	new->data0 = data0;
-	new->data1 = data1;
 	new->next = NULL;
+	new->action = (type << TYPE_SHIFT)
+		| (loc << LOC_SHIFT)
+		| (data0 << DATA0_SHIFT)
+		| data1;
 
 	if (list->length) {
 		list->tail->next = new;
diff --git a/include/action_list.h b/include/actions.h
index b6fd13a..661f11e 100644
--- a/include/action_list.h
+++ b/include/actions.h
@@ -1,19 +1,18 @@
+#ifndef ACTIONS_H
+#define ACTIONS_H
+
 #include <stdlib.h>
 #include <stdint.h>
 
 #include <tak.h>
 
-#ifndef ACTION_LIST_H
-#define ACTION_LIST_H
-
 enum A_TYPE { A_PLACE, A_MOVE };
 
+typedef uint32_t action_t;
+
 typedef struct action_node_s {
 	struct action_node_s *next;
-	enum A_TYPE type;
-	int8_t loc;
-	uint8_t data0;
-	uint8_t data1;
+	action_t action;
 } action_node_t;
 
 typedef struct action_list_s {
@@ -24,11 +23,11 @@ typedef struct action_list_s {
 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);
+int action_move_to_front(const action_t action, action_list_t *list);
 
-void action_take(action_node_t *action);
-void action_undo(action_node_t *action);
+void action_take(const action_t action);
+void action_undo(const action_t action);
 
-void action_to_ptn(action_node_t* action, char* out_ptn);
+void action_to_ptn(const action_t action, char* out_ptn);
 
 #endif
diff --git a/include/negamax.c b/include/negamax.c
index f6a7525..7f05040 100644
--- a/include/negamax.c
+++ b/include/negamax.c
@@ -131,6 +131,7 @@ negamax(const uint8_t cur_depth, float alpha, float beta,
 	uint64_t hash = zobrist_compute();
 	tt_entry_t *entry = tt_seek(hash);
 
+	// CAUTION: >= breaks search stability
 	if (entry != NULL && entry->depth == cur_depth) {
 		if (entry->flag == TT_EXACT) {
 			return entry->value;
@@ -146,15 +147,16 @@ negamax(const uint8_t cur_depth, float alpha, float beta,
 	if ((list = action_list_generate()) == NULL)
 		return alpha; // should never happen!
 
+	if (entry != NULL) {
+		action_move_to_front(entry->action, list);
+	}
 
-	/*
-	 * action_node_t *best = NULL;
-	 */
-
+	action_t best_action;
 	float value = -infty;
+
 	for (action_node_t *node=list->head; node!=NULL; node=node->next) {
 
-		action_take(node);
+		action_take(node->action);
 		// Compute the value of the node
 		float node_value;
 		if (ply >= 2*board_size - 2 && (w = check_win()) < 0xFF) {
@@ -168,14 +170,15 @@ negamax(const uint8_t cur_depth, float alpha, float beta,
 		} else {
 			node_value = colour * cnn1986_evaluate_black_win();
 		}
-		action_undo(node);
+		action_undo(node->action);
 
 		negamax_display_progress(cur_depth, list->length);
 
 		if (node_value > value) {
 			value = node_value;
+			best_action = node->action;
 			if (cur_depth == negamax_search_depth)
-				action_to_ptn(node, negamax_ptn);
+				action_to_ptn(node->action, negamax_ptn);
 		}
 
 		alpha = fmax(value, alpha);
@@ -189,12 +192,12 @@ negamax(const uint8_t cur_depth, float alpha, float beta,
 	else if (value <= alpha) flag = TT_UPPERBOUND;
 
 	if (entry == NULL) {
-		tt_insert(hash, flag, cur_depth, value);
+		tt_insert(hash, flag, cur_depth, value, best_action);
 	} else {
 		entry->flag = flag;
 		entry->value = value;
 		entry->depth = cur_depth;
-		// entry->action = best;
+		entry->action = best_action;
 	}
 
 	return value;
diff --git a/include/negamax.h b/include/negamax.h
index c902d3c..43995d1 100644
--- a/include/negamax.h
+++ b/include/negamax.h
@@ -2,7 +2,7 @@
 #include <math.h>
 
 #include <tak.h>
-#include <action_list.h>
+#include <actions.h>
 #include <xorshift64.h>
 #include <cnn1986.h>
 #include <tt_treap.h>
diff --git a/include/tt_treap.c b/include/tt_treap.c
index b48ffd4..369d767 100644
--- a/include/tt_treap.c
+++ b/include/tt_treap.c
@@ -12,10 +12,14 @@ static tt_entry_t * root;
 // ===================================================================
 
 void recurse_tree(tt_entry_t *n);
-tt_entry_t *new_treap_node(const uint64_t key, const enum TT_FLAG flag,
-													 const uint8_t depth, const float value);
 void bubble_up(tt_entry_t *n);
 
+tt_entry_t *
+new_treap_node(const uint64_t key, const enum TT_FLAG flag,
+							 const uint8_t depth, const float value,
+							 const action_t action);
+
+
 // ===================================================================
 // Exported functions
 // ===================================================================
@@ -43,8 +47,9 @@ tt_entry_t *tt_seek(const uint64_t key) {
 }
 
 int tt_insert(const uint64_t key, const enum TT_FLAG flag,
-										const uint8_t depth, const float value) {
-	tt_entry_t *m = new_treap_node(key, flag, depth, value);
+							const uint8_t depth, const float value,
+							const action_t action) {
+	tt_entry_t *m = new_treap_node(key, flag, depth, value, action);
 	if (root == NULL) {
 		root = m;
 		tt_num_cached = 1;
@@ -78,8 +83,10 @@ void recurse_tree(tt_entry_t *n) {
 	free(n);
 }
 
-tt_entry_t *new_treap_node(const uint64_t key, const enum TT_FLAG flag,
-													 const uint8_t depth, const float value) {
+tt_entry_t *
+new_treap_node(const uint64_t key, const enum TT_FLAG flag,
+							 const uint8_t depth, const float value,
+							 const action_t action) {
 	tt_entry_t *n = malloc(sizeof(struct treap_node_s));
 	// TODO: trap
 	n->key = key;
@@ -89,6 +96,7 @@ tt_entry_t *new_treap_node(const uint64_t key, const enum TT_FLAG flag,
 	n->left = NULL;
 	n->right = NULL;
 	n->parent = NULL;
+	n->action = action;
 	XORSHIFT64; n->weight = RANDOM32;
 	return n;
 }
diff --git a/include/tt_treap.h b/include/tt_treap.h
index 1a15e1b..3991e79 100644
--- a/include/tt_treap.h
+++ b/include/tt_treap.h
@@ -1,10 +1,11 @@
+#ifndef TT_TREAP_H
+#define TT_TREAP_H
+
 #include <stdlib.h>
 #include <stdint.h>
-#include <action_list.h>
-#include <xorshift64.h>
 
-#ifndef TT_TREAP_H
-#define TT_TREAP_H
+#include <actions.h>
+#include <xorshift64.h>
 
 // ===================================================================
 // Types
@@ -19,7 +20,7 @@ typedef struct treap_node_s {
 	enum TT_FLAG flag;
 	uint8_t depth;
 	float value;
-	action_node_t *action;
+	action_t action;
 } tt_entry_t;
 
 // ===================================================================
@@ -38,7 +39,7 @@ 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);
+							const uint8_t depth, const float value,
+							const action_t action);
 
 #endif