From 2ef0078ba2afd99c4fc2673497f3d3a39119cf5d Mon Sep 17 00:00:00 2001 From: tslil Date: Wed, 13 Jan 2021 16:39:16 -0500 Subject: Trying minimax --- include/ct1986.c | 258 +++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 258 insertions(+) create mode 100644 include/ct1986.c (limited to 'include/ct1986.c') diff --git a/include/ct1986.c b/include/ct1986.c new file mode 100644 index 0000000..7295088 --- /dev/null +++ b/include/ct1986.c @@ -0,0 +1,258 @@ +#include "ct1986.h" + +// =================================================================== +// Globals +// =================================================================== + +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]; + +#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+by+(ky+bx)*board_size; + // 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; + } +} + +float +ct1986_minimax(const uint8_t cur_depth, const uint8_t max_depth, + const uint8_t min) { + enum E_RESULT r; + uint16_t colours_backup[board_size]; + uint8_t celldat_backup[board_size], drops[board_size]; + const uint8_t white_count_backup = white_count, + black_count_backup = black_count; + + // 1.0 is a `certain' black win, -1.0 is a `certain' white win. + float this = 0, optimal = (min) ? 2.0 : -2.0; + + // Step across the board + for (uint8_t row = 0; row < board_size; row++) { + for (uint8_t col = 0; col < board_size; 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); + // 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? + + // Back up the row of the board + for (uint8_t y = 0; y < board_size; 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 < board_size; 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 everything... + + // For every number of steps + for (uint8_t steps = 1; steps < board_size && steps <= count; steps++) { + uint8_t idx, carry; + for (idx = 0; idx < steps; idx++) drops[idx]=0; + idx = 0; + while (idx < steps) { + // Increment the drop sequence + carry = 0; + drops[idx]++; + do { + if (carry) { drops[++idx]++; carry = 0;} + if (drops[idx] > count || drops[idx] > board_size) { + drops[idx] = 1; carry = 1; + } + } while (carry && idx < steps); + // If carry is still set here we're done + if (carry == 0) { + // Try it, and note that try_move will never return + // GAME_END. It does not check for winners. We don't + // presently do that either, trust in the magic + // numbers :) + r = try_move(loc, dir, steps, drops); + if (r == ACT_OK) { + // Decide what to do based on our depth + if (cur_depth == max_depth) { + // We're at the bottom, evaluate + this = ct1986_evaluate_black_win(); + } else { + // We're not at the bottom, recurse first + next_ply(); + this = ct1986_minimax(cur_depth + 1, max_depth, 1-min); + previous_ply(); + } + // Update depending on min and optimal + if ( (min && (this < optimal)) + || ((min==0) && (this > optimal))) { + optimal = this; + if (cur_depth == 0) + generate_move(loc, dir, steps, drops, ct1986_ptn); + } + // Reset the board data + if (dir <= M_DOWN) { + for (uint8_t y = 0; y < board_size; y++) { + colours[THE_COORDS(col, y)] = colours_backup[y]; + celldat[THE_COORDS(col, y)] = celldat_backup[y]; + } + } else { + for (uint8_t x = 0; x < board_size; x++) { + colours[THE_COORDS(x, row)] = colours_backup[x]; + celldat[THE_COORDS(x, row)] = celldat_backup[x]; + } + } + } + } + } + } + } + } else if (count == 0) { + // Empty square, try the three placements. Again, looping + // through enums, sigh. + for (enum STONE_VARIANT stone = STONE_FLAT; + stone <= STONE_CAPSTONE; stone++) { + // try_place will never check for winning, and we don't do + // that either here + r = try_place(loc, current_colour, stone); + // Legal placement, evaluate it + if (r == ACT_OK) { + // Decide what to do based on our depth + if (cur_depth == max_depth) { + // We're at the bottom, evaluate + this = ct1986_evaluate_black_win(); + } else { + // We're not at the bottom, recurse first + next_ply(); + this = ct1986_minimax(cur_depth + 1, max_depth, 1-min); + previous_ply(); + } + // Update depending on min and optimal + if ( (min && (this < optimal)) + || ((min==0) && (this > optimal))) { + optimal = this; + // Store the result if we're at the top + if (cur_depth == 0) + generate_place(loc, stone, ct1986_ptn); + } + // Reset the state + celldat[loc] = 0; + white_count = white_count_backup; + black_count = black_count_backup; + } + } + } + ct1986_display_progress(cur_depth); + } + } + return optimal; +} -- cgit v1.3.1