path: root/include/tak.c

/*
	This file is part of ct.

	This program is free software: you can redistribute it and/or modify
	it under the terms of the GNU General Public License as published by
	the Free Software Foundation, either version 3 of the License, or
	(at your option) any later version.

	This program is distributed in the hope that it will be useful, but
	WITHOUT ANY WARRANTY; without even the implied warranty of
	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
	General Public License for more details.

	You should have received a copy of the GNU General Public License
	along with ct. If not, see <https://www.gnu.org/licenses/>.
*/

#include "tak.h"

// ===================================================================
// Globals
// ===================================================================

enum WIN_TYPE won;
uint8_t board_size;
data_t celldat[36];
colour_stack_t colours[36];
enum COLOUR current_colour;
uint8_t white_count, black_count, ply;

// ===================================================================
// Helpers
// ===================================================================

#define NUM_SQUARES   (board_size * board_size)

// ===================================================================
// General state stuff
// ===================================================================

void
reset_state(const uint8_t new_board_size) {
	if (new_board_size == 6) {
		board_size = 6;
		white_count = 128 | 30;
		black_count = 128 | 30;
	} else {
		board_size = 5;
		white_count = 128 | 21;
		black_count = 128 | 21;
	}

	ply = 0;
	won = 0xFF; // i may live to regret this hack
	current_colour = C_BLACK;

	for (uint8_t k = 0; k < NUM_SQUARES; k++ ) {
		celldat[k] = 0;
	}
}

void
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;
	}
}

// ===================================================================
// Placing stones
// ===================================================================

enum ACT_RESULT
try_place(const int8_t location, const enum COLOUR colour,
					const enum STONE_VARIANT stone)
{
	// Game is over?
	if (won < 0xFF) return GAME_END;
	// Can't place on an occupied square
	if (COUNT_AT(location)) {
		return ACT_ILLEGAL;
	} else {
		switch (stone) {
			case STONE_STANDING:
				if (ply < 2) return ACT_ILLEGAL;
				// behold the magic GCC comment which defeates
				// -Wimplicit-fallthrough:
				// fall through
			case STONE_FLAT: {
				if (colour == C_BLACK) {
					if (black_count & 127) black_count--;
					else return ACT_ILLEGAL;
				} else {
					if (white_count & 127) white_count--;
					else return ACT_ILLEGAL;
				}
				break;
			}
			case STONE_CAPSTONE: {
				if (ply < 2) return ACT_ILLEGAL;
				if (colour == C_BLACK) {
					if (black_count & 128) black_count &= 127;
					else return ACT_ILLEGAL;
				} else {
					if (white_count & 128) white_count &= 127;
					else return ACT_ILLEGAL;
				}
				break;
			}
		}

		colours[location] = colour;
		celldat[location] = NUM_INC | stone;
		return ACT_OK;
	}
}

// ===================================================================
// Moving stacks
// ===================================================================

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

