From 44421af15c2f361764b8741bb93f9fddda3f8a8b Mon Sep 17 00:00:00 2001 From: Tom Smeding 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 +#include +#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 +#include +#include +#include "board.h" + +using namespace std; + + +static optional 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::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 +#include +#include +#include + +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 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 + 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 +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 +#include +#include +#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