Closing in!

1 files changed, 131 insertions, 4 deletions

diff --git a/include/ct1975.c b/include/ct1975.c
index 760fcd1..61f1fee 100644
--- a/include/ct1975.c
+++ b/include/ct1975.c
@@ -1,13 +1,17 @@
 #include "ct1975.h"
 
-float flattened[CONV_NUM+2];
-float dense1[DENSE1_NUM];
-float dense2[DENSE2_NUM];
+// ===================================================================
+// 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
-evaluate_black_win(void) {
+ct1975_evaluate_black_win(void) {
 	/* ------------------ *
 	 *  Convolution layer *
 	 * ------------------ */
@@ -87,3 +91,126 @@ evaluate_black_win(void) {
 
 	return output;
 }
+
+// ===================================================================
+// Select best move according the CNN above
+// ===================================================================
+
+char ct1975_ptn[9];
+float ct1975_optimal;
+
+#define BETTER(t,o) ((current_colour == C_BLACK && (t) > (o)) || (current_colour == C_WHITE && (t) < (o)))
+
+void
+ct1975_generate_ptn(void display_progress(void)) {
+	float this = 0;
+	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, 0.0 is a `certain' white win.
+	ct1975_optimal = (current_colour == C_BLACK) ? 0.0 : 1.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 && ply>2 && ((colours[loc] & 1) == current_colour)) {
+				// There are stones, can we move them?
+				// For every direction. 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 row/column of the board
+					if (dir == M_UP || dir == M_DOWN) {
+						for (uint8_t k = 0; k < board_size; k++) {
+							colours_backup[k] = colours[THE_COORDS(k, row)];
+							celldat_backup[k] = celldat[THE_COORDS(k, row)];
+						}
+					} else {
+						for (uint8_t k = 0; k < board_size; k++) {
+							colours_backup[k] = colours[THE_COORDS(col, k)];
+							celldat_backup[k] = celldat[THE_COORDS(col, k)];
+						}
+					}
+					// 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) {
+									this = ct1975_evaluate_black_win();
+									if (BETTER(this, ct1975_optimal)) {
+										// Update the chosen action
+										ct1975_optimal = this;
+										generate_move(board_size, loc, dir, steps, drops, ct1975_ptn);
+									}
+									// Reset the board data
+									if (dir == M_UP || dir == M_DOWN) {
+										for (uint8_t k = 0; k < board_size; k++) {
+											colours[THE_COORDS(k, row)] = colours_backup[k];
+											celldat[THE_COORDS(k, row)] = celldat_backup[k];
+										}
+									} else {
+										for (uint8_t k = 0; k < board_size; k++) {
+											colours[THE_COORDS(col, k)] = colours_backup[k];
+											celldat[THE_COORDS(col, k)] = celldat_backup[k];
+										}
+									}
+								}
+							}
+						}
+					}
+				}
+			} 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) {
+						this = ct1975_evaluate_black_win();
+						if (ply < 3 && BETTER(this, ct1975_optimal)) {
+							// Update the chosen action
+							ct1975_optimal = this;
+							generate_place(board_size, loc, stone, ct1975_ptn);
+						}
+						// Reset the state
+						celldat[loc] = 0;
+						white_count = white_count_backup;
+						black_count = black_count_backup;
+					}
+				}
+			}
+			display_progress();
+		}
+	}
+}