From 44421af15c2f361764b8741bb93f9fddda3f8a8b Mon Sep 17 00:00:00 2001
From: Tom Smeding <tom.smeding@gmail.com>
Date: Sat, 30 Jun 2018 00:30:14 +0200
Subject: Initial
---
.gitignore | 2 +
Makefile | 18 ++++++
ai_mm.cpp | 115 ++++++++++++++++++++++++++++++++++
ai_mm.h | 8 +++
ai_rand.cpp | 14 +++++
ai_rand.h | 8 +++
board.cpp | 200 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
board.h | 78 ++++++++++++++++++++++++
main.cpp | 76 +++++++++++++++++++++++
9 files changed, 519 insertions(+)
create mode 100644 .gitignore
create mode 100644 Makefile
create mode 100644 ai_mm.cpp
create mode 100644 ai_mm.h
create mode 100644 ai_rand.cpp
create mode 100644 ai_rand.h
create mode 100644 board.cpp
create mode 100644 board.h
create mode 100644 main.cpp
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;
+}
--
cgit v1.2.3-70-g09d2