path: root/include/action_list.c

#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);
}