aboutsummaryrefslogtreecommitdiff
path: root/include
diff options
context:
space:
mode:
Diffstat (limited to 'include')
-rw-r--r--include/negamax.c68
-rw-r--r--include/negamax.h2
-rw-r--r--include/zobrist.c75
3 files changed, 62 insertions, 83 deletions
diff --git a/include/negamax.c b/include/negamax.c
index 061b629..b51961d 100644
--- a/include/negamax.c
+++ b/include/negamax.c
@@ -8,74 +8,15 @@ const float infty = 3.0;
char negamax_ptn[9];
uint8_t negamax_search_depth = 3;
-static uint64_t *zobrist[15];
-
// ===================================================================
// Helpers
// ===================================================================
-static void
-zobrist_free(void);
-
-static int
-zobrist_init(void);
-
-static uint64_t
-zobrist_compute(void);
-
static float
negamax(const uint8_t cur_depth, float alpha, float beta,
const float colour);
// ===================================================================
-// Zobrist hashing
-// ===================================================================
-
-static uint64_t
-zobrist_compute(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);
- 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;
-}
-
-static int
-zobrist_init(void) {
- for (int k=0; k<15; k++) {
- if (zobrist[k] != NULL) return EXIT_FAILURE;
- }
-
- 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;
- }
- }
-
- return EXIT_SUCCESS;
-}
-
-static void
-zobrist_free(void) {
- for (int k=0; k<15; k++) {
- if (zobrist[k] != NULL) {
- free(zobrist[k]);
- zobrist[k] = NULL;
- }
- }
-}
-
-// ===================================================================
// α-β negamax using the cnn1986 evaluation function and transposition
// tables using Zobrist hasing and a treap
// ===================================================================
@@ -119,7 +60,7 @@ negamax(const uint8_t cur_depth, float alpha, float beta,
tt_entry_t *entry = tt_seek(hash);
// CAUTION: >= breaks search stability
- if (entry != NULL && entry->depth == cur_depth) {
+ if (entry != NULL && entry->depth >= cur_depth) {
if (entry->flag == TT_EXACT) {
return entry->value;
} else if (entry->flag == TT_LOWERBOUND && entry->value > alpha) {
@@ -145,6 +86,13 @@ negamax(const uint8_t cur_depth, float alpha, float beta,
for (action_node_t *node=list->head; node!=NULL; node=node->next) {
action_take(node->action);
+
+ {
+ if (zobrist_apply(node->action, hash) != zobrist_compute()) {
+ printf("! %s\n", (GET_TYPE(node->action)==A_PLACE)?"A_PLACE":"A_MOVE");
+ }
+ }
+
// Compute the value of the node
float node_value;
if (ply >= 2*board_size - 2 && (w = check_win()) < 0xFF) {
diff --git a/include/negamax.h b/include/negamax.h
index 43995d1..bba5af9 100644
--- a/include/negamax.h
+++ b/include/negamax.h
@@ -6,6 +6,7 @@
#include <xorshift64.h>
#include <cnn1986.h>
#include <tt_treap.h>
+#include <zobrist.h>
extern const float infty;
extern char negamax_ptn[9];
@@ -25,3 +26,4 @@ negamax_free(void);
// negamax_display_progress function is called on every new square at
// the top level.
float negamax_generate(void);
+extern uint8_t yes;
diff --git a/include/zobrist.c b/include/zobrist.c
index 8eeb758..6208339 100644
--- a/include/zobrist.c
+++ b/include/zobrist.c
@@ -60,8 +60,9 @@ zobrist_apply(const action_t action, uint64_t hash) {
const enum A_TYPE type = GET_TYPE(action);
const int8_t loc = GET_LOC(action);
if (type == A_PLACE) {
+ enum COLOUR c = (current_colour == C_BLACK) ? C_WHITE : C_BLACK;
hash ^= zobrist[0][loc*(2*3+1)
- +current_colour*3
+ +c*3
+GET_DATA0(action)];
} else {
const uint8_t gaps = GET_DATA0(action) & 0x7F,
@@ -70,35 +71,63 @@ zobrist_apply(const action_t action, uint64_t hash) {
dir = GET_DATA1(action) >> 4;
const int8_t delta = move_deltas[dir];
- // TODO: adapt this
int8_t steps = 1;
- uint8_t gap_bit = 1, total = 1;
- for (int8_t d = 1; d < num; d++, total++, gap_bit <<= 1) {
+ uint8_t gap_bit = 1, num_dropped = 1, total = COUNT_AT(loc);
+ for (int8_t d = 1; d < num; d++, num_dropped++, gap_bit <<= 1) {
if (gaps & gap_bit) {
- colours[loc] <<= total;
- colours[loc] |= colours[loc+steps*delta] & ((1 << total) - 1);
- colours[loc+steps*delta] >>= total;
- celldat[loc] += total*NUM_INC;
- celldat[loc+steps*delta] -= total*NUM_INC;
- total = 0;
+ const int8_t target = loc+steps*delta, th = COUNT_AT(target);
+ // Stash these stones to offset for the height at source
+ total += num_dropped;
+ // Apply XOR for stones at source and current target
+ uint8_t point = 1;
+ for (int k = 0, ht = th-1, hs = total-1; k < num_dropped;
+ k++, ht--, hs--, point<<=1) {
+ hash ^= zobrist[ht][target*(2*3+1)
+ +(point & colours[target])*3
+ +STONE_FLAT];
+ hash ^= zobrist[hs][loc*(2*3+1)
+ +(point & colours[target])*3
+ +STONE_FLAT];
+ }
+ // Continue processing gap sequence
+ num_dropped = 0;
steps++;
}
}
- colours[loc] <<= total;
- colours[loc] |= colours[loc+steps*delta] & ((1 << total) - 1);
- colours[loc+steps*delta] >>= total;
-
- celldat[loc] += total*NUM_INC;
- // celldat[loc] &= CLR_STONE; is not necessary, as STONE_FLAT == 0
- celldat[loc] |= STONE_AT(loc+steps*delta);
- celldat[loc+steps*delta] -= total*NUM_INC;
- celldat[loc+steps*delta] &= CLR_STONE;
+ total += num_dropped;
+ const int8_t target = loc+steps*delta, th = COUNT_AT(target);
+ const enum STONE_VARIANT top_stone = STONE_AT(target);
+ // Stash these stones to offset for the height at source
+ // Apply XOR for stones at source and end target. After this
+ // source will be correct, but we must account for crush @ target.
+ uint8_t point = 1;
+ for (int k = 0, ht = th-1, hs = total-1; k < num_dropped;
+ k++, ht--, hs--, point<<=1) {
+ if (k == 0) {
+ hash ^= zobrist[ht][target*(2*3+1)
+ +(point & colours[target])*3
+ +top_stone];
+ hash ^= zobrist[hs][loc*(2*3+1)
+ +(point & colours[target])*3
+ +top_stone];
+ } else {
+ hash ^= zobrist[ht][target*(2*3+1)
+ +(point & colours[target])*3
+ +STONE_FLAT];
+ hash ^= zobrist[hs][loc*(2*3+1)
+ +(point & colours[target])*3
+ +STONE_FLAT];
+ }
+ }
+ // Correct for crush
if (crush) {
- celldat[loc+steps*delta] |= STONE_STANDING;
- } else {
- celldat[loc+steps*delta] |= STONE_FLAT; // should be optimised out
+ hash ^= zobrist[th-1][target*(2*3+1)
+ +(colours[target] & 1)*3
+ +STONE_FLAT];
+ hash ^= zobrist[th-1][target*(2*3+1)
+ +(colours[target] & 1)*3
+ +STONE_STANDING];
}
-
}
return hash;
}
generated by cgit v1.3.1 (git 2.54.0) at 2026-08-30 16:15:29 +0000