aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--Makefile2
-rw-r--r--include/cnn1986.c114
-rw-r--r--include/cnn1986.h3
-rw-r--r--include/cnn1986_treap_cache.c81
-rw-r--r--include/cnn1986_treap_cache.h6
-rw-r--r--include/negamax.c (renamed from include/negamax_cnn1986.c)261
-rw-r--r--include/negamax.h19
-rw-r--r--include/negamax_cnn1986.h19
-rw-r--r--include/xorshift64.c3
-rw-r--r--include/xorshift64.h18
-rw-r--r--src/ct1986.c26
-rw-r--r--src/ctaklm.c39
12 files changed, 313 insertions, 278 deletions
diff --git a/Makefile b/Makefile
index 5aad419..82b04c1 100644
--- a/Makefile
+++ b/Makefile
@@ -3,7 +3,7 @@ DEFINES=-DDETERMINISTIC
CFLAGS=-O3 -Wall -Wextra -Wpedantic -std=c99 -D_DEFAULT_SOURCE $(DEFINES) -I$(IDIR)
LIBS=
-SRCS=include/tak.c include/negamax_cnn1986.c include/weights.c include/lcdlib.c include/cnn1986_treap_cache.c
+SRCS=include/tak.c include/xorshift64.c include/negamax.c include/weights.c include/cnn1986.c include/lcdlib.c include/cnn1986_treap_cache.c
OBJS=$(SRCS:.c=.o)
BUILDROOT_DIR=buildroot-2020.11.1
diff --git a/include/cnn1986.c b/include/cnn1986.c
new file mode 100644
index 0000000..039dddd
--- /dev/null
+++ b/include/cnn1986.c
@@ -0,0 +1,114 @@
+#include "cnn1986.h"
+#include "weights.h"
+
+// ===================================================================
+// Implementation of a small convolutional neural network
+// ===================================================================
+
+static float flattened[CONV_NUM+2];
+static float dense1[DENSE1_NUM];
+static float dense2[DENSE2_NUM];
+
+#ifndef DETERMINISTIC
+union u_f {
+ uint32_t u;
+ float f;
+};
+
+static union u_f fudge;
+
+#define RANDF { \
+ XORSHIFT; \
+ fudge.u = 0x3f800000 | RANDOM32 >> 10; \
+ fudge.f = (fudge.f - 1.5) * 0.01; \
+ }
+#endif
+
+#define RELU(x) ((x) = ((x)<0)?0:(x))
+
+float cnn1986_evaluate_black_win(void) {
+ /* ------------------ *
+ * Convolution layer *
+ * ------------------ */
+ // for each kernel
+ for (uint8_t kern = 0; kern < KERN_NUM; kern++) {
+ // the stride is 1, march across the board
+ for (uint8_t bx = 0; bx < KERN_OSIZE; bx++) {
+ for (uint8_t by = 0; by < KERN_OSIZE; by++) {
+ flattened[kern+KERN_NUM*(bx+by*KERN_OSIZE)] =
+ conv2d_biases[kern];
+ // Compute the convolution for this position
+ for (uint8_t ky = 0; ky < KERN_SIZE; ky++) {
+ for (uint8_t kx = 0; kx < KERN_SIZE; kx++) {
+ for (uint8_t c = 0; c < KERN_CHAN; c++) {
+ // Where we are on the board
+ const uint8_t loc = kx+bx+(ky+by)*5;
+ // Look up what's on the board at this location, and
+ // multiply it. For c=0 we have to do some extra work
+ float lookup = 0;
+ if (COUNT_AT(loc)>c) {
+ if (c==0) {
+ if (STONE_AT(loc) == STONE_STANDING) {
+ lookup = (colours[loc] & 1) ? +0.25 : -0.25;
+ } else if (STONE_AT(loc) == STONE_CAPSTONE) {
+ lookup = (colours[loc] & 1) ? +1.00 : -1.00;
+ } else {
+ lookup = (colours[loc] & 1) ? +0.50 : -0.50;
+ }
+ } else {
+ lookup = (colours[loc] & (1<<c)) ? +0.50 : -0.50;
+ }
+ }
+ flattened[kern+KERN_NUM*(bx+by*KERN_OSIZE)]
+ += lookup*conv2d_weights[kern][ky][kx][c];
+ }
+ }
+ }
+ RELU(flattened[kern+KERN_NUM*(bx+by*KERN_OSIZE)]);
+ }
+ }
+ }
+ // Add input of flat counts
+ flattened[CONV_NUM] = (float)(white_count & 127)/21.0;
+ flattened[CONV_NUM+1] = (float)(black_count & 127)/21.0;
+ /* ------------------ *
+ * First dense layer *
+ * ------------------ */
+ for (uint8_t d1 = 0; d1 < DENSE1_NUM; d1++) {
+ dense1[d1] = dense1_biases[d1];
+ for (uint8_t fl = 0; fl < CONV_NUM+2; fl++) {
+ dense1[d1] += flattened[fl]*dense1_weights[d1][fl];
+ }
+ RELU(dense1[d1]);
+ }
+ /* ------------------- *
+ * Second dense layer *
+ * ------------------- */
+ for (uint8_t d2 = 0; d2 < DENSE2_NUM; d2++) {
+ dense2[d2] = dense2_biases[d2];
+ for (uint8_t d1 = 0; d1 < DENSE1_NUM; d1++) {
+ dense2[d2] += dense1[d1]*dense2_weights[d2][d1];
+ }
+ RELU(dense2[d2]);
+ }
+ /* ------------- *
+ * Output layer *
+ * ------------- */
+ float output = output_bias;
+ for (uint8_t d2 = 0; d2 < DENSE2_NUM; d2++) {
+ output += dense2[d2]*output_weights[d2];
+ }
+ // Truncated Pade approximant of logistic function
+ output = (12.0+output+50.0*output/(output*output+10.0))/24.0;
+#ifndef DETERMINISTIC
+ RANDF;
+ output += fudge.f;
+#endif
+ if (output > 1.0) {
+ return 1.0;
+ }
+ else if (output < 0.0) {
+ return -1.0;
+ }
+ return 2*output-1.0;
+}
diff --git a/include/cnn1986.h b/include/cnn1986.h
new file mode 100644
index 0000000..c04a04e
--- /dev/null
+++ b/include/cnn1986.h
@@ -0,0 +1,3 @@
+#include <tak.h>
+
+float cnn1986_evaluate_black_win(void);
diff --git a/include/cnn1986_treap_cache.c b/include/cnn1986_treap_cache.c
index 06553c1..94eda58 100644
--- a/include/cnn1986_treap_cache.c
+++ b/include/cnn1986_treap_cache.c
@@ -5,36 +5,31 @@
// ===================================================================
typedef struct treap_node_s {
+ uint64_t key;
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;
+ /*
+ * 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)
+void recurse_tree(const TreapNode n);
+TreapNode new_treap_node(const float in_result, const uint64_t key);
+void bubble_up(const TreapNode n);
// ===================================================================
// Exported functions
@@ -51,13 +46,12 @@ void cnn1986_cache_free(void) {
return;
}
-int cnn1986_cache_seek(float *out_result) {
+int cnn1986_cache_seek(const uint64_t key, 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;
+
+ while (n != NULL && n->key != key) {
+ if (n->key > key) n = n->right;
else n = n->left;
}
if (n == NULL) return EXIT_FAILURE;
@@ -65,24 +59,22 @@ int cnn1986_cache_seek(float *out_result) {
return EXIT_SUCCESS;
}
-int cnn1986_cache_insert(float in_result) {
+int cnn1986_cache_insert(const uint64_t key, const float in_result) {
if (root == NULL) {
- root = new_treap_node(in_result);
+ root = new_treap_node(in_result, key);
cnn1986_num_cached = 1;
return EXIT_SUCCESS;
}
- TreapNode s = root, n = root, m = new_treap_node(in_result);
+ TreapNode s = root, n = root,
+ m = new_treap_node(in_result, key);
// 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;
+ if (n->key >= key) n = n->right;
+ else n = n->left;
}
// Make it a leaf
- e = compare_data(s);
- if (e == GT) s->right = m;
+ if (s->key > key) s->right = m;
else s->left = m;
m->parent = s;
// Now bubble upward to satisfy the heap property
@@ -95,26 +87,6 @@ int cnn1986_cache_insert(float in_result) {
// 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);
@@ -122,20 +94,15 @@ void recurse_tree(TreapNode n) {
free(n);
}
-TreapNode new_treap_node(float in_result) {
+TreapNode new_treap_node(const float in_result, const uint64_t key) {
TreapNode n = malloc(sizeof(struct treap_node_s));
// TODO: trap
+ n->key = key;
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;
+ n->weight = RANDOM32;
+ XORSHIFT;
// Set value
n->result = in_result;
return n;
diff --git a/include/cnn1986_treap_cache.h b/include/cnn1986_treap_cache.h
index 292e9c5..92208b2 100644
--- a/include/cnn1986_treap_cache.h
+++ b/include/cnn1986_treap_cache.h
@@ -1,12 +1,12 @@
#include <stdlib.h>
#include <stdint.h>
#include <tak.h>
+#include <xorshift64.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);
+int cnn1986_cache_seek(const uint64_t key, float *out_result);
+int cnn1986_cache_insert(const uint64_t key, const float in_result);
diff --git a/include/negamax_cnn1986.c b/include/negamax.c
index 1dd0e72..bc912ad 100644
--- a/include/negamax_cnn1986.c
+++ b/include/negamax.c
@@ -1,136 +1,76 @@
-#include "negamax_cnn1986.h"
+#include "negamax.h"
// ===================================================================
// Globals
// ===================================================================
const float infty = 3.0;
-char negamax_cnn1986_ptn[9];
-uint8_t negamax_cnn1986_search_depth = 3;
-uint8_t negamax_cnn1986_cache_threshold = 3;
+char negamax_ptn[9];
+uint8_t negamax_search_depth = 3;
// ===================================================================
-// Implementation of a small convolutional neural network
+// Zobrist hashing
// ===================================================================
-static float flattened[CONV_NUM+2];
-static float dense1[DENSE1_NUM];
-static float dense2[DENSE2_NUM];
+uint64_t *zobrist = NULL;
-#ifndef DETERMINISTIC
-union u_f {
- uint32_t u;
- float f;
-};
-
-static uint32_t state = 1;
-static union u_f fudge;
-
-#define DOXORSHIFT { \
- state ^= state << 13; \
- state ^= state >> 17; \
- state ^= state << 5; \
- fudge.u = 0x3f800000 | state >> 10; \
- fudge.f = (fudge.f - 1.5) * 0.01; \
- }
-#endif
-
-#define RELU(x) ((x) = ((x)<0)?0:(x))
-
-float
-cnn1986_evaluate_black_win(void) {
- /* ------------------ *
- * Convolution layer *
- * ------------------ */
- // for each kernel
- for (uint8_t kern = 0; kern < KERN_NUM; kern++) {
- // the stride is 1, march across the board
- for (uint8_t bx = 0; bx < KERN_OSIZE; bx++) {
- for (uint8_t by = 0; by < KERN_OSIZE; by++) {
- flattened[kern+KERN_NUM*(bx+by*KERN_OSIZE)] =
- conv2d_biases[kern];
- // Compute the convolution for this position
- for (uint8_t ky = 0; ky < KERN_SIZE; ky++) {
- for (uint8_t kx = 0; kx < KERN_SIZE; kx++) {
- for (uint8_t c = 0; c < KERN_CHAN; c++) {
- // Where we are on the board
- const uint8_t loc = kx+bx+(ky+by)*5;
- // Look up what's on the board at this location, and
- // multiply it. For c=0 we have to do some extra work
- float lookup = 0;
- if (COUNT_AT(loc)>c) {
- if (c==0) {
- if (STONE_AT(loc) == STONE_STANDING) {
- lookup = (colours[loc] & 1) ? +0.25 : -0.25;
- } else if (STONE_AT(loc) == STONE_CAPSTONE) {
- lookup = (colours[loc] & 1) ? +1.00 : -1.00;
- } else {
- lookup = (colours[loc] & 1) ? +0.50 : -0.50;
- }
- } else {
- lookup = (colours[loc] & (1<<c)) ? +0.50 : -0.50;
- }
- }
- flattened[kern+KERN_NUM*(bx+by*KERN_OSIZE)]
- += lookup*conv2d_weights[kern][ky][kx][c];
- }
- }
+static int negamax_init_zobrist(void) {
+ if (zobrist != NULL) return EXIT_FAILURE;
+ zobrist = malloc(sizeof(uint64_t)*board_size*board_size*16*3*2);
+ for (int l=0; l<board_size*board_size; l++) {
+ for (int h=0; h<16; h++) {
+ for (int c=0; c<2; c++) {
+ for (int s=0; s<3; s++) {
+ XORSHIFT;
+ zobrist[l*board_size*board_size+h*16+c*2+s] = RANDOM64;
}
- RELU(flattened[kern+KERN_NUM*(bx+by*KERN_OSIZE)]);
}
}
}
- // Add input of flat counts
- flattened[CONV_NUM] = (float)(white_count & 127)/21.0;
- flattened[CONV_NUM+1] = (float)(black_count & 127)/21.0;
- /* ------------------ *
- * First dense layer *
- * ------------------ */
- for (uint8_t d1 = 0; d1 < DENSE1_NUM; d1++) {
- dense1[d1] = dense1_biases[d1];
- for (uint8_t fl = 0; fl < CONV_NUM+2; fl++) {
- dense1[d1] += flattened[fl]*dense1_weights[d1][fl];
- }
- RELU(dense1[d1]);
+ return EXIT_SUCCESS;
+}
+
+static void negamax_free_zobrist(void) {
+ if (zobrist != NULL) {
+ free(zobrist);
+ zobrist = NULL;
}
- /* ------------------- *
- * Second dense layer *
- * ------------------- */
- for (uint8_t d2 = 0; d2 < DENSE2_NUM; d2++) {
- dense2[d2] = dense2_biases[d2];
- for (uint8_t d1 = 0; d1 < DENSE1_NUM; d1++) {
- dense2[d2] += dense1[d1]*dense2_weights[d2][d1];
+}
+
+uint64_t negamax_compute_zobrist(void) {
+ uint64_t result = 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++) {
+ result ^= zobrist[l*board_size*board_size
+ +h*16 +(c&1)*2 +s];
+ s = STONE_FLAT;
+ c >>= 1;
}
- RELU(dense2[d2]);
}
- /* ------------- *
- * Output layer *
- * ------------- */
- float output = output_bias;
- for (uint8_t d2 = 0; d2 < DENSE2_NUM; d2++) {
- output += dense2[d2]*output_weights[d2];
- }
- // Truncated Pade approximant of logistic function
- output = (12.0+output+50.0*output/(output*output+10.0))/24.0;
-#ifndef DETERMINISTIC
- DOXORSHIFT;
- output += fudge.f;
-#endif
- if (output > 1.0) {
- return 1.0;
- }
- else if (output < 0.0) {
- return -1.0;
- }
- return 2*output-1.0;
+ return result;
}
// ===================================================================
-// α-β negamax using the above evaluator
+// α-β negamax using the cnn1986 evaluation function
// ===================================================================
-static void
-previous_ply(void) {
+
+// Movement steps, orderd with the enum: UP DOWN LEFT RIGHT
+static int8_t deltas[4];
+
+void negamax_init_size(void) {
+ deltas[0] = +board_size;
+ deltas[1] = -board_size;
+ deltas[2] = -1;
+ deltas[3] = +1;
+ negamax_free_zobrist();
+ negamax_init_zobrist();
+}
+
+static void previous_ply(void) {
if (ply>0) ply--;
if (ply == 1) {
current_colour = C_WHITE;
@@ -140,10 +80,10 @@ previous_ply(void) {
}
}
-static inline void
-push_stones(const int8_t location, const uint8_t count,
- const uint8_t new_colours,
- const enum STONE_VARIANT top_stone) {
+static void push_stones(const int8_t location,
+ const uint8_t count,
+ const uint8_t new_colours,
+ const enum STONE_VARIANT top_stone) {
colours[location] = (colours[location] << count) | new_colours;
celldat[location] = top_stone
| ((celldat[location] + ((count << NUM_SHIFT))) & NUM_MASK);
@@ -152,12 +92,9 @@ push_stones(const int8_t location, const uint8_t count,
static float val;
static enum WIN_TYPE w;
-// UP DOWN LEFT RIGHT
-static const int8_t deltas[4] = { +5, -5, -1, +1};
-
#define WIN_EVALUATE_OR_RECURSE(store,reset) { \
w = 0xFF; \
- if (ply >= 2*5 - 3) w = check_win(); \
+ if (ply >= 2*board_size - 3) w = check_win(); \
if (w < 0xFF) { \
/* Somebody won, assign weights accordingly. */ \
if (w == WIN_ROAD_BLACK || w == WIN_FLAT_BLACK) { \
@@ -171,13 +108,13 @@ static const int8_t deltas[4] = { +5, -5, -1, +1};
/* Fix draw value to be completely neutral */ \
} else if (w == WIN_DRAW) val = 0; \
else val = -colour*infty; \
- } else if (cur_depth == negamax_cnn1986_search_depth) { \
+ } else if (cur_depth == negamax_search_depth) { \
/* We're at the bottom, evaluate */ \
val = colour * cnn1986_evaluate_black_win(); \
} else { \
/* We're not at the bottom, recurse first */ \
next_ply(); \
- val = -negamax_cnn1986(cur_depth + 1, -beta, -alpha, -colour); \
+ val = -negamax(cur_depth + 1, -beta, -alpha, -colour); \
previous_ply(); \
} \
{ reset }; \
@@ -190,15 +127,10 @@ static const int8_t deltas[4] = { +5, -5, -1, +1};
} \
}
-float
-negamax_cnn1986(const uint8_t cur_depth, float alpha, float beta,
- const float colour) {
-
- int sought = EXIT_FAILURE;
- if (cur_depth < negamax_cnn1986_cache_threshold) {
- sought = cnn1986_cache_seek(&alpha);
- }
- if (sought) {
+float negamax(const uint8_t cur_depth, float alpha, float beta,
+ const float colour) {
+ uint64_t hash = negamax_compute_zobrist();
+ if (cnn1986_cache_seek(hash, &alpha) == EXIT_FAILURE) {
const uint8_t black = (ply & 1),
material = (black) ? black_count : white_count,
flat = material & 127,
@@ -206,24 +138,24 @@ negamax_cnn1986(const uint8_t cur_depth, float alpha, float beta,
standing = (ply > 2 && (material & 127));
// Step across the board
- for (uint8_t row = 0; row < 5; row++) {
- for (uint8_t col = 0; col < 5; col++) {
+ for (uint8_t row = 0; row < board_size; row++) {
+ for (uint8_t col = 0; col < board_size; col++) {
// Try all valid actions for this square. Is it empty?
const uint8_t loc = THE_COORDS(col, row);
- const uint8_t count = (COUNT_AT(loc) > 5) ? 5 : COUNT_AT(loc);
+ const uint8_t count = (COUNT_AT(loc) > board_size) ? board_size : COUNT_AT(loc);
// Only try moves after CPS
if (count && ((colours[loc] & 1) == current_colour) && ply>2) {
- // There are stones, can we move them in a given direction?
+ // There are stones, let's try moving them
// Pre-compute end-stops
uint8_t end_stops[4][2]; // (end, not_crush)
// UP DOWN LEFT RIGHT
- end_stops[0][0] = (4-row > count) ? count : 4-row;
+ end_stops[0][0] = (board_size - row - 1 > count) ? count : board_size - row - 1;
end_stops[1][0] = (row > count) ? count : row;
end_stops[2][0] = (col > count) ? count : col;
- end_stops[3][0] = (4-col > count) ? count : 4-col;
+ end_stops[3][0] = (board_size - col - 1 > count) ? count : board_size - col - 1;
const uint8_t cap_top = STONE_AT(loc) == STONE_CAPSTONE;
- for (uint8_t d = 0; d < 4; d++){
+ for (uint8_t d = 0; d < board_size-1; d++){
end_stops[d][1] = 1;
const uint8_t stop = end_stops[d][0];
end_stops[d][0] = 0;
@@ -242,12 +174,13 @@ negamax_cnn1986(const uint8_t cur_depth, float alpha, float beta,
}
}
- uint16_t colours_backup[5];
- uint8_t celldat_backup[5], drops[5]; // we only use 4, the
- // fifth is to skip a
- // bounds check at (*)
- // Back up the row of the board
- for (uint8_t y = 0; y < 5; y++) {
+ uint16_t colours_backup[board_size];
+ uint8_t celldat_backup[board_size], drops[board_size];
+ // we only ever need board_size-1 in drops actually, the
+ // last spot is to skip a bounds check at (*)
+
+ //Back up the rows of the board
+ for (uint8_t y = 0; y < board_size; y++) {
colours_backup[y] = colours[THE_COORDS(col, y)];
celldat_backup[y] = celldat[THE_COORDS(col, y)];
}
@@ -258,7 +191,7 @@ negamax_cnn1986(const uint8_t cur_depth, float alpha, float beta,
for (enum MOVE_DIRECTION dir = M_UP; dir <= M_RIGHT; dir++) {
// Back-up the column once we start looking horizontally
if (dir == M_LEFT) {
- for (uint8_t x = 0; x < 5; x++) {
+ for (uint8_t x = 0; x < board_size; x++) {
colours_backup[x] = colours[THE_COORDS(x, row)];
celldat_backup[x] = celldat[THE_COORDS(x, row)];
}
@@ -274,18 +207,20 @@ negamax_cnn1986(const uint8_t cur_depth, float alpha, float beta,
for (uint8_t steps = 1;
steps <= end_stops[dir][0] && steps <= num;
steps++) {
- gaps = 0x07 >> (4-steps); // 0b0000[0111] because 4-1=3
- // and 5-1=4
+ // TODO: Generalise to board_size!
+ gaps = 0x07 >> (board_size-steps-1);
+ // 0b0000[0111] because 4-1=3 and 5-1=4
do {
// Ensure legal move if we have to crush
- const uint8_t last_drop_check = (num > 1) ? (gaps & 1<<(num - 2)) : 1;
+ const uint8_t last_drop_check =
+ (num > 1) ? (gaps & 1<<(num - 2)) : 1;
if (end_stops[dir][1] || last_drop_check) {
// Translate to a drop sequence
drops[0] = 1; mask = 1; idx = 0;
for (uint8_t d = 0; d + 1 < num; d++) {
if (gaps & mask) {
idx++;
- drops[idx] = 1; // (*) we don't need to bounds check
+ drops[idx] = 1; // (*) no bounds check
} else {
drops[idx] += 1;
}
@@ -310,17 +245,17 @@ negamax_cnn1986(const uint8_t cur_depth, float alpha, float beta,
WIN_EVALUATE_OR_RECURSE({
// If we did update the optimal value, store
// this move
- generate_move(loc, dir, steps, drops, negamax_cnn1986_ptn);
+ generate_move(loc, dir, steps, drops, negamax_ptn);
},{
// Reset the board data after recursing or
// before returning
if (dir <= M_DOWN) {
- for (uint8_t y = 0; y < 5; y++) {
+ for (uint8_t y = 0; y < board_size; y++) {
colours[THE_COORDS(col, y)] = colours_backup[y];
celldat[THE_COORDS(col, y)] = celldat_backup[y];
}
} else {
- for (uint8_t x = 0; x < 5; x++) {
+ for (uint8_t x = 0; x < board_size; x++) {
colours[THE_COORDS(x, row)] = colours_backup[x];
celldat[THE_COORDS(x, row)] = celldat_backup[x];
}
@@ -350,7 +285,7 @@ negamax_cnn1986(const uint8_t cur_depth, float alpha, float beta,
celldat[loc] = NUM_INC | STONE_FLAT;
WIN_EVALUATE_OR_RECURSE({
// If we did update the optimal value, store
- generate_place(loc, STONE_FLAT, negamax_cnn1986_ptn);
+ generate_place(loc, STONE_FLAT, negamax_ptn);
},{
// Reset the state
celldat[loc] = 0;
@@ -364,7 +299,7 @@ negamax_cnn1986(const uint8_t cur_depth, float alpha, float beta,
colours[loc] = current_colour;
celldat[loc] = NUM_INC | STONE_STANDING;
WIN_EVALUATE_OR_RECURSE({
- generate_place(loc, STONE_STANDING, negamax_cnn1986_ptn);
+ generate_place(loc, STONE_STANDING, negamax_ptn);
},{
celldat[loc] = 0;
if (black) black_count++;
@@ -380,7 +315,7 @@ negamax_cnn1986(const uint8_t cur_depth, float alpha, float beta,
colours[loc] = current_colour;
celldat[loc] = NUM_INC | STONE_CAPSTONE;
WIN_EVALUATE_OR_RECURSE({
- generate_place(loc, STONE_CAPSTONE, negamax_cnn1986_ptn);
+ generate_place(loc, STONE_CAPSTONE, negamax_ptn);
},{
celldat[loc] = 0;
if (black) black_count |= 128;
@@ -388,24 +323,24 @@ negamax_cnn1986(const uint8_t cur_depth, float alpha, float beta,
});
}
}
- negamax_cnn1986_display_progress(cur_depth);
+ negamax_display_progress(cur_depth);
}
}
- // 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(colour*alpha);
- } else {
- // Impose the colour
- alpha *= colour;
+ // Insert into the cache
+ cnn1986_cache_insert(hash, alpha);
}
return alpha;
}
inline float
-negamax_cnn1986_generate(void) {
+negamax_generate(void) {
// We need to start with something outside of [-∞,∞] because those
// values are wins
const float safe_infty = infty + 1;
- return negamax_cnn1986(0, -safe_infty, safe_infty, (ply&1)?1.0:-1.0);
+
+ cnn1986_cache_init();
+ float result = negamax(0, -safe_infty, safe_infty, (ply&1)?1.0:-1.0);
+ cnn1986_cache_free();
+
+ return result;
}
diff --git a/include/negamax.h b/include/negamax.h
new file mode 100644
index 0000000..fbdf8da
--- /dev/null
+++ b/include/negamax.h
@@ -0,0 +1,19 @@
+#include <stdint.h>
+#include <tak.h>
+#include <xorshift64.h>
+#include <cnn1986.h>
+#include <cnn1986_treap_cache.h>
+
+extern const float infty;
+extern char negamax_ptn[9];
+extern uint8_t negamax_search_depth;
+extern inline void negamax_display_progress(const uint8_t);
+
+void negamax_init_size(void);
+uint64_t negamax_compute_zobrist(void);
+
+// Do negamax to depth negamax_search_depth and return PTN of best move
+// in negamax_ptn, along with its value as the return. The
+// negamax_display_progress function is called on every new square at
+// the top level.
+float negamax_generate(void);
diff --git a/include/negamax_cnn1986.h b/include/negamax_cnn1986.h
deleted file mode 100644
index fc0d5f2..0000000
--- a/include/negamax_cnn1986.h
+++ /dev/null
@@ -1,19 +0,0 @@
-#include <stdint.h>
-#include <tak.h>
-#include <cnn1986_treap_cache.h>
-#include "weights.h"
-
-extern const float infty;
-extern char negamax_cnn1986_ptn[9];
-extern uint8_t negamax_cnn1986_search_depth;
-extern uint8_t negamax_cnn1986_cache_threshold;
-extern inline void negamax_cnn1986_display_progress(const uint8_t);
-
-// Do negamax to depth ct1986_search_depth and return PTN of best move
-// in ct1986_ptn, along with its value as the return. The
-// ct1986_display_progress function is called on every new square at
-// the top level.
-float negamax_cnn1986_generate(void);
-
-// Internal utility function
-float cnn1986_evaluate_black_win(void);
diff --git a/include/xorshift64.c b/include/xorshift64.c
new file mode 100644
index 0000000..04d5cfe
--- /dev/null
+++ b/include/xorshift64.c
@@ -0,0 +1,3 @@
+#include "xorshift64.h"
+
+uint64_t xors = (uint64_t)0xFEEDCAFEF00DDDDD;
diff --git a/include/xorshift64.h b/include/xorshift64.h
new file mode 100644
index 0000000..a12a38d
--- /dev/null
+++ b/include/xorshift64.h
@@ -0,0 +1,18 @@
+#include <stdint.h>
+
+#ifndef XORSHIFT_H
+#define XORSHIFT_H
+
+extern uint64_t xors;
+
+#define XORSHIFT { \
+ xors ^= xors >> 12; \
+ xors ^= xors << 25; \
+ xors ^= xors >> 27; \
+ xors *= 0x2545F4914F6CDD1D; \
+ }
+
+#define RANDOM64 (xors)
+#define RANDOM32 ((uint32_t)xors)
+
+#endif
diff --git a/src/ct1986.c b/src/ct1986.c
index e440255..2b0ffb5 100644
--- a/src/ct1986.c
+++ b/src/ct1986.c
@@ -2,7 +2,7 @@
#include <string.h>
#include <tak.h>
-#include <negamax_cnn1986.h>
+#include <negamax.h>
#include <lcdlib.h>
static char *gamelog = 0;
@@ -83,11 +83,11 @@ new_game(uint8_t size) {
gamelog[0] = 0;
}
-// Set up output function for negamax_cnn1986
+// Set up output function for negamax
static uint8_t perc;
inline void
-negamax_cnn1986_display_progress(const uint8_t depth) {
+negamax_display_progress(const uint8_t depth) {
if (depth == 0) {
perc++;
lcd_printf_line(L_OVERWRITE, "Computing: %d%%", perc*4);
@@ -95,12 +95,12 @@ negamax_cnn1986_display_progress(const uint8_t depth) {
}
static int
-negamax_cnn1986_turn() {
+negamax_turn() {
// Prepare progress bar
lcd_put_line(L_SCROLL, "Computing: 0%");
// Run the minimax
perc = 0;
- float minimax = negamax_cnn1986_generate();
+ float minimax = negamax_generate();
// Failed to find a move?
if (minimax < -infty) {
lcd_printf_line(L_SCROLL, "%s concedes!",
@@ -109,8 +109,8 @@ negamax_cnn1986_turn() {
} else {
lcd_printf_line(L_SCROLL, "%s: %s",
(ply & 1) ? "Black" : "White",
- negamax_cnn1986_ptn);
- return handle_turn(negamax_cnn1986_ptn);
+ negamax_ptn);
+ return handle_turn(negamax_ptn);
}
}
@@ -125,9 +125,9 @@ input_is_not_turn(const char *line) {
case 'l': { do_game_log(); break; }
case 'n': { new_game(5); break; }
case 's': {
- negamax_cnn1986_search_depth = line[1] - '0';
+ negamax_search_depth = line[1] - '0';
lcd_printf_line(L_SCROLL, "Search depth: %d",
- negamax_cnn1986_search_depth);
+ negamax_search_depth);
break;
}
case 'B': { human = 1; new_game(5); break; }
@@ -145,10 +145,8 @@ main(int argc, char **argv) {
if (lcd_begin() != EXIT_SUCCESS)
return EXIT_FAILURE;
- cnn1986_max_num_cached = 500;
- negamax_cnn1986_search_depth = 3;
- negamax_cnn1986_cache_threshold = 2;
- negamax_cnn1986_search_depth = 3;
+ negamax_init_size();
+ negamax_search_depth = 3;
new_game(5);
@@ -176,7 +174,7 @@ main(int argc, char **argv) {
}
}
if (playing) {
- negamax_cnn1986_turn();
+ negamax_turn();
human = 0;
}
}
diff --git a/src/ctaklm.c b/src/ctaklm.c
index aaeddde..59e0e2e 100644
--- a/src/ctaklm.c
+++ b/src/ctaklm.c
@@ -3,7 +3,7 @@
#include <string.h>
#include <tak.h>
-#include <negamax_cnn1986.h>
+#include <negamax.h>
static const char *blk = "\033[41m", *wht = "\033[44m";
static const char *und = "\033[4m", *rst = "\033[0m";
@@ -234,8 +234,8 @@ handle_turn(char *line) {
static void
new_game(uint8_t size) {
reset_state(size);
- printf("New %dx%d game! negamax_cnn1986 at search depth %d.\n",
- size, size, negamax_cnn1986_search_depth);
+ printf("New %dx%d game! negamax at search depth %d.\n",
+ size, size, negamax_search_depth);
if (gamelog) gamelog = realloc(gamelog, sizeof(char));
else gamelog = malloc(sizeof(char));
gamelog[0] = 0;
@@ -296,9 +296,9 @@ load_ptn(const char* fn) {
static float sum_depth, num_check, progress;
-// Set up output function for negamax_cnn1986
+// Set up output function for negamax
inline void
-negamax_cnn1986_display_progress(const uint8_t depth) {
+negamax_display_progress(const uint8_t depth) {
sum_depth += depth;
num_check += 1;
if (depth == 0) {
@@ -310,13 +310,13 @@ negamax_cnn1986_display_progress(const uint8_t depth) {
}
static int
-negamax_cnn1986_turn(void) {
+negamax_turn(void) {
if (won == 0xFF) {
fputs("Computing: 0%", stdout);
fflush(stdout);
// Run the minimax
sum_depth = 0; num_check = 0; progress = 0;
- float minimax = negamax_cnn1986_generate();
+ float minimax = negamax_generate();
printf(" [%d]\n", cnn1986_num_cached);
// Failed to find a move?
if (minimax < -infty) {
@@ -324,11 +324,11 @@ negamax_cnn1986_turn(void) {
return EXIT_FAILURE;
} else {
printf("Result: %s (%.2f, %.1e, %.2f)\n",
- negamax_cnn1986_ptn,
+ negamax_ptn,
minimax*100.0,
num_check,
sum_depth/num_check);
- return handle_turn(negamax_cnn1986_ptn);
+ return handle_turn(negamax_ptn);
}
} else {
return EXIT_FAILURE;
@@ -358,12 +358,12 @@ info, load, log, new, play (b|w), self-play, square <col><row>, <PTN>.");
} else if (!strcmp(line,"new")) {
new_game(5);
} else if (!strcmp(line,"self-play")) {
- while (negamax_cnn1986_turn() == 0);
+ while (negamax_turn() == 0);
} else if (!strncmp(line,"depth",5)) {
if (strnlen(line,7) == 7 && line[6] >= '0' && line[6] <= '9') {
- negamax_cnn1986_search_depth = line[6] - '0';
+ negamax_search_depth = line[6] - '0';
printf("New search depth: %d.\n",
- negamax_cnn1986_search_depth);
+ negamax_search_depth);
} else {
puts("Usage: depth [0-9].");
}
@@ -418,17 +418,16 @@ main(int argc, char **argv) {
/*
* cnn1986_max_num_cached = 500;
- * negamax_cnn1986_search_depth = 3;
- * negamax_cnn1986_cache_threshold = 3;
+ * negamax_search_depth = 3;
+ * negamax_cache_threshold = 3;
* new_game(5);
*/
// Test harness
- negamax_cnn1986_cache_threshold = atoi(argv[1]);
- cnn1986_max_num_cached = atoi(argv[2]);
- negamax_cnn1986_search_depth = 4;
+ negamax_init_size();
+ negamax_search_depth = 5;
new_game(5);
- for (int k=0; k<8; k++) negamax_cnn1986_turn();
+ for (int k=0; k<8; k++) negamax_turn();
return 0;
// Test harness
@@ -456,12 +455,10 @@ main(int argc, char **argv) {
}
}
if (playing) {
- negamax_cnn1986_turn();
+ negamax_turn();
human = 0;
}
}
- cnn1986_cache_free();
-
return EXIT_SUCCESS;
}
generated by cgit v1.2.3 (git 2.46.0) at 2026-08-30 12:22:54 +0000