diff options
Diffstat (limited to 'include')
| -rw-r--r-- | include/minimax_cnn1986.c (renamed from include/ct1986.c) | 189 | ||||
| -rw-r--r-- | include/minimax_cnn1986.h (renamed from include/ct1986.h) | 2 | ||||
| -rw-r--r-- | include/tak.c | 1 | ||||
| -rw-r--r-- | include/tak.h | 1 |
4 files changed, 109 insertions, 84 deletions
diff --git a/include/ct1986.c b/include/minimax_cnn1986.c index 24c9c64..e89e5a6 100644 --- a/include/ct1986.c +++ b/include/minimax_cnn1986.c @@ -1,4 +1,4 @@ -#include "ct1986.h" +#include "minimax_cnn1986.h" // =================================================================== // Globals @@ -6,7 +6,6 @@ const float infty = 3.0; char ct1986_ptn[9]; -void (*ct1986_display_progress)(const uint8_t); // =================================================================== // Implementation of a small convolutional neural network @@ -25,13 +24,13 @@ union u_f { static uint32_t state = 1; static union u_f fudge; -#define DOXORSHIFT { \ +#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)) @@ -139,49 +138,50 @@ previous_ply(void) { static float val; static enum WIN_TYPE w; -#define WIN_EVALUATE_OR_RECURSE(store) { \ - 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; \ +#define WIN_EVALUATE_OR_RECURSE(store) { \ + 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) { \ + /* We're at the bottom, evaluate */ \ + val = ct1986_evaluate_black_win(); \ + if ((ply & 1) == 0) val = val - 1.0; \ } else { \ - if (w == WIN_ROAD_WHITE || w == WIN_FLAT_WHITE) \ - val = -infty; \ - else val = infty; \ + /* We're not at the bottom, recurse first */ \ + next_ply(); \ + val = ct1986_minimax(cur_depth + 1, max_depth, 1-min, alpha, beta); \ + previous_ply(); \ } \ - } else if (cur_depth == max_depth) { \ - /* We're at the bottom, evaluate */ \ - val = ct1986_evaluate_black_win(); \ - if ((ply & 1) == 0) val = val - 1.0; \ - } else { \ - /* We're not at the bottom, recurse first */ \ - next_ply(); \ - val = ct1986_minimax(cur_depth + 1, max_depth, 1-min, alpha, beta); \ - 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; \ - } \ -} + /* 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; \ + } \ + } + +// 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) { - - enum E_RESULT r; const uint8_t black = (ply & 1), material = (black) ? black_count : white_count, flat = material & 127, @@ -200,19 +200,47 @@ ct1986_minimax(const uint8_t cur_depth, const uint8_t max_depth, // 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? - // I'm not a huge fan of looping through enums, but it's - // better than manually unrolling this. Sufficiently smart - // compilers? + + // 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 (*) + // 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) { @@ -221,35 +249,17 @@ ct1986_minimax(const uint8_t cur_depth, const uint8_t max_depth, celldat_backup[x] = celldat[THE_COORDS(x, row)]; } } - /* - * We don't do anything terribly efficient or smart here, - * just try all the ordered partitions of num ∈ {1,…,count} - * that will fit on the board in the current direction. - * Recall that count = max(stack height, carry limit). - */ - uint8_t upper; - switch (dir) { - case M_UP: { - upper = (4-row > count) ? count : 4-row; - break; - } - case M_DOWN: { - upper = (row > count) ? count : row; - break; - } - case M_LEFT: { - upper = (col > count) ? count : col; - break; - } - case M_RIGHT: // fall through - default: { - upper = (4-col > count) ? count : 4-col; - break; - } - } + /* + * 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 <= upper && steps <= num; steps++) { + for (uint8_t steps = 1; + steps <= end_stops[dir][0] && steps <= num; + steps++) { gaps = 0b00000111 >> (4-steps); do { // Translate to a drop sequence @@ -263,9 +273,24 @@ ct1986_minimax(const uint8_t cur_depth, const uint8_t max_depth, } mask <<= 1; } - // Try it, and manually check for win if it's valid - r = try_move(loc, dir, steps, drops); - if (r == ACT_OK) { + // 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 + 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); + } + // 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({ @@ -285,9 +310,9 @@ ct1986_minimax(const uint8_t cur_depth, const uint8_t max_depth, celldat[THE_COORDS(x, row)] = celldat_backup[x]; } } + // Prune + if (alpha >= beta) return optimal; } - // Prune - if (alpha >= beta) return optimal; /* * With thanks to * https://graphics.stanford.edu/~seander/bithacks.html#NextBitPermutation @@ -310,9 +335,9 @@ ct1986_minimax(const uint8_t cur_depth, const uint8_t max_depth, 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, ct1986_ptn); - }); + // 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++; @@ -359,5 +384,5 @@ ct1986_minimax(const uint8_t cur_depth, const uint8_t max_depth, inline float ct1986_generate(const uint8_t max_depth) { - return ct1986_minimax(0, max_depth, (ply & 1) ? 0 : 1, -infty, infty); + return ct1986_minimax(0, 1+2*max_depth, (ply & 1) ? 0 : 1, -infty, infty); } diff --git a/include/ct1986.h b/include/minimax_cnn1986.h index 3f2568d..3ccc004 100644 --- a/include/ct1986.h +++ b/include/minimax_cnn1986.h @@ -4,7 +4,7 @@ extern const float infty; extern char ct1986_ptn[9]; -extern void (*ct1986_display_progress)(const uint8_t); +extern inline void ct1986_display_progress(const uint8_t); float ct1986_evaluate_black_win(void); diff --git a/include/tak.c b/include/tak.c index 3d3ba0f..a748555 100644 --- a/include/tak.c +++ b/include/tak.c @@ -15,7 +15,6 @@ uint8_t white_count, black_count, ply; // Helpers // =================================================================== -#define NUM_MASK (0xF<<NUM_SHIFT) // 0b11110000 #define DFS_MASK 0b00001100 #define NOT_DFS_MASK 0b11110011 diff --git a/include/tak.h b/include/tak.h index 0a97c2d..1d49720 100644 --- a/include/tak.h +++ b/include/tak.h @@ -20,6 +20,7 @@ typedef uint8_t data_t; typedef uint16_t colour_stack_t; #define NUM_SHIFT 4 +#define NUM_MASK (0xF<<NUM_SHIFT) // 0b11110000 #define NUM_INC (0x1<<NUM_SHIFT) // 0b00010000 #define STONE_MASK 0b00000011 #define STONE_AT(l) (celldat[(l)] & STONE_MASK) |