enum ACT_RESULT
try_move(const int8_t location, const enum MOVE_DIRECTION direction,
				 const uint8_t steps, const uint8_t drops[5]) {
	// Game is over?
	if (won < 0xFF) return GAME_END;
	// Can't do this
	if (steps == 0 || steps > board_size) return ACT_ILLEGAL;
	// Check for stones at all
	const uint8_t avail = COUNT_AT(location);
	if (avail == 0) return ACT_ILLEGAL;
	// Does the current player own the pile?
	if ((colours[location] & 1) != current_colour) return ACT_ILLEGAL;
	// Is the desired direction and count on the board?
	int8_t delta = 0;
	switch (direction) {
		case M_UP:    {
			delta = +board_size;
			if (location + delta * steps > NUM_SQUARES)
				return ACT_ILLEGAL;
			break;
		};
		case M_DOWN:  {
			delta = -board_size;
			if (location + delta * steps < 0)
				return ACT_ILLEGAL;
			break;
		};
		case M_RIGHT: {
			delta = +1;
			if ((location + steps * delta) / board_size
					> location / board_size)
				return ACT_ILLEGAL;
			break;
		};
		case M_LEFT:  {
			delta = -1;
			// We need the extra check for zero here because, irritatingly,
			// -1 / board_size == 1 / board_size
			if ((location + steps * delta < 0) ||
					((location + steps * delta) / board_size
					 < location / board_size))
				return ACT_ILLEGAL;
			break;
		};
	};

	// For every square in the direction
	uint8_t total = 0;
	for (uint8_t k = 0; k < steps; k++) {
		// Can't drop 0 anywhere because we're past the first square
		if (drops[k] == 0)
			return ACT_ILLEGAL;
		// Can't drop more than BOARD_SIZE stones in a square
		if (drops[k] > board_size)
			return ACT_ILLEGAL;
		// Check for overflows
		if (COUNT_AT(location+(k+1)*delta) + drops[k] > 0x0F)
			return ACT_OVERFLOW;
		// Check for capstone
		if (STONE_AT(location+(k+1)*delta) == STONE_CAPSTONE)
			return ACT_ILLEGAL;
		// Check for wall
		if ( (STONE_AT(location+(k+1)*delta) == STONE_STANDING)
				 // If not last drop, or not dropping just one, or not a cap
				 && ( (k+1 < steps)
							|| (drops[k] != 1)
							|| (STONE_AT(location) != STONE_CAPSTONE) )
				 )
			return ACT_ILLEGAL;
		total += drops[k];
	}

	// Can't ask to move 0, more than board_size, or stones available
	if ( (total == 0) || (total > board_size) || (total > avail) )
		return ACT_ILLEGAL;

	// Nothing illegal, do it. First we add the stones to the
	// destination squares
	uint8_t j = total;
	for (uint8_t k = 0; k < steps; k++) {
		j -= drops[k];
		push_stones(location+(k+1)*delta,
								drops[k],
								(colours[location] >> j) & (0xFFFF >> (0x10 - drops[k])),
								(k == steps - 1) ? STONE_AT(location) : STONE_FLAT);
	}
	// Then we drop them from the source
	colours[location] >>= total;
	const uint8_t dec_count = celldat[location] - (total << NUM_SHIFT);
	celldat[location] = dec_count & NUM_MASK;

	return ACT_OK;
}

// ===================================================================
// Checking win
// ===================================================================

