diff options
| -rw-r--r-- | include/minimax_cnn1986.h | 19 | ||||
| -rw-r--r-- | include/negamax_cnn1986.c (renamed from include/minimax_cnn1986.c) | 182 | ||||
| -rw-r--r-- | include/negamax_cnn1986.h | 18 | ||||
| -rw-r--r-- | include/tak.c | 2 | ||||
| -rw-r--r-- | src/ctaklm.c | 25 |
5 files changed, 123 insertions, 123 deletions
diff --git a/include/minimax_cnn1986.h b/include/minimax_cnn1986.h deleted file mode 100644 index 3bc3301..0000000 --- a/include/minimax_cnn1986.h +++ /dev/null @@ -1,19 +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_black_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. - -float ct1986_generate(const uint8_t max_depth); - -extern char ct1986_ptn[9]; -extern float ct1986_optimal; diff --git a/include/minimax_cnn1986.c b/include/negamax_cnn1986.c index fed30e2..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 @@ -114,14 +115,17 @@ ct1986_evaluate_black_win(void) { DOXORSHIFT; output += fudge.f; #endif - if (output > 1.0) return 1.0; - else if (output < 0.0) return 0.0; - - return output; + if (output > 1.0) { + return 1.0; + } + else if (output < 0.0) { + return -1.0; + } + return 2*output-1.0; } // =================================================================== -// α-β minimax using the above evaluator +// α-β negamax using the above evaluator // =================================================================== static void @@ -135,63 +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; -#define WIN_EVALUATE_OR_RECURSE(store) { \ +// 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 */ \ - if (min == 0) { \ - if (w == WIN_ROAD_BLACK || w == WIN_FLAT_BLACK) \ - val = infty; \ - else val = -infty; \ - } else { \ - if (w == WIN_ROAD_WHITE || w == WIN_FLAT_WHITE) \ - val = -infty; \ - else val = infty; \ - } \ - } else if (cur_depth == max_depth) { \ + /* Somebody won, assign weights accordingly. Note in particular + that draws are only worth ∞/2 ;) + */ \ + 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_black_win(); \ - if ((ply & 1) == 0) val = 1.0 - 2*val; \ - if (min) val *= -1; \ + val = colour * ct1986_evaluate_black_win(); \ } else { \ /* We're not at the bottom, recurse first */ \ next_ply(); \ - val = ct1986_minimax(cur_depth + 1, max_depth, 1-min, alpha, beta); \ + val = -ct1986_negamax(cur_depth + 1, -beta, -alpha, -colour); \ previous_ply(); \ } \ - /* Update the optimal value */ \ - if (((min > 0) && (val <= optimal)) \ - || ((min == 0) && (val >= optimal))) { \ - optimal = val; \ - if (cur_depth == 0) (store); \ - } \ - /* Update alpha and beta */ \ - if (min) { \ - if (optimal < beta) beta = optimal; \ - } else { \ - if (optimal > alpha) alpha = optimal; \ + { reset }; \ + /* Prune */ \ + if (val >= beta) return beta; \ + /* Update the optimal value, which alpha carries */ \ + 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_minimax(const uint8_t cur_depth, const uint8_t max_depth, - const uint8_t min, 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)); - // 1.0 is a `certain' black win, -1.0 is a `certain' white win. - float optimal = (min) ? infty : -infty; - // Step across the board for (uint8_t row = 0; row < 5; row++) { for (uint8_t col = 0; col < 5; col++) { @@ -263,56 +265,55 @@ ct1986_minimax(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({ // If we did update the optimal value, store // this move generate_move(loc, dir, steps, drops, ct1986_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]; + } + } }); - // Reset the board data - 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]; - } - } - // Prune - if (alpha >= beta) return optimal; } /* * With thanks to @@ -338,13 +339,12 @@ ct1986_minimax(const uint8_t cur_depth, const uint8_t max_depth, WIN_EVALUATE_OR_RECURSE({ // If we did update the optimal value, store generate_place(loc, STONE_FLAT, ct1986_ptn); + },{ + // Reset the state + celldat[loc] = 0; + if (black) black_count++; + else white_count++; }); - // Reset the state - celldat[loc] = 0; - if (black) black_count++; - else white_count++; - // Prune - if (alpha >= beta) return optimal; // Do the same for walls, can't happen without flats if (standing) { @@ -354,11 +354,11 @@ ct1986_minimax(const uint8_t cur_depth, const uint8_t max_depth, celldat[loc] = NUM_INC | STONE_STANDING; WIN_EVALUATE_OR_RECURSE({ generate_place(loc, STONE_STANDING, ct1986_ptn); + },{ + celldat[loc] = 0; + if (black) black_count++; + else white_count++; }); - celldat[loc] = 0; - if (black) black_count++; - else white_count++; - if (alpha >= beta) return optimal; } } @@ -370,20 +370,20 @@ ct1986_minimax(const uint8_t cur_depth, const uint8_t max_depth, celldat[loc] = NUM_INC | STONE_CAPSTONE; WIN_EVALUATE_OR_RECURSE({ generate_place(loc, STONE_CAPSTONE, ct1986_ptn); + },{ + celldat[loc] = 0; + if (black) black_count |= 128; + else white_count |= 128; }); - celldat[loc] = 0; - if (black) black_count |= 128; - else white_count |= 128; - if (alpha >= beta) return optimal; } } ct1986_display_progress(cur_depth); } } - return optimal; + return alpha; } inline float -ct1986_generate(const uint8_t max_depth) { - return ct1986_minimax(0, 1+2*max_depth, (ply & 1) ? 0 : 1, -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) { diff --git a/src/ctaklm.c b/src/ctaklm.c index a7c299d..a1ca69d 100644 --- a/src/ctaklm.c +++ b/src/ctaklm.c @@ -3,7 +3,7 @@ #include <string.h> #include <tak.h> -#include <minimax_cnn1986.h> +#include <negamax_cnn1986.h> static const char *blk = "\033[41m", *wht = "\033[44m"; static const char *und = "\033[4m", *rst = "\033[0m"; @@ -151,9 +151,9 @@ print_info(void) { blk, black_count & 127, black_count >> 7, rst); } +static int human; static char *gamelog = 0; static uint8_t auto_board = 0xFF, auto_info = 0xFF; -static int human, search_depth; static void append_to_gamelog(const char *line, const uint8_t win_line) { @@ -234,8 +234,8 @@ handle_turn(char *line) { static void new_game(uint8_t size) { reset_state(size); - printf("New %dx%d game! ct1986 at search_depth %d.\n", - size, size, search_depth); + printf("New %dx%d game! ct1986 at search depth %d.\n", + size, size, ct1986_search_depth); if (gamelog) gamelog = realloc(gamelog, sizeof(char)); else gamelog = malloc(sizeof(char)); gamelog[0] = 0; @@ -308,7 +308,7 @@ ct1986_display_progress(const uint8_t depth) { } static int -ct1986_turn(const uint8_t search_depth) { +ct1986_turn(void) { if (won == 0xFF) { // Prepare progress bar fputs("Computing [", stdout); @@ -317,7 +317,7 @@ ct1986_turn(const uint8_t search_depth) { fflush(stdout); // Run the minimax sum_depth = 0; num_check = 0; - float minimax = ct1986_generate(search_depth); + float minimax = ct1986_generate(); fputs("\033[1C ", stdout); // Failed to find a move? if (minimax <= -infty) { @@ -353,18 +353,19 @@ info, load, log, new, play (b|w), self-play, square <col><row>, <PTN>."); blk, eval, rst); } else { printf("White heruistic chance: %s%.2f%s\n", - wht, 100-eval, rst); + wht, -eval, rst); } } else if (!strcmp(line,"log")) { puts(gamelog); } else if (!strcmp(line,"new")) { new_game(5); } else if (!strcmp(line,"self-play")) { - while (ct1986_turn(search_depth) == 0); + while (ct1986_turn() == 0); } else if (!strncmp(line,"depth",5)) { if (strnlen(line,7) == 7 && line[6] >= '0' && line[6] <= '9') { - search_depth = line[6] - '0'; - printf("New search depth: %d.\n",search_depth); + ct1986_search_depth = line[6] - '0'; + printf("New search depth: %d.\n", + ct1986_search_depth); } else { puts("Usage: depth [0-9]."); } @@ -418,7 +419,7 @@ main(int argc, char **argv) { (void)(argv); human = 0; - search_depth = 1; + ct1986_search_depth = 3; new_game(5); char *line = NULL; @@ -446,7 +447,7 @@ main(int argc, char **argv) { if (read == -1) { playing = 0; } else { - ct1986_turn(search_depth); + ct1986_turn(); human = 0; } } |