aboutsummaryrefslogtreecommitdiff
path: root/include
diff options
context:
space:
mode:
Diffstat (limited to 'include')
-rw-r--r--include/action_list.c262
-rw-r--r--include/action_list.h21
-rw-r--r--include/cnn1986_cache.c77
-rw-r--r--include/cnn1986_cache.h19
-rw-r--r--include/negamax.c92
-rw-r--r--include/negamax.h2
6 files changed, 335 insertions, 138 deletions
diff --git a/include/action_list.c b/include/action_list.c
new file mode 100644
index 0000000..198cd08
--- /dev/null
+++ b/include/action_list.c
@@ -0,0 +1,262 @@
+#include "action_list.h"
+
+// ===================================================================
+// Helper method declarations
+// ===================================================================
+
+static inline action_list_t *
+action_list_prepend(action_list_t *list, const enum A_TYPE type,
+ const uint8_t loc, const uint8_t data0,
+ const uint8_t data1);
+
+static inline void 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);
+
+// ===================================================================
+// Exported method implementations
+// ===================================================================
+
+void action_list_free(action_list_t *list) {
+ action_list_t *n = NULL;
+ while (list) {
+ n = list->next;
+ free(list);
+ list = n;
+ }
+}
+
+// Keep track of move offsets
+static int8_t deltas[4];
+
+void action_list_init(const uint8_t new_board_size) {
+ board_size = new_board_size;
+ deltas[0] = +board_size;
+ deltas[1] = -board_size;
+ deltas[2] = -1;
+ deltas[3] = +1;
+}
+
+action_list_t *action_list_generate(void) {
+
+ action_list_t *result = NULL;
+
+ 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++) {
+ // We'll need these at various points, the location of this
+ // square and the maximum number of stones we could pick up
+ 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)
+
+ // These are upper bounds, not counting walls and such. 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;
+
+ // Now we check for caps and walls
+ 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;
+ }
+ end_stops[d][0]++;
+ }
+ }
+ /*
+ * For each direction, generate all possible ordered integer
+ * partitions of 1 ≤ num ≤ count whose number of summands is
+ * exactly 1 ≤ summands ≤ min(end_stops[dir], num) -- we write
+ * summands as steps
+ */
+ for (enum MOVE_DIRECTION dir = M_UP; dir <= M_RIGHT; dir++) {
+ 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 {
+ /*
+ * We skip the partition if it calls for multiple stones at
+ * the end with a crush.
+ */
+ const uint8_t last_drop_check =
+ (num > 1) ? (gaps & 1<<(num - 2)) : 1;
+ if (end_stops[dir][1] || last_drop_check)
+ result = action_list_prepend(result, A_MOVE, loc, (dir<<4) | num, gaps);
+ /*
+ * 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, generate placements
+ if (flat) {
+ result = action_list_prepend(result, A_PLACE, loc, STONE_FLAT, 0);
+ if (standing)
+ result = action_list_prepend(result, A_PLACE, loc, STONE_STANDING, 0);
+ }
+ if (cap)
+ result = action_list_prepend(result, A_PLACE, loc, STONE_CAPSTONE, 0);
+ }
+ }
+ }
+ return result;
+}
+
+void action_take(action_list_t *action) {
+ const uint8_t loc = action->loc;
+ if (action->type == A_PLACE) {
+ const uint8_t black = (ply&1);
+ switch (action->data0) {
+ STONE_FLAT: {
+ if (black) black_count--;
+ else white_count--;
+ colours[loc] = current_colour;
+ celldat[loc] = NUM_INC | STONE_FLAT;
+ break;
+ }
+ STONE_STANDING: {
+ if (black) black_count--;
+ else white_count--;
+ colours[loc] = current_colour;
+ celldat[loc] = NUM_INC | STONE_STANDING;
+ break;
+ }
+ default: {
+ if (black) black_count &= 127;
+ else white_count &= 127;
+ colours[loc] = current_colour;
+ celldat[loc] = NUM_INC | STONE_CAPSTONE;
+ break;
+ }
+ }
+ } else {
+ uint8_t drops[board_size]; // we only ever need board_size-1 in
+ // drops actually, the last spot is to
+ // skip a bounds check at (*) later
+
+ const uint8_t gaps = action->data0,
+ num = action->data1 & 0x0F, // unpack
+ dir = action->data1 & 0xF0;
+ uint8_t steps, mask;
+ // Translate to a drop sequence
+ drops[0] = 1; mask = 1; steps = 0;
+ for (uint8_t d = 0; d + 1 < num; d++) {
+ if (gaps & mask) {
+ steps++;
+ drops[steps] = 1; // (*) no bounds check
+ } else {
+ drops[steps] += 1;
+ }
+ mask <<= 1;
+ }
+ // Push stones onto subesquent stack
+ 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);
+ }
+ // Drop them from the source
+ colours[loc] >>= num;
+ const uint8_t dec_count = celldat[loc] - (num << NUM_SHIFT);
+ celldat[loc] = dec_count & NUM_MASK;
+ }
+ // Always
+ next_ply();
+};
+
+void action_undo(action_list_t *action) {
+ const uint8_t loc = action->loc;
+ if (action->type == A_PLACE) {
+ const uint8_t black = (ply&1);
+ celldat[loc] = 0;
+ if (action->data0 == STONE_CAPSTONE) {
+ if (black) black_count |= 128;
+ else white_count |= 128;
+ } else {
+ if (black) black_count++;
+ else white_count++;
+ }
+ } else {
+ // TODO ???
+ }
+ previous_ply();
+};
+
+// ===================================================================
+// Helper method implementations
+// ===================================================================
+
+static inline action_list_t *
+action_list_prepend(action_list_t *list, const enum A_TYPE type,
+ const uint8_t loc, const uint8_t data0,
+ const uint8_t data1) {
+ action_list_t *new = malloc(sizeof(action_list_t));
+ // TODO: trap errno
+ new->loc = loc;
+ new->next = list;
+ new->data0 = data0;
+ new->data1 = data1;
+ return new;
+}
+
+static inline void
+previous_ply(void) {
+ if (ply>0) ply--;
+ if (ply == 1) {
+ current_colour = C_WHITE;
+ } else {
+ if (current_colour == C_BLACK) current_colour = C_WHITE;
+ else current_colour = C_BLACK;
+ }
+}
+
+static inline 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);
+}
diff --git a/include/action_list.h b/include/action_list.h
new file mode 100644
index 0000000..3670114
--- /dev/null
+++ b/include/action_list.h
@@ -0,0 +1,21 @@
+#include <stdlib.h>
+#include <stdint.h>
+
+#include <tak.h>
+
+enum A_TYPE { A_PLACE, A_MOVE };
+
+typedef struct action_list_s {
+ struct action_list_s *next;
+ enum A_TYPE type;
+ uint8_t loc;
+ uint8_t data0;
+ uint8_t data1;
+} action_list_t;
+
+void action_list_init(const uint8_t new_board_size);
+void action_list_free(action_list_t *list);
+action_list_t *action_list_generate(void);
+
+void action_take(action_list_t *action);
+void action_undo(action_list_t *action);
diff --git a/include/cnn1986_cache.c b/include/cnn1986_cache.c
deleted file mode 100644
index 303ef57..0000000
--- a/include/cnn1986_cache.c
+++ /dev/null
@@ -1,77 +0,0 @@
-#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 = 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) {
- n = c->next;
- free(c);
- c = n;
- }
- head = NULL;
- tail = NULL;
-}
-
-int cnn1986_cache_seek(const uint64_t key[4],
- float *out_result) {
- node_t *c = head;
- 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;
- }
- }
-
- if (fail == 1) {
- 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;
- }
- }
- // Failed to find it
- return EXIT_FAILURE;
-}
-
-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
- new->prev = NULL;
- 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;
- 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
deleted file mode 100644
index 14a894d..0000000
--- a/include/cnn1986_cache.h
+++ /dev/null
@@ -1,19 +0,0 @@
-#include <stdlib.h>
-#include <tak.h>
-
-extern uint32_t cnn1986_num_cached, cnn1986_max_num_cached;
-
-typedef struct node_s {
- struct node_s *next, *prev;
- uint64_t key[4];
- float result;
-} node_t;
-
-int cnn1986_cache_init(void);
-void cnn1986_cache_free(void);
-
-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/negamax.c b/include/negamax.c
index 3e3a209..fd8c7ac 100644
--- a/include/negamax.c
+++ b/include/negamax.c
@@ -95,7 +95,6 @@ static void push_stones(const int8_t location,
| ((celldat[location] + ((count << NUM_SHIFT))) & NUM_MASK);
}
-static float val;
static enum WIN_TYPE w;
#define WIN_EVALUATE_OR_RECURSE(store,reset) { \
@@ -104,53 +103,57 @@ static enum WIN_TYPE w;
if (w < 0xFF) { \
/* Somebody won, assign weights accordingly. */ \
if (w == WIN_ROAD_BLACK || w == WIN_FLAT_BLACK) { \
- val = colour*infty; \
+ value = colour*infty; \
/* Always take the win */ \
- if (cur_depth == 0 && val > 0) { \
+ if (value > 0) { \
{ reset }; \
- { store }; \
- return infty; \
+ if (cur_depth == negamax_search_depth) { store }; \
+ goto prune; \
} \
/* Fix draw value to be completely neutral */ \
- } else if (w == WIN_DRAW) val = 0; \
- else val = -colour*infty; \
- } else if (cur_depth == negamax_search_depth) { \
+ } else if (w == WIN_DRAW) value = 0; \
+ else value = -colour*infty; \
+ } if (cur_depth == 0) { \
/* We're at the bottom, evaluate */ \
- val = colour * cnn1986_evaluate_black_win(); \
+ value = fmax(value, colour * cnn1986_evaluate_black_win()); \
} else { \
/* We're not at the bottom, recurse first */ \
next_ply(); \
- val = -negamax(cur_depth + 1, -beta, -alpha, -colour); \
+ value = fmax(value, -negamax(cur_depth - 1, -beta, -alpha, -colour)); \
previous_ply(); \
} \
{ reset }; \
- /* Prune */ \
- if (val >= beta) return beta; \
/* Update the optimal value, which alpha carries */ \
- if (val > alpha) { \
- alpha = val; \
- if (cur_depth == 0) { store }; \
+ if (value > alpha) { \
+ alpha = value; \
+ if (cur_depth == negamax_search_depth) { store }; \
+ /* Prune */ \
+ if (alpha >= beta) goto prune; \
} \
}
float negamax(const uint8_t cur_depth, float alpha, float beta,
const float colour) {
- 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;
- }
+ /*
+ * 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) {
+ * alpha = fmax(alpha, entry->value);
+ * } else if (entry->flag == TT_UPPERBOUND) {
+ * beta = fmin(beta, entry->value);
+ * }
+ * if (alpha >= beta) return entry->value;
+ * }
+ * enum TT_FLAG flag;
+ */
+ float value = -infty;
const uint8_t black = (ply & 1),
material = (black) ? black_count : white_count,
flat = material & 127,
@@ -347,19 +350,22 @@ float negamax(const uint8_t cur_depth, float alpha, float beta,
}
}
- 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;
- }
+ prune:
+ /*
+ * flag = TT_EXACT;
+ * if (value <= alpha_orig) flag = TT_UPPERBOUND;
+ * else if (value >= beta) flag = TT_UPPERBOUND;
+ *
+ * if (entry == NULL) {
+ * tt_insert(hash, flag, cur_depth, value);
+ * } else {
+ * entry->flag = flag;
+ * entry->value = value;
+ * entry->depth = cur_depth;
+ * }
+ */
- return alpha;
+ return value;
}
inline float
@@ -369,7 +375,9 @@ negamax_generate(void) {
const float safe_infty = infty + 1;
tt_init();
- float result = negamax(0, -safe_infty, safe_infty, (ply&1)?1.0:-1.0);
+ float result = negamax(negamax_search_depth,
+ -safe_infty, safe_infty,
+ (ply&1)?1.0:-1.0);
tt_free();
return result;
diff --git a/include/negamax.h b/include/negamax.h
index f3a0a6c..1cfebdd 100644
--- a/include/negamax.h
+++ b/include/negamax.h
@@ -1,4 +1,6 @@
#include <stdint.h>
+#include <math.h>
+
#include <tak.h>
#include <xorshift64.h>
#include <cnn1986.h>
generated by cgit v1.3.1 (git 2.54.0) at 2026-08-30 16:41:31 +0000