diff options
Diffstat (limited to 'board.cpp')
-rw-r--r-- | board.cpp | 200 |
1 files changed, 200 insertions, 0 deletions
diff --git a/board.cpp b/board.cpp new file mode 100644 index 0000000..3b59aad --- /dev/null +++ b/board.cpp @@ -0,0 +1,200 @@ +#include <cstring> +#include <cctype> +#include <cassert> +#include "board.h" + +using namespace std; + + +static optional<int> parsePosition(string_view str) { + if (str.size() != 2) return nullopt; + char a = toupper(str[0]), b = str[1]; + if (a < 'A' || a > 'Z') return nullopt; + if (b < '0' || b > '9') return nullopt; + return N * (N - (b - '0')) + a - 'A'; +} + +Move::Move(int from, int to) + : from(from), to(to) {} + +optional<Move> Move::parse(string_view str) { + if (str.size() != 5) return nullopt; + if (str[2] != '-' && str[2] != ' ') return nullopt; + + if (auto from = parsePosition(str.substr(0, 2))) { + if (auto to = parsePosition(str.substr(3, 2))) { + Move mv; + mv.from = *from; + mv.to = *to; + return mv; + } + } + + return nullopt; +} + +ostream& operator<<(ostream &os, const Move &mv) { + os << (char)('A' + mv.from % N) << (char)('0' + N - mv.from / N) + << '-' + << (char)('A' + mv.to % N) << (char)('0' + N - mv.to / N); + return os; +} + + +static int colour(uint8_t value) { + return value < 4; +} + +static int rotateIndex(int index) { + int x = index % N, y = index / N; + return N * x + N-1 - y; +} + +static int rotateIndex(int index, int nturns) { + for (int i = 0; i < nturns % 4; i++) { + index = rotateIndex(index); + } + return index; +} + + +Board::Board() {} + +Board Board::makeInitial() { + Board bd; + memset(bd.cells, EMPTY, N * N); + + for (int i = 0; i < 4; i++) { + bd.cells[rotateIndex(N/2 - 1, i)] = BLACK; + bd.cells[rotateIndex(N/2 + 0, i)] = BLACK; + bd.cells[rotateIndex(N/2 + 1, i)] = BLACK; + bd.cells[rotateIndex(N + N/2, i)] = BLACK; + + bd.cells[rotateIndex(BOARDMID - 2 * N, i)] = WHITE; + bd.cells[rotateIndex(BOARDMID - 1 * N, i)] = WHITE; + } + + bd.cells[BOARDMID] = KING; + return bd; +} + +bool Board::stoneFlankedH(int pos, uint8_t by) const { + return (cells[pos-1] == by || (pos-1 == BOARDMID && cells[BOARDMID] == EMPTY)) && + (cells[pos+1] == by || (pos+1 == BOARDMID && cells[BOARDMID] == EMPTY)); +} + +bool Board::stoneFlankedV(int pos, uint8_t by) const { + return (cells[pos-N] == by || (pos-N == BOARDMID && cells[BOARDMID] == EMPTY)) && + (cells[pos+N] == by || (pos+N == BOARDMID && cells[BOARDMID] == EMPTY)); +} + +bool Board::kingEncircled(int pos) const { + if (pos == BOARDMID) { + return cells[pos-1] == BLACK && cells[pos+1] == BLACK && + cells[pos-N] == BLACK && cells[pos+N] == BLACK; + } else if (pos == BOARDMID-1) { + return cells[pos-1] == BLACK && cells[pos-N] == BLACK && cells[pos+N] == BLACK; + } else if (pos == BOARDMID+1) { + return cells[pos+1] == BLACK && cells[pos-N] == BLACK && cells[pos+N] == BLACK; + } else if (pos == BOARDMID-N) { + return cells[pos-1] == BLACK && cells[pos+1] == BLACK && cells[pos-N] == BLACK; + } else if (pos == BOARDMID+N) { + return cells[pos-1] == BLACK && cells[pos+1] == BLACK && cells[pos+N] == BLACK; + } else { + int x = pos % N, y = pos / N; + return (x > 0 && x < N-1 && cells[pos-1] == BLACK && cells[pos+1] == BLACK) || + (y > 0 && y < N-1 && cells[pos-N] == BLACK && cells[pos+N] == BLACK); + } +} + +void Board::apply(Move mv) { + cells[mv.to] = cells[mv.from]; + cells[mv.from] = EMPTY; + int i = mv.to; + int x = i % N, y = i / N; + + if (x > 1 && cells[i-1] != EMPTY && colour(cells[i-1]) != colour(cells[i])) { + if (cells[i-1] == KING ? kingEncircled(i-1) : stoneFlankedH(i-1, cells[i])) { + cells[i-1] = EMPTY; + } + } + + if (y > 1 && cells[i-N] != EMPTY && colour(cells[i-N]) != colour(cells[i])) { + if (cells[i-N] == KING ? kingEncircled(i-N) : stoneFlankedV(i-N, cells[i])) { + cells[i-N] = EMPTY; + } + } + + if (x < N-2 && cells[i+1] != EMPTY && colour(cells[i+1]) != colour(cells[i])) { + if (cells[i+1] == KING ? kingEncircled(i+1) : stoneFlankedH(i+1, cells[i])) { + cells[i+1] = EMPTY; + } + } + + if (y < N-2 && cells[i+N] != EMPTY && colour(cells[i+N]) != colour(cells[i])) { + if (cells[i+N] == KING ? kingEncircled(i+N) : stoneFlankedV(i+N, cells[i])) { + cells[i+N] = EMPTY; + } + } +} + +int Board::applyCW(Move mv) { + // TODO: make more efficient + apply(mv); + return checkWin(); +} + +int Board::checkWin() const { + for (int x = 0; x < N; x++) if (cells[x] == KING) return 1; + for (int y = 0; y < N; y++) if (cells[N * y] == KING) return 1; + for (int x = 0; x < N; x++) if (cells[N * (N-1) + x] == KING) return 1; + for (int y = 0; y < N; y++) if (cells[N * y + N-1] == KING) return 1; + + for (int i = 0; i < N * N; i++) { + if (cells[i] == KING) return 0; + } + + return -1; +} + +bool Board::isValid(Move mv) const { + if (mv.from < 0 || mv.from >= N * N || mv.to < 0 || mv.to >= N * N) return false; + if (mv.from == mv.to) return false; + if (cells[mv.from] == EMPTY || cells[mv.to] != EMPTY) return false; + + if (mv.to == BOARDMID) return false; + + int x1 = mv.from % N, y1 = mv.from / N; + int x2 = mv.to % N, y2 = mv.to / N; + if (x1 != x2 && y1 != y2) return false; + + if (x1 == x2) { + int delta = y2 < y1 ? -1 : 1; + for (int y = y1 + delta; y != y2; y += delta) { + if (cells[N * y + x1] != EMPTY) return false; + } + } else { + int delta = x2 < x1 ? -1 : 1; + for (int x = x1 + delta; x != x2; x += delta) { + if (cells[N * y1 + x] != EMPTY) return false; + } + } + + return true; +} + +bool Board::isValid(Move mv, int player) const { + uint8_t mask = player == 1 ? WHITE|KING : BLACK; + return isValid(mv) && (cells[mv.from] & mask) != 0; +} + +ostream& operator<<(ostream &os, const Board &bd) { + for (int y = 0; y < N; y++) { + if (y != 0) os << '\n'; + for (int x = 0; x < N; x++) { + if (x != 0) os << ' '; + os << ".O#-X"[bd.cells[N*y+x]]; + } + } + return os; +} |