From 6b48baaf6b67cc7364d5945eb6d9b25ea9683bd9 Mon Sep 17 00:00:00 2001 From: tslil clingman Date: Tue, 26 Jan 2021 22:39:28 -0500 Subject: Somehting along these lines, i'm tired --- include/zobrist.c | 104 ++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 104 insertions(+) create mode 100644 include/zobrist.c (limited to 'include/zobrist.c') diff --git a/include/zobrist.c b/include/zobrist.c new file mode 100644 index 0000000..8eeb758 --- /dev/null +++ b/include/zobrist.c @@ -0,0 +1,104 @@ +#include "zobrist.h" + +// =================================================================== +// Globals +// =================================================================== + +static uint64_t *zobrist[15]; + +// =================================================================== +// Helpers +// =================================================================== + + +// =================================================================== +// Exported method implementations +// =================================================================== + +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>= 1) + hash ^= zobrist[h][l*(2*3+1)+(c&1)*3+s]; + } + return hash; +} + +uint64_t +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) { + hash ^= zobrist[0][loc*(2*3+1) + +current_colour*3 + +GET_DATA0(action)]; + } else { + const uint8_t gaps = GET_DATA0(action) & 0x7F, + crush = GET_DATA0(action) & 0x80, + num = GET_DATA1(action) & 0x0F, + 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) { + 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; + 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; + if (crush) { + celldat[loc+steps*delta] |= STONE_STANDING; + } else { + celldat[loc+steps*delta] |= STONE_FLAT; // should be optimised out + } + + } + return hash; +} -- cgit v1.3.1 From 8f15c1131342376ab3de2c6ce50d1ca5f20ec32a Mon Sep 17 00:00:00 2001 From: tslil clingman Date: Tue, 26 Jan 2021 23:54:46 -0500 Subject: I don't have the presence of mind to debug this right now --- include/negamax.c | 68 ++++++------------------------------------------- include/negamax.h | 2 ++ include/zobrist.c | 75 ++++++++++++++++++++++++++++++++++++++----------------- 3 files changed, 62 insertions(+), 83 deletions(-) (limited to 'include/zobrist.c') diff --git a/include/negamax.c b/include/negamax.c index 061b629..b51961d 100644 --- a/include/negamax.c +++ b/include/negamax.c @@ -8,73 +8,14 @@ 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>= 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= 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 #include #include +#include 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; } -- cgit v1.3.1 From b5b337d4044a8e64956b8a2309739353f9ce339e Mon Sep 17 00:00:00 2001 From: tslil clingman Date: Thu, 28 Jan 2021 12:01:42 -0500 Subject: It would appear that any function call whatsoever is slower :/ For now we'll stay with directly recomputing it at each non-terminal node --- include/actions.c | 43 +++++++++++------------ include/actions.h | 20 ++++++----- include/negamax.c | 6 ---- include/zobrist.c | 103 ++++++------------------------------------------------ include/zobrist.h | 3 -- 5 files changed, 42 insertions(+), 133 deletions(-) (limited to 'include/zobrist.c') diff --git a/include/actions.c b/include/actions.c index 96264d0..5085330 100644 --- a/include/actions.c +++ b/include/actions.c @@ -187,10 +187,10 @@ action_list_t *action_list_generate(void) { } void action_take(const action_t action) { - const int8_t loc = GET_LOC(action); - if (GET_TYPE(action) == A_PLACE) { + const int8_t loc = A_GET_LOC(action); + if (A_GET_TYPE(action) == A_PLACE) { const uint8_t black = (current_colour == C_BLACK); - switch (GET_DATA0(action)) { + switch (A_GET_DATA0(action)) { case STONE_FLAT: { if (black) black_count--; else white_count--; @@ -217,9 +217,9 @@ void action_take(const action_t action) { // not interested in whether we crushed, it will work out by // anyway because we overwrite the top stone type. See (*) later // for when we do need to know. - const uint8_t gaps = GET_DATA0(action) & 0x7F, - num = GET_DATA1(action) & 0x0F, // unpack - dir = GET_DATA1(action) >> 4; + const uint8_t gaps = A_GET_DATA0(action) & 0x7F, + num = A_GET_DATA1(action) & 0x0F, // unpack + dir = A_GET_DATA1(action) >> 4; int8_t delta = move_deltas[dir]; // Use the Kernighan method to count the set bits @@ -266,11 +266,11 @@ void action_undo(const action_t action) { // Previous ply inline_prev_ply(); - const int8_t loc = GET_LOC(action); - if (GET_TYPE(action) == A_PLACE) { + const int8_t loc = A_GET_LOC(action); + if (A_GET_TYPE(action) == A_PLACE) { const uint8_t black = (current_colour == C_BLACK); celldat[loc] = 0; - if (GET_DATA0(action) == STONE_CAPSTONE) { + if (A_GET_DATA0(action) == STONE_CAPSTONE) { if (black) black_count |= 0x80; else white_count |= 0x80; } else { @@ -280,10 +280,10 @@ void action_undo(const action_t action) { } else { // See action_take for comments, this is the time reversal, but // there is one caveat -- undoing a crush! (*) - const uint8_t gaps = GET_DATA0(action) & 0x7F, - crush = GET_DATA0(action) & 0x80, - num = GET_DATA1(action) & 0x0F, - dir = GET_DATA1(action) >> 4; + const uint8_t gaps = A_GET_DATA0(action) & 0x7F, + crush = A_GET_DATA0(action) & 0x80, + num = A_GET_DATA1(action) & 0x0F, + dir = A_GET_DATA1(action) >> 4; const int8_t delta = move_deltas[dir]; int8_t steps = 1; @@ -317,13 +317,13 @@ void action_undo(const action_t action) { } void action_to_ptn(const action_t action, char* out_ptn) { - const int8_t loc = GET_LOC(action); - if (GET_TYPE(action) == A_PLACE) { - generate_place(loc, GET_DATA0(action), out_ptn); + const int8_t loc = A_GET_LOC(action); + if (A_GET_TYPE(action) == A_PLACE) { + generate_place(loc, A_GET_DATA0(action), out_ptn); } else { - const uint8_t gaps = GET_DATA0(action) & 0x7F, - num = GET_DATA1(action) & 0x0F, // unpack - dir = GET_DATA1(action) >> 4; + const uint8_t gaps = A_GET_DATA0(action) & 0x7F, + num = A_GET_DATA1(action) & 0x0F, // unpack + dir = A_GET_DATA1(action) >> 4; uint8_t drops[board_size]; // we only ever need board_size-1 in // drops actually, the last spot is to @@ -356,10 +356,7 @@ list_append(action_list_t *list, const enum A_TYPE type, // TODO: trap errno new->next = NULL; - new->action = (type << TYPE_SHIFT) - | (loc << LOC_SHIFT) - | (data0 << DATA0_SHIFT) - | data1; + new->action = A_BUILD(type, loc, data0, data1); if (list->length) { list->tail->next = new; diff --git a/include/actions.h b/include/actions.h index d331284..ced0315 100644 --- a/include/actions.h +++ b/include/actions.h @@ -10,14 +10,18 @@ enum A_TYPE { A_PLACE, A_MOVE }; typedef uint32_t action_t; -#define TYPE_SHIFT 24 -#define LOC_SHIFT 16 -#define DATA0_SHIFT 8 - -#define GET_TYPE(a) (enum A_TYPE)((a)>>TYPE_SHIFT) -#define GET_LOC(a) (int8_t)(((a)>>LOC_SHIFT) & 0xFF) -#define GET_DATA0(a) (uint8_t)(((a)>>DATA0_SHIFT) & 0xFF) -#define GET_DATA1(a) (uint8_t)((a) & 0xFF) +#define A_TYPE_SHIFT 24 +#define A_LOC_SHIFT 16 +#define A_DATA0_SHIFT 8 + +#define A_GET_TYPE(a) (enum A_TYPE)((a)>>A_TYPE_SHIFT) +#define A_GET_LOC(a) (int8_t)(((a)>>A_LOC_SHIFT) & 0xFF) +#define A_GET_DATA0(a) (uint8_t)(((a)>>A_DATA0_SHIFT) & 0xFF) +#define A_GET_DATA1(a) (uint8_t)((a) & 0xFF) +#define A_BUILD(type,loc,data0,data1) ((type) << A_TYPE_SHIFT \ + | (loc) << A_LOC_SHIFT \ + | (data0) << A_DATA0_SHIFT \ + | (data1)) typedef struct action_node_s { struct action_node_s *next; diff --git a/include/negamax.c b/include/negamax.c index b51961d..cfe2643 100644 --- a/include/negamax.c +++ b/include/negamax.c @@ -87,12 +87,6 @@ negamax(const uint8_t cur_depth, float alpha, float beta, 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/zobrist.c b/include/zobrist.c index 6208339..feff5fa 100644 --- a/include/zobrist.c +++ b/include/zobrist.c @@ -4,7 +4,7 @@ // Globals // =================================================================== -static uint64_t *zobrist[15]; +static uint64_t *zobrist; // =================================================================== // Helpers @@ -17,16 +17,12 @@ static uint64_t *zobrist[15]; int zobrist_init(void) { - for (int k=0; k<15; k++) { - if (zobrist[k] != NULL) return EXIT_FAILURE; - } + if (zobrist != 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>= 1) - hash ^= zobrist[h][l*(2*3+1)+(c&1)*3+s]; - } - return hash; -} - -uint64_t -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) - +c*3 - +GET_DATA0(action)]; - } else { - const uint8_t gaps = GET_DATA0(action) & 0x7F, - crush = GET_DATA0(action) & 0x80, - num = GET_DATA1(action) & 0x0F, - dir = GET_DATA1(action) >> 4; - const int8_t delta = move_deltas[dir]; - - int8_t steps = 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) { - 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++; - } - } - 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) { - 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]; - } + hash ^= zobrist[l*(15*2*3)+h*2*3+(c&1)*3+s]; } return hash; } diff --git a/include/zobrist.h b/include/zobrist.h index 4e760ca..cfc2941 100644 --- a/include/zobrist.h +++ b/include/zobrist.h @@ -10,6 +10,3 @@ zobrist_init(void); uint64_t zobrist_compute(void); - -uint64_t -zobrist_apply(const action_t action, uint64_t hash); -- cgit v1.3.1