diff options
Diffstat (limited to 'include/negamax_cnn1986.c')
| -rw-r--r-- | include/negamax_cnn1986.c | 411 |
1 files changed, 0 insertions, 411 deletions
diff --git a/include/negamax_cnn1986.c b/include/negamax_cnn1986.c deleted file mode 100644 index 1dd0e72..0000000 --- a/include/negamax_cnn1986.c +++ /dev/null @@ -1,411 +0,0 @@ -#include "negamax_cnn1986.h" - -// =================================================================== -// Globals -// =================================================================== - -const float infty = 3.0; -char negamax_cnn1986_ptn[9]; -uint8_t negamax_cnn1986_search_depth = 3; -uint8_t negamax_cnn1986_cache_threshold = 3; - -// =================================================================== -// Implementation of a small convolutional neural network -// =================================================================== - -static float flattened[CONV_NUM+2]; -static float dense1[DENSE1_NUM]; -static float dense2[DENSE2_NUM]; - -#ifndef DETERMINISTIC -union u_f { - uint32_t u; - float f; -}; - -static uint32_t state = 1; -static union u_f fudge; - -#define DOXORSHIFT { \ - state ^= state << 13; \ - state ^= state >> 17; \ - state ^= state << 5; \ - fudge.u = 0x3f800000 | state >> 10; \ - fudge.f = (fudge.f - 1.5) * 0.01; \ - } -#endif - -#define RELU(x) ((x) = ((x)<0)?0:(x)) - -float -cnn1986_evaluate_black_win(void) { - /* ------------------ * - * Convolution layer * - * ------------------ */ - // for each kernel - for (uint8_t kern = 0; kern < KERN_NUM; kern++) { - // the stride is 1, march across the board - for (uint8_t bx = 0; bx < KERN_OSIZE; bx++) { - for (uint8_t by = 0; by < KERN_OSIZE; by++) { - flattened[kern+KERN_NUM*(bx+by*KERN_OSIZE)] = - conv2d_biases[kern]; - // Compute the convolution for this position - for (uint8_t ky = 0; ky < KERN_SIZE; ky++) { - for (uint8_t kx = 0; kx < KERN_SIZE; kx++) { - for (uint8_t c = 0; c < KERN_CHAN; c++) { - // Where we are on the board - const uint8_t loc = kx+bx+(ky+by)*5; - // Look up what's on the board at this location, and - // multiply it. For c=0 we have to do some extra work - float lookup = 0; - if (COUNT_AT(loc)>c) { - if (c==0) { - if (STONE_AT(loc) == STONE_STANDING) { - lookup = (colours[loc] & 1) ? +0.25 : -0.25; - } else if (STONE_AT(loc) == STONE_CAPSTONE) { - lookup = (colours[loc] & 1) ? +1.00 : -1.00; - } else { - lookup = (colours[loc] & 1) ? +0.50 : -0.50; - } - } else { - lookup = (colours[loc] & (1<<c)) ? +0.50 : -0.50; - } - } - flattened[kern+KERN_NUM*(bx+by*KERN_OSIZE)] - += lookup*conv2d_weights[kern][ky][kx][c]; - } - } - } - RELU(flattened[kern+KERN_NUM*(bx+by*KERN_OSIZE)]); - } - } - } - // Add input of flat counts - flattened[CONV_NUM] = (float)(white_count & 127)/21.0; - flattened[CONV_NUM+1] = (float)(black_count & 127)/21.0; - /* ------------------ * - * First dense layer * - * ------------------ */ - for (uint8_t d1 = 0; d1 < DENSE1_NUM; d1++) { - dense1[d1] = dense1_biases[d1]; - for (uint8_t fl = 0; fl < CONV_NUM+2; fl++) { - dense1[d1] += flattened[fl]*dense1_weights[d1][fl]; - } - RELU(dense1[d1]); - } - /* ------------------- * - * Second dense layer * - * ------------------- */ - for (uint8_t d2 = 0; d2 < DENSE2_NUM; d2++) { - dense2[d2] = dense2_biases[d2]; - for (uint8_t d1 = 0; d1 < DENSE1_NUM; d1++) { - dense2[d2] += dense1[d1]*dense2_weights[d2][d1]; - } - RELU(dense2[d2]); - } - /* ------------- * - * Output layer * - * ------------- */ - float output = output_bias; - for (uint8_t d2 = 0; d2 < DENSE2_NUM; d2++) { - output += dense2[d2]*output_weights[d2]; - } - // Truncated Pade approximant of logistic function - output = (12.0+output+50.0*output/(output*output+10.0))/24.0; -#ifndef DETERMINISTIC - DOXORSHIFT; - output += fudge.f; -#endif - if (output > 1.0) { - return 1.0; - } - else if (output < 0.0) { - return -1.0; - } - return 2*output-1.0; -} - -// =================================================================== -// α-β negamax using the above evaluator -// =================================================================== - -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 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); -} - -static float val; -static enum WIN_TYPE w; - -// UP DOWN LEFT RIGHT -static const int8_t deltas[4] = { +5, -5, -1, +1}; - -#define WIN_EVALUATE_OR_RECURSE(store,reset) { \ - w = 0xFF; \ - if (ply >= 2*5 - 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_cnn1986_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_cnn1986(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_cnn1986(const uint8_t cur_depth, float alpha, float beta, - const float colour) { - - int sought = EXIT_FAILURE; - if (cur_depth < negamax_cnn1986_cache_threshold) { - sought = cnn1986_cache_seek(&alpha); - } - if (sought) { - 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 < 5; row++) { - for (uint8_t col = 0; col < 5; 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) > 5) ? 5 : COUNT_AT(loc); - // Only try moves after CPS - if (count && ((colours[loc] & 1) == current_colour) && ply>2) { - // There are stones, can we move them in a given direction? - - // Pre-compute end-stops - uint8_t end_stops[4][2]; // (end, not_crush) - // UP DOWN LEFT RIGHT - end_stops[0][0] = (4-row > count) ? count : 4-row; - end_stops[1][0] = (row > count) ? count : row; - end_stops[2][0] = (col > count) ? count : col; - end_stops[3][0] = (4-col > count) ? count : 4-col; - const uint8_t cap_top = STONE_AT(loc) == STONE_CAPSTONE; - for (uint8_t d = 0; d < 4; 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[5]; - uint8_t celldat_backup[5], drops[5]; // we only use 4, the - // fifth is to skip a - // bounds check at (*) - // Back up the row of the board - for (uint8_t y = 0; y < 5; 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 < 5; 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++) { - gaps = 0x07 >> (4-steps); // 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; // (*) we don't need to 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_cnn1986_ptn); - },{ - // Reset the board data after recursing or - // before returning - if (dir <= M_DOWN) { - for (uint8_t y = 0; y < 5; y++) { - colours[THE_COORDS(col, y)] = colours_backup[y]; - celldat[THE_COORDS(col, y)] = celldat_backup[y]; - } - } else { - for (uint8_t x = 0; x < 5; 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_cnn1986_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_cnn1986_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_cnn1986_ptn); - },{ - celldat[loc] = 0; - if (black) black_count |= 128; - else white_count |= 128; - }); - } - } - negamax_cnn1986_display_progress(cur_depth); - } - } - // Insert into the cache if we're not too deep, and make it - // useable for both min and max (colour * colour == 1) - if (cur_depth < negamax_cnn1986_cache_threshold) - cnn1986_cache_insert(colour*alpha); - } else { - // Impose the colour - alpha *= colour; - } - return alpha; -} - -inline float -negamax_cnn1986_generate(void) { - // We need to start with something outside of [-∞,∞] because those - // values are wins - const float safe_infty = infty + 1; - return negamax_cnn1986(0, -safe_infty, safe_infty, (ply&1)?1.0:-1.0); -} |