From cf921b2e647136dc34568e0fff78b67c14c8e2fa Mon Sep 17 00:00:00 2001 From: tslil clingman Date: Sun, 24 Jan 2021 19:06:49 -0500 Subject: Working on action lists to refactor --- Makefile | 4 +- include/action_list.c | 262 ++++++++++++++++++++++++++++++++++++++++++++++++ include/action_list.h | 21 ++++ include/cnn1986_cache.c | 77 -------------- include/cnn1986_cache.h | 19 ---- include/negamax.c | 96 ++++++++++-------- include/negamax.h | 2 + src/ctaklm.c | 12 ++- 8 files changed, 346 insertions(+), 147 deletions(-) create mode 100644 include/action_list.c create mode 100644 include/action_list.h delete mode 100644 include/cnn1986_cache.c delete mode 100644 include/cnn1986_cache.h diff --git a/Makefile b/Makefile index 0e7e1fa..2b0b6a2 100644 --- a/Makefile +++ b/Makefile @@ -1,9 +1,9 @@ IDIR=include DEFINES=-DDETERMINISTIC -CFLAGS=-O3 -Wall -Wextra -Wpedantic -std=c99 -D_DEFAULT_SOURCE $(DEFINES) -I$(IDIR) +CFLAGS=-O3 -Wall -Wextra -Wpedantic -std=c99 -D_DEFAULT_SOURCE $(DEFINES) -I$(IDIR) -lm LIBS= -SRCS=include/tak.c include/xorshift64.c include/negamax.c include/weights.c include/cnn1986.c include/lcdlib.c include/tt_treap.c +SRCS=$(wildcard include/*.c) OBJS=$(SRCS:.c=.o) BUILDROOT_DIR=buildroot-2020.11.1 diff --git a/include/action_list.c b/include/action_list.c new file mode 100644 index 0000000..198cd08 --- /dev/null +++ b/include/action_list.c @@ -0,0 +1,262 @@ +#include "action_list.h" + +// =================================================================== +// Helper method declarations +// =================================================================== + +static inline action_list_t * +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); + +// =================================================================== +// Exported method implementations +// =================================================================== + +void action_list_free(action_list_t *list) { + action_list_t *n = NULL; + while (list) { + n = list->next; + free(list); + list = n; + } +} + +// Keep track of move offsets +static int8_t deltas[4]; + +void action_list_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; +} + +action_list_t *action_list_generate(void) { + + action_list_t *result = NULL; + + 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++) { + // We'll need these at various points, the location of this + // square and the maximum number of stones we could pick up + 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) + + // These are upper bounds, not counting walls and such. 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; + + // Now we check for caps and walls + 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]++; + } + } + /* + * 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++) { + 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 { + /* + * 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 (end_stops[dir][1] || last_drop_check) + result = action_list_prepend(result, A_MOVE, loc, (dir<<4) | num, gaps); + /* + * 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, generate placements + if (flat) { + result = action_list_prepend(result, A_PLACE, loc, STONE_FLAT, 0); + if (standing) + result = action_list_prepend(result, A_PLACE, loc, STONE_STANDING, 0); + } + if (cap) + result = action_list_prepend(result, A_PLACE, loc, STONE_CAPSTONE, 0); + } + } + } + return result; +} + +void action_take(action_list_t *action) { + const uint8_t loc = action->loc; + if (action->type == A_PLACE) { + const uint8_t black = (ply&1); + switch (action->data0) { + STONE_FLAT: { + if (black) black_count--; + else white_count--; + colours[loc] = current_colour; + celldat[loc] = NUM_INC | STONE_FLAT; + break; + } + STONE_STANDING: { + if (black) black_count--; + else white_count--; + colours[loc] = current_colour; + celldat[loc] = NUM_INC | STONE_STANDING; + break; + } + default: { + if (black) black_count &= 127; + else white_count &= 127; + colours[loc] = current_colour; + celldat[loc] = NUM_INC | STONE_CAPSTONE; + break; + } + } + } 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; + } + 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); + } + // 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(); +}; + +void action_undo(action_list_t *action) { + const uint8_t loc = action->loc; + if (action->type == A_PLACE) { + const uint8_t black = (ply&1); + celldat[loc] = 0; + if (action->data0 == STONE_CAPSTONE) { + if (black) black_count |= 128; + else white_count |= 128; + } else { + if (black) black_count++; + else white_count++; + } + } else { + // TODO ??? + } + previous_ply(); +}; + +// =================================================================== +// Helper method implementations +// =================================================================== + +static inline action_list_t * +action_list_prepend(action_list_t *list, const enum A_TYPE type, + const uint8_t loc, const uint8_t data0, + const uint8_t data1) { + action_list_t *new = malloc(sizeof(action_list_t)); + // TODO: trap errno + new->loc = loc; + new->next = list; + new->data0 = data0; + new->data1 = data1; + return new; +} + +static inline 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 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); +} diff --git a/include/action_list.h b/include/action_list.h new file mode 100644 index 0000000..3670114 --- /dev/null +++ b/include/action_list.h @@ -0,0 +1,21 @@ +#include +#include + +#include + +enum A_TYPE { A_PLACE, A_MOVE }; + +typedef struct action_list_s { + struct action_list_s *next; + enum A_TYPE type; + uint8_t loc; + uint8_t data0; + uint8_t data1; +} action_list_t; + +void action_list_init(const uint8_t new_board_size); +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); diff --git a/include/cnn1986_cache.c b/include/cnn1986_cache.c deleted file mode 100644 index 303ef57..0000000 --- a/include/cnn1986_cache.c +++ /dev/null @@ -1,77 +0,0 @@ -#include "cnn1986_cache.h" - -#define DATA_STONE_SHIFT 6 -#define DATA_COUNT_SHIFT (DATA_STONE_SHIFT+2) -#define COLOUR_MASK 0x3F // 0b00111111 - -uint32_t cnn1986_num_cached, cnn1986_max_num_cached = 1000000; -node_t *head = NULL, *tail = NULL; - -int cnn1986_cache_init(void) { return EXIT_SUCCESS; } - -void cnn1986_cache_free(void) { - node_t *c = head, *n; - while (c) { - n = c->next; - free(c); - c = n; - } - head = NULL; - tail = NULL; -} - -int cnn1986_cache_seek(const uint64_t key[4], - float *out_result) { - node_t *c = head; - while (c != NULL) { - // Either seek next or move to front and return - uint8_t fail = 0; - for (int k=0; k<4; k++) { - if (c->key[k] != key[k]) { - fail = 1; break; - } - } - - if (fail == 1) { - c = c->next; - } else { - *out_result = c->result; - // Move to front - if (c != head) { - if (tail == c) tail=c->prev; - if (c->next) c->next->prev = c->prev; - c->prev->next = c->next; - c->prev = NULL; - c->next = head; - head->prev = c; - head = c; - } - return EXIT_SUCCESS; - } - } - // Failed to find it - return EXIT_FAILURE; -} - -int cnn1986_cache_insert(const uint64_t key[4], float in_result) { - node_t *new = malloc(sizeof(node_t)); - if (new == NULL) return EXIT_FAILURE; - // TODO: check errno - new->prev = NULL; - new->next = head; - if (head) head->prev = new; - head = new; - for (int k=0; k<4; k++) new->key[k] = key[k]; - new->result = in_result; - if (cnn1986_num_cached == 0) tail = new; - cnn1986_num_cached++; - - if (cnn1986_num_cached > cnn1986_max_num_cached) { - tail = tail->prev; - free(tail->next); - tail->next = NULL; - cnn1986_num_cached--; - } - - return EXIT_SUCCESS; -} diff --git a/include/cnn1986_cache.h b/include/cnn1986_cache.h deleted file mode 100644 index 14a894d..0000000 --- a/include/cnn1986_cache.h +++ /dev/null @@ -1,19 +0,0 @@ -#include -#include - -extern uint32_t cnn1986_num_cached, cnn1986_max_num_cached; - -typedef struct node_s { - struct node_s *next, *prev; - uint64_t key[4]; - float result; -} node_t; - -int cnn1986_cache_init(void); -void cnn1986_cache_free(void); - -int cnn1986_cache_seek(const uint64_t key[4], - float *out_result); - -int cnn1986_cache_insert(const uint64_t key[4], - const float in_result); diff --git a/include/negamax.c b/include/negamax.c index 3e3a209..fd8c7ac 100644 --- a/include/negamax.c +++ b/include/negamax.c @@ -95,7 +95,6 @@ static void push_stones(const int8_t location, | ((celldat[location] + ((count << NUM_SHIFT))) & NUM_MASK); } -static float val; static enum WIN_TYPE w; #define WIN_EVALUATE_OR_RECURSE(store,reset) { \ @@ -104,53 +103,57 @@ static enum WIN_TYPE w; if (w < 0xFF) { \ /* Somebody won, assign weights accordingly. */ \ if (w == WIN_ROAD_BLACK || w == WIN_FLAT_BLACK) { \ - val = colour*infty; \ + value = colour*infty; \ /* Always take the win */ \ - if (cur_depth == 0 && val > 0) { \ + if (value > 0) { \ { reset }; \ - { store }; \ - return infty; \ + if (cur_depth == negamax_search_depth) { store }; \ + goto prune; \ } \ /* Fix draw value to be completely neutral */ \ - } else if (w == WIN_DRAW) val = 0; \ - else val = -colour*infty; \ - } else if (cur_depth == negamax_search_depth) { \ + } else if (w == WIN_DRAW) value = 0; \ + else value = -colour*infty; \ + } if (cur_depth == 0) { \ /* We're at the bottom, evaluate */ \ - val = colour * cnn1986_evaluate_black_win(); \ + value = fmax(value, colour * cnn1986_evaluate_black_win()); \ } else { \ /* We're not at the bottom, recurse first */ \ next_ply(); \ - val = -negamax(cur_depth + 1, -beta, -alpha, -colour); \ + value = fmax(value, -negamax(cur_depth - 1, -beta, -alpha, -colour)); \ previous_ply(); \ } \ { reset }; \ - /* Prune */ \ - if (val >= beta) return beta; \ /* Update the optimal value, which alpha carries */ \ - if (val > alpha) { \ - alpha = val; \ - if (cur_depth == 0) { store }; \ + 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) { - if (entry->value > alpha) alpha = entry->value; - } else if (entry->flag == TT_UPPERBOUND) { - if (entry->value < beta) beta = entry->value; - } - if (alpha >= beta) return entry->value; - } - + /* + * 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, @@ -347,19 +350,22 @@ float negamax(const uint8_t cur_depth, float alpha, float beta, } } - enum TT_FLAG flag = TT_EXACT; - if (alpha <= alpha_orig) flag = TT_UPPERBOUND; - else if (alpha >= beta) flag = TT_UPPERBOUND; - - if (entry == NULL) { - tt_insert(hash, flag, cur_depth, alpha); - } else { - entry->flag = flag; - entry->value = alpha; - entry->depth = cur_depth; - } - - return alpha; + 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; } inline float @@ -369,7 +375,9 @@ negamax_generate(void) { const float safe_infty = infty + 1; tt_init(); - float result = negamax(0, -safe_infty, safe_infty, (ply&1)?1.0:-1.0); + float result = negamax(negamax_search_depth, + -safe_infty, safe_infty, + (ply&1)?1.0:-1.0); tt_free(); return result; diff --git a/include/negamax.h b/include/negamax.h index f3a0a6c..1cfebdd 100644 --- a/include/negamax.h +++ b/include/negamax.h @@ -1,4 +1,6 @@ #include +#include + #include #include #include diff --git a/src/ctaklm.c b/src/ctaklm.c index e80dd82..bc35c75 100644 --- a/src/ctaklm.c +++ b/src/ctaklm.c @@ -301,7 +301,7 @@ inline void negamax_display_progress(const uint8_t depth) { sum_depth += depth; num_check += 1; - if (depth == 0) { + if (depth == negamax_search_depth) { progress++; printf("\x1B[1GComputing: %.0f%%", (progress*100)/(board_size*board_size)); @@ -416,13 +416,15 @@ main(int argc, char **argv) { (void)(argc); (void)(argv); - // Test harness - negamax_search_depth = 5; + negamax_search_depth = 4; new_game(5); negamax_init(5); + tt_init(); + // Test harness + if (argc > 1) { load_ptn("data/0.ptn"); - for (int k=0; k<2; k++) negamax_turn(); - return 0; + negamax_turn(); + return 0; } // Test harness char *line = NULL; -- cgit v1.2.3