From de4f20f28afe23ecfc546ad242e5bb44710996cc Mon Sep 17 00:00:00 2001 From: tslil clingman Date: Tue, 26 Jan 2021 17:42:53 -0500 Subject: Storing best moves! --- include/action_list.c | 403 ------------------------------------------------- include/action_list.h | 34 ----- include/actions.c | 404 ++++++++++++++++++++++++++++++++++++++++++++++++++ include/actions.h | 33 +++++ include/negamax.c | 21 +-- include/negamax.h | 2 +- include/tt_treap.c | 20 ++- include/tt_treap.h | 15 +- 8 files changed, 472 insertions(+), 460 deletions(-) delete mode 100644 include/action_list.c delete mode 100644 include/action_list.h create mode 100644 include/actions.c create mode 100644 include/actions.h diff --git a/include/action_list.c b/include/action_list.c deleted file mode 100644 index 30ca918..0000000 --- a/include/action_list.c +++ /dev/null @@ -1,403 +0,0 @@ -#include "action_list.h" - -// =================================================================== -// Helper method declarations -// =================================================================== - -#define DANGER_MIN(a,b) (((a)<(b))?(a):(b)) - -#define CLR_STONE NUM_MASK - -static inline void -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); - -static inline void -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; - while (n) { - nn = n->next; - free(n); - n = nn; - } - free(list); - } -} - -// Keep track of move offsets -static int8_t deltas[4]; - -void action_list_init(void) { - deltas[0] = +board_size; - deltas[1] = -board_size; - deltas[2] = -1; - deltas[3] = +1; -} - -action_list_t *action_list_generate(void) { - action_list_t *list = malloc(sizeof(struct action_list_s)); - // TODO: trap errno - 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 material = (ply & 1) ? black_count : white_count, - flat = material & 0x7F, - cap = ((ply >= 2) && (material & 0x80)), - standing = ((ply >= 2) && flat); - - // 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); - const uint8_t count = DANGER_MIN(COUNT_AT(loc), board_size); - - // 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; - } - 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! - const uint8_t crush = - (steps == end_stops[dir]) && crushes[dir]; - // Store the move - - action_list_append(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)))); - } - } - } - } - } // end of if (count) { ... } - else if (material) { - // Empty square, generate placements - if (flat) { - action_list_append(list, A_PLACE, loc, STONE_FLAT, 0); - if (standing) - action_list_append(list, A_PLACE, loc, STONE_STANDING,0); - } - if (cap) - action_list_append(list, A_PLACE, loc, STONE_CAPSTONE, 0); - } - } - } - return list; -} - -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); - switch (action->data0) { - case STONE_FLAT: { - if (black) black_count--; - else white_count--; - colours[loc] = current_colour; - celldat[loc] = NUM_INC | STONE_FLAT; - break; - } - case 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 &= 0x7F; - else white_count &= 0x7F; - colours[loc] = current_colour; - celldat[loc] = NUM_INC | STONE_CAPSTONE; - break; - } - } - } else { - const uint8_t gaps = action->data0 & 0x7F, // not interested in - // whether we crushed, - // it will work out by - // anyway because we - // overwrite the top - // stone type. See (*) - // later for when we do - // need to know. - num = action->data1 & 0x0F, // unpack - dir = action->data1 >> 4; - int8_t delta = deltas[dir]; - - // Use the Kernighan method to count the set bits - int8_t steps = 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 - celldat[loc+steps*delta] |= STONE_AT(loc); - celldat[loc] &= CLR_STONE; - celldat[loc] |= STONE_FLAT; // should be optimised out - - uint8_t total = 1, gap_bit = 1 << (num - 2); // it's not important - // what negative - // shifts do here, we - // don't use gap_bit - // if num < 2 - // move stuff starting at destination - 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; - colours[loc+steps*delta] |= colours[loc] & ((1 << total) - 1); - colours[loc] >>= total; - celldat[loc+steps*delta] += total*NUM_INC; - celldat[loc] -= total*NUM_INC; - // Reset for next step - total = 0; - steps--; - } - } - // Move what remains (steps == 1 here always, so we simplify) - colours[loc+delta] <<= total; - colours[loc+delta] |= colours[loc] & ((1 << total) - 1); - colours[loc] >>= total; - celldat[loc+delta] += total*NUM_INC; - celldat[loc] -= total*NUM_INC; - } - // Next ply - inline_next_ply(); -} - -void action_undo(action_node_t *action) { - // Previous ply - inline_prev_ply(); - - const int8_t loc = action->loc; - if (action->type == A_PLACE) { - const uint8_t black = (current_colour == C_BLACK); - celldat[loc] = 0; - if (action->data0 == STONE_CAPSTONE) { - if (black) black_count |= 0x80; - else white_count |= 0x80; - } else { - if (black) black_count++; - else white_count++; - } - } else { - // See action_take for comments, this is the time reversal, but - // there is one caveat -- undoing a crush! (*) - const uint8_t gaps = action->data0 & 0x7F, - crush = action->data0 & 0x80, - num = action->data1 & 0x0F, - dir = action->data1 >> 4; - const int8_t delta = deltas[dir]; - - int8_t steps = 1; - uint8_t gap_bit = 1, total = 1; - for (int8_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); - colours[loc+steps*delta] >>= total; - celldat[loc] += total*NUM_INC; - celldat[loc+steps*delta] -= total*NUM_INC; - total = 0; - steps++; - } - } - colours[loc] <<= total; - colours[loc] |= colours[loc+steps*delta] & ((1 << total) - 1); - colours[loc+steps*delta] >>= total; - - celldat[loc] += total*NUM_INC; - // celldat[loc] &= CLR_STONE; is not necessary, as STONE_FLAT == 0 - celldat[loc] |= STONE_AT(loc+steps*delta); - celldat[loc+steps*delta] -= total*NUM_INC; - celldat[loc+steps*delta] &= CLR_STONE; - if (crush) { - celldat[loc+steps*delta] |= STONE_STANDING; - } else { - celldat[loc+steps*delta] |= STONE_FLAT; // should be optimised out - } - } -} - -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); - } else { - const uint8_t gaps = action->data0 & 0x7F, - num = action->data1 & 0x0F, // unpack - dir = action->data1 >> 4; - - 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 = 1; d < 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 -// =================================================================== - -static inline void -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 - - new->loc = loc; - new->type = type; - new->data0 = data0; - new->data1 = data1; - 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 -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/action_list.h b/include/action_list.h deleted file mode 100644 index b6fd13a..0000000 --- a/include/action_list.h +++ /dev/null @@ -1,34 +0,0 @@ -#include -#include - -#include - -#ifndef ACTION_LIST_H -#define ACTION_LIST_H - -enum A_TYPE { A_PLACE, A_MOVE }; - -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, *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/actions.c b/include/actions.c new file mode 100644 index 0000000..9b3534b --- /dev/null +++ b/include/actions.c @@ -0,0 +1,404 @@ +#include "actions.h" + +// =================================================================== +// Helper method declarations +// =================================================================== + +#define DANGER_MIN(a,b) (((a)<(b))?(a):(b)) + +#define CLR_STONE NUM_MASK + +#define TYPE_SHIFT 24 +#define LOC_SHIFT 16 +#define DATA0_SHIFT 8 + +#define GET_TYPE(a) (enum A_TYPE)((a)>>TYPE_SHIFT) +#define GET_LOC(a) (int8_t)(((a)>>LOC_SHIFT) & 0xFF) +#define GET_DATA0(a) (uint8_t)(((a)>>DATA0_SHIFT) & 0xFF) +#define GET_DATA1(a) (uint8_t)((a) & 0xFF) + +static inline void +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); + +static inline void +inline_prev_ply(void); + +// =================================================================== +// Exported method implementations +// =================================================================== + +int action_move_to_front(const action_t action, + action_list_t *list) { + action_node_t *n = list->head; + + // TODO: what if it's not in the list? + + while (n) { + if (n->action == action) { + const action_t t = list->head->action; + list->head->action = action; + n->action = t; + return EXIT_SUCCESS; + } + n = n->next; + } + + return EXIT_FAILURE; +} + + +void action_list_free(action_list_t *list) { + if (list) { + action_node_t *n = list->head, *nn; + while (n) { + nn = n->next; + free(n); + n = nn; + } + free(list); + } +} + +// Keep track of move offsets +static int8_t deltas[4]; + +void action_list_init(void) { + deltas[0] = +board_size; + deltas[1] = -board_size; + deltas[2] = -1; + deltas[3] = +1; +} + +action_list_t *action_list_generate(void) { + action_list_t *list = malloc(sizeof(struct action_list_s)); + // TODO: trap errno + 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 material = (ply & 1) ? black_count : white_count, + flat = material & 0x7F, + cap = ((ply >= 2) && (material & 0x80)), + standing = ((ply >= 2) && flat); + + // 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); + const uint8_t count = DANGER_MIN(COUNT_AT(loc), board_size); + + // 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; + } + 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! + const uint8_t crush = + (steps == end_stops[dir]) && crushes[dir]; + // Store the move + + list_append(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)))); + } + } + } + } + } // end of if (count) { ... } + else if (material) { + // Empty square, generate placements + if (flat) { + list_append(list, A_PLACE, loc, STONE_FLAT, 0); + if (standing) + list_append(list, A_PLACE, loc, STONE_STANDING,0); + } + if (cap) + list_append(list, A_PLACE, loc, STONE_CAPSTONE, 0); + } + } + } + return list; +} + +void action_take(const action_t action) { + const int8_t loc = GET_LOC(action); + if (GET_TYPE(action) == A_PLACE) { + const uint8_t black = (current_colour == C_BLACK); + switch (GET_DATA0(action)) { + case STONE_FLAT: { + if (black) black_count--; + else white_count--; + colours[loc] = current_colour; + celldat[loc] = NUM_INC | STONE_FLAT; + break; + } + case 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 &= 0x7F; + else white_count &= 0x7F; + colours[loc] = current_colour; + celldat[loc] = NUM_INC | STONE_CAPSTONE; + break; + } + } + } else { + // not interested in whether we crushed, it will work out by + // anyway because we overwrite the top stone type. See (*) later + // for when we do need to know. + const uint8_t gaps = GET_DATA0(action) & 0x7F, + num = GET_DATA1(action) & 0x0F, // unpack + dir = GET_DATA1(action) >> 4; + int8_t delta = deltas[dir]; + + // Use the Kernighan method to count the set bits + int8_t steps = 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 + celldat[loc+steps*delta] |= STONE_AT(loc); + celldat[loc] &= CLR_STONE; + celldat[loc] |= STONE_FLAT; // should be optimised out + + uint8_t total = 1, gap_bit = 1 << (num - 2); // it's not important + // what negative + // shifts do here, we + // don't use gap_bit + // if num < 2 + // move stuff starting at destination + 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; + colours[loc+steps*delta] |= colours[loc] & ((1 << total) - 1); + colours[loc] >>= total; + celldat[loc+steps*delta] += total*NUM_INC; + celldat[loc] -= total*NUM_INC; + // Reset for next step + total = 0; + steps--; + } + } + // Move what remains (steps == 1 here always, so we simplify) + colours[loc+delta] <<= total; + colours[loc+delta] |= colours[loc] & ((1 << total) - 1); + colours[loc] >>= total; + celldat[loc+delta] += total*NUM_INC; + celldat[loc] -= total*NUM_INC; + } + // Next ply + inline_next_ply(); +} + +void action_undo(const action_t action) { + // Previous ply + inline_prev_ply(); + + const int8_t loc = GET_LOC(action); + if (GET_TYPE(action) == A_PLACE) { + const uint8_t black = (current_colour == C_BLACK); + celldat[loc] = 0; + if (GET_DATA0(action) == STONE_CAPSTONE) { + if (black) black_count |= 0x80; + else white_count |= 0x80; + } else { + if (black) black_count++; + else white_count++; + } + } else { + // See action_take for comments, this is the time reversal, but + // there is one caveat -- undoing a crush! (*) + const uint8_t gaps = GET_DATA0(action) & 0x7F, + crush = GET_DATA0(action) & 0x80, + num = GET_DATA1(action) & 0x0F, + dir = GET_DATA1(action) >> 4; + const int8_t delta = deltas[dir]; + + int8_t steps = 1; + uint8_t gap_bit = 1, total = 1; + for (int8_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); + colours[loc+steps*delta] >>= total; + celldat[loc] += total*NUM_INC; + celldat[loc+steps*delta] -= total*NUM_INC; + total = 0; + steps++; + } + } + colours[loc] <<= total; + colours[loc] |= colours[loc+steps*delta] & ((1 << total) - 1); + colours[loc+steps*delta] >>= total; + + celldat[loc] += total*NUM_INC; + // celldat[loc] &= CLR_STONE; is not necessary, as STONE_FLAT == 0 + celldat[loc] |= STONE_AT(loc+steps*delta); + celldat[loc+steps*delta] -= total*NUM_INC; + celldat[loc+steps*delta] &= CLR_STONE; + if (crush) { + celldat[loc+steps*delta] |= STONE_STANDING; + } else { + celldat[loc+steps*delta] |= STONE_FLAT; // should be optimised out + } + } +} + +void action_to_ptn(const action_t action, char* out_ptn) { + const int8_t loc = GET_LOC(action); + if (GET_TYPE(action) == A_PLACE) { + generate_place(loc, GET_DATA0(action), out_ptn); + } else { + const uint8_t gaps = GET_DATA0(action) & 0x7F, + num = GET_DATA1(action) & 0x0F, // unpack + dir = GET_DATA1(action) >> 4; + + 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 = 1; d < 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 +// =================================================================== + +static inline void +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 + + new->next = NULL; + new->action = (type << TYPE_SHIFT) + | (loc << LOC_SHIFT) + | (data0 << DATA0_SHIFT) + | data1; + + if (list->length) { + list->tail->next = new; + list->tail = new; + } else { + list->head = new; + list->tail = new; + } + + list->length++; +} + +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/actions.h b/include/actions.h new file mode 100644 index 0000000..661f11e --- /dev/null +++ b/include/actions.h @@ -0,0 +1,33 @@ +#ifndef ACTIONS_H +#define ACTIONS_H + +#include +#include + +#include + +enum A_TYPE { A_PLACE, A_MOVE }; + +typedef uint32_t action_t; + +typedef struct action_node_s { + struct action_node_s *next; + action_t action; +} action_node_t; + +typedef struct action_list_s { + 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); +int action_move_to_front(const action_t action, action_list_t *list); + +void action_take(const action_t action); +void action_undo(const action_t action); + +void action_to_ptn(const action_t action, char* out_ptn); + +#endif diff --git a/include/negamax.c b/include/negamax.c index f6a7525..7f05040 100644 --- a/include/negamax.c +++ b/include/negamax.c @@ -131,6 +131,7 @@ negamax(const uint8_t cur_depth, float alpha, float beta, uint64_t hash = zobrist_compute(); tt_entry_t *entry = tt_seek(hash); + // CAUTION: >= breaks search stability if (entry != NULL && entry->depth == cur_depth) { if (entry->flag == TT_EXACT) { return entry->value; @@ -146,15 +147,16 @@ negamax(const uint8_t cur_depth, float alpha, float beta, if ((list = action_list_generate()) == NULL) return alpha; // should never happen! + if (entry != NULL) { + action_move_to_front(entry->action, list); + } - /* - * action_node_t *best = NULL; - */ - + action_t best_action; float value = -infty; + for (action_node_t *node=list->head; node!=NULL; node=node->next) { - action_take(node); + action_take(node->action); // Compute the value of the node float node_value; if (ply >= 2*board_size - 2 && (w = check_win()) < 0xFF) { @@ -168,14 +170,15 @@ negamax(const uint8_t cur_depth, float alpha, float beta, } else { node_value = colour * cnn1986_evaluate_black_win(); } - action_undo(node); + action_undo(node->action); negamax_display_progress(cur_depth, list->length); if (node_value > value) { value = node_value; + best_action = node->action; if (cur_depth == negamax_search_depth) - action_to_ptn(node, negamax_ptn); + action_to_ptn(node->action, negamax_ptn); } alpha = fmax(value, alpha); @@ -189,12 +192,12 @@ negamax(const uint8_t cur_depth, float alpha, float beta, else if (value <= alpha) flag = TT_UPPERBOUND; if (entry == NULL) { - tt_insert(hash, flag, cur_depth, value); + tt_insert(hash, flag, cur_depth, value, best_action); } else { entry->flag = flag; entry->value = value; entry->depth = cur_depth; - // entry->action = best; + entry->action = best_action; } return value; diff --git a/include/negamax.h b/include/negamax.h index c902d3c..43995d1 100644 --- a/include/negamax.h +++ b/include/negamax.h @@ -2,7 +2,7 @@ #include #include -#include +#include #include #include #include diff --git a/include/tt_treap.c b/include/tt_treap.c index b48ffd4..369d767 100644 --- a/include/tt_treap.c +++ b/include/tt_treap.c @@ -12,10 +12,14 @@ static tt_entry_t * root; // =================================================================== void recurse_tree(tt_entry_t *n); -tt_entry_t *new_treap_node(const uint64_t key, const enum TT_FLAG flag, - const uint8_t depth, const float value); void bubble_up(tt_entry_t *n); +tt_entry_t * +new_treap_node(const uint64_t key, const enum TT_FLAG flag, + const uint8_t depth, const float value, + const action_t action); + + // =================================================================== // Exported functions // =================================================================== @@ -43,8 +47,9 @@ tt_entry_t *tt_seek(const uint64_t key) { } int tt_insert(const uint64_t key, const enum TT_FLAG flag, - const uint8_t depth, const float value) { - tt_entry_t *m = new_treap_node(key, flag, depth, value); + const uint8_t depth, const float value, + const action_t action) { + tt_entry_t *m = new_treap_node(key, flag, depth, value, action); if (root == NULL) { root = m; tt_num_cached = 1; @@ -78,8 +83,10 @@ void recurse_tree(tt_entry_t *n) { free(n); } -tt_entry_t *new_treap_node(const uint64_t key, const enum TT_FLAG flag, - const uint8_t depth, const float value) { +tt_entry_t * +new_treap_node(const uint64_t key, const enum TT_FLAG flag, + const uint8_t depth, const float value, + const action_t action) { tt_entry_t *n = malloc(sizeof(struct treap_node_s)); // TODO: trap n->key = key; @@ -89,6 +96,7 @@ tt_entry_t *new_treap_node(const uint64_t key, const enum TT_FLAG flag, n->left = NULL; n->right = NULL; n->parent = NULL; + n->action = action; XORSHIFT64; n->weight = RANDOM32; return n; } diff --git a/include/tt_treap.h b/include/tt_treap.h index 1a15e1b..3991e79 100644 --- a/include/tt_treap.h +++ b/include/tt_treap.h @@ -1,10 +1,11 @@ +#ifndef TT_TREAP_H +#define TT_TREAP_H + #include #include -#include -#include -#ifndef TT_TREAP_H -#define TT_TREAP_H +#include +#include // =================================================================== // Types @@ -19,7 +20,7 @@ typedef struct treap_node_s { enum TT_FLAG flag; uint8_t depth; float value; - action_node_t *action; + action_t action; } tt_entry_t; // =================================================================== @@ -38,7 +39,7 @@ 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); + const uint8_t depth, const float value, + const action_t action); #endif -- cgit v1.2.3