aboutsummaryrefslogtreecommitdiff
path: root/include/negamax.c
diff options
context:
space:
mode:
Diffstat (limited to 'include/negamax.c')
-rw-r--r--include/negamax.c90
1 files changed, 71 insertions, 19 deletions
diff --git a/include/negamax.c b/include/negamax.c
index 7b4acc1..6c29481 100644
--- a/include/negamax.c
+++ b/include/negamax.c
@@ -17,6 +17,9 @@
#include "negamax.h"
#include "actions.h"
+#ifdef RECORD_PV
+#include "pv.h"
+#endif
// ===================================================================
// Variables
@@ -54,7 +57,11 @@ static inline enum WIN_TYPE check_win_cached(tak_state_p state,
static float negamax(tak_state_p state, const uint8_t cur_depth,
const uint8_t init_depth, float alpha, float beta,
- const float colour, const uint64_t hash);
+ const float colour, const uint64_t hash
+#ifdef RECORD_PV
+ , pv_leaf_t *out_leaf
+#endif
+);
// ===================================================================
// Exported functions
@@ -84,7 +91,7 @@ float negamax_generate(tak_state_p state) {
negamax_best_action = -1;
- // The transposition table is deliberately NOT cleared here: entries persist
+ // The transposition table is deliberately not cleared here: entries persist
// across plies. This is sound because the table is keyed on (board, side to
// move) and an entry is only reusable at a depth no greater than the one it
// was stored at. In particular the new root (the previous root's child,
@@ -93,11 +100,22 @@ float negamax_generate(tak_state_p state) {
// this is constant across iterative deepening
const uint64_t root_hash = zobrist_compute(state);
+#ifdef RECORD_PV
+ pv_leaf_t iteration_leaf;
+#endif
for (int d = 1; d <= negamax_search_depth; d++) {
result = negamax(state, d, d, -safe_infty, safe_infty,
- (state->ply & 1) ? +1.0 : -1.0, root_hash);
+ (state->ply & 1) ? +1.0 : -1.0, root_hash
+#ifdef RECORD_PV
+ , &iteration_leaf
+#endif
+ );
}
+#ifdef RECORD_PV
+ pv_publish_leaf(&iteration_leaf);
+#endif
+
action_to_ptn(negamax_best_action, negamax_ptn);
return result;
@@ -112,26 +130,43 @@ static enum WIN_TYPE w;
static float negamax(tak_state_p state, const uint8_t cur_depth,
const uint8_t init_depth, float alpha, float beta,
- const float colour, const uint64_t hash) {
+ const float colour, const uint64_t hash
+#ifdef RECORD_PV
+ , pv_leaf_t *out_leaf
+#endif
+) {
+
+ // the scratch buffer is per-level so that recursion does not clobber
+ const uint32_t level = init_depth - cur_depth;
tt_entry_t *entry = tt_seek(hash);
- if (entry != NULL && entry->depth >= cur_depth) {
+ // The root never early-returns from the table. Within one game the new
+ // root was only ever stored at depth D-1, so an early return could not
+ // fire anyway; across games the table persists across reset_state and
+ // a stale full-depth entry would early-return and leave
+ // negamax_best_action unset.
+ if (level > 0 && entry != NULL && entry->depth >= cur_depth) {
if (entry->flag == TT_EXACT) {
+#ifdef RECORD_PV
+ *out_leaf = entry->leaf;
+#endif
return entry->value;
} else if (entry->flag == TT_LOWERBOUND && entry->value > alpha) {
alpha = entry->value;
} else if (entry->flag == TT_UPPERBOUND && entry->value < beta) {
beta = entry->value;
}
- if (alpha >= beta)
+ if (alpha >= beta) {
+#ifdef RECORD_PV
+ *out_leaf = entry->leaf;
+#endif
return entry->value;
+ }
}
action_t *actions;
uint32_t num_actions;
- // the scratch buffer is per-level so that recursion does not clobber
- const uint32_t level = init_depth - cur_depth;
if ((actions = actions_generate_at(state, &num_actions, level)) == NULL)
return alpha; // should never happen!
@@ -153,6 +188,9 @@ static float negamax(tak_state_p state, const uint8_t cur_depth,
action_t best_action = actions[0];
float best_value = -infty;
+#ifdef RECORD_PV
+ pv_leaf_t candidate_leaf, best_leaf;
+#endif
for (uint32_t idx = 0; idx<num_actions; idx++) {
negamax_display_progress(cur_depth, init_depth, num_actions);
@@ -161,7 +199,7 @@ static float negamax(tak_state_p state, const uint8_t cur_depth,
const uint64_t child_hash = zobrist_compute(state);
- // Compute the value of the node
+ // Compute the value of the node and retain the leaf that produced it.
float node_value;
if (state->ply >= 2 * state->board_size - 2 &&
(w = check_win_cached(state, child_hash)) < 0xFF) {
@@ -172,18 +210,31 @@ static float negamax(tak_state_p state, const uint8_t cur_depth,
} else if (w == WIN_DRAW) {
node_value = 0;
}
+#ifdef RECORD_PV
+ pv_capture_leaf(&candidate_leaf, state, w);
+#endif
} else if (cur_depth > 1) {
// If nobody won, or too early and not leaf, recurse
node_value = -negamax(state, cur_depth - 1, init_depth, -beta, -alpha,
- -colour, child_hash);
+ -colour, child_hash
+#ifdef RECORD_PV
+ , &candidate_leaf
+#endif
+ );
} else {
node_value = colour * evaluate(state);
+#ifdef RECORD_PV
+ pv_capture_leaf(&candidate_leaf, state, (enum WIN_TYPE)0xFF);
+#endif
}
action_undo(state, actions[idx]);
- if (node_value > best_value) {
+ if (idx == 0 || node_value > best_value) {
best_value = node_value;
best_action = actions[idx];
+#ifdef RECORD_PV
+ best_leaf = candidate_leaf;
+#endif
}
if (best_value > alpha)
@@ -195,20 +246,21 @@ static float negamax(tak_state_p state, const uint8_t cur_depth,
if (cur_depth == init_depth)
negamax_best_action = best_action;
+#ifdef RECORD_PV
+ *out_leaf = best_leaf;
+#endif
+
flag = TT_EXACT;
if (best_value >= beta)
flag = TT_LOWERBOUND;
else if (best_value <= orig_alpha)
flag = TT_UPPERBOUND;
- if (entry == NULL) {
- tt_insert(hash, flag, cur_depth, best_value, best_action);
- } else {
- entry->flag = flag;
- entry->value = best_value;
- entry->depth = cur_depth;
- entry->action = best_action;
- }
+ entry = tt_store(hash, flag, cur_depth, best_value, best_action);
+#ifdef RECORD_PV
+ if (entry != NULL)
+ entry->leaf = best_leaf;
+#endif
return best_value;
}
generated by cgit v1.3.1 (git 2.54.0) at 2026-10-15 08:31:49 +0000