From 8418ddf3187ec0f526ef5d8dbb0689fc786fac92 Mon Sep 17 00:00:00 2001 From: tslil clingman Date: Mon, 25 Jan 2021 17:22:48 -0500 Subject: Still some bugs, standing stone becomes flat at depth4 self-play?? --- include/action_list.c | 75 ++++++++++++++++++++++++--------------------------- include/action_list.h | 15 +++++++---- include/negamax.c | 46 +++++++++++++++---------------- include/negamax.h | 11 +++++--- 4 files changed, 75 insertions(+), 72 deletions(-) (limited to 'include') diff --git a/include/action_list.c b/include/action_list.c index 10bbdcf..b338627 100644 --- a/include/action_list.c +++ b/include/action_list.c @@ -6,7 +6,7 @@ #define CLR_STONE NUM_MASK -static inline action_list_t * +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); @@ -16,11 +16,14 @@ action_list_prepend(action_list_t *list, const enum A_TYPE type, // =================================================================== void action_list_free(action_list_t *list) { - action_list_t *n = NULL; - while (list) { - n = list->next; + if (list) { + action_node_t *n = list->head, *nn; + while (n) { + nn = n->next; + free(n); + n = nn; + } free(list); - list = n; } } @@ -35,7 +38,10 @@ void action_list_init(void) { } action_list_t *action_list_generate(void) { - action_list_t *result = NULL; + action_list_t *result = malloc(sizeof(struct action_list_s)); + // TODO: trap errno + result->length = 0; + result->head = NULL; const uint8_t black = (ply < 2) ? (ply==1) : (ply & 1), material = (black) ? black_count : white_count, @@ -43,9 +49,9 @@ action_list_t *action_list_generate(void) { cap = (ply >= 2 && (material & 128)), standing = (ply >= 2 && (material & 127)); - // Step across the board - for (int8_t row = board_size - 1; row > 0; row--) { - for (int8_t col = board_size - 1; col > 0; col--) { + // Step across the board, reversed because we prepend to the list + for (int8_t row = board_size - 1; row >= 0; row--) { + for (int8_t col = board_size - 1; col >= 0; col--) { // We'll need these at various points: the location of this // square and the maximum number of stones we could pick up const int8_t loc = THE_COORDS(col, row); @@ -106,7 +112,7 @@ action_list_t *action_list_generate(void) { const uint8_t last_drop_check = (num > 1) ? (gaps & 1<<(num - 2)) : 1; if (end_stops[dir][1] || last_drop_check) - result = action_list_prepend(result, A_MOVE, loc, gaps, (dir<<4) | num); + action_list_prepend(result, A_MOVE, loc, gaps, (dir<<4) | num); /* * With thanks to * https://graphics.stanford.edu/~seander/bithacks.html#NextBitPermutation @@ -122,31 +128,22 @@ action_list_t *action_list_generate(void) { } else if (count == 0 && material) { // Empty square, generate placements if (flat) { - result = action_list_prepend(result, - A_PLACE, - loc, - STONE_FLAT, - 0); + action_list_prepend(result, A_PLACE, loc, + STONE_FLAT, 0); if (standing) - result = action_list_prepend(result, - A_PLACE, - loc, - STONE_STANDING, - 0); + action_list_prepend(result, A_PLACE, loc, + STONE_STANDING, 0); } if (cap) - result = action_list_prepend(result, - A_PLACE, - loc, - STONE_CAPSTONE, - 0); + action_list_prepend(result, A_PLACE, loc, + STONE_CAPSTONE, 0); } } } return result; } -void action_take(action_list_t *action) { +void action_take(action_node_t *action) { const int8_t loc = action->loc; if (action->type == A_PLACE) { const uint8_t black = (current_colour == C_BLACK); @@ -181,7 +178,7 @@ void action_take(action_list_t *action) { // Use the Kernighan method to count the set bits int8_t steps = 1; - for (uint8_t _gaps = gaps; _gaps > 0; steps++) _gaps &= _gaps - 1; + for (uint8_t _gaps = gaps; _gaps; steps++) _gaps &= _gaps - 1; // Move top stone type to destination celldat[loc+steps*delta] &= CLR_STONE; // necessary for crushing @@ -189,14 +186,13 @@ void action_take(action_list_t *action) { celldat[loc] &= CLR_STONE; celldat[loc] |= STONE_FLAT; // should be optimised out - uint8_t gap_bit = 0, total = 0; + uint8_t gap_bit = 0, total = 1; // num == 1 is a special case if (num > 1) { gap_bit = 1 << (num - 2); - total = 1; } // move stuff starting at destination - for (uint8_t d = 0; d + 1 < num; d++, total++, gap_bit >>= 1) { + for (uint8_t d = 1; d < num; d++, total++, gap_bit >>= 1) { // We took a step, move everything over so far if (gaps & gap_bit) { colours[loc+steps*delta] <<= total; @@ -209,7 +205,6 @@ void action_take(action_list_t *action) { steps--; } } - total++; // Move what remains (steps == 1 here always, so we simplify) colours[loc+delta] <<= total; colours[loc+delta] |= colours[loc] & ((1 << total) - 1); @@ -227,7 +222,7 @@ void action_take(action_list_t *action) { } } -void action_undo(action_list_t *action) { +void action_undo(action_node_t *action) { // Previous ply if (ply>0) ply--; if (ply == 1) { @@ -256,8 +251,8 @@ void action_undo(action_list_t *action) { const int8_t delta = deltas[dir]; int8_t steps = 1; - uint8_t gap_bit = 1, total = (num > 1) ? 1 : 0; - for (uint8_t d = 0; d + 1 < num; d++, total++, gap_bit <<= 1) { + uint8_t gap_bit = 1, total = 1; + for (uint8_t d = 1; d < num; d++, total++, gap_bit <<= 1) { if (gaps & gap_bit) { colours[loc] <<= total; colours[loc] |= colours[loc+steps*delta] & ((1 << total) - 1); @@ -268,7 +263,6 @@ void action_undo(action_list_t *action) { steps++; } } - total++; colours[loc] <<= total; colours[loc] |= colours[loc+steps*delta] & ((1 << total) - 1); colours[loc+steps*delta] >>= total; @@ -282,7 +276,7 @@ void action_undo(action_list_t *action) { } } -void action_to_ptn(action_list_t* action, char* out_ptn) { +void action_to_ptn(action_node_t* action, char* out_ptn) { const int8_t loc = action->loc; if (action->type == A_PLACE) { generate_place(loc, action->data0, out_ptn); @@ -314,16 +308,17 @@ void action_to_ptn(action_list_t* action, char* out_ptn) { // Helper method implementations // =================================================================== -static inline action_list_t * +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_t *new = malloc(sizeof(action_list_t)); + action_node_t *new = malloc(sizeof(action_list_t)); // TODO: trap errno + list->length++; new->loc = loc; new->type = type; - new->next = list; new->data0 = data0; new->data1 = data1; - return new; + new->next = list->head; + list->head = new; } diff --git a/include/action_list.h b/include/action_list.h index a0f5a34..14c733f 100644 --- a/include/action_list.h +++ b/include/action_list.h @@ -5,19 +5,24 @@ enum A_TYPE { A_PLACE, A_MOVE }; -typedef struct action_list_s { - struct action_list_s *next; +typedef struct action_node_s { + struct action_node_s *next; enum A_TYPE type; int8_t loc; uint8_t data0; uint8_t data1; +} action_node_t; + +typedef struct action_list_s { + struct action_node_s *head; + 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); -void action_take(action_list_t *action); -void action_undo(action_list_t *action); +void action_take(action_node_t *action); +void action_undo(action_node_t *action); -void action_to_ptn(action_list_t* action, char* out_ptn); +void action_to_ptn(action_node_t* action, char* out_ptn); diff --git a/include/negamax.c b/include/negamax.c index 16eba9a..43fa5f6 100644 --- a/include/negamax.c +++ b/include/negamax.c @@ -102,7 +102,7 @@ negamax_generate(void) { tt_init(); float result = negamax(negamax_search_depth, -safe_infty, safe_infty, - (ply&1)?1.0:-1.0); + (ply & 1) ? +1.0 : -1.0); tt_free(); return result; @@ -113,49 +113,47 @@ static enum WIN_TYPE w; static float negamax(const uint8_t cur_depth, float alpha, float beta, const float colour) { + + if (cur_depth == 0) return colour*cnn1986_evaluate_black_win(); + float value = -infty; action_list_t *list = action_list_generate(); + if (list == NULL) return value; // ??? - for (action_list_t *node=list; node!=NULL; node=node->next) { - negamax_display_progress(cur_depth); - + for (action_node_t *node=list->head; node!=NULL; node=node->next) { action_take(node); // Somebody won? - if (ply >= 2*board_size - 3 && (w = check_win()) < 0xFF) { - if (w == WIN_ROAD_BLACK || w == WIN_FLAT_BLACK) { - value = colour*infty; - if (value > 0) { - // Always take the win for ourselves - action_undo(node); - if (cur_depth == negamax_search_depth) - action_to_ptn(node, negamax_ptn); - goto prune; - } - } else if (w == WIN_DRAW) value = 0; // Draw is fixed at neutral + if (ply >= 2*board_size - 2 && (w = check_win()) < 0xFF) { + if (w == WIN_ROAD_BLACK || w == WIN_FLAT_BLACK) value = colour*infty; + else if (w == WIN_DRAW) value = 0; // Draw is fixed at neutral else value = -colour*infty; - } else if (cur_depth > 1) { - // Recurse away from the leaves - value = fmax(value, -negamax(cur_depth - 1, -beta, -alpha, -colour)); + if (value > 0) { + // Always take the win for ourselves + action_undo(node); + if (cur_depth == negamax_search_depth) { + action_to_ptn(node, negamax_ptn); + } + goto prune; + } } else { - // Evaluate a leaf - value = fmax(value, colour * cnn1986_evaluate_black_win()); + value = fmax(value, -negamax(cur_depth - 1, -beta, -alpha, -colour)); } action_undo(node); + negamax_display_progress(cur_depth, list->length); + if (value > alpha) { alpha = value; if (cur_depth == negamax_search_depth) action_to_ptn(node, negamax_ptn); + if (alpha >= beta) break; } - if (alpha >= beta) break; } - - action_list_free(list); - prune: + action_list_free(list); return value; } diff --git a/include/negamax.h b/include/negamax.h index 8a67638..c902d3c 100644 --- a/include/negamax.h +++ b/include/negamax.h @@ -10,10 +10,15 @@ extern const float infty; extern char negamax_ptn[9]; extern uint8_t negamax_search_depth; -extern inline void negamax_display_progress(const uint8_t); -void negamax_init(const uint8_t new_board_size); -void negamax_free(void); +extern inline void +negamax_display_progress(const uint8_t, const uint32_t length); + +void +negamax_init(const uint8_t new_board_size); + +void +negamax_free(void); // Do negamax to depth negamax_search_depth and return PTN of best move // in negamax_ptn, along with its value as the return. The -- cgit v1.2.3