// Check for the presence of a road connecting opposite sides
static enum WIN_TYPE
check_road_colour(const enum COLOUR colour) {
	int component[NUM_SQUARES], touching[NUM_SQUARES];

	/*
	  We're doing a poor version of a disjoint set data structure to
	  track and merge connected components. The array `component' stores
	  indices to the representative cells of each connected component. A
	  cell is representative if component[cell] = cell. We track only
	  whether representatives are touching sides, and do a 2-dimensional
	  DP approach to forming these from the board.

	  Note: we don't track the rank/size of each tree, because we're not
	  interested in good asymptotic complexity in the size of the board,
	  merely good performance for a single board size in practice. For
	  the same reason we also don't do path flattening/halving or
	  anything.
	*/
	for (int k=0; k<NUM_SQUARES; k++) {
		component[k] = k; // every square is in its own connected
											// component initially
		touching[k] = 0;  // and not connected to any sides
	}

	// touching is the bit mask for connectivity,
	// bottom | top | left | right
	//    1      2     4       8
	/*
	 * for (int k=0; k<board_size; k++) {
	 *	touching[THE_COORDS(k, 0)] = 1;
	 *	touching[THE_COORDS(k, board_size - 1)] = 2;
	 *	touching[THE_COORDS(0, k)] |= 4;
	 *	touching[THE_COORDS(board_size - 1, k)] |= 8;
	 * }
	 */

	int touch = 5;
	for (int row = 0; row < board_size; row++) {
		for (int col = 0; col < board_size; col++) {
			const int cur = THE_COORDS(col, row);
			if (COUNT_AT(cur)
			    && (colours[cur] & 1) == colour
			    && STONE_AT(cur) != STONE_STANDING) {

				// do we have any neighbours to the left and below?
				const int left_neighbour = ((cur % board_size > 0)
				                            && (COUNT_AT(cur - 1)) // wont ever be out of bounds
				                            && ((colours[cur - 1] & 1) == colour)
				                            && (STONE_AT(cur - 1) != STONE_STANDING));

				const int lowr_neighbour = ((cur >= board_size)
				                           && (COUNT_AT(cur - board_size))
				                           && ((colours[cur - board_size] & 1) == colour)
				                           && (STONE_AT(cur - board_size) != STONE_STANDING));

				// always take the component of the lower neighbour if
				// possible, failing that take the left neighbour, otherwise
				// we're not yet connected, so update our own component.
				if (lowr_neighbour) {
					// look up the root of the lower neighbour
					int root = cur - board_size;
					while (root != component[root])
						root = component[root];
					// join the set
					component[cur] = root;
					if (touch) {
						// something new
						touching[root] |= touch;
						// are we done?
						if ( (touching[root] & 0x3) == 0x3 || (touching[root] & 0xC) == 0xC)
							return (colour == C_BLACK) ? WIN_ROAD_BLACK : WIN_ROAD_WHITE;
					}
					// if we also have a left neighbour then we should `merge'
					// sets, and here we assume that the left neighbour set is
					// always smaller (may not be) for the direction of merge
					if (left_neighbour) {
						int left_root = cur - 1;
						while (left_root != component[left_root])
							left_root = component[left_root];
						// merge
						const int left_touch = touching[left_root];
						if (left_touch) {
							touching[root] |= left_touch;
							if ( (touching[root] & 0x3) == 0x3 || (touching[root] & 0xC) == 0xC)
								return (colour == C_BLACK) ? WIN_ROAD_BLACK : WIN_ROAD_WHITE;
						}
						component[left_root] = root;
					}
				} else if (left_neighbour) {
					int root = cur - 1;
					while (root != component[root])
						root = component[root];
					component[cur] = root;
					if (touch) {
						touching[root] |= touch;
						if ( (touching[root] & 0x3) == 0x3 || (touching[root] & 0xC) == 0xC)
							return (colour == C_BLACK) ? WIN_ROAD_BLACK : WIN_ROAD_WHITE;
					}
				} else if (touch) {
					// we had no left or lower neighbour, so we're on our own
					touching[cur] = touch;
				}
			}
			if (col + 2 == board_size) touch |= 8;
			else touch &= 0x3;
		}
		if (row + 2 == board_size) touch = 6;
		else touch = 4;
	}

	/*
	 * // Prime the search, we create connected components for all cells
	 * // that match COLOUR and aren't STANDING on the boundaries
	 * if ( COUNT_AT(0) && (colours[0] & 1) == colour
	 *      && STONE_AT(0) != STONE_STANDING ) {
	 *	connect[comp_idx++] = 3;
	 * }
	 * for (uint8_t k=1; k<board_size; k++) {
	 *	if ( COUNT_AT(THE_COORDS(k, 0))
	 *			 && (colours[THE_COORDS(k, 0)] & 1) == colour
	 *			 && STONE_AT(THE_COORDS(k, 0)) != STONE_STANDING ) {
	 *		dfs_stack[dfs_pntr++] = THE_COORDS(k, 0);
	 *		component[THE_COORDS(k, 0)] = comp_idx;
	 *		connect[comp_idx++] = 1;
	 *	}
	 *	if ( COUNT_AT(THE_COORDS(0, k))
	 *			 && (colours[THE_COORDS(0, k)] & 1) == colour
	 *			 && STONE_AT(THE_COORDS(0, k)) != STONE_STANDING ) {
	 *		dfs_stack[dfs_pntr++] = THE_COORDS(0, k);
	 *		component[THE_COORDS(0, k)] = comp_idx;
	 *		connect[comp_idx++] = 2;
	 *	}
	 * }
	 *
	 * while (dfs_pntr > 0) {
	 *	const uint8_t cur = dfs_stack[--dfs_pntr];
	 *	// Made it to the other side?
	 *	if (   (cur >= board_size * (board_size - 1) && bottoms[cur])
	 *	    || (cur % board_size + 1 == board_size && lefts[cur])     )
	 *		{
	 *			return (colour == C_BLACK) ? WIN_ROAD_BLACK : WIN_ROAD_WHITE;
	 *		}
	 *
	 *	// Check the four neighbours of this cell, provided they exist,
	 *	// are inhabited, and are of the appropriate colour
	 *
	 *	// Direction: > (same row)
	 *	if ( ((cur % board_size) + 1 < board_size)
	 *			 && (COUNT_AT(cur + 1)) // wont ever be out of bounds
	 *			 && ((colours[cur+1] & 1) == colour)
	 *			 && ((seen[cur+1]) == 0)
	 *			 && (STONE_AT(cur+1) != STONE_STANDING)) {
	 *		dfs_stack[dfs_pntr++] = cur + 1;
	 *		seen[cur+1] = 1;
	 *		lefts[cur+1] = lefts[cur];
	 *		bottoms[cur+1] = bottoms[cur];
	 *	}
	 *
	 *	// Direction: <  (same row)
	 *	if ( (cur % board_size > 0)
	 *			 && (COUNT_AT(cur - 1)) // wont ever be out of bounds
	 *			 && ((colours[cur-1] & 1) == colour)
	 *			 && ((seen[cur-1]) == 0)
	 *			 && (STONE_AT(cur-1) != STONE_STANDING)) {
	 *		dfs_stack[dfs_pntr++] = cur - 1;
	 *		seen[cur - 1] = 1;
	 *		lefts[cur-1] = lefts[cur];
	 *		bottoms[cur-1] = bottoms[cur];
	 *	}
	 *
	 *	// Direction: +
	 *	if ( (cur + board_size < NUM_SQUARES)
	 *			 && (COUNT_AT(cur + board_size))
	 *			 && ((colours[cur+board_size] & 1) == colour)
	 *			 && ((seen[cur+board_size]) == 0)
	 *			 && (STONE_AT(cur+board_size) != STONE_STANDING)) {
	 *		dfs_stack[dfs_pntr++] = cur + board_size;
	 *		seen[cur+board_size] = 1;
	 *		lefts[cur+board_size] = lefts[cur];
	 *		bottoms[cur+board_size] = bottoms[cur];
	 *	}
	 *
	 *	// Direction: -
	 *	if ( (cur >= board_size)
	 *			 && (COUNT_AT(cur - board_size))
	 *			 && ((colours[cur-board_size] & 1) == colour)
	 *			 && ((seen[cur-board_size]) == 0)
	 *			 && (STONE_AT(cur-board_size) != STONE_STANDING)) {
	 *		dfs_stack[dfs_pntr++] = cur - board_size;
	 *		seen[cur-board_size] = 1;
	 *		lefts[cur-board_size] = lefts[cur];
	 *		bottoms[cur-board_size] = bottoms[cur];
	 *	}
	 * }
	 */

	return 0xFF;
}

