From 9131e08817ae2f3bd58a8a0ba9f1e692ceb8604c Mon Sep 17 00:00:00 2001 From: tslil clingman Date: Tue, 26 Jan 2021 00:24:03 -0500 Subject: There is still a bug, it doesn't appear to be checking enough --- include/action_list.c | 226 ++++++++++++++++++++++++++++---------------------- include/cnn1986.c | 21 ----- include/negamax.c | 14 ++-- src/ctaklm.c | 2 +- 4 files changed, 135 insertions(+), 128 deletions(-) diff --git a/include/action_list.c b/include/action_list.c index c407ae9..9ddd74b 100644 --- a/include/action_list.c +++ b/include/action_list.c @@ -13,6 +13,13 @@ action_list_prepend(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); + +static inline void +inline_prev_ply(void); + + // =================================================================== // Exported method implementations // =================================================================== @@ -40,114 +47,123 @@ void action_list_init(void) { } action_list_t *action_list_generate(void) { - action_list_t *result = malloc(sizeof(struct action_list_s)); + action_list_t *list = malloc(sizeof(struct action_list_s)); // TODO: trap errno - result->length = 0; - result->head = NULL; + list->length = 0; + list->head = NULL; + + /* + * The check for whether it's a black piece to be played is actually + * black = (ply < 2) ? (ply==1) : (ply & 1), + * but material will always be sufficient in ply < 2 so we might as + * well save on the conditional. + */ - const uint8_t black = (ply < 2) ? (ply==1) : (ply & 1), - material = (black) ? black_count : white_count, + const uint8_t material = (ply & 1) ? black_count : white_count, flat = material & 0x7F, - cap = (ply >= 2 && (material & 0x80)), - standing = (ply >= 2 && flat); + cap = ((ply >= 2) && (material & 0x80)), + standing = ((ply >= 2) && flat); // 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--) { + for (int row = board_size - 1; row >= 0; row--) { + for (int 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); + const int loc = THE_COORDS(col, row); const uint8_t count = DANGER_MIN(COUNT_AT(loc), board_size); - // Only try moves after CPS - if (ply >= 2 && count && ((colours[loc] & 1) == current_colour)) { - // There are stones, let's try moving them - - // Pre-compute end-stops and crushes - uint8_t end_stops[4], crushes[4] = {0, 0, 0, 0}; - - // These are upper bounds, not counting walls and such. UP DOWN LEFT RIGHT - end_stops[0] = DANGER_MIN(board_size - row - 1, count); - end_stops[1] = DANGER_MIN(row, count); - end_stops[2] = DANGER_MIN(col, count); - end_stops[3] = DANGER_MIN(board_size - col - 1, count); - - // Now we check for caps and walls - const uint8_t cap_top = STONE_AT(loc) == STONE_CAPSTONE; - for (uint8_t d = 0; d < 4; d++){ - const int8_t delta = deltas[d]; - const uint8_t stop = end_stops[d]; - end_stops[d] = 0; - for (uint8_t k = 1; k <= stop; k++) { - const enum STONE_VARIANT stone = STONE_AT(loc+k*delta); - if (stone == STONE_STANDING) { - if (cap_top) { - crushes[d] = 0xFF; - end_stops[d]++; + + // Only try moves after CPS and if the colour is correct + if (count) { + if (ply >= 2 && ((colours[loc] & 1) == current_colour)) { + + // Pre-compute end-stops and crushes + uint8_t end_stops[4], crushes[4] = {0, 0, 0, 0}; + + // These are upper bounds, not counting walls and such. + // UP DOWN LEFT RIGHT + end_stops[0] = DANGER_MIN(board_size - row - 1, count); + end_stops[1] = DANGER_MIN(row, count); + end_stops[2] = DANGER_MIN(col, count); + end_stops[3] = DANGER_MIN(board_size - col - 1, count); + + // Now we check for caps and walls + const uint8_t cap_top = STONE_AT(loc) == STONE_CAPSTONE; + for (int d = 0; d < 4; d++){ + const int delta = deltas[d]; + const int stop = end_stops[d]; + end_stops[d] = 0; + for (int k = 1; k <= stop; k++) { + const enum STONE_VARIANT stone = STONE_AT(loc+k*delta); + if (stone == STONE_STANDING) { + if (cap_top) { + crushes[d] = 0xFF; + end_stops[d]++; + } + break; + } else if (stone == STONE_CAPSTONE) { + break; } - break; - } else if (stone == STONE_CAPSTONE) { - break; + end_stops[d]++; } - end_stops[d]++; } - } - /* - * For each direction, generate all possible ordered integer - * partitions of 1 ≤ num ≤ count whose number of summands is - * exactly 1 ≤ summands ≤ min(end_stops[dir], num) -- we write - * summands as steps - */ - for (enum MOVE_DIRECTION dir = M_UP; dir <= M_RIGHT; dir++) { - for (uint8_t num = 1; num <= count; num++) { - for (uint8_t steps = 1; - steps <= end_stops[dir] && steps <= num; - steps++) { - // TODO: Generalise to board_size! - uint8_t gaps = 0x07 >> (board_size-steps-1); - // 0b0000[0111] because 4-1=3 and 5-1=4 - do { - /* - * We skip the partition if it calls for multiple stones at - * the end with a crush. - */ - const uint8_t last_drop_check = - (num > 1) ? (gaps & 1<<(num - 2)) : 1; - if (crushes[dir] == 0 || last_drop_check) { - // We have to record a crush! - // THIS IS WHERE THE PROBLEM IS - const uint8_t crush = (steps == end_stops[dir]) && crushes[dir]; - action_list_prepend(result, A_MOVE, loc, - (crush << 7) | gaps, - (dir<<4) | num); - } - /* - * With thanks to - * https://graphics.stanford.edu/~seander/bithacks.html#NextBitPermutation - * we have the following magic to generate the next - * permutation of steps-many set bits - */ - uint8_t t = (gaps | (gaps - 1)); - gaps = (t + 1) | (((~t & -~t) - 1) >> (__builtin_ctz(gaps) + 1)); - } while (gaps && (gaps + 1 <= (1<<(num-1)))); + /* + * For each direction, generate all possible ordered integer + * partitions of 1 ≤ num ≤ count whose number of summands is + * exactly 1 ≤ summands ≤ min(end_stops[dir], num) -- we + * write summands as steps + */ + for (enum MOVE_DIRECTION dir=M_UP; dir<=M_RIGHT; dir++) { + for (uint8_t num = 1; num <= count; num++) { + for (uint8_t steps = 1; + steps <= end_stops[dir] && steps <= num; + steps++) { + // TODO: Generalise to board_size! + uint8_t gaps = 0x07 >> (board_size-steps-1); + // 0b0000[0111] because 4-1=3 and 5-1=4 + do { + /* + * We skip the partition if it calls for multiple + * stones at the end with a crush. + */ + const uint8_t last_drop_check = + (num > 1) ? (gaps & (1 << (num - 2))) : 1; + if (crushes[dir] == 0 || last_drop_check) { + // We have to record a crush! + const uint8_t crush = + (steps == end_stops[dir]) && crushes[dir]; + // Store the move + action_list_prepend(list, A_MOVE, loc, + (crush << 7) | gaps, + (dir<<4) | num); + } + /* + * With thanks to + * https://graphics.stanford.edu/~seander/bithacks.html#NextBitPermutation + * we have the following magic to generate the next + * permutation of steps-many set bits + */ + uint8_t t = (gaps | (gaps - 1)); + gaps = (t + 1) + | (((~t & -~t) - 1) >> (__builtin_ctz(gaps) + 1)); + } while (gaps && (gaps + 1 <= (1 << (num - 1)))); + } } } } - } else if (count == 0 && material) { + } // end of if (count) { ... } + else if (material) { // Empty square, generate placements if (flat) { - action_list_prepend(result, A_PLACE, loc, - STONE_FLAT, 0); + action_list_prepend(list, A_PLACE, loc, STONE_FLAT, 0); if (standing) - action_list_prepend(result, A_PLACE, loc, - STONE_STANDING, 0); + action_list_prepend(list, A_PLACE, loc, STONE_STANDING,0); } if (cap) - action_list_prepend(result, A_PLACE, loc, - STONE_CAPSTONE, 0); + action_list_prepend(list, A_PLACE, loc, STONE_CAPSTONE, 0); } } } - return result; + return list; } void action_take(action_node_t *action) { @@ -227,24 +243,12 @@ void action_take(action_node_t *action) { celldat[loc] -= total*NUM_INC; } // Next ply - ply++; - if (ply == 2) { - current_colour = C_WHITE; - } else { - if (current_colour == C_BLACK) current_colour = C_WHITE; - else current_colour = C_BLACK; - } + inline_next_ply(); } void action_undo(action_node_t *action) { // Previous ply - if (ply>0) ply--; - if (ply == 1) { - current_colour = C_WHITE; - } else { - if (current_colour == C_BLACK) current_colour = C_WHITE; - else current_colour = C_BLACK; - } + inline_prev_ply(); const int8_t loc = action->loc; if (action->type == A_PLACE) { @@ -342,3 +346,25 @@ action_list_prepend(action_list_t *list, const enum A_TYPE type, new->next = list->head; list->head = new; } + +static inline void +inline_next_ply(void) { + ply++; + if (ply == 2) { + current_colour = C_WHITE; + } else { + if (current_colour == C_BLACK) current_colour = C_WHITE; + else current_colour = C_BLACK; + } +} + +static inline void +inline_prev_ply(void) { + if (ply>0) ply--; + if (ply == 1) { + current_colour = C_WHITE; + } else { + if (current_colour == C_BLACK) current_colour = C_WHITE; + else current_colour = C_BLACK; + } +} diff --git a/include/cnn1986.c b/include/cnn1986.c index 17d4e84..ada1766 100644 --- a/include/cnn1986.c +++ b/include/cnn1986.c @@ -9,21 +9,6 @@ static float flattened[CONV_NUM+2]; static float dense1[DENSE1_NUM]; static float dense2[DENSE2_NUM]; -#ifndef DETERMINISTIC -union u_f { - uint32_t u; - float f; -}; - -static union u_f fudge; - -#define RANDF { \ - XORSHIFT; \ - fudge.u = 0x3f800000 | RANDOM32 >> 10; \ - fudge.f = (fudge.f - 1.5) * 0.01; \ - } -#endif - #define RELU(x) ((x) = ((x)<0)?0:(x)) float cnn1986_evaluate_black_win(void) { @@ -100,12 +85,6 @@ float cnn1986_evaluate_black_win(void) { } // Truncated Pade approximant of logistic function output = (12.0+output+50.0*output/(output*output+10.0))/24.0; -/* - * #ifndef DETERMINISTIC - * RANDF; - * output += fudge.f; - * #endif - */ if (output > 1.0) { return 1.0; } diff --git a/include/negamax.c b/include/negamax.c index 912705d..8b7345f 100644 --- a/include/negamax.c +++ b/include/negamax.c @@ -123,20 +123,22 @@ negamax(const uint8_t cur_depth, float alpha, float beta, action_take(node); // Compute the value of the node + float node_value; if (ply >= 2*board_size - 2 && (w = check_win()) < 0xFF) { - float winnings = -colour*infty; + node_value = -colour*infty; // Check win if far enough into the game - if (w == WIN_ROAD_BLACK || w == WIN_FLAT_BLACK) winnings = colour*infty; - else if (w == WIN_DRAW) winnings = 0; // Draw is fixed at neutral - value = fmax(value, winnings); + 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 > 1) { // If nobody won, or too early, recurse if not a leaf - value = fmax(value, -negamax(cur_depth - 1, -beta, -alpha, -colour)); + node_value = -negamax(cur_depth - 1, -beta, -alpha, -colour); } else { // Recursion would take us to a leaf, evaluate - value = fmax(value, colour*cnn1986_evaluate_black_win()); + node_value = colour * cnn1986_evaluate_black_win(); } + value = fmax(value, node_value); + action_undo(node); negamax_display_progress(cur_depth, list->length); diff --git a/src/ctaklm.c b/src/ctaklm.c index dda6eb1..a3685db 100644 --- a/src/ctaklm.c +++ b/src/ctaklm.c @@ -416,7 +416,7 @@ main(int argc, char **argv) { (void)(argc); (void)(argv); - negamax_search_depth = 5; + negamax_search_depth = 4; new_game(5); negamax_init(5); tt_init(); -- cgit v1.2.3