Storing best moves!

1 files changed, 0 insertions, 403 deletions

diff --git a/include/action_list.c b/include/action_list.c
deleted file mode 100644
index 30ca918..0000000
--- a/include/action_list.c
+++ /dev/null
@@ -1,403 +0,0 @@
-#include "action_list.h"
-
-// ===================================================================
-// Helper method declarations
-// ===================================================================
-
-#define DANGER_MIN(a,b) (((a)<(b))?(a):(b))
-
-#define CLR_STONE NUM_MASK
-
-static inline void
-action_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
-// ===================================================================
-
-/*
- * void action_list_ensure_at_front(const action_node_t *action,
- *																 const action_list_t *list) {
- *	action_node_t *copy = action_copy(action), *n = list->head, *nn;
- *	// ensure it's not there already
- *	while (n) {
- *		nn = n->next;
- *	}
- *
- *	copy->next = list->head;
- * }
- */
-
-action_node_t *action_copy(const action_node_t *action) {
-	action_node_t *copy = malloc(sizeof(struct action_node_s));
-	// TODO: trap
-	copy->data0 = action->data0;
-	copy->data1 = action->data1;
-	copy->loc = action->loc;
-	copy->type = action->type;
-	copy->next = NULL;
-	return copy;
-}
-
-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
-
-										action_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) {
-					action_list_append(list, A_PLACE, loc, STONE_FLAT, 0);
-					if (standing)
-						action_list_append(list, A_PLACE, loc, STONE_STANDING,0);
-				}
-				if (cap)
-					action_list_append(list, A_PLACE, loc, STONE_CAPSTONE, 0);
-			}
-		}
-	}
-	return list;
-}
-
-void action_take(action_node_t *action) {
-	const int8_t loc = action->loc;
-	if (action->type == A_PLACE) {
-		const uint8_t black = (current_colour == C_BLACK);
-		switch (action->data0) {
-			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 {
-		const uint8_t gaps = action->data0 & 0x7F, // 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.
-			num = action->data1 & 0x0F, // unpack
-			dir = action->data1 >> 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(action_node_t *action) {
-	// Previous ply
-	inline_prev_ply();
-
-	const int8_t loc = action->loc;
-	if (action->type == A_PLACE) {
-		const uint8_t black = (current_colour == C_BLACK);
-		celldat[loc] = 0;
-		if (action->data0 == 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 = action->data0 & 0x7F,
-			crush = action->data0 & 0x80,
-			num = action->data1 & 0x0F,
-			dir = action->data1 >> 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(action_node_t* action, char* out_ptn) {
-	const int8_t loc = action->loc;
-	if (action->type == A_PLACE) {
-		generate_place(loc, action->data0, out_ptn);
-	} else {
-		const uint8_t gaps = action->data0 & 0x7F,
-			num = action->data1 & 0x0F, // unpack
-			dir = action->data1 >> 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
-action_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->loc = loc;
-	new->type = type;
-	new->data0 = data0;
-	new->data1 = data1;
-	new->next = NULL;
-
-	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;
-	}
-}