enum WIN_TYPE
check_win(void) {
	// Road?
	enum WIN_TYPE rb, rw;
	rb = check_road_colour(C_BLACK);
	rw = check_road_colour(C_WHITE);

	if (rb == WIN_ROAD_BLACK && rw == WIN_ROAD_WHITE) {
		return (ply & 1) ? rb : rw; // Dragons
	} else if (rw == WIN_ROAD_WHITE) {
		return rw;
	} else if (rb == WIN_ROAD_BLACK) {
		return rb;
	}

	// Do we do a flat count?
	int8_t total = 0, board_full = 1;
	for (uint8_t k = 0; k < NUM_SQUARES; k++) {
		if (COUNT_AT(k) == 0) {
			board_full = 0;
		} else if (STONE_AT(k) == STONE_FLAT) {
			total += ((colours[k] & 1) == C_BLACK) ? +1 : -1 ;
		}
	}
	if (black_count == 0 || white_count == 0 || board_full) {
		// Decide based on count
		if (total > 0)  return WIN_FLAT_BLACK;
		else if (total < 0) return WIN_FLAT_WHITE;
		else return WIN_DRAW;
	}

	return 0xFF;
}
// ===================================================================
// PTN place parser
// ===================================================================

#define NULL 0

#define ASSERT_NONEMPTY {															\
		if (ptn == NULL || *ptn == 0) return PTN_INVALID;	\
	}

