experimenting with a lazy queue implementationlazy_queue

presently it's not correct

5 files changed, 93 insertions, 106 deletions

diff --git a/include/actions.c b/include/actions.c
index 4f226e1..c926e52 100644
--- a/include/actions.c
+++ b/include/actions.c
@@ -26,14 +26,14 @@
 #define CLR_STONE NUM_MASK
 
 static inline void
-list_append(action_list_t *list, const enum A_TYPE type,
-						const int8_t loc, const uint8_t data0,
-						const uint8_t data1);
+lq_append(action_lq_t *lq, const enum A_TYPE type,
+           const int8_t loc, const uint8_t data0,
+           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);
+lq_prepend(action_lq_t *lq, const enum A_TYPE type,
+            const int8_t loc, const uint8_t data0,
+            const uint8_t data1);
 
 static inline void
 inline_next_ply(void);
@@ -45,42 +45,50 @@ inline_prev_ply(void);
 // Exported method implementations
 // ===================================================================
 
-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;
+int action_move_to_front(const action_t action, action_lq_t *lq) {
+	for (int k=lq->i_f; k<lq->i_b; k++) {
+		if (lq->actions[k] == action) {
+			for (int j=k; j>lq->i_f; j--) {
+				lq->actions[j] = lq->actions[j-1];
+			}
+			lq->actions[lq->i_f] = action;
 			return EXIT_SUCCESS;
 		}
-		n = n->next;
 	}
-
 	return EXIT_FAILURE;
 }
 
