aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--Makefile4
-rw-r--r--include/cnn1986_cache.c51
-rw-r--r--include/cnn1986_cache.h11
-rw-r--r--include/cnn1986_treap_cache.h9
-rw-r--r--include/negamax.c72
-rw-r--r--include/negamax.h5
-rw-r--r--include/xorshift64.c2
-rw-r--r--include/xorshift64.h5
-rw-r--r--src/ctaklm.c16
9 files changed, 95 insertions, 80 deletions
diff --git a/Makefile b/Makefile
index 82b04c1..3ed8067 100644
--- a/Makefile
+++ b/Makefile
@@ -1,9 +1,9 @@
IDIR=include
DEFINES=-DDETERMINISTIC
-CFLAGS=-O3 -Wall -Wextra -Wpedantic -std=c99 -D_DEFAULT_SOURCE $(DEFINES) -I$(IDIR)
+CFLAGS=-g -Wall -Wextra -Wpedantic -std=c99 -D_DEFAULT_SOURCE $(DEFINES) -I$(IDIR)
LIBS=
-SRCS=include/tak.c include/xorshift64.c include/negamax.c include/weights.c include/cnn1986.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_cache.c
OBJS=$(SRCS:.c=.o)
BUILDROOT_DIR=buildroot-2020.11.1
diff --git a/include/cnn1986_cache.c b/include/cnn1986_cache.c
index d9545ac..692920a 100644
--- a/include/cnn1986_cache.c
+++ b/include/cnn1986_cache.c
@@ -4,9 +4,11 @@
#define DATA_COUNT_SHIFT (DATA_STONE_SHIFT+2)
#define COLOUR_MASK 0x3F // 0b00111111
-uint32_t cnn1986_num_cached, cnn1986_max_num_cached;
+uint32_t cnn1986_num_cached, cnn1986_max_num_cached = 1000000;
node_t *head = NULL, *tail = NULL;
+int cnn1986_cache_init(void) { return EXIT_SUCCESS; }
+
void cnn1986_cache_free(void) {
node_t *c = head, *n;
while (c) {
@@ -18,37 +20,22 @@ void cnn1986_cache_free(void) {
tail = NULL;
}
-int cnn1986_cache_seek(float *out_result) {
+int cnn1986_cache_seek(const uint64_t key[4],
+ float *out_result) {
node_t *c = head;
-
- if (c == NULL) return EXIT_FAILURE;
-
- uint8_t comp_data[25], fail;
- for (int k=0; k<25; k++) {
- comp_data[k] = (colours[k] & COLOUR_MASK)
- | (STONE_AT(k) << DATA_STONE_SHIFT)
- | (COUNT_AT(k) << DATA_COUNT_SHIFT);
- }
-
- // We've checked c = head already, so uncoditionally test it
- do {
- // Compare
- fail = 0;
- if (c->black_count == black_count && c->white_count == white_count) {
- for (int k=0; k<25; k++) {
- if (comp_data[k] != c->data[k]) {
- fail = 1;
- break;
- }
+ while (c != NULL) {
+ // Either seek next or move to front and return
+ uint8_t fail = 0;
+ for (int k=0; k<4; k++) {
+ if (c->key[k] != key[k]) {
+ fail = 1; break;
}
- } else { fail = 1; }
+ }
- // Either seek next or move to front and return
if (fail) {
c = c->next;
} else {
*out_result = c->result;
-
// Move to front
if (c != head) {
if (tail == c) tail=c->prev;
@@ -59,16 +46,14 @@ int cnn1986_cache_seek(float *out_result) {
head->prev = c;
head = c;
}
-
return EXIT_SUCCESS;
}
- } while (c);
-
+ }
// Failed to find it
return EXIT_FAILURE;
}
-int cnn1986_cache_insert(float in_result) {
+int cnn1986_cache_insert(const uint64_t key[4], float in_result) {
node_t *new = malloc(sizeof(node_t));
if (new == NULL) return EXIT_FAILURE;
// TODO: check errno
@@ -76,14 +61,8 @@ int cnn1986_cache_insert(float in_result) {
new->next = head;
if (head) head->prev = new;
head = new;
+ for (int k=0; k<4; k++) new->key[k] = key[k];
new->result = in_result;
- new->white_count = white_count;
- new->black_count = black_count;
- for (int k=0; k<25; k++) {
- new->data[k] = (colours[k] & COLOUR_MASK)
- | (STONE_AT(k) << DATA_STONE_SHIFT)
- | (COUNT_AT(k) << DATA_COUNT_SHIFT);
- }
if (cnn1986_num_cached == 0) tail = new;
cnn1986_num_cached++;
diff --git a/include/cnn1986_cache.h b/include/cnn1986_cache.h
index 8d82ee9..14a894d 100644
--- a/include/cnn1986_cache.h
+++ b/include/cnn1986_cache.h
@@ -1,18 +1,19 @@
#include <stdlib.h>
#include <tak.h>
-#define MAX_NUM_CACHED 123
-
extern uint32_t cnn1986_num_cached, cnn1986_max_num_cached;
typedef struct node_s {
struct node_s *next, *prev;
- uint16_t data[25], white_count, black_count;
+ uint64_t key[4];
float result;
} node_t;
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[4],
+ float *out_result);
+
+int cnn1986_cache_insert(const uint64_t key[4],
+ const float in_result);
diff --git a/include/cnn1986_treap_cache.h b/include/cnn1986_treap_cache.h
index 92208b2..20b2fbc 100644
--- a/include/cnn1986_treap_cache.h
+++ b/include/cnn1986_treap_cache.h
@@ -8,5 +8,10 @@ extern uint32_t cnn1986_num_cached;
int cnn1986_cache_init(void);
void cnn1986_cache_free(void);
-int cnn1986_cache_seek(const uint64_t key, float *out_result);
-int cnn1986_cache_insert(const uint64_t key, const float in_result);
+int cnn1986_cache_seek(const uint64_t key_lo,
+ const uint64_t key_hi,
+ float *out_result);
+
+int cnn1986_cache_insert(const uint64_t key_lo,
+ const uint64_t key_hi,
+ const float in_result);
diff --git a/include/negamax.c b/include/negamax.c
index e1c2991..3e57165 100644
--- a/include/negamax.c
+++ b/include/negamax.c
@@ -8,44 +8,62 @@ const float infty = 3.0;
char negamax_ptn[9];
uint8_t negamax_search_depth = 3;
+uint32_t cache_fails = 0;
+
// ===================================================================
// Zobrist hashing
// ===================================================================
-uint64_t *zobrist = NULL;
+uint64_t *zobrist[4];
+uint64_t *zobrist_empty[4];
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 k=0; k<board_size*board_size*16*3*2; k++) {
- XORSHIFT64;
- zobrist[k] = RANDOM64;
+ for (int k=0; k<4; k++) {
+ if (zobrist[k] != NULL) return EXIT_FAILURE;
+ if (zobrist_empty[k] != NULL) return EXIT_FAILURE;
}
+
+ for (int j=0; j<4; j++) {
+ zobrist[j] = malloc(sizeof(uint64_t)*board_size*board_size*15*3*2);
+ zobrist_empty[j] = malloc(sizeof(uint64_t)*board_size*board_size);
+ // TODO: trap errno
+ for (int k=0; k<board_size*board_size*15*3*2; k++) {
+ XORSHIFT64;
+ zobrist[j][k] = RANDOM64;
+ }
+ for (int k=0; k<board_size*board_size; k++) {
+ XORSHIFT64;
+ zobrist_empty[j][k] = RANDOM64;
+ }
+ }
+
return EXIT_SUCCESS;
}
static void negamax_free_zobrist(void) {
- if (zobrist != NULL) {
- free(zobrist);
- zobrist = NULL;
+ for (int k=0; k<4; k++) {
+ if (zobrist[k] != NULL) {
+ free(zobrist[k]);
+ zobrist[k] = NULL;
+ }
}
}
-uint64_t negamax_compute_zobrist(void) {
- uint64_t result = 0;
+void negamax_compute_zobrist(uint64_t *hash) {
+ for (int k=0; k<4; k++) hash[k] = 0;
for (uint8_t l=0; l<board_size*board_size; l++) {
const uint8_t count = COUNT_AT(l);
if (count) {
+ const enum STONE_VARIANT s = STONE_AT(l);
colour_stack_t c = colours[l];
- enum STONE_VARIANT s = STONE_AT(l);
for (uint8_t h=0; h<count; h++) {
- result ^= zobrist[l*16*2*3 + h*3*2 + (c&1)*3 + s];
- s = STONE_FLAT;
+ for (int k=0; k<4; k++) {
+ hash[k] ^= zobrist[k][l*16*3*2 + h*3*2 + (c&1)*3 + s];
+ }
c >>= 1;
}
}
}
- return result;
}
// ===================================================================
@@ -126,9 +144,15 @@ static enum WIN_TYPE w;
float negamax(const uint8_t cur_depth, float alpha, float beta,
const float colour) {
- uint64_t hash = negamax_compute_zobrist();
+ uint64_t hash[4];
+ negamax_compute_zobrist(hash);
- if (cnn1986_cache_seek(hash, &alpha) == EXIT_FAILURE) {
+ float stored_alpha;
+ int lookup = cnn1986_cache_seek(hash, &stored_alpha);
+
+ /*
+ * if (cnn1986_cache_seek(hash, &alpha) == EXIT_FAILURE) {
+ */
const uint8_t black = (ply & 1),
material = (black) ? black_count : white_count,
flat = material & 127,
@@ -323,10 +347,17 @@ float negamax(const uint8_t cur_depth, float alpha, float beta,
}
negamax_display_progress(cur_depth);
}
- }
+ /*
+ * }
+ */
// Insert into the cache
- cnn1986_cache_insert(hash, alpha);
}
+ if (lookup == EXIT_FAILURE)
+ cnn1986_cache_insert(hash, alpha);
+ else {
+ if (stored_alpha != alpha)
+ cache_fails++;
+ }
return alpha;
}
@@ -336,6 +367,9 @@ negamax_generate(void) {
// values are wins
const float safe_infty = infty + 1;
+
+ cache_fails=0;
+
cnn1986_cache_init();
float result = negamax(0, -safe_infty, safe_infty, (ply&1)?1.0:-1.0);
cnn1986_cache_free();
diff --git a/include/negamax.h b/include/negamax.h
index d00780d..52a8fd2 100644
--- a/include/negamax.h
+++ b/include/negamax.h
@@ -2,15 +2,16 @@
#include <tak.h>
#include <xorshift64.h>
#include <cnn1986.h>
-#include <cnn1986_treap_cache.h>
+#include <cnn1986_cache.h>
extern const float infty;
extern char negamax_ptn[9];
extern uint8_t negamax_search_depth;
+extern uint32_t cache_fails;
extern inline void negamax_display_progress(const uint8_t);
void negamax_init(const uint8_t new_board_size);
-uint64_t negamax_compute_zobrist(void);
+void negamax_compute_zobrist(uint64_t hash[4]);
// Do negamax to depth negamax_search_depth and return PTN of best move
// in negamax_ptn, along with its value as the return. The
diff --git a/include/xorshift64.c b/include/xorshift64.c
index 04d5cfe..516218a 100644
--- a/include/xorshift64.c
+++ b/include/xorshift64.c
@@ -1,3 +1,3 @@
#include "xorshift64.h"
-uint64_t xors = (uint64_t)0xFEEDCAFEF00DDDDD;
+uint64_t xors = (uint64_t)0xBF58476D1CE4E5B9;
diff --git a/include/xorshift64.h b/include/xorshift64.h
index ee41abc..62a0a4e 100644
--- a/include/xorshift64.h
+++ b/include/xorshift64.h
@@ -9,10 +9,9 @@ extern uint64_t xors;
xors ^= xors >> 12; \
xors ^= xors << 25; \
xors ^= xors >> 27; \
- xors *= 0x2545F4914F6CDD1D; \
}
-#define RANDOM64 (xors)
-#define RANDOM32 ((uint32_t)xors)
+#define RANDOM64 (xors*0x2545F4914F6CDD1D)
+#define RANDOM32 ((uint32_t)RANDOM64)
#endif
diff --git a/src/ctaklm.c b/src/ctaklm.c
index f7a58d9..2232bc4 100644
--- a/src/ctaklm.c
+++ b/src/ctaklm.c
@@ -317,7 +317,7 @@ negamax_turn(void) {
// Run the minimax
sum_depth = 0; num_check = 0; progress = 0;
float minimax = negamax_generate();
- printf(" [%d]\n", cnn1986_num_cached);
+ printf(" [%d] <%d>\n", cnn1986_num_cached, cache_fails);
// Failed to find a move?
if (minimax < -infty) {
puts("Opponent failed to find a move!");
@@ -416,19 +416,15 @@ main(int argc, char **argv) {
(void)(argc);
(void)(argv);
- /*
- * cnn1986_max_num_cached = 500;
- * negamax_search_depth = 3;
- * negamax_cache_threshold = 3;
- * new_game(5);
- */
-
// Test harness
negamax_search_depth = 5;
new_game(5);
negamax_init(5);
- for (int k=0; k<2; k++) negamax_turn();
- return 0;
+ /*
+ * load_ptn("data/0.ptn");
+ * for (int k=0; k<2; k++) negamax_turn();
+ * return 0;
+ */
// Test harness
char *line = NULL;
generated by cgit v1.3.1 (git 2.54.0) at 2026-08-30 18:51:05 +0000