Try to squeeze out a little more performance

``Common wisdom'' dictates that placements are often better than stack
moves, so we bias the generated move list in this fashion. Seems to be
a little faster.

3 files changed, 47 insertions, 23 deletions

diff --git a/include/actions.c b/include/actions.c
index 800a2d4..316b19f 100644
--- a/include/actions.c
+++ b/include/actions.c
@@ -31,6 +31,11 @@ list_append(action_list_t *list, const enum A_TYPE type,
 						const uint8_t data1);
 
 static inline void
+list_prepend(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
@@ -82,6 +87,8 @@ void action_list_init(void) {
 	move_deltas[3] = +1;
 }
 
+// We bias place over move by prepending place actions and appending
+// move actions to the generated list
 action_list_t *action_list_generate(void) {
 	action_list_t *list = malloc(sizeof(struct action_list_s));
 
@@ -198,12 +205,12 @@ action_list_t *action_list_generate(void) {
 			else if (material) {
 				// Empty square, generate placements
 				if (flat) {
-					list_append(list, A_PLACE, loc, STONE_FLAT, 0);
+					list_prepend(list, A_PLACE, loc, STONE_FLAT, 0);
 					if (standing)
-						list_append(list, A_PLACE, loc, STONE_STANDING,0);
+						list_prepend(list, A_PLACE, loc, STONE_STANDING,0);
 				}
 				if (cap)
-					list_append(list, A_PLACE, loc, STONE_CAPSTONE, 0);
+					list_prepend(list, A_PLACE, loc, STONE_CAPSTONE, 0);
 			}
 		}
 	}
@@ -397,6 +404,24 @@ list_append(action_list_t *list, const enum A_TYPE type,
 }
 
 static inline void
+list_prepend(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->next = list->head;
+	list->head = new;
+	new->action = A_BUILD(type, loc, data0, data1);
+
+	if (list->length == 0) {
+		list->tail = new;
+	}
+
+	list->length++;
+}
+
+static inline void
 inline_next_ply(void) {
 	ply++;
 	if (ply == 2) {
diff --git a/include/actions.h b/include/actions.h
index a1c90cc..181aec2 100644
--- a/include/actions.h
+++ b/include/actions.h
@@ -31,18 +31,18 @@ enum A_TYPE { A_PLACE, A_MOVE };
 
 typedef uint32_t action_t;
 
-#define A_TYPE_SHIFT  24
-#define A_LOC_SHIFT   16
-#define A_DATA0_SHIFT  8
-
-#define A_GET_TYPE(a)  (enum A_TYPE)((a)>>A_TYPE_SHIFT)
-#define A_GET_LOC(a)   (int8_t)(((a)>>A_LOC_SHIFT) & 0xFF)
-#define A_GET_DATA0(a) (uint8_t)(((a)>>A_DATA0_SHIFT) & 0xFF)
-#define A_GET_DATA1(a) (uint8_t)((a) & 0xFF)
-#define A_BUILD(type,loc,data0,data1) ((type) << A_TYPE_SHIFT \
-																			 | (loc) << A_LOC_SHIFT \
-																			 | (data0) << A_DATA0_SHIFT \
-																			 | (data1))
+#define A_DATA1_SHIFT 24
+#define A_DATA0_SHIFT 16
+#define A_LOC_SHIFT   8
+
+#define A_GET_DATA1(a)  (enum A_TYPE)((a)>>A_DATA1_SHIFT)
+#define A_GET_DATA0(a)   (int8_t)(((a)>>A_DATA0_SHIFT) & 0xFF)
+#define A_GET_LOC(a) (uint8_t)(((a)>>A_LOC_SHIFT) & 0xFF)
+#define A_GET_TYPE(a) (uint8_t)((a) & 0xFF)
+#define A_BUILD(type,loc,data0,data1) ((type)												\
+																			 | (loc) << A_LOC_SHIFT				\
+																			 | (data0) << A_DATA0_SHIFT		\
+																			 | (data1) << A_DATA1_SHIFT)
 
 typedef struct action_node_s {
 	struct action_node_s *next;
diff --git a/include/negamax.c b/include/negamax.c
index cdcfcf9..44deea9 100644
--- a/include/negamax.c
+++ b/include/negamax.c
@@ -30,7 +30,7 @@ uint8_t negamax_search_depth = 3;
 // ===================================================================
 
 static float negamax(const uint8_t cur_depth, float alpha, float beta,
-				const float colour);
+										 const float colour, const uint64_t hash);
 
 // ===================================================================
 // Exported functions
@@ -54,9 +54,8 @@ float negamax_generate(void) {
 
 	tt_init();
 	float result =
-		negamax(negamax_search_depth,
-						-safe_infty, safe_infty,
-						(ply & 1) ? +1.0 : -1.0);
+		negamax(negamax_search_depth, -safe_infty, safe_infty,
+						(ply & 1) ? +1.0 : -1.0, zobrist_compute());
 	tt_free();
 
 	return result;
@@ -71,9 +70,8 @@ static enum TT_FLAG flag;
 static enum WIN_TYPE w;
 
 static float negamax(const uint8_t cur_depth, float alpha, float beta,
-										 const float colour) {
+										 const float colour, const uint64_t hash) {
 
-	uint64_t hash = zobrist_compute();
 	tt_entry_t *entry = tt_seek(hash);
 
 	// CAUTION: ≥ breaks search stability (vs =) on shallow depths
@@ -117,7 +115,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, -colour);
+			node_value = -negamax(cur_depth - 1, -beta, -alpha,
+														-colour, zobrist_compute());
 		} else {
 			node_value = colour * cnn1986_evaluate_black_win();
 		}
@@ -130,7 +129,7 @@ static float negamax(const uint8_t cur_depth, float alpha, float beta,
 				action_to_ptn(node->action, negamax_ptn);
 		}
 
-		alpha = fmax(best_value, alpha);
+		if (best_value > alpha) alpha = best_value;
 		if (alpha >= beta) break;
 	}