#define ASSERT_MORE { if (*ptn == 0) return PTN_INVALID; }

enum PTN_RESULT
parse_place(char *ptn, uint8_t *out_location,
						enum STONE_VARIANT *out_stone) {

	ASSERT_NONEMPTY;

	*out_stone = STONE_FLAT;
	switch (*ptn) {
		case 'C' : { ptn++; *out_stone = STONE_CAPSTONE; break; };
		case 'S' : { ptn++; *out_stone = STONE_STANDING; break; };
		case 'F' : { ptn++; break; };
	}

	ASSERT_MORE;

	if ( (*ptn < 'a') || (*ptn > '`' + board_size) ) return PTN_INVALID;
	*out_location = *ptn - 'a';

	ptn++; ASSERT_MORE;

	if ( (*ptn < '1') || (*ptn > board_size + '0') ) return PTN_INVALID;
	*out_location += board_size * (*ptn - '1');

	if (*(++ptn) > 0) return PTN_INVALID;

	return PTN_OK;
}

// ===================================================================
// PTN move parser
// ===================================================================

enum PTN_RESULT
parse_move(char *ptn, uint8_t *out_location,
					 enum MOVE_DIRECTION *out_direction,
					 uint8_t *out_steps, uint8_t out_drops[5]) {

	ASSERT_NONEMPTY;

	uint8_t picked_up = 1;

	// Optionally indicate how many stones picked up
	if ( (*ptn >= '1') && (*ptn <= '0' + board_size)) {
		picked_up = *ptn - '0';
		ptn++; ASSERT_MORE;
	}

	// column must be on the board
	if ( (*ptn < 'a') || (*ptn > '`' + board_size) ) return PTN_INVALID;
	*out_location = *ptn - 'a';

	ptn++; ASSERT_MORE;

	// row must be on the board
	if ( (*ptn < '1') || (*ptn > board_size + '0') ) return PTN_INVALID;
	*out_location += board_size * (*ptn - '1');

	ptn++; ASSERT_MORE;

	// valid direction
	switch (*ptn) {
		case '+': { *out_direction = M_UP;    break; }
		case '-': { *out_direction = M_DOWN;  break; }
		case '<': { *out_direction = M_LEFT;  break; }
		case '>': { *out_direction = M_RIGHT; break; }
		default: return PTN_INVALID;
	}

	// Handle the case 'n<column><row><direction>' as
	// 'n<column><row><direction>n' for convenience, if n is omitted
	// assume n = 1
	ptn++;
	if (*ptn == 0) {
		*out_steps = 1;
		out_drops[0] = picked_up;
		return PTN_OK;
	}

	// Parse the drops in each subsequent square
	*out_steps = 0;
	uint8_t total = 0;
	while (*ptn) {
		// can't drop more than the carry limit, or less than 1
		if ( (*ptn < '1') || (*ptn > '0' + board_size) )
			return PTN_INVALID;

		// can't move more than the size of the board in any direction
		if ( (*out_steps + 1 >= board_size) && *ptn)
			return PTN_INVALID;

		out_drops[*out_steps] = *ptn - '0';
		total += out_drops[*out_steps];
		*out_steps += 1;
		ptn++;
	}

	// Mismatch between number of stones picked up and total dropped
	if ( total != picked_up ) return PTN_INVALID;

	return PTN_OK;
}

