diff options
| -rw-r--r-- | Makefile | 4 | ||||
| -rw-r--r-- | include/cnn1986_treap_cache.c | 198 | ||||
| -rw-r--r-- | include/cnn1986_treap_cache.h | 12 | ||||
| -rw-r--r-- | include/negamax_cnn1986.c | 8 | ||||
| -rw-r--r-- | include/negamax_cnn1986.h | 2 |
5 files changed, 219 insertions, 5 deletions
@@ -3,7 +3,7 @@ DEFINES=-DDETERMINISTIC CFLAGS=-O3 -Wall -Wextra -Wpedantic -std=c99 -D_DEFAULT_SOURCE $(DEFINES) -I$(IDIR) LIBS= -SRCS=$(wildcard include/*.c) $(wildcard 3rd-party/*.c) +SRCS=include/tak.c include/negamax_cnn1986.c include/weights.c include/lcdlib.c include/cnn1986_treap_cache.c OBJS=$(SRCS:.c=.o) BUILDROOT_DIR=buildroot-2020.11.1 @@ -22,7 +22,7 @@ endif ctaklm: src/ctaklm.o $(OBJS) $(CC) $(CFLAGS) src/ctaklm.o $(OBJS) -o ctaklm - $(STRIP) ctaklm +# $(STRIP) ctaklm $(SIZE) ctaklm pptdb: src/pptdb.o $(OBJS) diff --git a/include/cnn1986_treap_cache.c b/include/cnn1986_treap_cache.c new file mode 100644 index 0000000..06553c1 --- /dev/null +++ b/include/cnn1986_treap_cache.c @@ -0,0 +1,198 @@ +#include "cnn1986_treap_cache.h" + +// =================================================================== +// Types +// =================================================================== + +typedef struct treap_node_s { + uint32_t weight; + struct treap_node_s *left, *right, *parent; + colour_stack_t colours[25]; + data_t celldat[25]; + uint8_t white_count, black_count; + float result; +} * TreapNode; + +enum E_CMP { EQ, GT, LT }; + +// =================================================================== +// Variables +// =================================================================== + +uint32_t cnn1986_num_cached; +uint32_t cnn1986_max_num_cached; // TODO +static TreapNode root; +static uint64_t xors = (uint64_t)123134124234879; + +// =================================================================== +// Helper declarations +// =================================================================== + +enum E_CMP compare_data(TreapNode n); +void recurse_tree(TreapNode n); +TreapNode new_treap_node(float in_result); +void bubble_up(TreapNode n); + +#define XORSHIFT { xors ^= xors >> 12; xors ^= xors << 25; xors ^= xors >> 27; } +#define RANDOM (xors *= 0x2545F4914F6CDD1D) + +// =================================================================== +// Exported functions +// =================================================================== + +int cnn1986_cache_init(void) { + root = NULL; + cnn1986_num_cached = 0; + return EXIT_SUCCESS; +} + +void cnn1986_cache_free(void) { + recurse_tree(root); + return; +} + +int cnn1986_cache_seek(float *out_result) { + if (root == NULL) return EXIT_FAILURE; + TreapNode n = root; + enum E_CMP e; + e = compare_data(n); + while (n != NULL && e != EQ) { + if (e == GT) n = n->right; + else n = n->left; + } + if (n == NULL) return EXIT_FAILURE; + *out_result = n->result; + return EXIT_SUCCESS; +} + +int cnn1986_cache_insert(float in_result) { + if (root == NULL) { + root = new_treap_node(in_result); + cnn1986_num_cached = 1; + return EXIT_SUCCESS; + } + TreapNode s = root, n = root, m = new_treap_node(in_result); + // Find the correct position by doing a BST traversal + enum E_CMP e; + while (n!=NULL) { + s = n; + e = compare_data(n); + if (e == LT) n = n->left; + else n = n->right; + } + // Make it a leaf + e = compare_data(s); + if (e == GT) s->right = m; + else s->left = m; + m->parent = s; + // Now bubble upward to satisfy the heap property + bubble_up(m); + cnn1986_num_cached++; + return EXIT_SUCCESS; +} + +// =================================================================== +// Helper implementations +// =================================================================== + +enum E_CMP compare_data(TreapNode n) { + if (n->white_count < white_count) return LT; + else if (n->white_count > white_count) return GT; + + if (n->black_count < black_count) return LT; + else if (n->black_count > black_count) return GT; + + for (int k = 0; k<25; k++) { + if (n->colours[k] < colours[k]) return LT; + if (n->colours[k] > colours[k]) return GT; + } + + for (int k = 0; k<25; k++) { + if (n->celldat[k] < celldat[k]) return LT; + if (n->celldat[k] > celldat[k]) return GT; + } + + return EQ; +} + +void recurse_tree(TreapNode n) { + if (n==NULL) return; + if (n->left != NULL) recurse_tree(n->left); + if (n->right != NULL) recurse_tree(n->right); + free(n); +} + +TreapNode new_treap_node(float in_result) { + TreapNode n = malloc(sizeof(struct treap_node_s)); + // TODO: trap + n->left = NULL; + n->right = NULL; + n->parent = NULL; + XORSHIFT; n->weight = RANDOM; + // Set key + for (int k = 0; k<25; k++) { + n->celldat[k] = celldat[k]; + n->colours[k] = colours[k]; + } + n->black_count = black_count; + n->white_count = white_count; + // Set value + n->result = in_result; + return n; +} + +void rotate_left(TreapNode n) { + TreapNode 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(TreapNode n) { + TreapNode 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(TreapNode 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/cnn1986_treap_cache.h b/include/cnn1986_treap_cache.h new file mode 100644 index 0000000..292e9c5 --- /dev/null +++ b/include/cnn1986_treap_cache.h @@ -0,0 +1,12 @@ +#include <stdlib.h> +#include <stdint.h> +#include <tak.h> + +extern uint32_t cnn1986_num_cached; +extern uint32_t cnn1986_max_num_cached; + +int cnn1986_cache_init(void); +void cnn1986_cache_free(void); + +int cnn1986_cache_seek(float *out_result); +int cnn1986_cache_insert(float in_result); diff --git a/include/negamax_cnn1986.c b/include/negamax_cnn1986.c index 6c834f1..1dd0e72 100644 --- a/include/negamax_cnn1986.c +++ b/include/negamax_cnn1986.c @@ -391,9 +391,13 @@ negamax_cnn1986(const uint8_t cur_depth, float alpha, float beta, negamax_cnn1986_display_progress(cur_depth); } } - // Insert into the cache if we're not too deep + // Insert into the cache if we're not too deep, and make it + // useable for both min and max (colour * colour == 1) if (cur_depth < negamax_cnn1986_cache_threshold) - cnn1986_cache_insert(alpha); + cnn1986_cache_insert(colour*alpha); + } else { + // Impose the colour + alpha *= colour; } return alpha; } diff --git a/include/negamax_cnn1986.h b/include/negamax_cnn1986.h index 3002837..fc0d5f2 100644 --- a/include/negamax_cnn1986.h +++ b/include/negamax_cnn1986.h @@ -1,6 +1,6 @@ #include <stdint.h> #include <tak.h> -#include <cnn1986_cache.h> +#include <cnn1986_treap_cache.h> #include "weights.h" extern const float infty; |