diff options
Diffstat (limited to 'include/negamax.c')
| -rw-r--r-- | include/negamax.c | 232 |
1 files changed, 116 insertions, 116 deletions
diff --git a/include/negamax.c b/include/negamax.c index 30aed05..e85aba9 100644 --- a/include/negamax.c +++ b/include/negamax.c @@ -1,18 +1,18 @@ /* - This file is part of ct. + This file is part of ct. - This program is free software: you can redistribute it and/or modify - it under the terms of the GNU General Public License as published by - the Free Software Foundation, either version 3 of the License, or - (at your option) any later version. + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. - This program is distributed in the hope that it will be useful, but - WITHOUT ANY WARRANTY; without even the implied warranty of - MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU - General Public License for more details. + This program is distributed in the hope that it will be useful, but + WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + General Public License for more details. - You should have received a copy of the GNU General Public License - along with ct. If not, see <https://www.gnu.org/licenses/>. + You should have received a copy of the GNU General Public License + along with ct. If not, see <https://www.gnu.org/licenses/>. */ #include "negamax.h" @@ -31,46 +31,46 @@ static uint64_t negamax_best_action; // =================================================================== static float negamax(const uint8_t cur_depth, const uint8_t init_depth, - float alpha, float beta, - const float colour, const uint64_t hash); + 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(); + board_size = new_board_size; + action_list_init(); + zobrist_init(); + tt_init(); } void negamax_free(void) { - zobrist_free(); + 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; + // 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(d, d, -safe_infty, safe_infty, + (ply & 1) ? +1.0 : -1.0, zobrist_compute()); + } + tt_free(); - action_to_ptn(negamax_best_action, negamax_ptn); + action_to_ptn(negamax_best_action, negamax_ptn); - return result; + return result; } // =================================================================== -// α-β negamax with iterative deepening, using the cnn1986 evaluation +// α-β negamax with iterative deepening, using the nn1986 evaluation // function and transposition tables using Zobrist hasing and a // chaining hash table // =================================================================== @@ -79,88 +79,88 @@ 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; - } - - 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); - } - - 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(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 * cnn1986_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; - } - - 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; + 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; + } + + 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); + } + + 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(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; + } + + 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; } |