aboutsummaryrefslogtreecommitdiff
path: root/include
diff options
context:
space:
mode:
Diffstat (limited to 'include')
-rw-r--r--include/cnn1986_cache.c98
-rw-r--r--include/cnn1986_cache.h18
-rw-r--r--include/lcdlib.c7
-rw-r--r--include/negamax_cnn1986.c370
-rw-r--r--include/negamax_cnn1986.h4
5 files changed, 290 insertions, 207 deletions
diff --git a/include/cnn1986_cache.c b/include/cnn1986_cache.c
new file mode 100644
index 0000000..d9545ac
--- /dev/null
+++ b/include/cnn1986_cache.c
@@ -0,0 +1,98 @@
+#include "cnn1986_cache.h"
+
+#define DATA_STONE_SHIFT 6
+#define DATA_COUNT_SHIFT (DATA_STONE_SHIFT+2)
+#define COLOUR_MASK 0x3F // 0b00111111
+
+uint32_t cnn1986_num_cached, cnn1986_max_num_cached;
+node_t *head = NULL, *tail = NULL;
+
+void cnn1986_cache_free(void) {
+ node_t *c = head, *n;
+ while (c) {
+ n = c->next;
+ free(c);
+ c = n;
+ }
+ head = NULL;
+ tail = NULL;
+}
+
+int cnn1986_cache_seek(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;
+ }
+ }
+ } 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;
+ if (c->next) c->next->prev = c->prev;
+ c->prev->next = c->next;
+ c->prev = NULL;
+ c->next = head;
+ head->prev = c;
+ head = c;
+ }
+
+ return EXIT_SUCCESS;
+ }
+ } while (c);
+
+ // Failed to find it
+ return EXIT_FAILURE;
+}
+
+int cnn1986_cache_insert(float in_result) {
+ node_t *new = malloc(sizeof(node_t));
+ if (new == NULL) return EXIT_FAILURE;
+ // TODO: check errno
+ new->prev = NULL;
+ new->next = head;
+ if (head) head->prev = new;
+ head = new;
+ 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++;
+
+ if (cnn1986_num_cached > cnn1986_max_num_cached) {
+ tail = tail->prev;
+ free(tail->next);
+ tail->next = NULL;
+ cnn1986_num_cached--;
+ }
+
+ return EXIT_SUCCESS;
+}
diff --git a/include/cnn1986_cache.h b/include/cnn1986_cache.h
new file mode 100644
index 0000000..8d82ee9
--- /dev/null
+++ b/include/cnn1986_cache.h
@@ -0,0 +1,18 @@
+#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;
+ 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);
diff --git a/include/lcdlib.c b/include/lcdlib.c
index ea47062..0933b2c 100644
--- a/include/lcdlib.c
+++ b/include/lcdlib.c
@@ -1,15 +1,10 @@
#include "lcdlib.h"
-// ===================================================================
-// Globals
-// ===================================================================
-
static char previous_lines[LCD_HEIGHT][LCD_WIDTH+1];
+static const char* esc = "\x1B[L";
static FILE *lcd = NULL;
static int line_idx;
-static const char* esc = "\x1B[L";
-
int
lcd_begin(void) {
lcd = fopen("/dev/lcd", "w");
diff --git a/include/negamax_cnn1986.c b/include/negamax_cnn1986.c
index 3aa282f..b9d618d 100644
--- a/include/negamax_cnn1986.c
+++ b/include/negamax_cnn1986.c
@@ -7,6 +7,7 @@
const float infty = 3.0;
char negamax_cnn1986_ptn[9];
uint8_t negamax_cnn1986_search_depth = 3;
+uint8_t negamax_cnn1986_cache_threshold = 3;
// ===================================================================
// Implementation of a small convolutional neural network
@@ -192,234 +193,203 @@ 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) {
- 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 < 5; row++) {
- for (uint8_t col = 0; col < 5; 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);
- // 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?
+ if (cnn1986_cache_seek(&alpha)) {
+ 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));
- // 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[1][0] = (row > count) ? count : row;
- end_stops[2][0] = (col > count) ? count : col;
- end_stops[3][0] = (4-col > count) ? count : 4-col;
- const uint8_t cap_top = STONE_AT(loc) == STONE_CAPSTONE;
- for (uint8_t d = 0; d < 4; 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]++;
+ // Step across the board
+ for (uint8_t row = 0; row < 5; row++) {
+ for (uint8_t col = 0; col < 5; 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);
+ // 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?
+
+ // 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[1][0] = (row > count) ? count : row;
+ end_stops[2][0] = (col > count) ? count : col;
+ end_stops[3][0] = (4-col > count) ? count : 4-col;
+ const uint8_t cap_top = STONE_AT(loc) == STONE_CAPSTONE;
+ for (uint8_t d = 0; d < 4; 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;
}
- break;
- } else if (stone == STONE_CAPSTONE) {
- break;
+ end_stops[d][0]++;
}
- end_stops[d][0]++;
}
- }
- 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++) {
- colours_backup[y] = colours[THE_COORDS(col, y)];
- celldat_backup[y] = celldat[THE_COORDS(col, y)];
- }
+ 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++) {
+ 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 < 5; 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 < 5; 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++) {
- gaps = 0x07 >> (4-steps); // 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; // (*) we don't need to bounds check
- } else {
- drops[idx] += 1;
+ /*
+ * 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++) {
+ gaps = 0x07 >> (4-steps); // 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; // (*) we don't need to bounds check
+ } else {
+ drops[idx] += 1;
+ }
+ mask <<= 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);
- }
- // 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;
+ // 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_cnn1986_ptn);
- },{
- // Reset the board data after recursing or
- // before returning
- if (dir <= M_DOWN) {
- for (uint8_t y = 0; y < 5; 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++) {
- colours[THE_COORDS(x, row)] = colours_backup[x];
- celldat[THE_COORDS(x, row)] = celldat_backup[x];
+ // 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_cnn1986_ptn);
+ },{
+ // Reset the board data after recursing or
+ // before returning
+ if (dir <= M_DOWN) {
+ for (uint8_t y = 0; y < 5; 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++) {
+ 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))));
+ });
+ }
+ /*
+ * 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
+ } 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;
- /*
- * w = 0xFF;
- * if (ply >= 2*5 - 3) w = check_win();
- * if (w < 0xFF) {
- * /\* Somebody won, assign weights accordingly. Note in particular
- * that draws are only worth ∞/2 ;)
- * *\/
- * if (w == WIN_ROAD_BLACK || w == WIN_FLAT_BLACK)
- * val = infty;
- * else if (w == WIN_DRAW) val = 0;
- * else val = -infty;
- * val *= colour;
- * } else if (cur_depth == negamax_cnn1986_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);
- * previous_ply();
- * }
- * celldat[loc] = 0;
- * if (black) black_count++;
- * else white_count++;
- * /\* Prune *\/
- * if (val >= beta) return beta;
- * /\* Update the optimal value, which alpha carries *\/
- * if (val > alpha) {
- * alpha = val;
- * if (cur_depth == 0) {
- * generate_place(loc, STONE_FLAT, negamax_cnn1986_ptn);
- * /\* Did we win? *\/
- * if (alpha >= infty && w < 0xFF)
- * return alpha;
- * };
- * }
- */
- WIN_EVALUATE_OR_RECURSE({
- // If we did update the optimal value, store
- generate_place(loc, STONE_FLAT, negamax_cnn1986_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 (flat) {
+ // Generate the placement
if (black) black_count--;
else white_count--;
colours[loc] = current_colour;
- celldat[loc] = NUM_INC | STONE_STANDING;
+ celldat[loc] = NUM_INC | STONE_FLAT;
WIN_EVALUATE_OR_RECURSE({
- generate_place(loc, STONE_STANDING, negamax_cnn1986_ptn);
+ // If we did update the optimal value, store
+ generate_place(loc, STONE_FLAT, negamax_cnn1986_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_cnn1986_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_cnn1986_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_cnn1986_ptn);
+ },{
+ celldat[loc] = 0;
+ if (black) black_count |= 128;
+ else white_count |= 128;
+ });
+ }
}
+ negamax_cnn1986_display_progress(cur_depth);
}
- negamax_cnn1986_display_progress(cur_depth);
}
+ // Insert into the cache if we're not too deep
+ if (cur_depth < negamax_cnn1986_cache_threshold)
+ cnn1986_cache_insert(alpha);
}
return alpha;
}
diff --git a/include/negamax_cnn1986.h b/include/negamax_cnn1986.h
index 799ca4c..3002837 100644
--- a/include/negamax_cnn1986.h
+++ b/include/negamax_cnn1986.h
@@ -1,10 +1,12 @@
#include <stdint.h>
-#include "tak.h"
+#include <tak.h>
+#include <cnn1986_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
generated by cgit v1.2.3 (git 2.46.0) at 2026-08-30 14:39:36 +0000