aboutsummaryrefslogtreecommitdiff
path: root/include/negamax.c
diff options
context:
space:
mode:
Diffstat (limited to 'include/negamax.c')
-rw-r--r--include/negamax.c208
1 files changed, 106 insertions, 102 deletions
diff --git a/include/negamax.c b/include/negamax.c
index e85aba9..0f2c450 100644
--- a/include/negamax.c
+++ b/include/negamax.c
@@ -16,6 +16,7 @@
*/
#include "negamax.h"
+#include "actions.h"
// ===================================================================
// Variables
@@ -30,43 +31,40 @@ static uint64_t negamax_best_action;
// Helper declarations
// ===================================================================
-static float negamax(const uint8_t cur_depth, const uint8_t init_depth,
- float alpha, float beta,
- const float colour, const uint64_t hash);
+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);
// ===================================================================
// Exported functions
// ===================================================================
void negamax_init(const uint8_t new_board_size) {
- board_size = new_board_size;
- action_list_init();
- zobrist_init();
- tt_init();
+ action_list_init(new_board_size);
+ zobrist_init(new_board_size);
+ tt_init();
}
-void negamax_free(void) {
- zobrist_free();
-}
+void negamax_free(void) { zobrist_free(); }
-float negamax_generate(void) {
- // We need to start with something outside of [-∞,∞] because those
- // values are wins
- const float safe_infty = infty + 1;
- float result = -infty;
+float negamax_generate(tak_state_p state) {
+ // We need to start with something outside of [-∞,∞] because those
+ // values are wins
+ const float safe_infty = infty + 1;
+ float result = -infty;
- negamax_best_action = -1;
+ negamax_best_action = -1;
- tt_init();
- for (int d = 1; d <= negamax_search_depth; d++) {
- result = negamax(d, d, -safe_infty, safe_infty,
- (ply & 1) ? +1.0 : -1.0, zobrist_compute());
- }
- tt_free();
+ tt_init();
+ 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, zobrist_compute(state));
+ }
+ tt_free();
- action_to_ptn(negamax_best_action, negamax_ptn);
+ action_to_ptn(negamax_best_action, negamax_ptn);
- return result;
+ return result;
}
// ===================================================================
@@ -78,89 +76,95 @@ float negamax_generate(void) {
static enum TT_FLAG flag;
static enum WIN_TYPE w;
-static float negamax(const uint8_t cur_depth, const uint8_t init_depth,
- float alpha, float beta,
- const float colour, const uint64_t hash) {
-
- tt_entry_t *entry = tt_seek(hash);
-
- // CAUTION: ≥ breaks search stability (vs =) on shallow depths
- if (entry != NULL && entry->depth >= cur_depth) {
- if (entry->flag == TT_EXACT) {
- 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) return entry->value;
- }
+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) {
- action_list_t *list;
- if ((list = action_list_generate()) == NULL)
- return alpha; // should never happen!
-
- if (entry != NULL) {
- action_move_to_front(entry->action, list);
- }
+ tt_entry_t *entry = tt_seek(hash);
- if (init_depth > 1 && cur_depth == init_depth) {
- action_move_to_front(negamax_best_action, list);
+ // CAUTION: ≥ breaks search stability (vs =) on shallow depths
+ if (entry != NULL && entry->depth >= cur_depth) {
+ if (entry->flag == TT_EXACT) {
+ 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;
}
-
- // TODO: what to do if this is never written to?
- action_t best_action = list->head->action;
- 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);
-
- action_take(node->action);
-
- // Compute the value of the node
- float node_value;
- if (ply >= 2*board_size - 2 && (w = check_win()) < 0xFF) {
- node_value = -colour*infty;
- // Check win if far enough into the game
- if (w == WIN_ROAD_BLACK || w == WIN_FLAT_BLACK) {
- node_value = colour*infty;
- } else if (w == WIN_DRAW) {
- node_value = 0;
- }
- } else if (cur_depth > 1) {
- // If nobody won, or too early and not leaf, recurse
- node_value = -negamax(cur_depth - 1, init_depth,
- -beta, -alpha,
- -colour, zobrist_compute());
- } else {
- node_value = colour * nn1986_evaluate_black_win();
- }
- action_undo(node->action);
-
- if (node_value > best_value) {
- best_value = node_value;
- best_action = node->action;
- }
-
- if (best_value > alpha) alpha = best_value;
- if (alpha >= beta) break;
+ if (alpha >= beta)
+ return entry->value;
+ }
+
+ action_list_t *list;
+ if ((list = action_list_generate(state)) == NULL)
+ return alpha; // should never happen!
+
+ if (entry != NULL) {
+ action_move_to_front(entry->action, list);
+ }
+
+ if (init_depth > 1 && cur_depth == init_depth) {
+ action_move_to_front(negamax_best_action, list);
+ }
+
+ // TODO: what to do if this is never written to?
+ action_t best_action = list->head->action;
+ 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);
+
+ action_take(state, node->action);
+
+ // Compute the value of the node
+ float node_value;
+ if (state->ply >= 2 * state->board_size - 2 &&
+ (w = check_win(state)) < 0xFF) {
+ node_value = -colour * infty;
+ // Check win if far enough into the game
+ if (w == WIN_ROAD_BLACK || w == WIN_FLAT_BLACK) {
+ node_value = colour * infty;
+ } else if (w == WIN_DRAW) {
+ node_value = 0;
+ }
+ } 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, zobrist_compute(state));
+ } else {
+ node_value = colour * nn1986_evaluate_black_win(state);
}
+ action_undo(state, node->action);
- action_list_free(list);
- if (cur_depth == init_depth) negamax_best_action = best_action;
-
- flag = TT_EXACT;
- if (best_value >= beta) flag = TT_LOWERBOUND;
- else if (best_value <= 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;
+ if (node_value > best_value) {
+ best_value = node_value;
+ best_action = node->action;
}
- return best_value;
+ if (best_value > alpha)
+ alpha = best_value;
+ if (alpha >= beta)
+ break;
+ }
+
+ action_list_free(list);
+ if (cur_depth == init_depth)
+ negamax_best_action = best_action;
+
+ flag = TT_EXACT;
+ if (best_value >= beta)
+ flag = TT_LOWERBOUND;
+ else if (best_value <= 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;
+ }
+
+ return best_value;
}
generated by cgit v1.2.3 (git 2.46.0) at 2026-08-30 10:00:06 +0000