diff options
Diffstat (limited to 'include/negamax.c')
| -rw-r--r-- | include/negamax.c | 432 |
1 files changed, 215 insertions, 217 deletions
diff --git a/include/negamax.c b/include/negamax.c index 3e57165..3e3a209 100644 --- a/include/negamax.c +++ b/include/negamax.c @@ -14,34 +14,27 @@ uint32_t cache_fails = 0; // Zobrist hashing // =================================================================== -uint64_t *zobrist[4]; -uint64_t *zobrist_empty[4]; +uint64_t *zobrist[15]; static int negamax_init_zobrist(void) { - for (int k=0; k<4; k++) { + + for (int k=0; k<15; k++) { if (zobrist[k] != NULL) return EXIT_FAILURE; - if (zobrist_empty[k] != NULL) return EXIT_FAILURE; } - for (int j=0; j<4; j++) { - zobrist[j] = malloc(sizeof(uint64_t)*board_size*board_size*15*3*2); - zobrist_empty[j] = malloc(sizeof(uint64_t)*board_size*board_size); - // TODO: trap errno - for (int k=0; k<board_size*board_size*15*3*2; k++) { + 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; } - for (int k=0; k<board_size*board_size; k++) { - XORSHIFT64; - zobrist_empty[j][k] = RANDOM64; - } } return EXIT_SUCCESS; } static void negamax_free_zobrist(void) { - for (int k=0; k<4; k++) { + for (int k=0; k<15; k++) { if (zobrist[k] != NULL) { free(zobrist[k]); zobrist[k] = NULL; @@ -49,21 +42,20 @@ static void negamax_free_zobrist(void) { } } -void negamax_compute_zobrist(uint64_t *hash) { - for (int k=0; k<4; k++) hash[k] = 0; +uint64_t negamax_compute_zobrist(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); - if (count) { - const enum STONE_VARIANT s = STONE_AT(l); - colour_stack_t c = colours[l]; - for (uint8_t h=0; h<count; h++) { - for (int k=0; k<4; k++) { - hash[k] ^= zobrist[k][l*16*3*2 + h*3*2 + (c&1)*3 + s]; - } + 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; } // =================================================================== @@ -144,220 +136,229 @@ static enum WIN_TYPE w; float negamax(const uint8_t cur_depth, float alpha, float beta, const float colour) { - uint64_t hash[4]; - negamax_compute_zobrist(hash); - - float stored_alpha; - int lookup = cnn1986_cache_seek(hash, &stored_alpha); - - /* - * 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; + 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; + } + + 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]++; } - 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 (*) + 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)]; - } + //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)]; - } + // 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); + } + /* + * 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; } - // 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]; - } - } - }); + mask <<= 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)))); - } + // 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 + } + } 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_FLAT; + celldat[loc] = NUM_INC | STONE_STANDING; WIN_EVALUATE_OR_RECURSE({ - // If we did update the optimal value, store - generate_place(loc, STONE_FLAT, negamax_ptn); + generate_place(loc, STONE_STANDING, 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; - }); - } + // 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 - } - if (lookup == EXIT_FAILURE) - cnn1986_cache_insert(hash, alpha); - else { - if (stored_alpha != alpha) - cache_fails++; + negamax_display_progress(cur_depth); } + } + + 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; + } + return alpha; } @@ -367,12 +368,9 @@ negamax_generate(void) { // values are wins const float safe_infty = infty + 1; - - cache_fails=0; - - cnn1986_cache_init(); + tt_init(); float result = negamax(0, -safe_infty, safe_infty, (ply&1)?1.0:-1.0); - cnn1986_cache_free(); + tt_free(); return result; } |