diff options
| -rw-r--r-- | include/actions.c | 68 | ||||
| -rw-r--r-- | include/actions.h | 15 | ||||
| -rw-r--r-- | include/negamax.c | 62 | ||||
| -rw-r--r-- | include/negamax.h | 7 | ||||
| -rw-r--r-- | include/tt_llcht.c | 85 | ||||
| -rw-r--r-- | include/tt_llcht.h (renamed from include/tt_treap.h) | 14 | ||||
| -rw-r--r-- | include/tt_treap.c | 158 | ||||
| -rw-r--r-- | include/zobrist.c | 50 | ||||
| -rw-r--r-- | include/zobrist.h | 12 |
9 files changed, 204 insertions, 267 deletions
diff --git a/include/actions.c b/include/actions.c index 9b3534b..5085330 100644 --- a/include/actions.c +++ b/include/actions.c @@ -8,15 +8,6 @@ #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, @@ -65,13 +56,13 @@ void action_list_free(action_list_t *list) { } // Keep track of move offsets -static int8_t deltas[4]; +int8_t move_deltas[4]; void action_list_init(void) { - deltas[0] = +board_size; - deltas[1] = -board_size; - deltas[2] = -1; - deltas[3] = +1; + move_deltas[0] = +board_size; + move_deltas[1] = -board_size; + move_deltas[2] = -1; + move_deltas[3] = +1; } action_list_t *action_list_generate(void) { @@ -117,7 +108,7 @@ action_list_t *action_list_generate(void) { // 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 delta = move_deltas[d]; const int stop = end_stops[d]; end_stops[d] = 0; for (int k = 1; k <= stop; k++) { @@ -196,10 +187,10 @@ action_list_t *action_list_generate(void) { } void action_take(const action_t action) { - const int8_t loc = GET_LOC(action); - if (GET_TYPE(action) == A_PLACE) { + const int8_t loc = A_GET_LOC(action); + if (A_GET_TYPE(action) == A_PLACE) { const uint8_t black = (current_colour == C_BLACK); - switch (GET_DATA0(action)) { + switch (A_GET_DATA0(action)) { case STONE_FLAT: { if (black) black_count--; else white_count--; @@ -226,10 +217,10 @@ void action_take(const action_t action) { // 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]; + const uint8_t gaps = A_GET_DATA0(action) & 0x7F, + num = A_GET_DATA1(action) & 0x0F, // unpack + dir = A_GET_DATA1(action) >> 4; + int8_t delta = move_deltas[dir]; // Use the Kernighan method to count the set bits int8_t steps = 1; @@ -275,11 +266,11 @@ 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 int8_t loc = A_GET_LOC(action); + if (A_GET_TYPE(action) == A_PLACE) { const uint8_t black = (current_colour == C_BLACK); celldat[loc] = 0; - if (GET_DATA0(action) == STONE_CAPSTONE) { + if (A_GET_DATA0(action) == STONE_CAPSTONE) { if (black) black_count |= 0x80; else white_count |= 0x80; } else { @@ -289,11 +280,11 @@ void action_undo(const action_t action) { } 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]; + const uint8_t gaps = A_GET_DATA0(action) & 0x7F, + crush = A_GET_DATA0(action) & 0x80, + num = A_GET_DATA1(action) & 0x0F, + dir = A_GET_DATA1(action) >> 4; + const int8_t delta = move_deltas[dir]; int8_t steps = 1; uint8_t gap_bit = 1, total = 1; @@ -326,13 +317,13 @@ void action_undo(const action_t action) { } 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); + const int8_t loc = A_GET_LOC(action); + if (A_GET_TYPE(action) == A_PLACE) { + generate_place(loc, A_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; + const uint8_t gaps = A_GET_DATA0(action) & 0x7F, + num = A_GET_DATA1(action) & 0x0F, // unpack + dir = A_GET_DATA1(action) >> 4; uint8_t drops[board_size]; // we only ever need board_size-1 in // drops actually, the last spot is to @@ -365,10 +356,7 @@ list_append(action_list_t *list, const enum A_TYPE type, // TODO: trap errno new->next = NULL; - new->action = (type << TYPE_SHIFT) - | (loc << LOC_SHIFT) - | (data0 << DATA0_SHIFT) - | data1; + new->action = A_BUILD(type, loc, data0, data1); if (list->length) { list->tail->next = new; diff --git a/include/actions.h b/include/actions.h index 661f11e..ced0315 100644 --- a/include/actions.h +++ b/include/actions.h @@ -10,6 +10,19 @@ enum A_TYPE { A_PLACE, A_MOVE }; typedef uint32_t action_t; +#define A_TYPE_SHIFT 24 +#define A_LOC_SHIFT 16 +#define A_DATA0_SHIFT 8 + +#define A_GET_TYPE(a) (enum A_TYPE)((a)>>A_TYPE_SHIFT) +#define A_GET_LOC(a) (int8_t)(((a)>>A_LOC_SHIFT) & 0xFF) +#define A_GET_DATA0(a) (uint8_t)(((a)>>A_DATA0_SHIFT) & 0xFF) +#define A_GET_DATA1(a) (uint8_t)((a) & 0xFF) +#define A_BUILD(type,loc,data0,data1) ((type) << A_TYPE_SHIFT \ + | (loc) << A_LOC_SHIFT \ + | (data0) << A_DATA0_SHIFT \ + | (data1)) + typedef struct action_node_s { struct action_node_s *next; action_t action; @@ -20,6 +33,8 @@ typedef struct action_list_s { uint32_t length; } action_list_t; +extern int8_t move_deltas[4]; + void action_list_init(void); void action_list_free(action_list_t *list); action_list_t *action_list_generate(void); diff --git a/include/negamax.c b/include/negamax.c index 061b629..cfe2643 100644 --- a/include/negamax.c +++ b/include/negamax.c @@ -8,74 +8,15 @@ const float infty = 3.0; char negamax_ptn[9]; uint8_t negamax_search_depth = 3; -static uint64_t *zobrist[15]; - // =================================================================== // Helpers // =================================================================== -static void -zobrist_free(void); - -static int -zobrist_init(void); - -static uint64_t -zobrist_compute(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<board_size*board_size; l++) { - colour_stack_t c = colours[l]; - const uint8_t count = COUNT_AT(l); - enum STONE_VARIANT s = STONE_AT(l); - for (uint8_t h=0; h<15; h++) { - if (h<count) { - hash ^= zobrist[h][l*(2*3+1)+(c&1)*3+s]; - c >>= 1; - } - } - } - return hash; -} - -static int -zobrist_init(void) { - for (int k=0; k<15; k++) { - if (zobrist[k] != NULL) return EXIT_FAILURE; - } - - for (int j=0; j<15; j++) { - zobrist[j] = malloc(sizeof(uint64_t)*board_size*board_size*(2*3+1)); - for (int k=0; k<board_size*board_size*(2*3+1); k++) { - XORSHIFT64; - zobrist[j][k] = RANDOM64; - } - } - - return EXIT_SUCCESS; -} - -static void -zobrist_free(void) { - for (int k=0; k<15; k++) { - if (zobrist[k] != NULL) { - free(zobrist[k]); - zobrist[k] = NULL; - } - } -} - -// =================================================================== // α-β negamax using the cnn1986 evaluation function and transposition // tables using Zobrist hasing and a treap // =================================================================== @@ -119,7 +60,7 @@ negamax(const uint8_t cur_depth, float alpha, float beta, tt_entry_t *entry = tt_seek(hash); // CAUTION: >= breaks search stability - if (entry != NULL && entry->depth == cur_depth) { + if (entry != NULL && entry->depth >= cur_depth) { if (entry->flag == TT_EXACT) { return entry->value; } else if (entry->flag == TT_LOWERBOUND && entry->value > alpha) { @@ -145,6 +86,7 @@ negamax(const uint8_t cur_depth, float alpha, float beta, for (action_node_t *node=list->head; node!=NULL; node=node->next) { action_take(node->action); + // Compute the value of the node float node_value; if (ply >= 2*board_size - 2 && (w = check_win()) < 0xFF) { diff --git a/include/negamax.h b/include/negamax.h index 43995d1..b41871e 100644 --- a/include/negamax.h +++ b/include/negamax.h @@ -2,10 +2,12 @@ #include <math.h> #include <tak.h> + #include <actions.h> -#include <xorshift64.h> #include <cnn1986.h> -#include <tt_treap.h> +#include <tt_llcht.h> +#include <xorshift64.h> +#include <zobrist.h> extern const float infty; extern char negamax_ptn[9]; @@ -25,3 +27,4 @@ negamax_free(void); // negamax_display_progress function is called on every new square at // the top level. float negamax_generate(void); +extern uint8_t yes; diff --git a/include/tt_llcht.c b/include/tt_llcht.c new file mode 100644 index 0000000..03fa6cb --- /dev/null +++ b/include/tt_llcht.c @@ -0,0 +1,85 @@ +#include "tt_llcht.h" + +// =================================================================== +// Variables +// =================================================================== + +uint32_t tt_num_cached; +static tt_entry_t *table[TT_LLCHT_SIZE+1]; + +// =================================================================== +// Helper declarations +// =================================================================== + +tt_entry_t * +new_ll_node(const uint64_t key, const enum TT_FLAG flag, + const uint8_t depth, const float value, + const action_t action); + + +// =================================================================== +// Exported functions +// =================================================================== + +int tt_init(void) { + for (uint k=0; k<=TT_LLCHT_SIZE; k++) + table[k] = NULL; + return EXIT_SUCCESS; +} + +void tt_free(void) { + tt_entry_t *n, *nn; + for (uint k=0; k<=TT_LLCHT_SIZE; k++) { + n = table[k]; + while (n) { + nn = n->next; + free(n); + n = nn; + } + } +} + +tt_entry_t *tt_seek(const uint64_t key) { + tt_entry_t *lookup = table[key & TT_LLCHT_SIZE]; + while (lookup && lookup->key != key) + lookup = lookup->next; + return lookup; +} + +int tt_insert(const uint64_t key, const enum TT_FLAG flag, + const uint8_t depth, const float value, + const action_t action) { + tt_entry_t *new = new_ll_node(key, flag, depth, value, action), *n; + // TODO: trap + + const uint32_t idx = key & TT_LLCHT_SIZE; + if ((n = table[idx]) != NULL) { + for (; n->next != NULL; n = n->next); + n->next = new; + } else { + table[idx] = new; + } + + tt_num_cached++; + + return EXIT_SUCCESS; +} + +// =================================================================== +// Helper function implementations +// =================================================================== + +tt_entry_t * +new_ll_node(const uint64_t key, const enum TT_FLAG flag, + const uint8_t depth, const float value, + const action_t action) { + tt_entry_t *new = malloc(sizeof(struct tt_node_s)); + // TODO: trap errno + new->key = key; + new->next = NULL; + new->flag = flag; + new->depth = depth; + new->value = value; + new->action = action; + return new; +} diff --git a/include/tt_treap.h b/include/tt_llcht.h index 3991e79..f9a7a78 100644 --- a/include/tt_treap.h +++ b/include/tt_llcht.h @@ -1,11 +1,10 @@ -#ifndef TT_TREAP_H -#define TT_TREAP_H +#ifndef TT_LLCHT_H +#define TT_LLCHT_H #include <stdlib.h> #include <stdint.h> #include <actions.h> -#include <xorshift64.h> // =================================================================== // Types @@ -13,10 +12,9 @@ enum TT_FLAG { TT_EXACT, TT_LOWERBOUND, TT_UPPERBOUND }; -typedef struct treap_node_s { +typedef struct tt_node_s { uint64_t key; - uint32_t weight; - struct treap_node_s *left, *right, *parent; + struct tt_node_s *next; enum TT_FLAG flag; uint8_t depth; float value; @@ -27,6 +25,8 @@ typedef struct treap_node_s { // Globals // =================================================================== +#define TT_LLCHT_SIZE ((uint32_t)((1<<19) - 1)) + extern uint32_t tt_num_cached; // =================================================================== @@ -36,7 +36,7 @@ extern uint32_t tt_num_cached; int tt_init(void); void tt_free(void); -tt_entry_t *tt_seek(uint64_t key); +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, diff --git a/include/tt_treap.c b/include/tt_treap.c deleted file mode 100644 index 369d767..0000000 --- a/include/tt_treap.c +++ /dev/null @@ -1,158 +0,0 @@ -#include "tt_treap.h" - -// =================================================================== -// Variables -// =================================================================== - -uint32_t tt_num_cached; -static tt_entry_t * root; - -// =================================================================== -// Helper declarations -// =================================================================== - -void recurse_tree(tt_entry_t *n); -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 -// =================================================================== - -int tt_init(void) { - root = NULL; - tt_num_cached = 0; - return EXIT_SUCCESS; -} - -void tt_free(void) { - recurse_tree(root); - return; -} - -tt_entry_t *tt_seek(const uint64_t key) { - if (root == NULL) return NULL; - tt_entry_t * n = root; - - while (n != NULL && n->key != key) { - if (n->key > key) n = n->right; - else n = n->left; - } - return n; -} - -int tt_insert(const uint64_t key, const enum TT_FLAG flag, - 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; - return EXIT_SUCCESS; - } - tt_entry_t *s = root, *n = root; - // Find the correct position by doing a BST traversal - while (n!=NULL) { - s = n; - if (n->key >= key) n = n->right; - else n = n->left; - } - // Make it a leaf - if (s->key > key) s->right = m; - else s->left = m; - m->parent = s; - // Now bubble upward to satisfy the heap property - bubble_up(m); - tt_num_cached++; - return EXIT_SUCCESS; -} - -// =================================================================== -// Helper implementations -// =================================================================== - -void recurse_tree(tt_entry_t *n) { - if (n==NULL) return; - if (n->left != NULL) recurse_tree(n->left); - if (n->right != NULL) recurse_tree(n->right); - free(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) { - tt_entry_t *n = malloc(sizeof(struct treap_node_s)); - // TODO: trap - n->key = key; - n->flag = flag; - n->depth = depth; - n->value = value; - n->left = NULL; - n->right = NULL; - n->parent = NULL; - n->action = action; - XORSHIFT64; n->weight = RANDOM32; - return n; -} - -void rotate_left(tt_entry_t *n) { - tt_entry_t *a = n->parent, *b = a->left, *c = n->left; - /* - We are the right child, so do this - a n - / \ / \ - b n --> a d - / \ / \ - c d b c - */ - n->parent = a->parent; - // We may have to repair one level up as well - if (a->parent!=NULL) { - if (a->parent->left == a) a->parent->left = n; - else a->parent->right = n; - } - a->parent = n; - n->left = a; a->parent = n; - a->left = b; if (b!=NULL) b->parent = a; - a->right = c; if (c!=NULL) c->parent = a; -} - -void rotate_right(tt_entry_t *n) { - tt_entry_t *a = n->parent, *b = a->right, *d = n->right; - /* - We are the left child, so do this - a n - / \ / \ - n b --> c a - / \ / \ - c d d b - */ - n->parent = a->parent; - // We may have to repair one level up as well - if (a->parent!=NULL) { - if (a->parent->left == a) a->parent->left = n; - else a->parent->right = n; - } - a->parent = n; - n->right = a; a->parent = n; - a->left = d; if (d!=NULL) d->parent = a; - a->right = b; if (b!=NULL) b->parent = a; -} - -//This preserves the BST quality of the treap -void bubble_up(tt_entry_t *n) { - // Nothing to be done in this case - if (n==NULL || n->parent == NULL) return; - // Bubble until the treap invariants are satisfied - while (n->parent != NULL && n->weight < n->parent->weight) { - if (n->parent->left == n) rotate_right(n); - else rotate_left(n); - } - if (n->parent == NULL) root = n; -} diff --git a/include/zobrist.c b/include/zobrist.c new file mode 100644 index 0000000..feff5fa --- /dev/null +++ b/include/zobrist.c @@ -0,0 +1,50 @@ +#include "zobrist.h" + +// =================================================================== +// Globals +// =================================================================== + +static uint64_t *zobrist; + +// =================================================================== +// Helpers +// =================================================================== + + +// =================================================================== +// Exported method implementations +// =================================================================== + +int +zobrist_init(void) { + if (zobrist != NULL) return EXIT_FAILURE; + + zobrist = malloc(sizeof(uint64_t)*board_size*board_size*(15*2*3)); + for (int k=0; k<board_size*board_size*(15*2*3); k++) { + XORSHIFT64; + zobrist[k] = RANDOM64; + } + + return EXIT_SUCCESS; +} + +void +zobrist_free(void) { + if (zobrist != NULL) { + free(zobrist); + zobrist = NULL; + } +} + +uint64_t +zobrist_compute(void) { + uint64_t hash = 0; + for (uint8_t l=0; l<board_size*board_size; l++) { + colour_stack_t c = colours[l]; + const uint8_t count = COUNT_AT(l); + enum STONE_VARIANT s = STONE_AT(l); + for (uint8_t h=0; h<count; h++, c >>= 1) + hash ^= zobrist[l*(15*2*3)+h*2*3+(c&1)*3+s]; + } + return hash; +} diff --git a/include/zobrist.h b/include/zobrist.h new file mode 100644 index 0000000..cfc2941 --- /dev/null +++ b/include/zobrist.h @@ -0,0 +1,12 @@ +#include <xorshift64.h> +#include <tak.h> +#include <actions.h> + +void +zobrist_free(void); + +int +zobrist_init(void); + +uint64_t +zobrist_compute(void); |