/*
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 .
*/
#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 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 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' as
// 'nn' 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 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;
}