Storing best moves!

1 files changed, 404 insertions, 0 deletions

diff --git a/include/actions.c b/include/actions.c
new file mode 100644
index 0000000..9b3534b
--- /dev/null
+++ b/include/actions.c
@@ -0,0 +1,404 @@
+#include "actions.h"
+
+// ===================================================================
+// Helper method declarations
+// ===================================================================
+
+#define DANGER_MIN(a,b) (((a)<(b))?(a):(b))
+
+#define CLR_STONE NUM_MASK
+
+#define TYPE_SHIFT  24
+#define LOC_SHIFT   16
+#define DATA0_SHIFT  8
+
+#define GET_TYPE(a)  (enum A_TYPE)((a)>>TYPE_SHIFT)
+#define GET_LOC(a)   (int8_t)(((a)>>LOC_SHIFT) & 0xFF)
+#define GET_DATA0(a) (uint8_t)(((a)>>DATA0_SHIFT) & 0xFF)
+#define GET_DATA1(a) (uint8_t)((a) & 0xFF)
+
+static inline void
+list_append(action_list_t *list, const enum A_TYPE type,
+						const int8_t loc, const uint8_t data0,
+						const uint8_t data1);
+
+static inline void
+inline_next_ply(void);
+
+static inline void
+inline_prev_ply(void);
+
+// ===================================================================
+// Exported method implementations
+// ===================================================================
+
+int action_move_to_front(const action_t action,
+												 action_list_t *list) {
+	action_node_t *n = list->head;
+
+	// TODO: what if it's not in the list?
+
+	while (n) {
+		if (n->action == action) {
+			const action_t t = list->head->action;
+			list->head->action = action;
+			n->action = t;
+			return EXIT_SUCCESS;
+		}
+		n = n->next;
+	}
+
+	return EXIT_FAILURE;
+}
+
+
+void action_list_free(action_list_t *list) {
+	if (list) {
+		action_node_t *n = list->head, *nn;
+		while (n) {
+			nn = n->next;
+			free(n);
+			n = nn;
+		}
+		free(list);
+	}
+}
+
+// Keep track of move offsets
+static int8_t deltas[4];
+
+void action_list_init(void) {
+	deltas[0] = +board_size;
+	deltas[1] = -board_size;
+	deltas[2] = -1;
+	deltas[3] = +1;
+}
+
+action_list_t *action_list_generate(void) {
+	action_list_t *list = malloc(sizeof(struct action_list_s));
+	// TODO: trap errno
+	list->length = 0;
+	list->head = NULL;
+
+	/*
+	 * The check for whether it's a black piece to be played is actually
+	 *     black = (ply < 2) ? (ply==1) : (ply & 1),
+	 * but material will always be sufficient in ply < 2 so we might as
+	 * well save on the conditional.
+	 */
+
+	const uint8_t material = (ply & 1) ? black_count : white_count,
+		flat = material & 0x7F,
+		cap = ((ply >= 2) && (material & 0x80)),
+		standing = ((ply >= 2) && flat);
+
+	// Step across the board
+	for (int row = 0; row < board_size; row++) {
+		for (int 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 int loc = THE_COORDS(col, row);
+			const uint8_t count = DANGER_MIN(COUNT_AT(loc), board_size);
+
+			// Only try moves after CPS and if the colour is correct
+			if (count) {
+				if (ply >= 2 && ((colours[loc] & 1) == current_colour)) {
+
+					// Pre-compute end-stops and crushes
+					uint8_t end_stops[4], crushes[4] = {0, 0, 0, 0};
+
+					// These are upper bounds, not counting walls and such.
+					// UP DOWN LEFT RIGHT
+					end_stops[0] = DANGER_MIN(board_size - row - 1, count);
+					end_stops[1] = DANGER_MIN(row, count);
+					end_stops[2] = DANGER_MIN(col, count);
+					end_stops[3] = DANGER_MIN(board_size - col - 1, count);
+
+					// Now we check for caps and walls
+					const uint8_t cap_top = STONE_AT(loc) == STONE_CAPSTONE;
+					for (int d = 0; d < 4; d++){
+						const int delta = deltas[d];
+						const int stop = end_stops[d];
+						end_stops[d] = 0;
+						for (int k = 1; k <= stop; k++) {
+							const enum STONE_VARIANT stone = STONE_AT(loc+k*delta);
+							if (stone == STONE_STANDING) {
+								if (cap_top) {
+									crushes[d] = 0xFF;
+									end_stops[d]++;
+								}
+								break;
+							} else if (stone == STONE_CAPSTONE) {
+								break;
+							}
+							end_stops[d]++;
+						}
+					}
+					/*
+					 * 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++) {
+						for (uint8_t num = 1; num <= count; num++) {
+							for (uint8_t steps = 1;
+									 steps <= end_stops[dir] && steps <= num;
+									 steps++) {
+								// TODO: Generalise to board_size!
+								uint8_t 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 (crushes[dir] == 0 || last_drop_check) {
+										// We have to record a crush!
+										const uint8_t crush =
+											(steps == end_stops[dir]) && crushes[dir];
+										// Store the move
+
+										list_append(list, A_MOVE, loc,
+																(crush << 7) | gaps,
+																(dir<<4) | num);
+									}
+									/*
+									 * 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
+									 */
+									uint8_t t = (gaps | (gaps - 1));
+									gaps = (t + 1)
+										| (((~t & -~t) - 1) >> (__builtin_ctz(gaps) + 1));
+								} while (gaps && (gaps + 1 <= (1 << (num - 1))));
+							}
+						}
+					}
+				}
+			} // end of if (count) { ... }
+			else if (material) {
+				// Empty square, generate placements
+				if (flat) {
+					list_append(list, A_PLACE, loc, STONE_FLAT, 0);
+					if (standing)
+						list_append(list, A_PLACE, loc, STONE_STANDING,0);
+				}
+				if (cap)
+					list_append(list, A_PLACE, loc, STONE_CAPSTONE, 0);
+			}
+		}
+	}
+	return list;
+}
+
+void action_take(const action_t action) {
+	const int8_t loc = GET_LOC(action);
+	if (GET_TYPE(action) == A_PLACE) {
+		const uint8_t black = (current_colour == C_BLACK);
+		switch (GET_DATA0(action)) {
+			case STONE_FLAT: {
+				if (black) black_count--;
+				else white_count--;
+				colours[loc] = current_colour;
+				celldat[loc] = NUM_INC | STONE_FLAT;
+				break;
+			}
+			case 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 &= 0x7F;
+				else white_count &= 0x7F;
+				colours[loc] = current_colour;
+				celldat[loc] = NUM_INC | STONE_CAPSTONE;
+				break;
+			}
+		}
+	} else {
+		 // not interested in whether we crushed, it will work out by
+		 // anyway because we overwrite the top stone type. See (*) later
+		 // for when we do need to know.
+		const uint8_t gaps = GET_DATA0(action) & 0x7F,
+			num = GET_DATA1(action) & 0x0F, // unpack
+			dir = GET_DATA1(action) >> 4;
+		int8_t delta = deltas[dir];
+
+		// Use the Kernighan method to count the set bits
+		int8_t steps = 1;
+		for (uint8_t _gaps = gaps; _gaps; steps++) _gaps &= _gaps - 1;
+
+		// Move top stone type to destination
+		celldat[loc+steps*delta] &= CLR_STONE; // necessary for crushing
+		celldat[loc+steps*delta] |= STONE_AT(loc);
+		celldat[loc] &= CLR_STONE;
+		celldat[loc] |= STONE_FLAT; // should be optimised out
+
+		uint8_t total = 1, gap_bit = 1 << (num - 2); // it's not important
+																								 // what negative
+																								 // shifts do here, we
+																								 // don't use gap_bit
+																								 // if num < 2
+		// move stuff starting at destination
+		for (uint8_t d = 1; d < num; d++, total++, gap_bit >>= 1) {
+			// We took a step, move everything over so far
+			if (gaps & gap_bit) {
+				colours[loc+steps*delta] <<= total;
+				colours[loc+steps*delta] |= colours[loc] & ((1 << total) - 1);
+				colours[loc] >>= total;
+				celldat[loc+steps*delta] += total*NUM_INC;
+				celldat[loc] -= total*NUM_INC;
+				// Reset for next step
+				total = 0;
+				steps--;
+			}
+		}
+		// Move what remains (steps == 1 here always, so we simplify)
+		colours[loc+delta] <<= total;
+		colours[loc+delta] |= colours[loc] & ((1 << total) - 1);
+		colours[loc] >>= total;
+		celldat[loc+delta] += total*NUM_INC;
+		celldat[loc] -= total*NUM_INC;
+	}
+	// Next ply
+	inline_next_ply();
+}
+
+void action_undo(const action_t action) {
+	// Previous ply
+	inline_prev_ply();
+
+	const int8_t loc = GET_LOC(action);
+	if (GET_TYPE(action) == A_PLACE) {
+		const uint8_t black = (current_colour == C_BLACK);
+		celldat[loc] = 0;
+		if (GET_DATA0(action) == STONE_CAPSTONE) {
+			if (black) black_count |= 0x80;
+			else white_count |= 0x80;
+		} else {
+			if (black) black_count++;
+			else white_count++;
+		}
+	} else {
+		// See action_take for comments, this is the time reversal, but
+		// there is one caveat -- undoing a crush! (*)
+		const uint8_t gaps = GET_DATA0(action) & 0x7F,
+			crush = GET_DATA0(action) & 0x80,
+			num = GET_DATA1(action) & 0x0F,
+			dir = GET_DATA1(action) >> 4;
+		const int8_t delta = deltas[dir];
+
+		int8_t steps = 1;
+		uint8_t gap_bit = 1, total = 1;
+		for (int8_t d = 1; d < num; d++, total++, gap_bit <<= 1) {
+			if (gaps & gap_bit) {
+				colours[loc] <<= total;
+				colours[loc] |= colours[loc+steps*delta] & ((1 << total) - 1);
+				colours[loc+steps*delta] >>= total;
+				celldat[loc] += total*NUM_INC;
+				celldat[loc+steps*delta] -= total*NUM_INC;
+				total = 0;
+				steps++;
+			}
+		}
+		colours[loc] <<= total;
+		colours[loc] |= colours[loc+steps*delta] & ((1 << total) - 1);
+		colours[loc+steps*delta] >>= total;
+
+		celldat[loc] += total*NUM_INC;
+		// celldat[loc] &= CLR_STONE; is not necessary, as STONE_FLAT == 0
+		celldat[loc] |= STONE_AT(loc+steps*delta);
+		celldat[loc+steps*delta] -= total*NUM_INC;
+		celldat[loc+steps*delta] &= CLR_STONE;
+		if (crush) {
+			celldat[loc+steps*delta] |= STONE_STANDING;
+		} else {
+			celldat[loc+steps*delta] |= STONE_FLAT; // should be optimised out
+		}
+	}
+}
+
+void action_to_ptn(const action_t action, char* out_ptn) {
+	const int8_t loc = GET_LOC(action);
+	if (GET_TYPE(action) == A_PLACE) {
+		generate_place(loc, GET_DATA0(action), out_ptn);
+	} else {
+		const uint8_t gaps = GET_DATA0(action) & 0x7F,
+			num = GET_DATA1(action) & 0x0F, // unpack
+			dir = GET_DATA1(action) >> 4;
+
+		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 (**)
+		uint8_t mask = 1, steps = 0;
+		// Translate to a drop sequence
+		drops[0] = 1; mask = 1;
+		for (uint8_t d = 1; d < num; d++) {
+			if (gaps & mask) {
+				steps++;
+				drops[steps] = 1; // (**) no bounds check
+			} else {
+				drops[steps] += 1;
+			}
+			mask <<= 1;
+		}
+		generate_move(loc, dir, steps+1, drops, out_ptn);
+	}
+}
+
+// ===================================================================
+// Helper method implementations
+// ===================================================================
+
+static inline void
+list_append(action_list_t *list, const enum A_TYPE type,
+						const int8_t loc, const uint8_t data0,
+						const uint8_t data1) {
+	action_node_t *new = malloc(sizeof(action_list_t));
+	// TODO: trap errno
+
+	new->next = NULL;
+	new->action = (type << TYPE_SHIFT)
+		| (loc << LOC_SHIFT)
+		| (data0 << DATA0_SHIFT)
+		| data1;
+
+	if (list->length) {
+		list->tail->next = new;
+		list->tail = new;
+	} else {
+		list->head = new;
+		list->tail = new;
+	}
+
+	list->length++;
+}
+
+static inline void
+inline_next_ply(void) {
+	ply++;
+	if (ply == 2) {
+		current_colour = C_WHITE;
+	} else {
+		if (current_colour == C_BLACK) current_colour = C_WHITE;
+		else current_colour = C_BLACK;
+	}
+}
+
+static inline void
+inline_prev_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;
+	}
+}