// ===================================================================
// Generate PTN for place
// ===================================================================

void
generate_place(const uint8_t in_location,
							 const enum STONE_VARIANT in_stone, char out_ptn[4]) {
	switch (in_stone) {
		case STONE_FLAT: { break; }
		case STONE_STANDING: { *out_ptn = 'S'; out_ptn++; break; }
		case STONE_CAPSTONE: { *out_ptn = 'C'; out_ptn++; break; }
	}
	*out_ptn = 'a' + (in_location % board_size); out_ptn++;
	*out_ptn = '1' + (in_location / board_size); out_ptn++;
	*out_ptn = 0;
}

// ===================================================================
// Generate PTN for move
// ===================================================================

void
generate_move(const uint8_t in_location,
							const enum MOVE_DIRECTION in_direction,
							const uint8_t in_steps, const uint8_t in_drops[5],
							char out_ptn[10]) {
	uint8_t total = 0;
	for (uint8_t k = 0; k<in_steps; k++) total+=in_drops[k];
	if (total > 1) {
		*out_ptn = '0' + total; out_ptn++;
	}

	*out_ptn = 'a' + (in_location % board_size); out_ptn++;
	*out_ptn = '1' + (in_location / board_size); out_ptn++;

	switch (in_direction) {
		case M_UP:    { *out_ptn = '+'; break; }
		case M_DOWN:  { *out_ptn = '-'; break; }
		case M_LEFT:  { *out_ptn = '<'; break; }
		case M_RIGHT: { *out_ptn = '>'; break; }
	}; out_ptn++;

	for (uint8_t k = 0; (total > 1) && (k < in_steps); k++) {
		*out_ptn = '0' + in_drops[k]; out_ptn++;
	}

	*out_ptn = 0;
}

// ===================================================================
// Driver
// ===================================================================

static uint8_t
is_not_placement(char *ptn) {
	if (ptn == 0) return 0;
	for (;;ptn++) {
		switch (*ptn) {
			case '+':
			case '-':
			case '>':
			case '<': return 1;
			case 0:   return 0;
		}
	}
}

enum ACT_RESULT
do_ptn(char *ptn) {
	// Game over?
	if (won < 0xFF) return GAME_END;

	enum PTN_RESULT ptn_res;
	enum ACT_RESULT act_res;
	uint8_t location;

	// Placing or moving?
	if (is_not_placement(ptn)) {
		uint8_t steps, drops[5];
		enum MOVE_DIRECTION direction;
		// Parse it as a move
		ptn_res = parse_move(ptn, &location, &direction, &steps, drops);
		// If valid PTN, try to do it
		if (ptn_res == PTN_OK) {
			if (ply < 2) return ACT_ILLEGAL;
			act_res = try_move(location, direction, steps, drops);
		} else {
			return ACT_INVALID_PTN;
		}
	} else {
		// It was not a move
		enum STONE_VARIANT stone;
		// Was it a valid placement?
		ptn_res = parse_place(ptn, &location, &stone);
		// If so, try it
		if (ptn_res == PTN_OK)
			act_res = try_place(location, current_colour, stone);
		else
			return ACT_INVALID_PTN;
	}
	// A valid ply occured
	if (act_res == ACT_OK) {
		// Don't bother checking that the game was won early on, could be
		// more conservative here :)
		if (ply >= board_size) {
			won = check_win();
			if (won < 0xFF) {
				// Winning move, but no need to update current colour
				ply++;
				return GAME_END;
			}
		}
		// Only step if the game isn't over yet
		next_ply();
	}
	return act_res;
}