From 277b3150630878f83a6895bea73c6d5d36ed0dbf Mon Sep 17 00:00:00 2001 From: tslil clingman Date: Tue, 26 Jan 2021 14:38:19 -0500 Subject: Stable negamax-alpha-beta fail-soft --- include/action_list.c | 63 +++++++++++++++++++++++++++++++++++++++------------ include/action_list.h | 8 ++++++- include/negamax.c | 60 +++++++++++++++++++++++++++++++++--------------- include/tt_treap.h | 4 ++++ 4 files changed, 101 insertions(+), 34 deletions(-) (limited to 'include') diff --git a/include/action_list.c b/include/action_list.c index 9ddd74b..30ca918 100644 --- a/include/action_list.c +++ b/include/action_list.c @@ -9,10 +9,9 @@ #define CLR_STONE NUM_MASK static inline void -action_list_prepend(action_list_t *list, const enum A_TYPE type, - const int8_t loc, const uint8_t data0, - const uint8_t data1); - +action_list_append(action_list_t *list, const enum A_TYPE type, + const int8_t loc, const uint8_t data0, + const uint8_t data1); static inline void inline_next_ply(void); @@ -24,6 +23,30 @@ inline_prev_ply(void); // Exported method implementations // =================================================================== +/* + * void action_list_ensure_at_front(const action_node_t *action, + * const action_list_t *list) { + * action_node_t *copy = action_copy(action), *n = list->head, *nn; + * // ensure it's not there already + * while (n) { + * nn = n->next; + * } + * + * copy->next = list->head; + * } + */ + +action_node_t *action_copy(const action_node_t *action) { + action_node_t *copy = malloc(sizeof(struct action_node_s)); + // TODO: trap + copy->data0 = action->data0; + copy->data1 = action->data1; + copy->loc = action->loc; + copy->type = action->type; + copy->next = NULL; + return copy; +} + void action_list_free(action_list_t *list) { if (list) { action_node_t *n = list->head, *nn; @@ -64,9 +87,9 @@ action_list_t *action_list_generate(void) { cap = ((ply >= 2) && (material & 0x80)), standing = ((ply >= 2) && flat); - // Step across the board, reversed because we prepend to the list - for (int row = board_size - 1; row >= 0; row--) { - for (int col = board_size - 1; col >= 0; col--) { + // Step across the board + for (int row = 0; row < board_size; row++) { + for (int col = 0; col < board_size; col++) { // We'll need these at various points: the location of this // square and the maximum number of stones we could pick up const int loc = THE_COORDS(col, row); @@ -132,7 +155,8 @@ action_list_t *action_list_generate(void) { const uint8_t crush = (steps == end_stops[dir]) && crushes[dir]; // Store the move - action_list_prepend(list, A_MOVE, loc, + + action_list_append(list, A_MOVE, loc, (crush << 7) | gaps, (dir<<4) | num); } @@ -154,12 +178,12 @@ action_list_t *action_list_generate(void) { else if (material) { // Empty square, generate placements if (flat) { - action_list_prepend(list, A_PLACE, loc, STONE_FLAT, 0); + action_list_append(list, A_PLACE, loc, STONE_FLAT, 0); if (standing) - action_list_prepend(list, A_PLACE, loc, STONE_STANDING,0); + action_list_append(list, A_PLACE, loc, STONE_STANDING,0); } if (cap) - action_list_prepend(list, A_PLACE, loc, STONE_CAPSTONE, 0); + action_list_append(list, A_PLACE, loc, STONE_CAPSTONE, 0); } } } @@ -333,18 +357,27 @@ void action_to_ptn(action_node_t* action, char* out_ptn) { // =================================================================== static inline void -action_list_prepend(action_list_t *list, const enum A_TYPE type, +action_list_append(action_list_t *list, const enum A_TYPE type, const int8_t loc, const uint8_t data0, const uint8_t data1) { action_node_t *new = malloc(sizeof(action_list_t)); // TODO: trap errno - list->length++; + new->loc = loc; new->type = type; new->data0 = data0; new->data1 = data1; - new->next = list->head; - list->head = new; + new->next = NULL; + + if (list->length) { + list->tail->next = new; + list->tail = new; + } else { + list->head = new; + list->tail = new; + } + + list->length++; } static inline void diff --git a/include/action_list.h b/include/action_list.h index 14c733f..b6fd13a 100644 --- a/include/action_list.h +++ b/include/action_list.h @@ -3,6 +3,9 @@ #include +#ifndef ACTION_LIST_H +#define ACTION_LIST_H + enum A_TYPE { A_PLACE, A_MOVE }; typedef struct action_node_s { @@ -14,15 +17,18 @@ typedef struct action_node_s { } action_node_t; typedef struct action_list_s { - struct action_node_s *head; + struct action_node_s *head, *tail; uint32_t length; } action_list_t; void action_list_init(void); void action_list_free(action_list_t *list); action_list_t *action_list_generate(void); +action_node_t *action_copy(const action_node_t* action); void action_take(action_node_t *action); void action_undo(action_node_t *action); void action_to_ptn(action_node_t* action, char* out_ptn); + +#endif diff --git a/include/negamax.c b/include/negamax.c index db5d39b..856f3fc 100644 --- a/include/negamax.c +++ b/include/negamax.c @@ -93,6 +93,19 @@ negamax_free(void) { zobrist_free(); } +static enum WIN_TYPE w; + +static inline float +negamax_evaluate_terminal(const float colour) { + if (ply >= 2*board_size - 2 && (w = check_win()) < 0xFF) { + // Check win if far enough into the game + if (w == WIN_ROAD_BLACK || w == WIN_FLAT_BLACK) return colour*infty; + else if (w == WIN_DRAW) return 0; // Draw is fixed at neutral + else return -colour*infty; + } else { + return colour * cnn1986_evaluate_black_win(); + } +} float negamax_generate(void) { @@ -109,7 +122,7 @@ negamax_generate(void) { return result; } -static enum WIN_TYPE w; +static enum TT_FLAG flag; static float negamax(const uint8_t cur_depth, float alpha, float beta, @@ -120,7 +133,7 @@ negamax(const uint8_t cur_depth, float alpha, float beta, * tt_entry_t *entry = tt_seek(hash); * const float alpha_orig = alpha; * - * if (entry != NULL && entry->depth >= cur_depth) { + * if (entry != NULL && entry->depth == cur_depth) { * if (entry->flag == TT_EXACT) { * return entry->value; * } else if (entry->flag == TT_LOWERBOUND) { @@ -128,15 +141,24 @@ negamax(const uint8_t cur_depth, float alpha, float beta, * } else if (entry->flag == TT_UPPERBOUND) { * beta = fmin(beta, entry->value); * } - * if (alpha >= beta) return entry->value; + * if (alpha >= beta) { + * if (cur_depth == negamax_search_depth) + * action_to_ptn(entry->action, negamax_ptn); + * return entry->value; + * } * } */ - float value = -infty; + action_list_t *list; + if ((list = action_list_generate()) == NULL) + return alpha; // should never happen! + - action_list_t *list = action_list_generate(); - if (list == NULL) return value; // ??? + /* + * action_node_t *best = NULL; + */ + float value = -infty; for (action_node_t *node=list->head; node!=NULL; node=node->next) { action_take(node); @@ -147,42 +169,44 @@ negamax(const uint8_t cur_depth, float alpha, float beta, 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; // Draw is fixed at neutral - } else if (cur_depth > 0) { - // If nobody won, or too early, recurse if not a leaf + else if (w == WIN_DRAW) node_value = 0; // Draw is neutral + } else if (cur_depth > 1) { + // If nobody won, or too early and not leaf, recurse node_value = -negamax(cur_depth - 1, -beta, -alpha, -colour); } else { - // Recursion would take us to a leaf, evaluate node_value = colour * cnn1986_evaluate_black_win(); } - - value = fmax(value, node_value); - action_undo(node); negamax_display_progress(cur_depth, list->length); - if (value > alpha) { - alpha = value; + if (node_value > value) { + value = node_value; if (cur_depth == negamax_search_depth) action_to_ptn(node, negamax_ptn); - if (alpha >= beta) break; } + + alpha = fmax(value, alpha); + if (alpha >= beta) break; } action_list_free(list); /* - * enum TT_FLAG flag = TT_EXACT; + * flag = TT_EXACT; * if (value <= alpha_orig) flag = TT_UPPERBOUND; * else if (value >= beta) flag = TT_UPPERBOUND; * * if (entry == NULL) { * tt_insert(hash, flag, cur_depth, value); - * } else { + * } + */ + /* + * else { * entry->flag = flag; * entry->value = value; * entry->depth = cur_depth; + * entry->action = best; * } */ diff --git a/include/tt_treap.h b/include/tt_treap.h index 793d536..1a15e1b 100644 --- a/include/tt_treap.h +++ b/include/tt_treap.h @@ -1,5 +1,6 @@ #include #include +#include #include #ifndef TT_TREAP_H @@ -18,6 +19,7 @@ typedef struct treap_node_s { enum TT_FLAG flag; uint8_t depth; float value; + action_node_t *action; } tt_entry_t; // =================================================================== @@ -34,7 +36,9 @@ int tt_init(void); void tt_free(void); tt_entry_t *tt_seek(uint64_t key); + int tt_insert(const uint64_t key, const enum TT_FLAG flag, const uint8_t depth, const float value); + // const action_node_t* action); #endif -- cgit v1.2.3