From 18496a371a2204e8c1b448921a87108f4aa7ada3 Mon Sep 17 00:00:00 2001 From: tslil clingman Date: Sat, 23 Jan 2021 18:20:05 -0500 Subject: Attempting Zobrist hashing --- include/negamax.c | 346 ++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 346 insertions(+) create mode 100644 include/negamax.c (limited to 'include/negamax.c') diff --git a/include/negamax.c b/include/negamax.c new file mode 100644 index 0000000..bc912ad --- /dev/null +++ b/include/negamax.c @@ -0,0 +1,346 @@ +#include "negamax.h" + +// =================================================================== +// Globals +// =================================================================== + +const float infty = 3.0; +char negamax_ptn[9]; +uint8_t negamax_search_depth = 3; + +// =================================================================== +// Zobrist hashing +// =================================================================== + +uint64_t *zobrist = NULL; + +static int negamax_init_zobrist(void) { + if (zobrist != NULL) return EXIT_FAILURE; + zobrist = malloc(sizeof(uint64_t)*board_size*board_size*16*3*2); + for (int l=0; l>= 1; + } + } + return result; +} + +// =================================================================== +// α-β negamax using the cnn1986 evaluation function +// =================================================================== + + +// Movement steps, orderd with the enum: UP DOWN LEFT RIGHT +static int8_t deltas[4]; + +void negamax_init_size(void) { + deltas[0] = +board_size; + deltas[1] = -board_size; + deltas[2] = -1; + deltas[3] = +1; + negamax_free_zobrist(); + negamax_init_zobrist(); +} + +static 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 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); +} + +static float val; +static enum WIN_TYPE w; + +#define WIN_EVALUATE_OR_RECURSE(store,reset) { \ + w = 0xFF; \ + if (ply >= 2*board_size - 3) w = check_win(); \ + if (w < 0xFF) { \ + /* Somebody won, assign weights accordingly. */ \ + if (w == WIN_ROAD_BLACK || w == WIN_FLAT_BLACK) { \ + val = colour*infty; \ + /* Always take the win */ \ + if (cur_depth == 0 && val > 0) { \ + { reset }; \ + { store }; \ + return infty; \ + } \ + /* 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) { \ + /* 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(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 }; \ + } \ + } + +float negamax(const uint8_t cur_depth, float alpha, float beta, + const float colour) { + uint64_t hash = negamax_compute_zobrist(); + 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; + } + 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 (*) + + //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)]; + } + } + /* + * 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); + } + // 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 + 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_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; + }); + } + } + negamax_display_progress(cur_depth); + } + } + // Insert into the cache + cnn1986_cache_insert(hash, alpha); + } + return alpha; +} + +inline float +negamax_generate(void) { + // We need to start with something outside of [-∞,∞] because those + // values are wins + const float safe_infty = infty + 1; + + cnn1986_cache_init(); + float result = negamax(0, -safe_infty, safe_infty, (ply&1)?1.0:-1.0); + cnn1986_cache_free(); + + return result; +} -- cgit v1.2.3