+action_lq_t *action_lq_copy_with_mtf(action_lq_t *lq, action_t front) {
+	// Normalise, empty list ---> null
+	if (lq == NULL || lq->length == 0) return NULL;
+	action_lq_t *copy = malloc(sizeof(action_lq_t));
+
+	copy->length = lq->length;
+	copy->i_b = lq->i_b;
+	copy->i_f = lq->i_f;
 
-void action_list_free(action_list_t *list) {
-	if (list) {
-		action_node_t *n = list->head, *nn;
-		while (n) {
-			nn = n->next;
-			free(n);
-			n = nn;
+	for (int source=lq->i_f, dest=copy->i_f+1;
+	     source < lq->i_b; source++, dest++) {
+		if (lq->actions[source] == front) {
+			source++;
+			if (source >= lq->i_b) break;
 		}
-		free(list);
+		copy->actions[dest] = lq->actions[source];
 	}
+
+	copy->actions[copy->i_f] = front;
+
+	return copy;
+}
+
+void action_lq_free(action_lq_t *lq) {
+	free(lq);
 }
 
 // Keep track of move offsets
 int8_t move_deltas[4];
 
-void action_list_init(void) {
+void action_lq_init(void) {
 	move_deltas[0] = +board_size;
 	move_deltas[1] = -board_size;
 	move_deltas[2] = -1;
@@ -89,12 +97,13 @@ void action_list_init(void) {
 
 // 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));
+action_lq_t *action_lq_generate(void) {
+	action_lq_t *lq = malloc(sizeof(action_lq_t));
 
 	// TODO: trap errno
-	list->length = 0;
-	list->head = NULL;
+	lq->length = 0;
+	lq->i_f = ACTION_AR_LEN;
+	lq->i_b = ACTION_AR_LEN;
 
 	/*
 	 * The check for whether it's a black piece to be played is actually
@@ -183,9 +192,9 @@ action_list_t *action_list_generate(void) {
 											(steps == end_stops[dir]) && crushes[dir];
 										// Store the move
 
-										list_append(list, A_MOVE, loc,
-																(crush << 7) | gaps,
-																(dir<<4) | num);
+										lq_append(lq, A_MOVE, loc,
+										           (crush << 7) | gaps,
+										           (dir<<4) | num);
 									}
 									/*
 									 * With thanks to
@@ -205,16 +214,16 @@ action_list_t *action_list_generate(void) {
 			else if (material) {
 				// Empty square, generate placements
 				if (flat) {
-					list_prepend(list, A_PLACE, loc, STONE_FLAT, 0);
+					lq_prepend(lq, A_PLACE, loc, STONE_FLAT, 0);
 					if (standing)
-						list_prepend(list, A_PLACE, loc, STONE_STANDING,0);
+						lq_prepend(lq, A_PLACE, loc, STONE_STANDING,0);
 				}
 				if (cap)
-					list_prepend(list, A_PLACE, loc, STONE_CAPSTONE, 0);
+					lq_prepend(lq, A_PLACE, loc, STONE_CAPSTONE, 0);
 			}
 		}
 	}
-	return list;
+	return lq;
 }
 
 void action_take(const action_t action) {
@@ -383,42 +392,19 @@ void action_to_ptn(const action_t action, char* out_ptn) {
 // ===================================================================
 
 static inline void
-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_node_t));
-	// TODO: trap errno
-
-	new->next = NULL;
-	new->action = A_BUILD(type, loc, data0, data1);
-
-	if (list->length) {
-		list->tail->next = new;
-		list->tail = new;
-	} else {
-		list->head = new;
-		list->tail = new;
-	}
-
-	list->length++;
+lq_append(action_lq_t *lq, const enum A_TYPE type,
+           const int8_t loc, const uint8_t data0,
+           const uint8_t data1) {
+	lq->actions[lq->i_b++] = A_BUILD(type, loc, data0, data1);
+	lq->length++;
 }
 
 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++;
+lq_prepend(action_lq_t *lq, const enum A_TYPE type,
+            const int8_t loc, const uint8_t data0,
+            const uint8_t data1) {
+	lq->actions[--lq->i_f] = A_BUILD(type, loc, data0, data1);
+	lq->length++;
 }
 
 static inline void
diff --git a/include/actions.h b/include/actions.h
index 75c881e..54b9077 100644
--- a/include/actions.h
+++ b/include/actions.h
@@ -44,15 +44,12 @@ typedef uint32_t action_t;
 																			 | (data0) << A_DATA0_SHIFT		\
 																			 | (data1) << A_DATA1_SHIFT)
 
-typedef struct action_node_s {
-	struct action_node_s *next;
-	action_t action;
-} action_node_t;
-
-typedef struct action_list_s {
-	struct action_node_s *head, *tail;
-	uint32_t length;
-} action_list_t;
+// lazy queue
+#define ACTION_AR_LEN 256
+typedef struct action_lq_s {
+	action_t actions[ACTION_AR_LEN*2];
+	int length, i_f, i_b;
+} action_lq_t;
 
 // ===================================================================
 // Variables
@@ -64,11 +61,12 @@ extern int8_t move_deltas[4];
 // Methods
 // ===================================================================
 
-void action_list_init(void);
-void action_list_free(action_list_t *list);
-action_list_t *action_list_generate(void);
+void action_lq_init(void);
+void action_lq_free(action_lq_t *lq);
+action_lq_t *action_lq_generate(void);
+action_lq_t *action_lq_copy_with_mtf(action_lq_t *lq, action_t front);
 
-int action_move_to_front(const action_t action, action_list_t *list);
+int action_move_to_front(const action_t action, action_lq_t *lq);
 
 void action_take(const action_t action);
 void action_undo(const action_t action);
diff --git a/include/negamax.c b/include/negamax.c
index 30aed05..8c06c5f 100644
--- a/include/negamax.c
+++ b/include/negamax.c
@@ -40,7 +40,7 @@ static float negamax(const uint8_t cur_depth, const uint8_t init_depth,
 
 void negamax_init(const uint8_t new_board_size) {
 	board_size = new_board_size;
-	action_list_init();
+	action_lq_init();
 	zobrist_init();
 	tt_init();
 }
@@ -82,10 +82,11 @@ static float negamax(const uint8_t cur_depth, const uint8_t init_depth,
 										 float alpha, float beta,
 										 const float colour, const uint64_t hash) {
 
+	action_lq_t *lq = NULL;
 	tt_entry_t *entry = tt_seek(hash);
 
-	// CAUTION: ≥ breaks search stability (vs =) on shallow depths
 	if (entry != NULL && entry->depth >= cur_depth) {
+		// CAUTION: ≥ breaks search stability (vs =) on shallow depths
 		if (entry->flag == TT_EXACT) {
 			return entry->value;
 		} else if (entry->flag == TT_LOWERBOUND && entry->value > alpha) {
@@ -95,27 +96,27 @@ static float negamax(const uint8_t cur_depth, const uint8_t init_depth,
 		}
 		if (alpha >= beta) return entry->value;
 	}
+	//		lq = action_lq_copy_with_mtf(entry->lq, entry->best);
 
-	action_list_t *list;
-	if ((list = action_list_generate()) == NULL)
+	if ((lq = action_lq_generate()) == NULL)
 		return alpha; // should never happen!
 
 	if (entry != NULL) {
-		action_move_to_front(entry->action, list);
+		action_move_to_front(entry->best, lq);
 	}
 
 	if (init_depth > 1 && cur_depth == init_depth) {
-		action_move_to_front(negamax_best_action, list);
+		action_move_to_front(negamax_best_action, lq);
 	}
 
 	// TODO: what to do if this is never written to?
-	action_t best_action = list->head->action;
+	action_t best_action = lq->actions[lq->i_f];
 	float best_value = -infty;
 
-	for (action_node_t *node=list->head; node!=NULL; node=node->next) {
-		negamax_display_progress(cur_depth, init_depth, list->length);
+	for (int k=lq->i_f; k<lq->i_b; k++) {
+		negamax_display_progress(cur_depth, init_depth, lq->length);
 
-		action_take(node->action);
+		action_take(lq->actions[k]);
 
 		// Compute the value of the node
 		float node_value;
@@ -135,18 +136,18 @@ static float negamax(const uint8_t cur_depth, const uint8_t init_depth,
 		} else {
 			node_value = colour * cnn1986_evaluate_black_win();
 		}
-		action_undo(node->action);
+		action_undo(lq->actions[k]);
 
 		if (node_value > best_value) {
 			best_value = node_value;
-			best_action = node->action;
+			best_action = lq->actions[k];
 		}
 
 		if (best_value > alpha) alpha = best_value;
 		if (alpha >= beta) break;
 	}
 
-	action_list_free(list);
+	action_lq_free(lq);
 	if (cur_depth == init_depth) negamax_best_action = best_action;
 
 	flag = TT_EXACT;
@@ -157,9 +158,9 @@ static float negamax(const uint8_t cur_depth, const uint8_t init_depth,
 		tt_insert(hash, flag, cur_depth, best_value, best_action);
 	} else {
 		entry->flag = flag;
+		entry->best = best_action;
 		entry->value = best_value;
 		entry->depth = cur_depth;
-		entry->action = best_action;
 	}
 
 	return best_value;
diff --git a/include/tt_llcht.c b/include/tt_llcht.c
index 60f8ccc..51ebad9 100644
--- a/include/tt_llcht.c
+++ b/include/tt_llcht.c
@@ -29,7 +29,7 @@ static tt_entry_t *table[TT_LLCHT_SIZE+1];
 
 tt_entry_t * new_ll_node(const uint64_t key, const enum TT_FLAG flag,
 												 const uint8_t depth, const float value,
-												 const action_t action);
+                         const action_t best);
 
 
 // ===================================================================
@@ -63,8 +63,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,
-							const action_t action) {
-	tt_entry_t *new = new_ll_node(key, flag, depth, value, action), *n;
+              const action_t best) {
+	tt_entry_t *n,
+		*new = new_ll_node(key, flag, depth, value, best);
 	// TODO: trap
 
 	const uint32_t idx = key & TT_LLCHT_SIZE;
@@ -84,14 +85,14 @@ int tt_insert(const uint64_t key, const enum TT_FLAG flag,
 
 tt_entry_t * new_ll_node(const uint64_t key, const enum TT_FLAG flag,
 												 const uint8_t depth, const float value,
-												 const action_t action) {
+                         const action_t best) {
 	tt_entry_t *new = malloc(sizeof(struct tt_node_s));
 	// TODO: trap errno
 	new->key = key;
+	new->best = best;
 	new->next = NULL;
 	new->flag = flag;
 	new->depth = depth;
 	new->value = value;
-	new->action = action;
 	return new;
 }
diff --git a/include/tt_llcht.h b/include/tt_llcht.h
index 377de10..c1151a0 100644
--- a/include/tt_llcht.h
+++ b/include/tt_llcht.h
@@ -35,7 +35,8 @@ typedef struct tt_node_s {
 	enum TT_FLAG flag;
 	uint8_t depth;
 	float value;
-	action_t action;
+	action_t best;
+	//	action_lq_t *lq;
 } tt_entry_t;
 
 // ===================================================================
@@ -55,6 +56,6 @@ 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,
-							const action_t action);
+              const action_t best);
 
 #endif