aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--Makefile4
-rw-r--r--include/cnn1986.c10
-rw-r--r--include/cnn1986_cache.c2
-rw-r--r--include/cnn1986_treap_cache.h17
-rw-r--r--include/negamax.c432
-rw-r--r--include/negamax.h5
-rw-r--r--include/tak.c3
-rw-r--r--include/tt_treap.c (renamed from include/cnn1986_treap_cache.c)80
-rw-r--r--include/tt_treap.h40
-rw-r--r--src/ctaklm.c10
10 files changed, 306 insertions, 297 deletions
diff --git a/Makefile b/Makefile
index 3ed8067..0e7e1fa 100644
--- a/Makefile
+++ b/Makefile
@@ -1,9 +1,9 @@
IDIR=include
DEFINES=-DDETERMINISTIC
-CFLAGS=-g -Wall -Wextra -Wpedantic -std=c99 -D_DEFAULT_SOURCE $(DEFINES) -I$(IDIR)
+CFLAGS=-O3 -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_cache.c
+SRCS=include/tak.c include/xorshift64.c include/negamax.c include/weights.c include/cnn1986.c include/lcdlib.c include/tt_treap.c
OBJS=$(SRCS:.c=.o)
BUILDROOT_DIR=buildroot-2020.11.1
diff --git a/include/cnn1986.c b/include/cnn1986.c
index 039dddd..17d4e84 100644
--- a/include/cnn1986.c
+++ b/include/cnn1986.c
@@ -100,10 +100,12 @@ float cnn1986_evaluate_black_win(void) {
}
// 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
+/*
+ * #ifndef DETERMINISTIC
+ * RANDF;
+ * output += fudge.f;
+ * #endif
+ */
if (output > 1.0) {
return 1.0;
}
diff --git a/include/cnn1986_cache.c b/include/cnn1986_cache.c
index 692920a..303ef57 100644
--- a/include/cnn1986_cache.c
+++ b/include/cnn1986_cache.c
@@ -32,7 +32,7 @@ int cnn1986_cache_seek(const uint64_t key[4],
}
}
- if (fail) {
+ if (fail == 1) {
c = c->next;
} else {
*out_result = c->result;
diff --git a/include/cnn1986_treap_cache.h b/include/cnn1986_treap_cache.h
deleted file mode 100644
index 20b2fbc..0000000
--- a/include/cnn1986_treap_cache.h
+++ /dev/null
@@ -1,17 +0,0 @@
-#include <stdlib.h>
-#include <stdint.h>
-#include <tak.h>
-#include <xorshift64.h>
-
-extern uint32_t cnn1986_num_cached;
-
-int cnn1986_cache_init(void);
-void cnn1986_cache_free(void);
-
-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 3e57165..3e3a209 100644
--- a/include/negamax.c
+++ b/include/negamax.c
@@ -14,34 +14,27 @@ uint32_t cache_fails = 0;
// Zobrist hashing
// ===================================================================
-uint64_t *zobrist[4];
-uint64_t *zobrist_empty[4];
+uint64_t *zobrist[15];
static int negamax_init_zobrist(void) {
- for (int k=0; k<4; k++) {
+
+ for (int k=0; k<15; 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++) {
+ 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;
}
- 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) {
- for (int k=0; k<4; k++) {
+ for (int k=0; k<15; k++) {
if (zobrist[k] != NULL) {
free(zobrist[k]);
zobrist[k] = NULL;
@@ -49,21 +42,20 @@ static void negamax_free_zobrist(void) {
}
}
-void negamax_compute_zobrist(uint64_t *hash) {
- for (int k=0; k<4; k++) hash[k] = 0;
+uint64_t negamax_compute_zobrist(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);
- if (count) {
- const enum STONE_VARIANT s = STONE_AT(l);
- colour_stack_t c = colours[l];
- for (uint8_t h=0; h<count; h++) {
- for (int k=0; k<4; k++) {
- hash[k] ^= zobrist[k][l*16*3*2 + h*3*2 + (c&1)*3 + s];
- }
+ 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;
}
// ===================================================================
@@ -144,220 +136,229 @@ static enum WIN_TYPE w;
float negamax(const uint8_t cur_depth, float alpha, float beta,
const float colour) {
- uint64_t hash[4];
- negamax_compute_zobrist(hash);
-
- 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,
- cap = (ply > 2 && (material & 128)),
- standing = (ply > 2 && (material & 127));
-
- // Step across the board
- 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) > board_size) ? board_size : COUNT_AT(loc);
- // Only try moves after CPS
- if (count && ((colours[loc] & 1) == current_colour) && ply>2) {
- // 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] = (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] = (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 < board_size-1; d++){
- end_stops[d][1] = 1;
- const uint8_t stop = end_stops[d][0];
- end_stops[d][0] = 0;
- for (uint8_t k = 1; k <= stop; k++) {
- const uint8_t stone = STONE_AT(loc+k*deltas[d]);
- if (stone == STONE_STANDING) {
- if (cap_top) {
- end_stops[d][1] = 0;
- end_stops[d][0]++;
- }
- break;
- } else if (stone == STONE_CAPSTONE) {
- break;
+ uint64_t hash = negamax_compute_zobrist();
+ tt_entry_t *entry = tt_seek(hash);
+ const float alpha_orig = alpha;
+
+ if (entry != NULL && entry -> depth <= cur_depth) {
+ if (entry->flag == TT_EXACT) {
+ return entry->value;
+ } else if (entry->flag == TT_LOWERBOUND) {
+ if (entry->value > alpha) alpha = entry->value;
+ } else if (entry->flag == TT_UPPERBOUND) {
+ if (entry->value < beta) beta = entry->value;
+ }
+ if (alpha >= beta) return entry->value;
+ }
+
+ const uint8_t black = (ply & 1),
+ material = (black) ? black_count : white_count,
+ flat = material & 127,
+ cap = (ply > 2 && (material & 128)),
+ standing = (ply > 2 && (material & 127));
+
+ // Step across the board
+ 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) > board_size) ? board_size : COUNT_AT(loc);
+ // Only try moves after CPS
+ if (count && ((colours[loc] & 1) == current_colour) && ply>2) {
+ // 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] = (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] = (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 < board_size-1; d++){
+ end_stops[d][1] = 1;
+ const uint8_t stop = end_stops[d][0];
+ end_stops[d][0] = 0;
+ for (uint8_t k = 1; k <= stop; k++) {
+ const uint8_t stone = STONE_AT(loc+k*deltas[d]);
+ if (stone == STONE_STANDING) {
+ if (cap_top) {
+ end_stops[d][1] = 0;
+ end_stops[d][0]++;
}
- end_stops[d][0]++;
+ break;
+ } else if (stone == STONE_CAPSTONE) {
+ break;
}
+ end_stops[d][0]++;
}
+ }
- 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 (*)
+ 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)];
- }
+ //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)];
+ }
- // I'm not a huge fan of looping through enums, but it's
- // better than manually unrolling this. Sufficiently smart
- // compilers?
- 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 < board_size; x++) {
- colours_backup[x] = colours[THE_COORDS(x, row)];
- celldat_backup[x] = celldat[THE_COORDS(x, row)];
- }
+ // I'm not a huge fan of looping through enums, but it's
+ // better than manually unrolling this. Sufficiently smart
+ // compilers?
+ 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 < board_size; x++) {
+ colours_backup[x] = colours[THE_COORDS(x, row)];
+ celldat_backup[x] = celldat[THE_COORDS(x, row)];
}
- /*
- * We don't do anything terribly efficient here just try
- * all the ordered partitions of num ∈ {1 … end_stop}, and
- * skip the partition if it calls for multiple stones at
- * the end with a crush.
- */
- uint8_t gaps, t, idx, mask;
- for (uint8_t num = 1; num <= count; num++) {
- for (uint8_t steps = 1;
- steps <= end_stops[dir][0] && steps <= num;
- steps++) {
- // 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;
- 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; // (*) no bounds check
- } else {
- drops[idx] += 1;
- }
- mask <<= 1;
- }
- // Do it, and manually check for win if it's valid
- uint8_t j = num;
- for (uint8_t k = 0; k < steps; k++) {
- j -= drops[k];
- push_stones(loc+(k+1)*deltas[dir],
- drops[k],
- (colours[loc] >> j) & (0xFFFF >> (0x10 - drops[k])),
- (k == steps - 1) ? STONE_AT(loc) : STONE_FLAT);
+ }
+ /*
+ * We don't do anything terribly efficient here just try
+ * all the ordered partitions of num ∈ {1 … end_stop}, and
+ * skip the partition if it calls for multiple stones at
+ * the end with a crush.
+ */
+ uint8_t gaps, t, idx, mask;
+ for (uint8_t num = 1; num <= count; num++) {
+ for (uint8_t steps = 1;
+ steps <= end_stops[dir][0] && steps <= num;
+ steps++) {
+ // 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;
+ 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; // (*) no bounds check
+ } else {
+ drops[idx] += 1;
}
- // Then we drop them from the source
- colours[loc] >>= num;
- const uint8_t dec_count = celldat[loc] - (num << NUM_SHIFT);
- celldat[loc] = dec_count & NUM_MASK;
-
- // First check for wins, if we're at the bottom
- // evaluate, otherwise recurse
- WIN_EVALUATE_OR_RECURSE({
- // If we did update the optimal value, store
- // this move
- 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 < 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 < board_size; x++) {
- colours[THE_COORDS(x, row)] = colours_backup[x];
- celldat[THE_COORDS(x, row)] = celldat_backup[x];
- }
- }
- });
+ mask <<= 1;
}
- /*
- * With thanks to
- * https://graphics.stanford.edu/~seander/bithacks.html#NextBitPermutation
- * we have the following magic to generate the next
- * permutation of steps-many set bits
- */
- t = (gaps | (gaps - 1));
- gaps = (t + 1) | (((~t & -~t) - 1) >> (__builtin_ctz(gaps) + 1));
- } while (gaps && (gaps + 1 <= (1<<(num-1))));
- }
+ // Do it, and manually check for win if it's valid
+ uint8_t j = num;
+ for (uint8_t k = 0; k < steps; k++) {
+ j -= drops[k];
+ push_stones(loc+(k+1)*deltas[dir],
+ drops[k],
+ (colours[loc] >> j) & (0xFFFF >> (0x10 - drops[k])),
+ (k == steps - 1) ? STONE_AT(loc) : STONE_FLAT);
+ }
+ // Then we drop them from the source
+ colours[loc] >>= num;
+ const uint8_t dec_count = celldat[loc] - (num << NUM_SHIFT);
+ celldat[loc] = dec_count & NUM_MASK;
+
+ // First check for wins, if we're at the bottom
+ // evaluate, otherwise recurse
+ WIN_EVALUATE_OR_RECURSE({
+ // If we did update the optimal value, store
+ // this move
+ 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 < 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 < board_size; x++) {
+ colours[THE_COORDS(x, row)] = colours_backup[x];
+ celldat[THE_COORDS(x, row)] = celldat_backup[x];
+ }
+ }
+ });
+ }
+ /*
+ * With thanks to
+ * https://graphics.stanford.edu/~seander/bithacks.html#NextBitPermutation
+ * we have the following magic to generate the next
+ * permutation of steps-many set bits
+ */
+ t = (gaps | (gaps - 1));
+ gaps = (t + 1) | (((~t & -~t) - 1) >> (__builtin_ctz(gaps) + 1));
+ } while (gaps && (gaps + 1 <= (1<<(num-1))));
}
}
- } else if (material && count == 0) {
- // Empty square, try placements
-
- if (flat) {
- // Generate the placement
+ }
+ } else if (material && count == 0) {
+ // Empty square, try placements
+
+ if (flat) {
+ // Generate the placement
+ if (black) black_count--;
+ else white_count--;
+ colours[loc] = current_colour;
+ celldat[loc] = NUM_INC | STONE_FLAT;
+ WIN_EVALUATE_OR_RECURSE({
+ // If we did update the optimal value, store
+ generate_place(loc, STONE_FLAT, negamax_ptn);
+ },{
+ // Reset the state
+ celldat[loc] = 0;
+ if (black) black_count++;
+ else white_count++;
+ });
+ // Do the same for walls, can't happen without flats
+ if (standing) {
if (black) black_count--;
else white_count--;
colours[loc] = current_colour;
- celldat[loc] = NUM_INC | STONE_FLAT;
+ celldat[loc] = NUM_INC | STONE_STANDING;
WIN_EVALUATE_OR_RECURSE({
- // If we did update the optimal value, store
- generate_place(loc, STONE_FLAT, negamax_ptn);
+ generate_place(loc, STONE_STANDING, negamax_ptn);
},{
- // Reset the state
celldat[loc] = 0;
if (black) black_count++;
else white_count++;
});
- // Do the same for walls, can't happen without flats
- if (standing) {
- if (black) black_count--;
- else white_count--;
- colours[loc] = current_colour;
- celldat[loc] = NUM_INC | STONE_STANDING;
- WIN_EVALUATE_OR_RECURSE({
- generate_place(loc, STONE_STANDING, negamax_ptn);
- },{
- celldat[loc] = 0;
- if (black) black_count++;
- else white_count++;
- });
- }
}
+ }
- // and for caps
- if (cap) {
- if (black) black_count &= 127;
- else white_count &= 127;
- colours[loc] = current_colour;
- celldat[loc] = NUM_INC | STONE_CAPSTONE;
- WIN_EVALUATE_OR_RECURSE({
- generate_place(loc, STONE_CAPSTONE, negamax_ptn);
- },{
- celldat[loc] = 0;
- if (black) black_count |= 128;
- else white_count |= 128;
- });
- }
+ // and for caps
+ if (cap) {
+ if (black) black_count &= 127;
+ else white_count &= 127;
+ colours[loc] = current_colour;
+ celldat[loc] = NUM_INC | STONE_CAPSTONE;
+ WIN_EVALUATE_OR_RECURSE({
+ generate_place(loc, STONE_CAPSTONE, negamax_ptn);
+ },{
+ celldat[loc] = 0;
+ if (black) black_count |= 128;
+ else white_count |= 128;
+ });
}
- negamax_display_progress(cur_depth);
}
- /*
- * }
- */
- // Insert into the cache
- }
- if (lookup == EXIT_FAILURE)
- cnn1986_cache_insert(hash, alpha);
- else {
- if (stored_alpha != alpha)
- cache_fails++;
+ negamax_display_progress(cur_depth);
}
+ }
+
+ enum TT_FLAG flag = TT_EXACT;
+ if (alpha <= alpha_orig) flag = TT_UPPERBOUND;
+ else if (alpha >= beta) flag = TT_UPPERBOUND;
+
+ if (entry == NULL) {
+ tt_insert(hash, flag, cur_depth, alpha);
+ } else {
+ entry->flag = flag;
+ entry->value = alpha;
+ entry->depth = cur_depth;
+ }
+
return alpha;
}
@@ -367,12 +368,9 @@ negamax_generate(void) {
// values are wins
const float safe_infty = infty + 1;
-
- cache_fails=0;
-
- cnn1986_cache_init();
+ tt_init();
float result = negamax(0, -safe_infty, safe_infty, (ply&1)?1.0:-1.0);
- cnn1986_cache_free();
+ tt_free();
return result;
}
diff --git a/include/negamax.h b/include/negamax.h
index 52a8fd2..f3a0a6c 100644
--- a/include/negamax.h
+++ b/include/negamax.h
@@ -2,16 +2,15 @@
#include <tak.h>
#include <xorshift64.h>
#include <cnn1986.h>
-#include <cnn1986_cache.h>
+#include <tt_treap.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);
-void negamax_compute_zobrist(uint64_t hash[4]);
+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
diff --git a/include/tak.c b/include/tak.c
index 964225e..6d07ea0 100644
--- a/include/tak.c
+++ b/include/tak.c
@@ -329,6 +329,9 @@ check_win(void) {
enum WIN_TYPE rb, rw;
rb = check_road_colour(C_BLACK);
rw = check_road_colour(C_WHITE);
+ for (uint8_t k=0; k<NUM_SQUARES; k++)
+ celldat[k] &= NOT_DFS_MASK;
+
if (rb == WIN_ROAD_BLACK && rw == WIN_ROAD_WHITE) {
return (ply & 1) ? rb : rw; // Dragons
diff --git a/include/cnn1986_treap_cache.c b/include/tt_treap.c
index 941ec1c..b48ffd4 100644
--- a/include/cnn1986_treap_cache.c
+++ b/include/tt_treap.c
@@ -1,72 +1,56 @@
-#include "cnn1986_treap_cache.h"
-
-// ===================================================================
-// Types
-// ===================================================================
-
-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;
- */
- float result;
-} * TreapNode;
+#include "tt_treap.h"
// ===================================================================
// Variables
// ===================================================================
-uint32_t cnn1986_num_cached;
-static TreapNode root;
+uint32_t tt_num_cached;
+static tt_entry_t * root;
// ===================================================================
// Helper declarations
// ===================================================================
-void recurse_tree(const TreapNode n);
-TreapNode new_treap_node(const float in_result, const uint64_t key);
-void bubble_up(const TreapNode n);
+void recurse_tree(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);
+void bubble_up(tt_entry_t *n);
// ===================================================================
// Exported functions
// ===================================================================
-int cnn1986_cache_init(void) {
+int tt_init(void) {
root = NULL;
- cnn1986_num_cached = 0;
+ tt_num_cached = 0;
return EXIT_SUCCESS;
}
-void cnn1986_cache_free(void) {
+void tt_free(void) {
recurse_tree(root);
return;
}
-int cnn1986_cache_seek(const uint64_t key, float *out_result) {
- if (root == NULL) return EXIT_FAILURE;
- TreapNode n = root;
+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;
}
- if (n == NULL) return EXIT_FAILURE;
- *out_result = n->result;
- return EXIT_SUCCESS;
+ return n;
}
-int cnn1986_cache_insert(const uint64_t key, const float in_result) {
+int tt_insert(const uint64_t key, const enum TT_FLAG flag,
+ const uint8_t depth, const float value) {
+ tt_entry_t *m = new_treap_node(key, flag, depth, value);
if (root == NULL) {
- root = new_treap_node(in_result, key);
- cnn1986_num_cached = 1;
+ root = m;
+ tt_num_cached = 1;
return EXIT_SUCCESS;
}
- TreapNode s = root, n = root,
- m = new_treap_node(in_result, key);
+ tt_entry_t *s = root, *n = root;
// Find the correct position by doing a BST traversal
while (n!=NULL) {
s = n;
@@ -79,7 +63,7 @@ int cnn1986_cache_insert(const uint64_t key, const float in_result) {
m->parent = s;
// Now bubble upward to satisfy the heap property
bubble_up(m);
- cnn1986_num_cached++;
+ tt_num_cached++;
return EXIT_SUCCESS;
}
@@ -87,28 +71,30 @@ int cnn1986_cache_insert(const uint64_t key, const float in_result) {
// Helper implementations
// ===================================================================
-void recurse_tree(TreapNode n) {
+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);
}
-TreapNode new_treap_node(const float in_result, const uint64_t key) {
- TreapNode n = malloc(sizeof(struct treap_node_s));
+tt_entry_t *new_treap_node(const uint64_t key, const enum TT_FLAG flag,
+ const uint8_t depth, const float value) {
+ 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;
XORSHIFT64; n->weight = RANDOM32;
- // Set value
- n->result = in_result;
return n;
}
-void rotate_left(TreapNode n) {
- TreapNode a = n->parent, b = a->left, c = n->left;
+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
@@ -129,8 +115,8 @@ void rotate_left(TreapNode n) {
a->right = c; if (c!=NULL) c->parent = a;
}
-void rotate_right(TreapNode n) {
- TreapNode a = n->parent, b = a->right, d = n->right;
+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
@@ -152,7 +138,7 @@ void rotate_right(TreapNode n) {
}
//This preserves the BST quality of the treap
-void bubble_up(TreapNode n) {
+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
diff --git a/include/tt_treap.h b/include/tt_treap.h
new file mode 100644
index 0000000..793d536
--- /dev/null
+++ b/include/tt_treap.h
@@ -0,0 +1,40 @@
+#include <stdlib.h>
+#include <stdint.h>
+#include <xorshift64.h>
+
+#ifndef TT_TREAP_H
+#define TT_TREAP_H
+
+// ===================================================================
+// Types
+// ===================================================================
+
+enum TT_FLAG { TT_EXACT, TT_LOWERBOUND, TT_UPPERBOUND };
+
+typedef struct treap_node_s {
+ uint64_t key;
+ uint32_t weight;
+ struct treap_node_s *left, *right, *parent;
+ enum TT_FLAG flag;
+ uint8_t depth;
+ float value;
+} tt_entry_t;
+
+// ===================================================================
+// Globals
+// ===================================================================
+
+extern uint32_t tt_num_cached;
+
+// ===================================================================
+// Methods
+// ===================================================================
+
+int tt_init(void);
+void tt_free(void);
+
+tt_entry_t *tt_seek(uint64_t key);
+int tt_insert(const uint64_t key, const enum TT_FLAG flag,
+ const uint8_t depth, const float value);
+
+#endif
diff --git a/src/ctaklm.c b/src/ctaklm.c
index 2232bc4..e80dd82 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] <%d>\n", cnn1986_num_cached, cache_fails);
+ printf(" [%d]\n", tt_num_cached);
// Failed to find a move?
if (minimax < -infty) {
puts("Opponent failed to find a move!");
@@ -420,11 +420,9 @@ main(int argc, char **argv) {
negamax_search_depth = 5;
new_game(5);
negamax_init(5);
- /*
- * load_ptn("data/0.ptn");
- * 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.2.3 (git 2.46.0) at 2026-08-30 09:52:07 +0000