aboutsummaryrefslogtreecommitdiff
path: root/include
diff options
context:
space:
mode:
Diffstat (limited to 'include')
-rw-r--r--include/cnn1986_treap_cache.c198
-rw-r--r--include/cnn1986_treap_cache.h12
-rw-r--r--include/negamax_cnn1986.c8
-rw-r--r--include/negamax_cnn1986.h2
4 files changed, 217 insertions, 3 deletions
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;
generated by cgit v1.2.3 (git 2.46.0) at 2026-08-30 10:59:30 +0000