From 7e58eadab1678d794344a0b14c7872296f585f96 Mon Sep 17 00:00:00 2001
From: tslil <tslil@posteo.de>
Date: Sat, 3 Jul 2021 16:17:27 -0400
Subject: experimenting with a lazy queue implementation

presently it's not correct
---
 include/negamax.c | 29 +++++++++++++++--------------
 1 file changed, 15 insertions(+), 14 deletions(-)

(limited to 'include/negamax.c')

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;
-- 
cgit v1.2.3