From cb143299411851667a8e3aae4d7a55f729694b12 Mon Sep 17 00:00:00 2001 From: tslil clingman Date: Sun, 24 Jan 2021 21:31:59 -0500 Subject: This is the basic idea, there's ≥ 1 bug (generates illegals...) MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit --- Makefile | 2 +- include/action_list.c | 176 +++++++++---- include/action_list.h | 2 + include/negamax.c | 705 +++++++++++++++++++++++++++----------------------- include/negamax.h | 3 +- src/ctaklm.c | 12 +- 6 files changed, 524 insertions(+), 376 deletions(-) diff --git a/Makefile b/Makefile index 2b0b6a2..eacaff8 100644 --- a/Makefile +++ b/Makefile @@ -1,6 +1,6 @@ IDIR=include DEFINES=-DDETERMINISTIC -CFLAGS=-O3 -Wall -Wextra -Wpedantic -std=c99 -D_DEFAULT_SOURCE $(DEFINES) -I$(IDIR) -lm +CFLAGS=-g -Wall -Wextra -Wpedantic -std=c99 -D_DEFAULT_SOURCE $(DEFINES) -I$(IDIR) -lm LIBS= SRCS=$(wildcard include/*.c) diff --git a/include/action_list.c b/include/action_list.c index 198cd08..9afb199 100644 --- a/include/action_list.c +++ b/include/action_list.c @@ -9,12 +9,8 @@ action_list_prepend(action_list_t *list, const enum A_TYPE type, const uint8_t loc, const uint8_t data0, const uint8_t data1); -static inline void previous_ply(void); - -static inline void -push_stones(const int8_t location, const uint8_t count, - const uint8_t new_colours, - const enum STONE_VARIANT top_stone); +static inline void inline_previous_ply(void); +static inline void inline_next_ply(void); // =================================================================== // Exported method implementations @@ -97,7 +93,7 @@ action_list_t *action_list_generate(void) { * summands as steps */ for (enum MOVE_DIRECTION dir = M_UP; dir <= M_RIGHT; dir++) { - uint8_t gaps, t, idx, mask; + uint8_t gaps, t; for (uint8_t num = 1; num <= count; num++) { for (uint8_t steps = 1; steps <= end_stops[dir][0] && steps <= num; @@ -146,14 +142,14 @@ void action_take(action_list_t *action) { if (action->type == A_PLACE) { const uint8_t black = (ply&1); switch (action->data0) { - STONE_FLAT: { + case STONE_FLAT: { if (black) black_count--; else white_count--; colours[loc] = current_colour; celldat[loc] = NUM_INC | STONE_FLAT; break; } - STONE_STANDING: { + case STONE_STANDING: { if (black) black_count--; else white_count--; colours[loc] = current_colour; @@ -169,42 +165,53 @@ void action_take(action_list_t *action) { } } } else { - uint8_t drops[board_size]; // we only ever need board_size-1 in - // drops actually, the last spot is to - // skip a bounds check at (*) later - const uint8_t gaps = action->data0, num = action->data1 & 0x0F, // unpack - dir = action->data1 & 0xF0; - uint8_t steps, mask; - // Translate to a drop sequence - drops[0] = 1; mask = 1; steps = 0; - for (uint8_t d = 0; d + 1 < num; d++) { - if (gaps & mask) { - steps++; - drops[steps] = 1; // (*) no bounds check - } else { - drops[steps] += 1; + dir = action->data1 & 0xF0, + delta = deltas[dir]; + + // Unfortunately num == 1 is a special case + if (num > 1) { + uint8_t steps, mask = 1<<(num-2), gaps_prime = gaps; + // Use the Kernighan method to count the set bits + for (steps = 1; gaps_prime; steps++) gaps_prime &= gaps_prime - 1; + // then from the destination to the source + for (uint8_t d = 0; d + 1 < num; d++) { + // transfer the top colour + colours[loc+steps*delta] <<= 1; + colours[loc+steps*delta] |= colours[loc] & 1; + colours[loc] >>= 1; + // increase the stone count, copy top stone if appropriate + celldat[loc+steps*delta] += NUM_INC; + if (d==0) { + celldat[loc+steps*delta] &= NUM_MASK; + celldat[loc+steps*delta] |= STONE_AT(loc); + celldat[loc] &= NUM_MASK; + celldat[loc] |= STONE_FLAT; // this should be optimised out :) + } + // decrement the count, the top colour + celldat[loc] -= NUM_INC; + + if (gaps & mask) steps--; + mask >>= 1; } - mask <<= 1; - } - // Push stones onto subesquent stack - uint8_t j = num; - for (uint8_t k = 0; k <= steps; k++) { - j -= drops[k]; - push_stones(loc+(k+1)*deltas[dir], - drops[k], - (colours[loc] >> j) & (0xFFFF >> (0x10 - drops[k])), - (k == steps - 1) ? STONE_AT(loc) : STONE_FLAT); + } else { + // Oh well + colours[loc+delta] <<= 1; + colours[loc+delta] |= colours[loc] & 1; + celldat[loc+delta] += NUM_INC; + celldat[loc+delta] &= NUM_MASK; + celldat[loc+delta] |= STONE_AT(loc); + + colours[loc] >>= 1; + celldat[loc] &= NUM_MASK; + celldat[loc] |= STONE_FLAT; // this should be optimised out :) + celldat[loc] -= NUM_INC; } - // Drop them from the source - colours[loc] >>= num; - const uint8_t dec_count = celldat[loc] - (num << NUM_SHIFT); - celldat[loc] = dec_count & NUM_MASK; } // Always - next_ply(); -}; + inline_next_ply(); +} void action_undo(action_list_t *action) { const uint8_t loc = action->loc; @@ -219,10 +226,74 @@ void action_undo(action_list_t *action) { else white_count++; } } else { - // TODO ??? + // See action_take for comments, this is the time reversal + const uint8_t gaps = action->data0, + num = action->data1 & 0x0F, // unpack + dir = action->data1 & 0xF0, + delta = deltas[dir]; + + uint8_t steps = 1, mask = 1; + if (num > 1) { + for (uint8_t d = 0; d + 1 < num; d++) { + colours[loc] <<= 1; + colours[loc] |= colours[loc+steps*delta] & 1; + colours[loc+steps*delta] >>= 1; + + celldat[loc] += NUM_INC; + if (d + 2 == num) { + celldat[loc] &= NUM_MASK; + celldat[loc] |= STONE_AT(loc+steps*delta); + celldat[loc+steps*delta] &= NUM_MASK; + celldat[loc+steps*delta] |= STONE_FLAT; + } + celldat[loc+steps*delta] -= NUM_INC; + + if (gaps & mask) steps++; + mask <<= 1; + } + } else { + colours[loc] <<= 1; + colours[loc] |= colours[loc+delta] & 1; + celldat[loc] += NUM_INC; + celldat[loc] &= NUM_MASK; + celldat[loc] |= STONE_AT(loc+delta); + + colours[loc+delta] >>= 1; + celldat[loc+delta] &= NUM_MASK; + celldat[loc+delta] |= STONE_FLAT; + celldat[loc+delta] -= NUM_INC; + } } - previous_ply(); -}; + inline_previous_ply(); +} + +void action_to_ptn(action_list_t* action, char* out_ptn) { + const uint8_t loc = action->loc; + if (action->type == A_PLACE) { + generate_place(loc, action->data0, out_ptn); + } else { + const uint8_t gaps = action->data0, + num = action->data1 & 0x0F, // unpack + dir = action->data1 & 0xF0; + + uint8_t drops[board_size]; // we only ever need board_size-1 in + // drops actually, the last spot is to + // skip a bounds check at (*) + uint8_t mask = 1, steps = 0; + // Translate to a drop sequence + drops[0] = 1; mask = 1; + for (uint8_t d = 0; d + 1 < num; d++) { + if (gaps & mask) { + steps++; + drops[steps] = 1; // (*) no bounds check + } else { + drops[steps] += 1; + } + mask <<= 1; + } + generate_move(loc, dir, steps+1, drops, out_ptn); + } +} // =================================================================== // Helper method implementations @@ -235,6 +306,7 @@ action_list_prepend(action_list_t *list, const enum A_TYPE type, action_list_t *new = malloc(sizeof(action_list_t)); // TODO: trap errno new->loc = loc; + new->type = type; new->next = list; new->data0 = data0; new->data1 = data1; @@ -242,9 +314,9 @@ action_list_prepend(action_list_t *list, const enum A_TYPE type, } static inline void -previous_ply(void) { - if (ply>0) ply--; - if (ply == 1) { +inline_next_ply(void) { + ply++; + if (ply == 2) { current_colour = C_WHITE; } else { if (current_colour == C_BLACK) current_colour = C_WHITE; @@ -253,10 +325,12 @@ previous_ply(void) { } static inline void -push_stones(const int8_t location, const uint8_t count, - const uint8_t new_colours, - const enum STONE_VARIANT top_stone) { - colours[location] = (colours[location] << count) | new_colours; - celldat[location] = top_stone - | ((celldat[location] + ((count << NUM_SHIFT))) & NUM_MASK); +inline_previous_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/action_list.h b/include/action_list.h index 3670114..03881c5 100644 --- a/include/action_list.h +++ b/include/action_list.h @@ -19,3 +19,5 @@ action_list_t *action_list_generate(void); void action_take(action_list_t *action); void action_undo(action_list_t *action); + +void action_to_ptn(action_list_t* action, char* out_ptn); diff --git a/include/negamax.c b/include/negamax.c index fd8c7ac..812f8f7 100644 --- a/include/negamax.c +++ b/include/negamax.c @@ -8,16 +8,48 @@ const float infty = 3.0; char negamax_ptn[9]; uint8_t negamax_search_depth = 3; -uint32_t cache_fails = 0; +static uint64_t *zobrist[15]; // =================================================================== -// Zobrist hashing +// Helpers // =================================================================== -uint64_t *zobrist[15]; +static void +zobrist_free(void); + +static int +zobrist_init(void); + +static uint64_t +zobrist_compute(void); -static int negamax_init_zobrist(void) { +static float +negamax(const uint8_t cur_depth, float alpha, float beta, + const float colour); + +// =================================================================== +// Zobrist hashing +// =================================================================== + +static uint64_t +zobrist_compute(void) { + uint64_t hash = 0; + for (uint8_t l=0; l>= 1; + } + } + } + return hash; +} +static int +zobrist_init(void) { for (int k=0; k<15; k++) { if (zobrist[k] != NULL) return EXIT_FAILURE; } @@ -33,7 +65,8 @@ static int negamax_init_zobrist(void) { return EXIT_SUCCESS; } -static void negamax_free_zobrist(void) { +static void +zobrist_free(void) { for (int k=0; k<15; k++) { if (zobrist[k] != NULL) { free(zobrist[k]); @@ -42,343 +75,377 @@ static void negamax_free_zobrist(void) { } } -uint64_t negamax_compute_zobrist(void) { - uint64_t hash = 0; - for (uint8_t l=0; l>= 1; - } - } - } - return hash; -} - // =================================================================== -// α-β negamax using the cnn1986 evaluation function +// α-β negamax using the cnn1986 evaluation function and transposition +// tables using Zobrist hasing and a treap // =================================================================== - -// Movement steps, orderd with the enum: UP DOWN LEFT RIGHT -static int8_t deltas[4]; - -void negamax_init(const uint8_t new_board_size) { +void +negamax_init(const uint8_t new_board_size) { board_size = new_board_size; - deltas[0] = +board_size; - deltas[1] = -board_size; - deltas[2] = -1; - deltas[3] = +1; - negamax_free_zobrist(); - negamax_init_zobrist(); + zobrist_init(); + action_list_init(board_size); } -static void previous_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; - } +void +negamax_free(void) { + zobrist_free(); } -static void push_stones(const int8_t location, - const uint8_t count, - const uint8_t new_colours, - const enum STONE_VARIANT top_stone) { - colours[location] = (colours[location] << count) | new_colours; - celldat[location] = top_stone - | ((celldat[location] + ((count << NUM_SHIFT))) & NUM_MASK); -} -static enum WIN_TYPE w; +float +negamax_generate(void) { + // We need to start with something outside of [-∞,∞] because those + // values are wins + const float safe_infty = infty + 1; -#define WIN_EVALUATE_OR_RECURSE(store,reset) { \ - w = 0xFF; \ - if (ply >= 2*board_size - 3) w = check_win(); \ - if (w < 0xFF) { \ - /* Somebody won, assign weights accordingly. */ \ - if (w == WIN_ROAD_BLACK || w == WIN_FLAT_BLACK) { \ - value = colour*infty; \ - /* Always take the win */ \ - if (value > 0) { \ - { reset }; \ - if (cur_depth == negamax_search_depth) { store }; \ - goto prune; \ - } \ - /* Fix draw value to be completely neutral */ \ - } else if (w == WIN_DRAW) value = 0; \ - else value = -colour*infty; \ - } if (cur_depth == 0) { \ - /* We're at the bottom, evaluate */ \ - value = fmax(value, colour * cnn1986_evaluate_black_win()); \ - } else { \ - /* We're not at the bottom, recurse first */ \ - next_ply(); \ - value = fmax(value, -negamax(cur_depth - 1, -beta, -alpha, -colour)); \ - previous_ply(); \ - } \ - { reset }; \ - /* Update the optimal value, which alpha carries */ \ - if (value > alpha) { \ - alpha = value; \ - if (cur_depth == negamax_search_depth) { store }; \ - /* Prune */ \ - if (alpha >= beta) goto prune; \ - } \ - } + tt_init(); + float result = negamax(negamax_search_depth, + -safe_infty, safe_infty, + (ply&1)?1.0:-1.0); + tt_free(); -float negamax(const uint8_t cur_depth, float alpha, float beta, - const float colour) { + return result; +} - /* - * uint64_t hash = negamax_compute_zobrist(); - * tt_entry_t *entry = tt_seek(hash); - * const float alpha_orig = alpha; - * - * if (entry != NULL && entry->depth >= cur_depth) { - * if (entry->flag == TT_EXACT) { - * return entry->value; - * } else if (entry->flag == TT_LOWERBOUND) { - * alpha = fmax(alpha, entry->value); - * } else if (entry->flag == TT_UPPERBOUND) { - * beta = fmin(beta, entry->value); - * } - * if (alpha >= beta) return entry->value; - * } - * enum TT_FLAG flag; - */ +static float +negamax(const uint8_t cur_depth, float alpha, float beta, + const float colour) { float value = -infty; - const uint8_t black = (ply & 1), - material = (black) ? black_count : white_count, - flat = material & 127, - cap = (ply > 2 && (material & 128)), - standing = (ply > 2 && (material & 127)); - - // Step across the board - for (uint8_t row = 0; row < board_size; row++) { - for (uint8_t col = 0; col < board_size; col++) { - // Try all valid actions for this square. Is it empty? - const uint8_t loc = THE_COORDS(col, row); - const uint8_t count = (COUNT_AT(loc) > board_size) ? board_size : COUNT_AT(loc); - // Only try moves after CPS - if (count && ((colours[loc] & 1) == current_colour) && ply>2) { - // There are stones, let's try moving them - // Pre-compute end-stops - uint8_t end_stops[4][2]; // (end, not_crush) - // UP DOWN LEFT RIGHT - end_stops[0][0] = (board_size - row - 1 > count) ? count : board_size - row - 1; - end_stops[1][0] = (row > count) ? count : row; - end_stops[2][0] = (col > count) ? count : col; - end_stops[3][0] = (board_size - col - 1 > count) ? count : board_size - col - 1; - const uint8_t cap_top = STONE_AT(loc) == STONE_CAPSTONE; - for (uint8_t d = 0; d < board_size-1; d++){ - end_stops[d][1] = 1; - const uint8_t stop = end_stops[d][0]; - end_stops[d][0] = 0; - for (uint8_t k = 1; k <= stop; k++) { - const uint8_t stone = STONE_AT(loc+k*deltas[d]); - if (stone == STONE_STANDING) { - if (cap_top) { - end_stops[d][1] = 0; - end_stops[d][0]++; - } - break; - } else if (stone == STONE_CAPSTONE) { - break; - } - end_stops[d][0]++; - } - } + action_list_t *action_list = action_list_generate(); - uint16_t colours_backup[board_size]; - uint8_t celldat_backup[board_size], drops[board_size]; - // we only ever need board_size-1 in drops actually, the - // last spot is to skip a bounds check at (*) + for (action_list_t *action = action_list; + action != NULL; + action = action->next) { - //Back up the rows of the board - for (uint8_t y = 0; y < board_size; y++) { - colours_backup[y] = colours[THE_COORDS(col, y)]; - celldat_backup[y] = celldat[THE_COORDS(col, y)]; - } + negamax_display_progress(cur_depth); - // I'm not a huge fan of looping through enums, but it's - // better than manually unrolling this. Sufficiently smart - // compilers? - for (enum MOVE_DIRECTION dir = M_UP; dir <= M_RIGHT; dir++) { - // Back-up the column once we start looking horizontally - if (dir == M_LEFT) { - for (uint8_t x = 0; x < board_size; x++) { - colours_backup[x] = colours[THE_COORDS(x, row)]; - celldat_backup[x] = celldat[THE_COORDS(x, row)]; - } - } - /* - * We don't do anything terribly efficient here just try - * all the ordered partitions of num ∈ {1 … end_stop}, and - * skip the partition if it calls for multiple stones at - * the end with a crush. - */ - uint8_t gaps, t, idx, mask; - for (uint8_t num = 1; num <= count; num++) { - for (uint8_t steps = 1; - steps <= end_stops[dir][0] && steps <= num; - steps++) { - // TODO: Generalise to board_size! - gaps = 0x07 >> (board_size-steps-1); - // 0b0000[0111] because 4-1=3 and 5-1=4 - do { - // Ensure legal move if we have to crush - const uint8_t last_drop_check = - (num > 1) ? (gaps & 1<<(num - 2)) : 1; - if (end_stops[dir][1] || last_drop_check) { - // Translate to a drop sequence - drops[0] = 1; mask = 1; idx = 0; - for (uint8_t d = 0; d + 1 < num; d++) { - if (gaps & mask) { - idx++; - drops[idx] = 1; // (*) no bounds check - } else { - drops[idx] += 1; - } - mask <<= 1; - } - // Do it, and manually check for win if it's valid - uint8_t j = num; - for (uint8_t k = 0; k < steps; k++) { - j -= drops[k]; - push_stones(loc+(k+1)*deltas[dir], - drops[k], - (colours[loc] >> j) & (0xFFFF >> (0x10 - drops[k])), - (k == steps - 1) ? STONE_AT(loc) : STONE_FLAT); - } - // Then we drop them from the source - colours[loc] >>= num; - const uint8_t dec_count = celldat[loc] - (num << NUM_SHIFT); - celldat[loc] = dec_count & NUM_MASK; - - // First check for wins, if we're at the bottom - // evaluate, otherwise recurse - WIN_EVALUATE_OR_RECURSE({ - // If we did update the optimal value, store - // this move - generate_move(loc, dir, steps, drops, negamax_ptn); - },{ - // Reset the board data after recursing or - // before returning - if (dir <= M_DOWN) { - for (uint8_t y = 0; y < board_size; y++) { - colours[THE_COORDS(col, y)] = colours_backup[y]; - celldat[THE_COORDS(col, y)] = celldat_backup[y]; - } - } else { - for (uint8_t x = 0; x < board_size; x++) { - colours[THE_COORDS(x, row)] = colours_backup[x]; - celldat[THE_COORDS(x, row)] = celldat_backup[x]; - } - } - }); - } - /* - * 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 - */ - t = (gaps | (gaps - 1)); - gaps = (t + 1) | (((~t & -~t) - 1) >> (__builtin_ctz(gaps) + 1)); - } while (gaps && (gaps + 1 <= (1<<(num-1)))); - } - } - } - } else if (material && count == 0) { - // Empty square, try placements - - if (flat) { - // Generate the placement - if (black) black_count--; - else white_count--; - colours[loc] = current_colour; - celldat[loc] = NUM_INC | STONE_FLAT; - WIN_EVALUATE_OR_RECURSE({ - // If we did update the optimal value, store - generate_place(loc, STONE_FLAT, negamax_ptn); - },{ - // Reset the state - celldat[loc] = 0; - if (black) black_count++; - else white_count++; - }); - // Do the same for walls, can't happen without flats - if (standing) { - if (black) black_count--; - else white_count--; - colours[loc] = current_colour; - celldat[loc] = NUM_INC | STONE_STANDING; - WIN_EVALUATE_OR_RECURSE({ - generate_place(loc, STONE_STANDING, negamax_ptn); - },{ - celldat[loc] = 0; - if (black) black_count++; - else white_count++; - }); - } - } - - // and for caps - if (cap) { - if (black) black_count &= 127; - else white_count &= 127; - colours[loc] = current_colour; - celldat[loc] = NUM_INC | STONE_CAPSTONE; - WIN_EVALUATE_OR_RECURSE({ - generate_place(loc, STONE_CAPSTONE, negamax_ptn); - },{ - celldat[loc] = 0; - if (black) black_count |= 128; - else white_count |= 128; - }); - } - } - negamax_display_progress(cur_depth); + if (cur_depth > 1) { + value = colour*cnn1986_evaluate_black_win(); + } else { + action_take(action); + value = fmax(value, -negamax(cur_depth - 1, -beta, -alpha, -colour)); + action_undo(action); + } + // alpha = fmax(alpha, value); + if (value > alpha) { + alpha = value; + action_to_ptn(action, negamax_ptn); } + if (alpha >= beta) break; } - prune: - /* - * 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 { - * entry->flag = flag; - * entry->value = value; - * entry->depth = cur_depth; - * } - */ + action_list_free(action_list); return value; } -inline float -negamax_generate(void) { - // We need to start with something outside of [-∞,∞] because those - // values are wins - const float safe_infty = infty + 1; - tt_init(); - float result = negamax(negamax_search_depth, - -safe_infty, safe_infty, - (ply&1)?1.0:-1.0); - tt_free(); - - return result; -} +/* + * // Movement steps, orderd with the enum: UP DOWN LEFT RIGHT + * static int8_t deltas[4]; + * + * void negamax_init(const uint8_t new_board_size) { + * board_size = new_board_size; + * deltas[0] = +board_size; + * deltas[1] = -board_size; + * deltas[2] = -1; + * deltas[3] = +1; + * negamax_free_zobrist(); + * negamax_init_zobrist(); + * } + * + * static void previous_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; + * } + * } + * + * static void push_stones(const int8_t location, + * const uint8_t count, + * const uint8_t new_colours, + * const enum STONE_VARIANT top_stone) { + * colours[location] = (colours[location] << count) | new_colours; + * celldat[location] = top_stone + * | ((celldat[location] + ((count << NUM_SHIFT))) & NUM_MASK); + * } + * + * static enum WIN_TYPE w; + * + * #define WIN_EVALUATE_OR_RECURSE(store,reset) { \ + * w = 0xFF; \ + * if (ply >= 2*board_size - 3) w = check_win(); \ + * if (w < 0xFF) { \ + * /\* Somebody won, assign weights accordingly. *\/ \ + * if (w == WIN_ROAD_BLACK || w == WIN_FLAT_BLACK) { \ + * value = colour*infty; \ + * /\* Always take the win *\/ \ + * if (value > 0) { \ + * { reset }; \ + * if (cur_depth == negamax_search_depth) { store }; \ + * goto prune; \ + * } \ + * /\* Fix draw value to be completely neutral *\/ \ + * } else if (w == WIN_DRAW) value = 0; \ + * else value = -colour*infty; \ + * } if (cur_depth == 0) { \ + * /\* We're at the bottom, evaluate *\/ \ + * value = fmax(value, colour * cnn1986_evaluate_black_win()); \ + * } else { \ + * /\* We're not at the bottom, recurse first *\/ \ + * next_ply(); \ + * value = fmax(value, -negamax(cur_depth - 1, -beta, -alpha, -colour)); \ + * previous_ply(); \ + * } \ + * { reset }; \ + * /\* Update the optimal value, which alpha carries *\/ \ + * if (value > alpha) { \ + * alpha = value; \ + * if (cur_depth == negamax_search_depth) { store }; \ + * /\* Prune *\/ \ + * if (alpha >= beta) goto prune; \ + * } \ + * } + * + * float negamax(const uint8_t cur_depth, float alpha, float beta, + * const float colour) { + * + * /\* + * * uint64_t hash = negamax_compute_zobrist(); + * * tt_entry_t *entry = tt_seek(hash); + * * const float alpha_orig = alpha; + * * + * * if (entry != NULL && entry->depth >= cur_depth) { + * * if (entry->flag == TT_EXACT) { + * * return entry->value; + * * } else if (entry->flag == TT_LOWERBOUND) { + * * alpha = fmax(alpha, entry->value); + * * } else if (entry->flag == TT_UPPERBOUND) { + * * beta = fmin(beta, entry->value); + * * } + * * if (alpha >= beta) return entry->value; + * * } + * * enum TT_FLAG flag; + * *\/ + * + * float value = -infty; + * const uint8_t black = (ply & 1), + * material = (black) ? black_count : white_count, + * flat = material & 127, + * cap = (ply > 2 && (material & 128)), + * standing = (ply > 2 && (material & 127)); + * + * // Step across the board + * for (uint8_t row = 0; row < board_size; row++) { + * for (uint8_t col = 0; col < board_size; col++) { + * // Try all valid actions for this square. Is it empty? + * const uint8_t loc = THE_COORDS(col, row); + * const uint8_t count = (COUNT_AT(loc) > board_size) ? board_size : COUNT_AT(loc); + * // Only try moves after CPS + * if (count && ((colours[loc] & 1) == current_colour) && ply>2) { + * // There are stones, let's try moving them + * + * // Pre-compute end-stops + * uint8_t end_stops[4][2]; // (end, not_crush) + * // UP DOWN LEFT RIGHT + * end_stops[0][0] = (board_size - row - 1 > count) ? count : board_size - row - 1; + * end_stops[1][0] = (row > count) ? count : row; + * end_stops[2][0] = (col > count) ? count : col; + * end_stops[3][0] = (board_size - col - 1 > count) ? count : board_size - col - 1; + * const uint8_t cap_top = STONE_AT(loc) == STONE_CAPSTONE; + * for (uint8_t d = 0; d < board_size-1; d++){ + * end_stops[d][1] = 1; + * const uint8_t stop = end_stops[d][0]; + * end_stops[d][0] = 0; + * for (uint8_t k = 1; k <= stop; k++) { + * const uint8_t stone = STONE_AT(loc+k*deltas[d]); + * if (stone == STONE_STANDING) { + * if (cap_top) { + * end_stops[d][1] = 0; + * end_stops[d][0]++; + * } + * break; + * } else if (stone == STONE_CAPSTONE) { + * break; + * } + * end_stops[d][0]++; + * } + * } + * + * uint16_t colours_backup[board_size]; + * uint8_t celldat_backup[board_size], drops[board_size]; + * // we only ever need board_size-1 in drops actually, the + * // last spot is to skip a bounds check at (*) + * + * //Back up the rows of the board + * for (uint8_t y = 0; y < board_size; y++) { + * colours_backup[y] = colours[THE_COORDS(col, y)]; + * celldat_backup[y] = celldat[THE_COORDS(col, y)]; + * } + * + * // I'm not a huge fan of looping through enums, but it's + * // better than manually unrolling this. Sufficiently smart + * // compilers? + * for (enum MOVE_DIRECTION dir = M_UP; dir <= M_RIGHT; dir++) { + * // Back-up the column once we start looking horizontally + * if (dir == M_LEFT) { + * for (uint8_t x = 0; x < board_size; x++) { + * colours_backup[x] = colours[THE_COORDS(x, row)]; + * celldat_backup[x] = celldat[THE_COORDS(x, row)]; + * } + * } + * /\* + * * We don't do anything terribly efficient here just try + * * all the ordered partitions of num ∈ {1 … end_stop}, and + * * skip the partition if it calls for multiple stones at + * * the end with a crush. + * *\/ + * uint8_t gaps, t, idx, mask; + * for (uint8_t num = 1; num <= count; num++) { + * for (uint8_t steps = 1; + * steps <= end_stops[dir][0] && steps <= num; + * steps++) { + * // TODO: Generalise to board_size! + * gaps = 0x07 >> (board_size-steps-1); + * // 0b0000[0111] because 4-1=3 and 5-1=4 + * do { + * // Ensure legal move if we have to crush + * const uint8_t last_drop_check = + * (num > 1) ? (gaps & 1<<(num - 2)) : 1; + * if (end_stops[dir][1] || last_drop_check) { + * // Translate to a drop sequence + * drops[0] = 1; mask = 1; idx = 0; + * for (uint8_t d = 0; d + 1 < num; d++) { + * if (gaps & mask) { + * idx++; + * drops[idx] = 1; // (*) no bounds check + * } else { + * drops[idx] += 1; + * } + * mask <<= 1; + * } + * // Do it, and manually check for win if it's valid + * uint8_t j = num; + * for (uint8_t k = 0; k < steps; k++) { + * j -= drops[k]; + * push_stones(loc+(k+1)*deltas[dir], + * drops[k], + * (colours[loc] >> j) & (0xFFFF >> (0x10 - drops[k])), + * (k == steps - 1) ? STONE_AT(loc) : STONE_FLAT); + * } + * // Then we drop them from the source + * colours[loc] >>= num; + * const uint8_t dec_count = celldat[loc] - (num << NUM_SHIFT); + * celldat[loc] = dec_count & NUM_MASK; + * + * // First check for wins, if we're at the bottom + * // evaluate, otherwise recurse + * WIN_EVALUATE_OR_RECURSE({ + * // If we did update the optimal value, store + * // this move + * generate_move(loc, dir, steps, drops, negamax_ptn); + * },{ + * // Reset the board data after recursing or + * // before returning + * if (dir <= M_DOWN) { + * for (uint8_t y = 0; y < board_size; y++) { + * colours[THE_COORDS(col, y)] = colours_backup[y]; + * celldat[THE_COORDS(col, y)] = celldat_backup[y]; + * } + * } else { + * for (uint8_t x = 0; x < board_size; x++) { + * colours[THE_COORDS(x, row)] = colours_backup[x]; + * celldat[THE_COORDS(x, row)] = celldat_backup[x]; + * } + * } + * }); + * } + * /\* + * * 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 + * *\/ + * t = (gaps | (gaps - 1)); + * gaps = (t + 1) | (((~t & -~t) - 1) >> (__builtin_ctz(gaps) + 1)); + * } while (gaps && (gaps + 1 <= (1<<(num-1)))); + * } + * } + * } + * } else if (material && count == 0) { + * // Empty square, try placements + * + * if (flat) { + * // Generate the placement + * if (black) black_count--; + * else white_count--; + * colours[loc] = current_colour; + * celldat[loc] = NUM_INC | STONE_FLAT; + * WIN_EVALUATE_OR_RECURSE({ + * // If we did update the optimal value, store + * generate_place(loc, STONE_FLAT, negamax_ptn); + * },{ + * // Reset the state + * celldat[loc] = 0; + * if (black) black_count++; + * else white_count++; + * }); + * // Do the same for walls, can't happen without flats + * if (standing) { + * if (black) black_count--; + * else white_count--; + * colours[loc] = current_colour; + * celldat[loc] = NUM_INC | STONE_STANDING; + * WIN_EVALUATE_OR_RECURSE({ + * generate_place(loc, STONE_STANDING, negamax_ptn); + * },{ + * celldat[loc] = 0; + * if (black) black_count++; + * else white_count++; + * }); + * } + * } + * + * // and for caps + * if (cap) { + * if (black) black_count &= 127; + * else white_count &= 127; + * colours[loc] = current_colour; + * celldat[loc] = NUM_INC | STONE_CAPSTONE; + * WIN_EVALUATE_OR_RECURSE({ + * generate_place(loc, STONE_CAPSTONE, negamax_ptn); + * },{ + * celldat[loc] = 0; + * if (black) black_count |= 128; + * else white_count |= 128; + * }); + * } + * } + * negamax_display_progress(cur_depth); + * } + * } + * + * prune: + * /\* + * * 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 { + * * entry->flag = flag; + * * entry->value = value; + * * entry->depth = cur_depth; + * * } + * *\/ + * + * return value; + * } + */ diff --git a/include/negamax.h b/include/negamax.h index 1cfebdd..8a67638 100644 --- a/include/negamax.h +++ b/include/negamax.h @@ -2,6 +2,7 @@ #include #include +#include #include #include #include @@ -12,7 +13,7 @@ extern uint8_t negamax_search_depth; extern inline void negamax_display_progress(const uint8_t); void negamax_init(const uint8_t new_board_size); -uint64_t negamax_compute_zobrist(void); +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 diff --git a/src/ctaklm.c b/src/ctaklm.c index bc35c75..1ccc1d0 100644 --- a/src/ctaklm.c +++ b/src/ctaklm.c @@ -416,15 +416,17 @@ main(int argc, char **argv) { (void)(argc); (void)(argv); - negamax_search_depth = 4; + negamax_search_depth = 3; new_game(5); negamax_init(5); tt_init(); // Test harness if (argc > 1) { - load_ptn("data/0.ptn"); - negamax_turn(); - return 0; } + negamax_search_depth = 5; + load_ptn("data/0.ptn"); + negamax_turn(); + return 0; + } // Test harness char *line = NULL; @@ -456,5 +458,7 @@ main(int argc, char **argv) { } } + negamax_free(); + return EXIT_SUCCESS; } -- cgit v1.2.3