diff options
Diffstat (limited to 'include')
| -rw-r--r-- | include/negamax.c | 35 | ||||
| -rw-r--r-- | include/negamax.h | 1 |
2 files changed, 26 insertions, 10 deletions
diff --git a/include/negamax.c b/include/negamax.c index 44deea9..f5bbf02 100644 --- a/include/negamax.c +++ b/include/negamax.c @@ -24,12 +24,14 @@ const float infty = 3.0; char negamax_ptn[9]; uint8_t negamax_search_depth = 3; +static uint64_t negamax_best_action; // =================================================================== // Helper declarations // =================================================================== -static float negamax(const uint8_t cur_depth, float alpha, float beta, +static float negamax(const uint8_t cur_depth, const uint8_t init_depth, + float alpha, float beta, const float colour, const uint64_t hash); // =================================================================== @@ -51,25 +53,31 @@ 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; + + negamax_best_action = -1; tt_init(); - float result = - negamax(negamax_search_depth, -safe_infty, safe_infty, - (ply & 1) ? +1.0 : -1.0, zobrist_compute()); + 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(); return result; } // =================================================================== -// α-β negamax using the cnn1986 evaluation function and transposition -// tables using Zobrist hasing and a chaining hash table +// α-β negamax with iterative deepening, using the cnn1986 evaluation +// function and transposition tables using Zobrist hasing and a +// chaining hash table // =================================================================== static enum TT_FLAG flag; static enum WIN_TYPE w; -static float negamax(const uint8_t cur_depth, float alpha, float beta, +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); @@ -94,12 +102,16 @@ static float negamax(const uint8_t cur_depth, float alpha, float beta, 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, list->length); + negamax_display_progress(cur_depth, init_depth, list->length); action_take(node->action); @@ -115,7 +127,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, + node_value = -negamax(cur_depth - 1, init_depth, + -beta, -alpha, -colour, zobrist_compute()); } else { node_value = colour * cnn1986_evaluate_black_win(); @@ -125,8 +138,10 @@ static float negamax(const uint8_t cur_depth, float alpha, float beta, if (node_value > best_value) { best_value = node_value; best_action = node->action; - if (cur_depth == negamax_search_depth) + if (cur_depth == init_depth) { action_to_ptn(node->action, negamax_ptn); + negamax_best_action = best_action; + } } if (best_value > alpha) alpha = best_value; diff --git a/include/negamax.h b/include/negamax.h index 77461b8..b3dec75 100644 --- a/include/negamax.h +++ b/include/negamax.h @@ -33,6 +33,7 @@ extern char negamax_ptn[9]; extern uint8_t negamax_search_depth; extern void negamax_display_progress(const uint8_t cur_depth, + const uint8_t init_depth, const uint32_t length); // =================================================================== |