Initial

9 files changed, 519 insertions, 0 deletions

diff --git a/.gitignore b/.gitignore
new file mode 100644
index 0000000..87e54c2
--- /dev/null
+++ b/.gitignore
@@ -0,0 +1,2 @@
+main
+*.o
diff --git a/Makefile b/Makefile
new file mode 100644
index 0000000..2be8c3c
--- /dev/null
+++ b/Makefile
@@ -0,0 +1,18 @@
+CXX = g++
+CXXFLAGS = -Wall -Wextra -O3 -std=c++17 -fwrapv -flto
+
+TARGET = main
+
+.PHONY: all clean
+
+all: $(TARGET)
+
+clean:
+	rm -f $(TARGET) *.o
+
+
+main: $(patsubst %.cpp,%.o,$(wildcard *.cpp))
+	$(CXX) $(CXXFLAGS) $^ -o $@ $(LDFLAGS)
+
+%.o: %.cpp $(wildcard *.h)
+	$(CXX) $(CXXFLAGS) -c -o $@ $<
diff --git a/ai_mm.cpp b/ai_mm.cpp
new file mode 100644
index 0000000..8d61e20
--- /dev/null
+++ b/ai_mm.cpp
@@ -0,0 +1,115 @@
+#include <climits>
+#include <cassert>
+#include "ai_mm.h"
+
+
+static const int mm_depth = 3;
+
+
+// Positive scores for white
+static int evaluate(const Board &bd, int win) {
+	const int large = 10000;
+
+	int score = -large;  // to counteract the +=large for KING
+	score += 8;  // to counteract the imbalance in white/black stones
+
+	for (int i = 0; i < N * N; i++) {
+		switch (bd.cells[i]) {
+			case EMPTY: break;
+			case WHITE: score += 1; break;
+			case KING: score += large; break;
+			case BLACK: score -= 1; break;
+		}
+	}
+
+	if (win == 1) score += large;
+
+	return score;
+}
+
+static int minimaxBlack(const Board &bd, int depth, int alpha, int beta);
+
+static int minimaxWhite(const Board &bd, int depth, int alpha, int beta) {
+	int win = bd.checkWin();
+	if (depth == 0 || win != 0) {
+		return evaluate(bd, win);
+	}
+
+	int bestValue = INT_MIN;
+
+	bd.forEachMove(1, [&bd, depth, &alpha, &beta, &bestValue](Move mv) {
+		Board bd2 = bd;
+		bd2.apply(mv);
+		int value = minimaxBlack(bd2, depth - 1, alpha, beta);
+		// cerr << string(6 - 2 * depth, ' ') << "mmW: " << mv << ": " << value << endl;
+		bestValue = max(bestValue, value);
+		alpha = max(alpha, bestValue);
+		if (beta <= alpha) return true;
+		return false;
+	});
+
+	return bestValue;
+}
+
+static int minimaxBlack(const Board &bd, int depth, int alpha, int beta) {
+	int win = bd.checkWin();
+	if (depth == 0 || win != 0) {
+		return evaluate(bd, win);
+	}
+
+	int bestValue = INT_MAX;
+
+	bd.forEachMove(-1, [&bd, depth, &alpha, &beta, &bestValue](Move mv) {
+		Board bd2 = bd;
+		bd2.apply(mv);
+		int value = minimaxWhite(bd2, depth - 1, alpha, beta);
+		// cerr << string(6 - 2 * depth, ' ') << "mmB: " << mv << ": " << value << endl;
+		bestValue = min(bestValue, value);
+		beta = min(beta, bestValue);
+		if (beta <= alpha) return true;
+		return false;
+	});
+
+	return bestValue;
+}
+
+static int minimaxGeneric(const Board &bd, int depth, int alpha, int beta, int player) {
+	if (player == 1) return minimaxWhite(bd, depth, alpha, beta);
+	else return minimaxBlack(bd, depth, alpha, beta);
+}
+
+Move AI::MM::findMove(const Board &bd, int player) {
+	/* {
+		int pl = player;
+		Board bd2 = bd;
+		Move mv;
+		mv = Move(3, 30); assert(bd2.isValid(mv, pl)); bd2.apply(mv); pl = -pl;
+		mv = Move(22, 21); assert(bd2.isValid(mv, pl)); bd2.apply(mv); pl = -pl;
+		cerr << bd2 << endl;
+		// mv = Move(77, 80); assert(bd2.isValid(mv, pl)); bd2.apply(mv); pl = -pl;
+		cerr << "## " << evaluate(bd2, 0) << endl;
+	} */
+
+	Move bestMove(-1, -1);
+	int bestScore = INT_MIN;
+	// 'bestScore', and 'score' below, have positive values good for 'player'.
+
+	// cerr << "MM::findMove(player=" << player << "):" << endl;
+	cerr << '[';
+
+	bd.forEachMove(player, [&bd, player, &bestScore, &bestMove](Move mv) {
+		Board bd2 = bd;
+		bd2.apply(mv);
+		int score = player * minimaxGeneric(bd2, mm_depth, INT_MIN, INT_MAX, -player);
+		// cerr << "fM: " << mv << ": " << score << endl;
+		cerr << score << ',';
+		if (score > bestScore) {
+			bestScore = score;
+			bestMove = mv;
+		}
+	});
+
+	cerr << ']' << endl;
+
+	return bestMove;
+}
diff --git a/ai_mm.h b/ai_mm.h
new file mode 100644
index 0000000..6304cbc
--- /dev/null
+++ b/ai_mm.h
@@ -0,0 +1,8 @@
+#pragma once
+
+#include "board.h"
+
+
+namespace AI::MM {
+	Move findMove(const Board &bd, int player);
+}
diff --git a/ai_rand.cpp b/ai_rand.cpp
new file mode 100644
index 0000000..9bd3eed
--- /dev/null
+++ b/ai_rand.cpp
@@ -0,0 +1,14 @@
+#include "ai_rand.h"
+
+
+Move AI::Rand::findMove(const Board &bd, int player) {
+	Move poss[N * N * N];
+	int nposs = 0;
+
+	bd.forEachMove(player, [&bd, &poss, &nposs](Move mv) {
+		poss[nposs++] = mv;
+	});
+
+	if (nposs == 0) return Move(-1, -1);
+	return poss[rand() % nposs];
+}
diff --git a/ai_rand.h b/ai_rand.h
new file mode 100644
index 0000000..defa011
--- /dev/null
+++ b/ai_rand.h
@@ -0,0 +1,8 @@
+#pragma once
+
+#include "board.h"
+
+
+namespace AI::Rand {
+	Move findMove(const Board &bd, int player);
+}
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;
+}
diff --git a/board.h b/board.h
new file mode 100644
index 0000000..1ab0646
--- /dev/null
+++ b/board.h
@@ -0,0 +1,78 @@
+#pragma once
+
+#include <iostream>
+#include <optional>
+#include <string_view>
+#include <cstdint>
+
+using namespace std;
+
+const int N = 9;
+const int BOARDMID = N * (N/2) + N/2;
+
+const uint8_t EMPTY = 0, WHITE = 1, KING = 2, BLACK = 4;
+
+
+struct Move {
+	int from, to;
+
+	Move() = default;
+	Move(int from, int to);
+
+	static optional<Move> parse(string_view str);
+};
+
+struct Board {
+	uint8_t cells[N * N];
+
+	static Board makeInitial();
+
+	void apply(Move mv);
+	int applyCW(Move mv);
+	int checkWin() const;  // 1=win white, -1=win black, 0=none yet
+
+	bool isValid(Move mv, int player) const;
+
+	// Calls the callback for each valid move of the specified player.
+	// F should have a signature compatible with bool F(Move mv).
+	// If the callback returns true, iteration is stopped.
+	// Callback should not modify this Board instance.
+	template <typename F>
+	void forEachMove(int player, F callback) const;
+
+private:
+	Board();
+
+	bool isValid(Move mv) const;
+	bool stoneFlankedH(int pos, uint8_t by) const;
+	bool stoneFlankedV(int pos, uint8_t by) const;
+	bool kingEncircled(int pos) const;
+};
+
+ostream& operator<<(ostream &os, const Move &mv);
+ostream& operator<<(ostream &os, const Board &bd);
+
+
+template <typename F>
+void Board::forEachMove(int player, F callback) const {
+	static const int deltas[4][2] = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};
+
+	for (int y = 0; y < N; y++)
+	for (int x = 0; x < N; x++) {
+		uint8_t v = cells[N * y + x];
+		if (player == 1 ? v != WHITE && v != KING : v != BLACK) continue;
+
+		for (int i = 0; i < 4; i++) {
+			int x2 = x + deltas[i][0], y2 = y + deltas[i][1];
+			while (x2 >= 0 && x2 < N && y2 >= 0 && y2 < N) {
+				if (cells[N * y2 + x2] != EMPTY) break;
+				if (N * y2 + x2 != BOARDMID) {
+					callback(Move(N * y + x, N * y2 + x2));
+				}
+
+				x2 += deltas[i][0];
+				y2 += deltas[i][1];
+			}
+		}
+	}
+}
diff --git a/main.cpp b/main.cpp
new file mode 100644
index 0000000..c699715
--- /dev/null
+++ b/main.cpp
@@ -0,0 +1,76 @@
+#include <iostream>
+#include <cassert>
+#include <sys/time.h>
+#include "board.h"
+#include "ai_mm.h"
+#include "ai_rand.h"
+
+using namespace std;
+
+
+static void skipLine(istream &stream) {
+	while (stream.get() != '\n');
+}
+
+int main() {
+	struct timeval tv;
+	gettimeofday(&tv, nullptr);
+	srand(tv.tv_sec * 1000000UL + tv.tv_usec);
+
+	Board bd = Board::makeInitial();
+	// cerr << bd << endl;
+
+	int onturn = -1;
+
+	char c = cin.peek();
+	if (c == 's' || c == 'S') {
+		skipLine(cin);
+		Move mv = AI::MM::findMove(bd, onturn);
+		assert(bd.isValid(mv, onturn));
+		cout << mv << endl;
+		bd.apply(mv);
+		onturn = -onturn;
+	}
+
+	int win;
+
+	string line;
+	while (true) {
+		cerr << bd << endl;
+
+		getline(cin, line);
+		if (!cin || line[0] == 'q' || line[0] == 'Q') break;
+
+		Move mv;
+		if (auto omv = Move::parse(line)) {
+			mv = *omv;
+		} else {
+			cerr << "Unreadable move" << endl;
+			break;
+		}
+
+		if (!bd.isValid(mv, onturn)) {
+			cerr << "Invalid move read" << endl;
+			break;
+		}
+
+		win = bd.applyCW(mv);
+		onturn = -onturn;
+		if (win != 0) break;
+
+		cerr << bd << endl;
+
+		mv = AI::MM::findMove(bd, onturn);
+		assert(bd.isValid(mv, onturn));
+
+		cout << mv << endl;
+
+		win = bd.applyCW(mv);
+		onturn = -onturn;
+		if (win != 0) break;
+	}
+
+	cerr << bd << endl;
+	if (win == 1) cerr << "White won" << endl;
+	else if (win == -1) cerr << "Black won" << endl;
+}