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 int8_t loc, const uint8_t data0,
										const uint8_t data1);

// ===================================================================
// 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(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 *result = NULL;

	const uint8_t black = (ply < 2) ? (ply==1) : (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 (int8_t row = board_size - 1; row > 0; row--) {
		for (int8_t col = board_size - 1; col > 0; col--) {
			// We'll need these at various points: the location of this
			// square and the maximum number of stones we could pick up
			const int8_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 (ply >= 2 && count && ((colours[loc] & 1) == current_colour)) {
				// 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 < 4; d++){
					const int8_t delta = deltas[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*delta);
						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++) {
					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!
							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 (end_stops[dir][1] || last_drop_check)
									result = action_list_prepend(result, A_MOVE, loc, 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))));
						}
					}
				}
			} else if (count == 0 && material) {
				// 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 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 &= 127;
				else white_count &= 127;
				colours[loc] = current_colour;
				celldat[loc] = NUM_INC | STONE_CAPSTONE;
				break;
			}
		}
	} else {
		const uint8_t gaps = action->data0,
			num = action->data1 & 0x0F, // unpack
			dir = action->data1 >> 4;
		int8_t delta = deltas[dir];

		// Unfortunately num == 1 is a special case
		if (num > 1) {
			uint8_t steps, mask = 1<<(num-2), gaps_prime = gaps;
			// Use the Kernighan method to count the set bits
			for (steps = 1; gaps_prime; steps++) gaps_prime &= gaps_prime - 1;
			// then from the destination to the source
			for (uint8_t d = 0; d + 1 <= num; d++) {
				// transfer the top colour
				colours[loc+steps*delta] <<= 1;
				colours[loc+steps*delta] |= colours[loc] & 1;
				colours[loc] >>= 1;
				// increase the stone count, copy top stone if appropriate
				celldat[loc+steps*delta] += NUM_INC;
				if (d==0) {
					celldat[loc+steps*delta] &= NUM_MASK;
					celldat[loc+steps*delta] |= STONE_AT(loc);
					celldat[loc] &= NUM_MASK;
					celldat[loc] |= STONE_FLAT; // this should be optimised out :)
				}
				// decrement the count, the top colour
				celldat[loc] -= NUM_INC;

				if (gaps & mask) steps--;
				mask >>= 1;
			}
		} else {
			// Oh well
			colours[loc+delta] <<= 1;
			colours[loc+delta] |= colours[loc] & 1;
			celldat[loc+delta] += NUM_INC;
			celldat[loc+delta] &= NUM_MASK;
			celldat[loc+delta] |= STONE_AT(loc);

			colours[loc] >>= 1;
			celldat[loc] &= NUM_MASK;
			celldat[loc] |= STONE_FLAT; // this should be optimised out :)
			celldat[loc] -= NUM_INC;
		}
	}
	// Next ply
	ply++;
	if (ply == 2) {
		current_colour = C_WHITE;
	} else {
		if (current_colour == C_BLACK) current_colour = C_WHITE;
		else current_colour = C_BLACK;
	}
}

void action_undo(action_list_t *action) {
	// Previous ply
	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;
	}

	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 |= 128;
			else white_count |= 128;
		} else {
			if (black) black_count++;
			else white_count++;
		}
	} else {
		// See action_take for comments, this is the time reversal
		const uint8_t gaps = action->data0,
			num = action->data1 & 0x0F, // unpack
			dir = action->data1 >> 4;
		const int8_t delta = deltas[dir];

		uint8_t steps = 1, mask = 1;
		if (num > 1) {
			for (uint8_t d = 0; d + 1 <= num; d++) {
				colours[loc] <<= 1;
				colours[loc] |= colours[loc+steps*delta] & 1;
				colours[loc+steps*delta] >>= 1;

				celldat[loc] += NUM_INC;
				if (d + 1 == num) {
					celldat[loc] &= NUM_MASK;
					celldat[loc] |= STONE_AT(loc+steps*delta);
					celldat[loc+steps*delta] &= NUM_MASK;
					celldat[loc+steps*delta] |= STONE_FLAT;
				}
				celldat[loc+steps*delta] -= NUM_INC;

				if (gaps & mask) steps++;
				mask <<= 1;
			}
		} else {
			colours[loc] <<= 1;
			colours[loc] |= colours[loc+delta] & 1;
			celldat[loc] += NUM_INC;
			celldat[loc] &= NUM_MASK;
			celldat[loc] |= STONE_AT(loc+delta);

			colours[loc+delta] >>= 1;
			celldat[loc+delta] &= NUM_MASK;
			celldat[loc+delta] |= STONE_FLAT;
			celldat[loc+delta] -= NUM_INC;
		}
	}
}

void action_to_ptn(action_list_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,
			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 = 0; d + 1 < 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 action_list_t *
action_list_prepend(action_list_t *list, const enum A_TYPE type,
										const int8_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->type = type;
	new->next = list;
	new->data0 = data0;
	new->data1 = data1;
	return new;
}