Working on action lists to refactor

1 files changed, 262 insertions, 0 deletions

diff --git a/include/action_list.c b/include/action_list.c
new file mode 100644
index 0000000..198cd08
--- /dev/null
+++ b/include/action_list.c
@@ -0,0 +1,262 @@
+#include "action_list.h"
+
+// ===================================================================
+// Helper method declarations
+// ===================================================================
+
+static inline action_list_t *
+action_list_prepend(action_list_t *list, const enum A_TYPE type,
+										const uint8_t loc, const uint8_t data0,
+										const uint8_t data1);
+
+static inline void 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);
+
+// ===================================================================
+// Exported method implementations
+// ===================================================================
+
+void action_list_free(action_list_t *list) {
+	action_list_t *n = NULL;
+	while (list) {
+		n = list->next;
+		free(list);
+		list = n;
+	}
+}
+
+// Keep track of move offsets
+static int8_t deltas[4];
+
+void action_list_init(const uint8_t new_board_size) {
+	board_size = new_board_size;
+	deltas[0] = +board_size;
+	deltas[1] = -board_size;
+	deltas[2] = -1;
+	deltas[3] = +1;
+}
+
+action_list_t *action_list_generate(void) {
+
+	action_list_t *result = NULL;
+
+	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));
+
+	// Step across the board
+	for (uint8_t row = 0; row < board_size; row++) {
+		for (uint8_t col = 0; col < board_size; col++) {
+			// We'll need these at various points, the location of this
+			// square and the maximum number of stones we could pick up
+			const uint8_t loc = THE_COORDS(col, row);
+			const uint8_t count = (COUNT_AT(loc) > board_size) ? board_size : COUNT_AT(loc);
+			// Only try moves after CPS
+			if (count && ((colours[loc] & 1) == current_colour) && ply>2) {
+				// There are stones, let's try moving them
+
+				// Pre-compute end-stops
+				uint8_t end_stops[4][2]; // (end, not_crush)
+
+				// These are upper bounds, not counting walls and such. UP DOWN LEFT RIGHT
+				end_stops[0][0] = (board_size - row - 1 > count) ? count : board_size - row - 1;
+				end_stops[1][0] = (row > count) ? count : row;
+				end_stops[2][0] = (col > count) ? count : col;
+				end_stops[3][0] = (board_size - col - 1 > count) ? count : board_size - col - 1;
+
+				// Now we check for caps and walls
+				const uint8_t cap_top = STONE_AT(loc) == STONE_CAPSTONE;
+				for (uint8_t d = 0; d < board_size-1; 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]++;
+					}
+				}
+				/*
+				 * For each direction, generate all possible ordered integer
+				 * partitions of 1 ≤ num ≤ count whose number of summands is
+				 * exactly 1 ≤ summands ≤ min(end_stops[dir], num) -- we write
+				 * summands as steps
+				 */
+				for (enum MOVE_DIRECTION dir = M_UP; dir <= M_RIGHT; dir++) {
+					uint8_t gaps, t, idx, mask;
+					for (uint8_t num = 1; num <= count; num++) {
+						for (uint8_t steps = 1;
+								 steps <= end_stops[dir][0] && steps <= num;
+								 steps++) {
+							// TODO: Generalise to board_size!
+							gaps = 0x07 >> (board_size-steps-1);
+							// 0b0000[0111] because 4-1=3 and 5-1=4
+							do  {
+								/*
+								 * We skip the partition if it calls for multiple stones at
+								 * the end with a crush.
+								 */
+								const uint8_t last_drop_check =
+									(num > 1) ? (gaps & 1<<(num - 2)) : 1;
+								if (end_stops[dir][1] || last_drop_check)
+									result = action_list_prepend(result, A_MOVE, loc, (dir<<4) | num, gaps);
+								/*
+								 * 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, generate placements
+				if (flat) {
+					result = action_list_prepend(result, A_PLACE, loc, STONE_FLAT, 0);
+					if (standing)
+						result = action_list_prepend(result, A_PLACE, loc, STONE_STANDING, 0);
+				}
+				if (cap)
+					result = action_list_prepend(result, A_PLACE, loc, STONE_CAPSTONE, 0);
+			}
+		}
+	}
+	return result;
+}
+
+void action_take(action_list_t *action) {
+	const uint8_t loc = action->loc;
+	if (action->type == A_PLACE) {
+		const uint8_t black = (ply&1);
+		switch (action->data0) {
+			STONE_FLAT: {
+				if (black) black_count--;
+				else white_count--;
+				colours[loc] = current_colour;
+				celldat[loc] = NUM_INC | STONE_FLAT;
+				break;
+			}
+			STONE_STANDING:  {
+				if (black) black_count--;
+				else white_count--;
+				colours[loc] = current_colour;
+				celldat[loc] = NUM_INC | STONE_STANDING;
+				break;
+			}
+			default: {
+				if (black) black_count &= 127;
+				else white_count &= 127;
+				colours[loc] = current_colour;
+				celldat[loc] = NUM_INC | STONE_CAPSTONE;
+				break;
+			}
+		}
+	} else {
+		uint8_t drops[board_size]; // we only ever need board_size-1 in
+															 // drops actually, the last spot is to
+															 // skip a bounds check at (*) later
+
+		const uint8_t gaps = action->data0,
+			num = action->data1 & 0x0F, // unpack
+			dir = action->data1 & 0xF0;
+		uint8_t steps, mask;
+		// Translate to a drop sequence
+		drops[0] = 1; mask = 1; steps = 0;
+		for (uint8_t d = 0; d + 1 < num; d++) {
+			if (gaps & mask) {
+				steps++;
+				drops[steps] = 1; // (*) no bounds check
+			} else {
+				drops[steps] += 1;
+			}
+			mask <<= 1;
+		}
+		// Push stones onto subesquent stack
+		uint8_t j = num;
+		for (uint8_t k = 0; k <= steps; k++) {
+			j -= drops[k];
+			push_stones(loc+(k+1)*deltas[dir],
+									drops[k],
+									(colours[loc] >> j) & (0xFFFF >> (0x10 - drops[k])),
+									(k == steps - 1) ? STONE_AT(loc) : STONE_FLAT);
+		}
+		// Drop them from the source
+		colours[loc] >>= num;
+		const uint8_t dec_count = celldat[loc] - (num << NUM_SHIFT);
+		celldat[loc] = dec_count & NUM_MASK;
+	}
+	// Always
+	next_ply();
+};
+
+void action_undo(action_list_t *action) {
+	const uint8_t loc = action->loc;
+	if (action->type == A_PLACE) {
+		const uint8_t black = (ply&1);
+		celldat[loc] = 0;
+		if (action->data0 == STONE_CAPSTONE) {
+			if (black) black_count |= 128;
+			else white_count |= 128;
+		} else {
+			if (black) black_count++;
+			else white_count++;
+		}
+	} else {
+		// TODO ???
+	}
+	previous_ply();
+};
+
+// ===================================================================
+// Helper method implementations
+// ===================================================================
+
+static inline action_list_t *
+action_list_prepend(action_list_t *list, const enum A_TYPE type,
+										const uint8_t loc, const uint8_t data0,
+										const uint8_t data1) {
+	action_list_t *new = malloc(sizeof(action_list_t));
+	// TODO: trap errno
+	new->loc = loc;
+	new->next = list;
+	new->data0 = data0;
+	new->data1 = data1;
+	return new;
+}
+
+static inline 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 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);
+}