diff options
Diffstat (limited to 'include')
| -rw-r--r-- | include/minimax_cnn1986.h | 20 | ||||
| -rw-r--r-- | include/negamax_cnn1986.c (renamed from include/minimax_cnn1986.c) | 109 | ||||
| -rw-r--r-- | include/negamax_cnn1986.h | 18 | ||||
| -rw-r--r-- | include/tak.c | 2 |
4 files changed, 72 insertions, 77 deletions
diff --git a/include/minimax_cnn1986.h b/include/minimax_cnn1986.h deleted file mode 100644 index dd529e6..0000000 --- a/include/minimax_cnn1986.h +++ /dev/null @@ -1,20 +0,0 @@ -#include <stdint.h> -#include "tak.h" -#include "weights.h" - -extern const float infty; -extern char ct1986_ptn[9]; -extern inline void ct1986_display_progress(const uint8_t); - -float -ct1986_evaluate_win(void); - -// Generate PTN of the ````best'''' action and store it in ct1986_ptn, -// along with its value as the return. The ct1986_display_progress -// function pointer is called on every new square. - -extern char ct1986_ptn[9]; -float ct1986_generate(const uint8_t max_depth); - -void -ct1986_generate_ptn(void display_progress(void)); diff --git a/include/minimax_cnn1986.c b/include/negamax_cnn1986.c index 38edb33..fafb38c 100644 --- a/include/minimax_cnn1986.c +++ b/include/negamax_cnn1986.c @@ -1,4 +1,4 @@ -#include "minimax_cnn1986.h" +#include "negamax_cnn1986.h" // =================================================================== // Globals @@ -6,6 +6,7 @@ const float infty = 3.0; char ct1986_ptn[9]; +uint8_t ct1986_search_depth = 3; // =================================================================== // Implementation of a small convolutional neural network @@ -36,7 +37,7 @@ static union u_f fudge; #define RELU(x) ((x) = ((x)<0)?0:(x)) float -ct1986_evaluate_win(void) { +ct1986_evaluate_black_win(void) { /* ------------------ * * Convolution layer * * ------------------ */ @@ -115,19 +116,16 @@ ct1986_evaluate_win(void) { output += fudge.f; #endif if (output > 1.0) { - if (ply & 1) return 1.0; - else return -1.0; + return 1.0; } else if (output < 0.0) { - if (ply & 1) return -1.0; - else return 1.0; + return -1.0; } - - return (ply & 1) ? 2.0*output-1.0 : 1.0-2*output; + return 2*output-1.0; } // =================================================================== -// α-β minimax using the above evaluator +// α-β negamax using the above evaluator // =================================================================== static void @@ -141,61 +139,61 @@ previous_ply(void) { } } +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 - 2) w = check_win(); \ if (w < 0xFF) { \ /* Somebody won, assign weights accordingly. Note in particular - that draws are only worth ∞/2 ;) \ + that draws are only worth ∞/2 ;) */ \ - if (ply & 1) { \ - if (w == WIN_ROAD_WHITE || w == WIN_FLAT_WHITE) \ - val = -infty; \ - else if (w == WIN_DRAW) val = infty/2.0; \ - else val = infty; \ - } else { \ - if (w == WIN_ROAD_BLACK || w == WIN_FLAT_BLACK) \ - val = -infty; \ - else if (w == WIN_DRAW) val = infty/2.0; \ - else val = infty; \ - } \ - } else if (cur_depth == max_depth) { \ + if (w == WIN_ROAD_BLACK || w == WIN_FLAT_BLACK) \ + val = infty; \ + else if (w == WIN_DRAW) val = infty/2.0; \ + else val = -infty; \ + val *= colour; \ + } else if (cur_depth == ct1986_search_depth) { \ /* We're at the bottom, evaluate */ \ - val = ct1986_evaluate_win(); \ + val = colour * ct1986_evaluate_black_win(); \ } else { \ /* We're not at the bottom, recurse first */ \ next_ply(); \ - val = -ct1986_negamax(cur_depth + 1, max_depth, -beta, -alpha); \ + val = -ct1986_negamax(cur_depth + 1, -beta, -alpha, -colour); \ previous_ply(); \ } \ { reset }; \ /* Prune */ \ - if (val >= beta) return val; \ + if (val >= beta) return beta; \ /* Update the optimal value, which alpha carries */ \ - if (val > optimal) { \ - optimal = val; \ - if (val > alpha) alpha = val; \ + if (val > alpha) { \ + alpha = val; \ if (cur_depth == 0) { store }; \ } \ } -// UP DOWN LEFT RIGHT -static const int8_t deltas[4] = { +5, -5, -1, +1}; - float -ct1986_negamax(const uint8_t cur_depth, const uint8_t max_depth, - float alpha, float beta) { +ct1986_negamax(const uint8_t cur_depth, float alpha, float beta, + const float colour) { 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)); - float optimal = -infty; - // Step across the board for (uint8_t row = 0; row < 5; row++) { for (uint8_t col = 0; col < 5; col++) { @@ -267,35 +265,34 @@ ct1986_negamax(const uint8_t cur_depth, const uint8_t max_depth, steps++) { gaps = 0b00000111 >> (4-steps); 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; + 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; } - mask <<= 1; - } - // TODO: Work out what this should be before partition - - // Ensure legal move if we have to crush - if (end_stops[dir][1] || drops[steps-1] <= 1) { - // Try it, and manually check for win if it's valid + // Do it, and manually check for win if it's valid uint8_t j = num; for (uint8_t k = 0; k < steps; k++) { - // Dear future me, i'm sorry j -= drops[k]; - colours[loc+(k+1)*deltas[dir]] = (colours[loc+(k+1)*deltas[dir]] << drops[k]) - | ((colours[loc] >> j) & (0xFFFF >> (0x10 - drops[k]))); - celldat[loc+(k+1)*deltas[dir]] = (k == steps - 1) ? STONE_AT(loc) : STONE_FLAT - | ((celldat[loc+(k+1)*deltas[dir]] + ((drops[k] << NUM_SHIFT))) & NUM_MASK); + 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({ @@ -387,6 +384,6 @@ ct1986_negamax(const uint8_t cur_depth, const uint8_t max_depth, } inline float -ct1986_generate(const uint8_t max_depth) { - return ct1986_negamax(0, max_depth, -infty, infty); +ct1986_generate(void) { + return ct1986_negamax(0, -infty, infty, (ply&1)?1.0:-1.0); } diff --git a/include/negamax_cnn1986.h b/include/negamax_cnn1986.h new file mode 100644 index 0000000..411d877 --- /dev/null +++ b/include/negamax_cnn1986.h @@ -0,0 +1,18 @@ +#include <stdint.h> +#include "tak.h" +#include "weights.h" + +extern const float infty; +extern char ct1986_ptn[9]; +extern uint8_t ct1986_search_depth; +extern inline void ct1986_display_progress(const uint8_t); + +// Do negamax to depth ct1986_search_depth and return PTN of best move +// in ct1986_ptn, along with its value as the return. The +// ct1986_display_progress function is called on every new square at +// the top level. +float ct1986_generate(void); + +// Internal utility function +float +ct1986_evaluate_black_win(void); diff --git a/include/tak.c b/include/tak.c index a748555..e400578 100644 --- a/include/tak.c +++ b/include/tak.c @@ -109,7 +109,7 @@ try_place(const int8_t location, const enum COLOUR colour, // Moving stacks // =================================================================== -static void +static inline void push_stones(const int8_t location, const uint8_t count, const uint8_t new_colours, const enum STONE_VARIANT top_stone) { |