From 82d679ab5fa43c33ae52fe7b66d7c358f6046a45 Mon Sep 17 00:00:00 2001 From: tslil clingman Date: Mon, 18 Jan 2021 23:14:12 -0500 Subject: First steps towards character LCD --- include/ct1986.c | 362 ---------------------------------------------- include/ct1986.h | 28 ---- include/minimax_cnn1986.c | 362 ++++++++++++++++++++++++++++++++++++++++++++++ include/minimax_cnn1986.h | 28 ++++ 4 files changed, 390 insertions(+), 390 deletions(-) delete mode 100644 include/ct1986.c delete mode 100644 include/ct1986.h create mode 100644 include/minimax_cnn1986.c create mode 100644 include/minimax_cnn1986.h (limited to 'include') diff --git a/include/ct1986.c b/include/ct1986.c deleted file mode 100644 index ec73f7c..0000000 --- a/include/ct1986.c +++ /dev/null @@ -1,362 +0,0 @@ -#include "ct1986.h" - -// =================================================================== -// Globals -// =================================================================== - -const float infty = 3.0; -char ct1986_ptn[9]; -void (*ct1986_display_progress)(const uint8_t); - -// =================================================================== -// 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 -ct1986_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< 1.0) return 1.0; - else if (output < 0.0) return 0.0; - - return output; -} - -// =================================================================== -// α-β minimax 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 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; \ - } 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 { \ - /* 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; \ - } \ -} - -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, - 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++) { - // 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? - // I'm not a huge fan of looping through enums, but it's - // better than manually unrolling this. Sufficiently smart - // compilers? - - 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)]; - } - 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 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: { - upper = (4-col > count) ? count : 4-col; - break; - } - } - uint8_t gaps, t, idx, mask; - for (uint8_t num = 1; num <= count; num++) { - for (uint8_t steps = 1; steps <= upper && steps <= num; steps++) { - gaps = 0b00000111 >> (4-steps); - do { - // 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; - } - // Try it, and manually check for win if it's valid - r = try_move(loc, dir, steps, drops); - if (r == ACT_OK) { - // 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 - 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 - * 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, ct1986_ptn); - }); - // 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) { - 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, ct1986_ptn); - }); - celldat[loc] = 0; - if (black) black_count++; - else white_count++; - if (alpha >= beta) return optimal; - } - } - - // 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, ct1986_ptn); - }); - celldat[loc] = 0; - if (black) black_count |= 128; - else white_count |= 128; - if (alpha >= beta) return optimal; - } - } - ct1986_display_progress(cur_depth); - } - } - return optimal; -} - -inline float -ct1986_generate(const uint8_t max_depth) { - return ct1986_minimax(0, max_depth, (ply & 1) ? 0 : 1, -infty, infty); -} diff --git a/include/ct1986.h b/include/ct1986.h deleted file mode 100644 index 3f2568d..0000000 --- a/include/ct1986.h +++ /dev/null @@ -1,28 +0,0 @@ -#include -#include "tak.h" -#include "weights.h" - -extern const float infty; -extern char ct1986_ptn[9]; -extern 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); - -// Access to the internal method -float -ct1986_minimax(const uint8_t cur_depth, const uint8_t max_depth, - const uint8_t min, float alpha, float beta); - -extern char ct1986_ptn[9]; -extern float ct1986_optimal; - - -void -ct1986_generate_ptn(void display_progress(void)); diff --git a/include/minimax_cnn1986.c b/include/minimax_cnn1986.c new file mode 100644 index 0000000..ce950ba --- /dev/null +++ b/include/minimax_cnn1986.c @@ -0,0 +1,362 @@ +#include "minimax_cnn1986.h" + +// =================================================================== +// Globals +// =================================================================== + +const float infty = 3.0; +char ct1986_ptn[9]; +void (*ct1986_display_progress)(const uint8_t); + +// =================================================================== +// 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 +ct1986_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< 1.0) return 1.0; + else if (output < 0.0) return 0.0; + + return output; +} + +// =================================================================== +// α-β minimax 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 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; \ + } 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 { \ + /* 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; \ + } \ +} + +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, + 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++) { + // 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? + // I'm not a huge fan of looping through enums, but it's + // better than manually unrolling this. Sufficiently smart + // compilers? + + 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)]; + } + 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 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: { + upper = (4-col > count) ? count : 4-col; + break; + } + } + uint8_t gaps, t, idx, mask; + for (uint8_t num = 1; num <= count; num++) { + for (uint8_t steps = 1; steps <= upper && steps <= num; steps++) { + gaps = 0b00000111 >> (4-steps); + do { + // 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; + } + // Try it, and manually check for win if it's valid + r = try_move(loc, dir, steps, drops); + if (r == ACT_OK) { + // 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 + 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 + * 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, ct1986_ptn); + }); + // 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) { + 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, ct1986_ptn); + }); + celldat[loc] = 0; + if (black) black_count++; + else white_count++; + if (alpha >= beta) return optimal; + } + } + + // 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, ct1986_ptn); + }); + celldat[loc] = 0; + if (black) black_count |= 128; + else white_count |= 128; + if (alpha >= beta) return optimal; + } + } + ct1986_display_progress(cur_depth); + } + } + return optimal; +} + +inline float +ct1986_generate(const uint8_t max_depth) { + return ct1986_minimax(0, max_depth, (ply & 1) ? 0 : 1, -infty, infty); +} diff --git a/include/minimax_cnn1986.h b/include/minimax_cnn1986.h new file mode 100644 index 0000000..3f2568d --- /dev/null +++ b/include/minimax_cnn1986.h @@ -0,0 +1,28 @@ +#include +#include "tak.h" +#include "weights.h" + +extern const float infty; +extern char ct1986_ptn[9]; +extern 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); + +// Access to the internal method +float +ct1986_minimax(const uint8_t cur_depth, const uint8_t max_depth, + const uint8_t min, float alpha, float beta); + +extern char ct1986_ptn[9]; +extern float ct1986_optimal; + + +void +ct1986_generate_ptn(void display_progress(void)); -- cgit v1.2.3 From c81898d6a760e2057f0933c9da6160702a4d0f61 Mon Sep 17 00:00:00 2001 From: tslil clingman Date: Wed, 20 Jan 2021 13:23:58 -0500 Subject: In-lined as much as a i dare --- Makefile | 3 +- include/minimax_cnn1986.c | 96 ++++++++++++++++++++++++++++++----------------- include/minimax_cnn1986.h | 2 +- include/tak.c | 1 - include/tak.h | 1 + src/ct1986.c | 8 ++-- src/ctaklm.c | 10 ++--- 7 files changed, 71 insertions(+), 50 deletions(-) (limited to 'include') diff --git a/Makefile b/Makefile index c12d1ab..4a9c77b 100644 --- a/Makefile +++ b/Makefile @@ -1,7 +1,6 @@ IDIR=include -TDIR=3rd-party DEFINES=-DDETERMINISTIC -CFLAGS=-O3 -Wall -Wextra -std=c99 -D_DEFAULT_SOURCE $(DEFINES) -I$(IDIR) -I$(TDIR) +CFLAGS=-O3 -Wall -Wextra -std=c99 -D_DEFAULT_SOURCE $(DEFINES) -I$(IDIR) LIBS= SRCS=$(wildcard include/*.c) $(wildcard 3rd-party/*.c) diff --git a/include/minimax_cnn1986.c b/include/minimax_cnn1986.c index ce950ba..d13195d 100644 --- a/include/minimax_cnn1986.c +++ b/include/minimax_cnn1986.c @@ -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 @@ -177,11 +176,12 @@ static enum WIN_TYPE w; } \ } +// 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,9 +200,33 @@ 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 @@ -213,6 +237,10 @@ ct1986_minimax(const uint8_t cur_depth, const uint8_t max_depth, 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) { @@ -222,33 +250,16 @@ ct1986_minimax(const uint8_t cur_depth, const uint8_t max_depth, } } /* - * 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). + * 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 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: { - upper = (4-col > count) ? count : 4-col; - break; - } - } 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 @@ -262,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({ @@ -284,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 diff --git a/include/minimax_cnn1986.h b/include/minimax_cnn1986.h index 3f2568d..3ccc004 100644 --- a/include/minimax_cnn1986.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< Date: Wed, 20 Jan 2021 15:38:03 -0500 Subject: Can't stop half-way through turn --- include/minimax_cnn1986.c | 2 +- src/ct1986.c | 2 +- src/ctaklm.c | 47 +++++++++++++++++++++++++---------------------- 3 files changed, 27 insertions(+), 24 deletions(-) (limited to 'include') diff --git a/include/minimax_cnn1986.c b/include/minimax_cnn1986.c index d13195d..7363b23 100644 --- a/include/minimax_cnn1986.c +++ b/include/minimax_cnn1986.c @@ -384,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/src/ct1986.c b/src/ct1986.c index b265b57..2e57ea6 100644 --- a/src/ct1986.c +++ b/src/ct1986.c @@ -167,7 +167,7 @@ main(int argc, char **argv) { if (lcd == NULL) return EXIT_FAILURE; human = 0; - search_depth = 3; + search_depth = 1; new_game(5); char *line = NULL; diff --git a/src/ctaklm.c b/src/ctaklm.c index eb2a788..24613e9 100644 --- a/src/ctaklm.c +++ b/src/ctaklm.c @@ -309,28 +309,31 @@ ct1986_display_progress(const uint8_t depth) { static int ct1986_turn(const uint8_t search_depth) { - // Prepare progress bar - fputs("Computing [", stdout); - for (int k = 0; k < board_size * board_size; k++) putchar(' '); - fputs("]\033[26D",stdout); - fflush(stdout); - // Run the minimax - sum_depth = 0; num_check = 0; - float minimax = ct1986_generate(search_depth); - fputs("\033[1C ", stdout); - // Failed to find a move? - if ((minimax <= -infty && (ply & 1) == 1) - ||(minimax >= infty && (ply & 1) == 0)) { - puts("Opponent concedes!"); - return EXIT_FAILURE; + if (won == 0xFF) { + // Prepare progress bar + fputs("Computing [", stdout); + for (int k = 0; k < board_size * board_size; k++) putchar(' '); + fputs("]\033[26D",stdout); + fflush(stdout); + // Run the minimax + sum_depth = 0; num_check = 0; + float minimax = ct1986_generate(search_depth); + fputs("\033[1C ", stdout); + // Failed to find a move? + if (minimax <= -infty) { + puts("Opponent concedes!"); + return EXIT_FAILURE; + } else { + printf("Result: %s (%.2f, %.1e, %.2f)\n", + ct1986_ptn, + minimax*100.0, + num_check, + sum_depth/num_check); + handle_turn(ct1986_ptn); + return EXIT_SUCCESS; + } } else { - printf("Result: %s (%.2f, %.1e, %.2f)\n", - ct1986_ptn, - minimax*100.0, - num_check, - sum_depth/num_check); - handle_turn(ct1986_ptn); - return EXIT_SUCCESS; + return EXIT_FAILURE; } } @@ -415,7 +418,7 @@ main(int argc, char **argv) { (void)(argv); human = 0; - search_depth = 3; + search_depth = 1; new_game(5); char *line = NULL; -- cgit v1.2.3