aboutsummaryrefslogtreecommitdiff
path: root/include
diff options
context:
space:
mode:
Diffstat (limited to 'include')
-rw-r--r--include/actions.c68
-rw-r--r--include/actions.h15
-rw-r--r--include/negamax.c62
-rw-r--r--include/negamax.h7
-rw-r--r--include/tt_llcht.c85
-rw-r--r--include/tt_llcht.h (renamed from include/tt_treap.h)14
-rw-r--r--include/tt_treap.c158
-rw-r--r--include/zobrist.c50
-rw-r--r--include/zobrist.h12
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);
generated by cgit v1.3.1 (git 2.54.0) at 2026-08-30 20:21:31 +0000