From b26b8840e2cebec9ea8294d24ceb6663942005d4 Mon Sep 17 00:00:00 2001 From: tomsmeding Date: Mon, 12 Mar 2018 00:20:50 +0100 Subject: Initial --- .gitignore | 2 + Makefile | 26 +++++ board.cpp | 341 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ board.h | 67 ++++++++++++ main.cpp | 85 +++++++++++++++ minimax.cpp | 9 ++ minimax.h | 93 +++++++++++++++++ move.cpp | 21 ++++ move.h | 12 +++ 9 files changed, 656 insertions(+) create mode 100644 .gitignore create mode 100644 Makefile create mode 100644 board.cpp create mode 100644 board.h create mode 100644 main.cpp create mode 100644 minimax.cpp create mode 100644 minimax.h create mode 100644 move.cpp create mode 100644 move.h diff --git a/.gitignore b/.gitignore new file mode 100644 index 0000000..c21c104 --- /dev/null +++ b/.gitignore @@ -0,0 +1,2 @@ +chess +obj/ diff --git a/Makefile b/Makefile new file mode 100644 index 0000000..04267f9 --- /dev/null +++ b/Makefile @@ -0,0 +1,26 @@ +CXX = g++ +CXXFLAGS = -Wall -Wextra -std=c++14 -O2 -fwrapv +TARGET = chess + +OBJDIR = obj + +.PHONY: all clean + +.SUFFIXES: + +all: $(TARGET) + +clean: + @echo "Cleaning" + @rm -f $(TARGET) + @rm -rf $(OBJDIR) + + +$(OBJDIR)/%.o: %.cpp $(wildcard *.h) + @mkdir -p $(OBJDIR) + @echo "CXX $<" + @$(CXX) $(CXXFLAGS) -c -o $@ $< + +$(TARGET): $(patsubst %.cpp,$(OBJDIR)/%.o,$(wildcard *.cpp)) + @echo "LD -o $@" + @$(CXX) -o $@ $^ diff --git a/board.cpp b/board.cpp new file mode 100644 index 0000000..c49339a --- /dev/null +++ b/board.cpp @@ -0,0 +1,341 @@ +#include +#include +#include "board.h" + + +static inline int pawnShiftDeltaY(int clr) { + return clr == WHITE ? -1 : 1; +} + +static inline int homerowY(int clr) { + return clr == WHITE ? 7 : 0; +} + + +Board::Board() { + bd[0] = -ROOK; bd[1] = -KNIGHT; bd[2] = -BISHOP; bd[3] = -KING; + bd[4] = -QUEEN; bd[5] = -BISHOP; bd[6] = -KNIGHT; bd[7] = -ROOK; + for (int i = 8; i < 16; i++) bd[i] = -PAWN; + + memset(bd + 16, 0, 32 * sizeof(int)); + + for (int i = 48; i < 56; i++) bd[i] = PAWN; + bd[56] = ROOK; bd[57] = KNIGHT; bd[58] = BISHOP; bd[59] = KING; + bd[60] = QUEEN; bd[61] = BISHOP; bd[62] = KNIGHT; bd[63] = ROOK; + + pieceScore[0] = pieceScore[1] = 0; + lastTarget = -1; + onTurn = WHITE; + kingMoved[0] = kingMoved[1] = false; + rookLmoved[0] = rookLmoved[1] = false; + rookRmoved[0] = rookRmoved[1] = false; +} + +int Board::locate(int stone) const { + for (int i = 0; i < 64; i++) { + if (at(i) == stone) return i; + } + return -1; +} + +#define SHIFTER(from_, to_) \ + [f_ = (from_), t_ = (to_)](Board &B) { \ + B.pieceScore[colour(B.at(f_))] += worth(B.at(t_)); \ + B.at(t_) = B.at(f_); B.at(f_) = EMPTY; B.lastTarget = t_; \ + B.onTurn = !B.onTurn; \ + } + +// ~390k runs per second +vector Board::subsequents() const { + vector subs; + + for (int i = 0; i < 64; i++) { + int stone = at(i), clr = colour(stone); + if (clr != onTurn) continue; + int x = i % 8, y = i / 8; + + switch (abs(stone)) { + case EMPTY: + break; + + case PAWN: { + int delta = pawnShiftDeltaY(clr); + int homerow = homerowY(clr) + delta; + int lastRow = homerowY(!clr); + if (y == homerow && at(x, y + delta) == EMPTY && at(x, y + 2 * delta) == EMPTY) { + subs.push_back(newWith(SHIFTER(i, IDX(x, y + 2 * delta)))); + } + if (y != lastRow && at(x, y + delta) == EMPTY) { + subs.push_back(newWith(SHIFTER(i, IDX(x, y + delta)))); + } + if (y != lastRow && x != 0 && at(x - 1, y + delta) != EMPTY && + colour(at(x - 1, y + delta)) != clr) { + subs.push_back(newWith(SHIFTER(i, IDX(x - 1, y + delta)))); + } + if (y != lastRow && x != 7 && at(x + 1, y + delta) != EMPTY && + colour(at(x + 1, y + delta)) != clr) { + subs.push_back(newWith(SHIFTER(i, IDX(x + 1, y + delta)))); + } + if (x != 0 && y == homerow + 3 * delta && + at(x - 1, y) == -stone && lastTarget == IDX(x - 1, y)) { + subs.push_back(newWith([x, y, delta, clr](Board &B) { + B.pieceScore[clr] += worth(PAWN); + B.at(x - 1, y + delta) = B.at(x, y); + B.at(x, y) = EMPTY; + B.at(x - 1, y) = EMPTY; + B.lastTarget = IDX(x - 1, y + delta); + B.onTurn = !B.onTurn; + })); + } + if (x != 7 && y == homerow + 3 * delta && + at(x + 1, y) == -stone && lastTarget == IDX(x + 1, y)) { + subs.push_back(newWith([x, y, delta, clr](Board &B) { + B.pieceScore[clr] += worth(PAWN); + B.at(x + 1, y + delta) = B.at(x, y); + B.at(x, y) = EMPTY; + B.at(x + 1, y) = EMPTY; + B.lastTarget = IDX(x + 1, y + delta); + B.onTurn = !B.onTurn; + })); + } + break; + } + + case ROOK: { + int homerow = homerowY(clr); + int which = y == homerow ? (x == 0 ? -1 : x == 7) : 0; + for (int x2 = x - 1; x2 >= 0; x2--) { + if (at(x2, y) == EMPTY || colour(at(x2, y)) != clr) { + subs.push_back(newWith([i, x, y, x2, which, clr](Board &B) { + SHIFTER(i, IDX(x2, y))(B); + if (which == -1) B.rookLmoved[clr] = true; + else if (which == 1) B.rookRmoved[clr] = true; + })); + } + if (at(x2, y) != EMPTY) break; + } + for (int x2 = x + 1; x2 < 8; x2++) { + if (at(x2, y) == EMPTY || colour(at(x2, y)) != clr) { + subs.push_back(newWith([i, x, y, x2, which, clr](Board &B) { + SHIFTER(i, IDX(x2, y))(B); + if (which == -1) B.rookLmoved[clr] = true; + else if (which == 1) B.rookRmoved[clr] = true; + })); + } + if (at(x2, y) != EMPTY) break; + } + for (int y2 = y - 1; y2 >= 0; y2--) { + if (at(x, y2) == EMPTY || colour(at(x, y2)) != clr) { + subs.push_back(newWith([i, x, y, y2, which, clr](Board &B) { + SHIFTER(i, IDX(x, y2))(B); + if (which == -1) B.rookLmoved[clr] = true; + else if (which == 1) B.rookRmoved[clr] = true; + })); + } + if (at(x, y2) != EMPTY) break; + } + for (int y2 = y + 1; y2 < 8; y2++) { + if (at(x, y2) == EMPTY || colour(at(x, y2)) != clr) { + subs.push_back(newWith([i, x, y, y2, which, clr](Board &B) { + SHIFTER(i, IDX(x, y2))(B); + if (which == -1) B.rookLmoved[clr] = true; + else if (which == 1) B.rookRmoved[clr] = true; + })); + } + if (at(x, y2) != EMPTY) break; + } + break; + } + + case KNIGHT: + for (int dy = -1; dy <= 1; dy += 2) + for (int dx = -1; dx <= 1; dx += 2) + for (int onetwo = 1; onetwo <= 2; onetwo++) { + int x2 = x + onetwo * dx, y2 = y + (3 - onetwo) * dy; + if (x2 >= 0 && x2 < 8 && y2 >= 0 && y2 < 8 && + (at(x2, y2) == EMPTY || colour(at(x2, y2)) != clr)) { + subs.push_back(newWith(SHIFTER(i, IDX(x2, y2)))); + } + } + break; + + case BISHOP: + for (int i2 = i - 9; i2 >= 0; i2 -= 9) { + if (at(i2) == EMPTY || colour(at(i2)) != clr) { + subs.push_back(newWith(SHIFTER(i, i2))); + } + if (at(i2) != EMPTY) break; + if (i2 % 8 == 0) break; + } + for (int i2 = i - 7; i2 >= 0; i2 -= 7) { + if (at(i2) == EMPTY || colour(at(i2)) != clr) { + subs.push_back(newWith(SHIFTER(i, i2))); + } + if (at(i2) != EMPTY) break; + if (i2 % 8 == 7) break; + } + for (int i2 = i + 7; i2 < 64; i2 += 7) { + if (at(i2) == EMPTY || colour(at(i2)) != clr) { + subs.push_back(newWith(SHIFTER(i, i2))); + } + if (at(i2) != EMPTY) break; + if (i2 % 8 == 0) break; + } + for (int i2 = i + 9; i2 < 64; i2 += 9) { + if (at(i2) == EMPTY || colour(at(i2)) != clr) { + subs.push_back(newWith(SHIFTER(i, i2))); + } + if (at(i2) != EMPTY) break; + if (i2 % 8 == 7) break; + } + break; + + case KING: { + for (int dy = -1; dy <= 1; dy++) + for (int dx = -1; dx <= 1; dx++) { + if (dx == 0 && dy == 0) continue; + int x2 = x + dx, y2 = y + dy; + if (x2 < 0 || x2 >= 8 || y2 < 0 || y2 >= 8) continue; + if (at(x2, y2) == EMPTY || colour(at(x2, y2)) != clr) { + subs.push_back(newWith([i, x2, y2, clr](Board &B) { + SHIFTER(i, IDX(x2, y2))(B); + B.kingMoved[clr] = true; + })); + } + } + int homerow = homerowY(clr); + if (!kingMoved[clr]) { + if (!rookLmoved[clr] && + at(1, homerow) == EMPTY && at(2, homerow) == EMPTY) { + subs.push_back(newWith([i, homerow, clr](Board &B) { + B.at(i - 1) = B.at(i - 3); + B.at(i - 3) = EMPTY; + B.at(i - 2) = B.at(i); + B.at(i - i) = EMPTY; + B.kingMoved[clr] = true; + B.rookLmoved[clr] = true; + B.onTurn = !B.onTurn; + })); + } + if (!rookRmoved[clr] && + at(4, homerow) == EMPTY && at(5, homerow) == EMPTY && at(6, homerow) == EMPTY) { + subs.push_back(newWith([i, homerow, clr](Board &B) { + B.at(i + 2) = B.at(i + 4); + B.at(i + 4) = EMPTY; + B.at(i + 3) = B.at(i); + B.at(i) = EMPTY; + B.kingMoved[clr] = true; + B.rookRmoved[clr] = true; + B.onTurn = !B.onTurn; + })); + } + } + break; + } + + case QUEEN: + for (int dy = -1; dy <= 1; dy++) + for (int dx = -1; dx <= 1; dx++) { + if (dx == 0 && dy == 0) continue; + for (int k = 1; k < 7; k++) { + int x2 = x + k * dx, y2 = y + k * dy; + if (x2 < 0 || x2 >= 8 || y2 < 0 || y2 >= 8) break; + if (at(x2, y2) == EMPTY || colour(at(x2, y2)) != clr) { + subs.push_back(newWith(SHIFTER(i, IDX(x2, y2)))); + } + if (at(x2, y2) != EMPTY) break; + } + } + break; + } + } + + return subs; +} + +void Board::apply(const Move &mv) { + assert(mv.castle == 0); + onTurn = !onTurn; + int dx = mv.to % 8 - mv.from % 8; + if (abs(dx) == 1 && lastTarget == mv.from + dx) { + if (at(mv.from) == PAWN && at(mv.from + dx) == -PAWN && + mv.from / 8 == homerowY(BLACK) + 3 * pawnShiftDeltaY(BLACK) && + mv.to / 8 == homerowY(BLACK) + 2 * pawnShiftDeltaY(BLACK)) { + at(mv.from + dx) = EMPTY; + at(mv.to) = PAWN; + at(mv.from) = EMPTY; + lastTarget = mv.to; + pieceScore[WHITE] += worth(PAWN); + return; + } else if (at(mv.from) == -PAWN && at(mv.from + dx) == PAWN && + mv.from / 8 == homerowY(WHITE) + 3 * pawnShiftDeltaY(WHITE) && + mv.to / 8 == homerowY(WHITE) + 2 * pawnShiftDeltaY(WHITE)) { + at(mv.from + dx) = EMPTY; + at(mv.to) = -PAWN; + at(mv.from) = EMPTY; + lastTarget = mv.to; + pieceScore[BLACK] += worth(PAWN); + return; + } + } + int clr = colour(at(mv.from)); + int homerow = homerowY(clr); + int x = mv.from % 8, y = mv.from / 8; + if (y == homerow && abs(at(mv.from)) == ROOK) { + if (x == 0) rookLmoved[clr] = true; + else if (x == 7) rookRmoved[clr] = true; + } else if (abs(at(mv.from)) == KING) { + kingMoved[clr] = true; + } + pieceScore[clr] += worth(at(mv.to)); + at(mv.to) = at(mv.from); + at(mv.from) = EMPTY; + lastTarget = mv.to; +} + +bool Board::isValid(const Move &mv) { + assert(mv.castle == 0); + if (colour(at(mv.from)) != onTurn) return false; + Board B(*this); + B.apply(mv); + // cerr << "after applying:" << endl << B << endl; + // cerr << subsequents()[27] << endl; + // cerr << (B == subsequents()[27]) << endl; + for (const Board &B2 : subsequents()) { + if (B == B2) return true; + } + return false; +} + +ostream& operator<<(ostream &os, const Board &B) { + for (int y = 0; y < 8; y++) { + os << "\x1B[34m" << "87654321"[y] << "\x1B[0m "; + for (int x = 0; x < 8; x++) { + if (x != 0) os << ' '; + if (B.at(x, y) >= 0) { + os << ".PRNBKQ"[B.at(x, y)]; + } else { + os << ".prnbkq"[-B.at(x, y)]; + } + } + if (y == 0) { + os << " ps[W] = " << B.pieceScore[WHITE]; + os << " onTurn = " << (&"WHITE\0BLACK"[B.onTurn * 6]); + } else if (y == 1) { + os << " ps[B] = " << B.pieceScore[BLACK]; + } + os << '\n'; + } + os << " \x1B[34ma b c d e f g h\x1B[0m" << '\n'; + return os; +} + +bool operator==(const Board &B1, const Board &B2) { + bool c1 = memcmp(B1.bd, B2.bd, 64 * sizeof B1.bd[0]) == 0; + bool c2 = B1.lastTarget == B2.lastTarget; + bool c3 = B1.onTurn == B2.onTurn; + bool c4 = memcmp(B1.kingMoved, B2.kingMoved, 2 * sizeof(bool)) == 0; + bool c5 = memcmp(B1.rookLmoved, B2.rookLmoved, 2 * sizeof(bool)) == 0; + bool c6 = memcmp(B1.rookRmoved, B2.rookRmoved, 2 * sizeof(bool)) == 0; + return c1 && c2 && c3 && c4 && c5 && c6; +} diff --git a/board.h b/board.h new file mode 100644 index 0000000..a714de0 --- /dev/null +++ b/board.h @@ -0,0 +1,67 @@ +#pragma once + +#include +#include +#include "move.h" + +using namespace std; + + +const int WHITE = 0; +const int BLACK = 1; + +const int EMPTY = 0, PAWN = 1, ROOK = 2, KNIGHT = 3, BISHOP = 4, KING = 5, QUEEN = 6; + +// WHITE WHITE WHITE y = 0 +// ... +// ... +// BLACK BLACK BLACK y = 7 + + +#define IDX(x_, y_) (8 * (y_) + (x_)) + + +class Board { + int bd[64]; // 0 = empty, >0 = white, <0 = black + +public: + int pieceScore[2]; // captured points by player + int lastTarget; // destination of last move + int onTurn; // colour of player to move + bool kingMoved[2], rookLmoved[2], rookRmoved[2]; + + Board(); + + template // void(Board&) + inline Board newWith(const F &func) const { + Board B(*this); + func(B); + return B; + } + + inline int& at(int x, int y) {return at(IDX(x, y));} + inline int& at(int idx) {return bd[idx];} + inline int at(int x, int y) const {return at(IDX(x, y));} + inline int at(int idx) const {return bd[idx];} + + int locate(int stone) const; + + static inline int colour(int stone) {return stone > 0 ? WHITE : BLACK;} + + static inline int worth(int stone) { + static const int w[7] = {0, 1, 5, 3, 3, 100000000, 9}; + if (stone < -6 || stone > 6) __asm("int3\n\t"); + return w[abs(stone)]; + } + + vector subsequents() const; + + void apply(const Move &mv); // does not perform checking + + bool isValid(const Move &mv); + + friend bool operator==(const Board &B1, const Board &B2); +}; + +ostream& operator<<(ostream &os, const Board &B); +bool operator==(const Board &B1, const Board &B2); diff --git a/main.cpp b/main.cpp new file mode 100644 index 0000000..1419b08 --- /dev/null +++ b/main.cpp @@ -0,0 +1,85 @@ +#include +#include +#include +#include +#include "board.h" +#include "minimax.h" + + +const int AB_MAXDEPTH = 6; + +int main() { + Board B; + cout << B << endl; + + // clock_t start = clock(); + // for (int i = 0; i < 1000000; i++) { + // B.subsequents(); + // } + // clock_t diff = clock() - start; + // cout << (double)diff / CLOCKS_PER_SEC << endl; + + // for (const Board &B2 : B.subsequents()) { + // cout << B2 << endl; + // } + + while (true) { + string line; + getline(cin, line); + if (!cin) break; + if (line == "s") { + cout << "----------------------" << endl; + for (const Board &B2 : B.subsequents()) { + cout << B2 << endl; + } + cout << "----------------------" << endl << B << endl; + continue; + } + if (line == "q") break; + if (line == "r") { + vector subs = B.subsequents(); + if (subs.size() == 0) { + cout << "No possible moves" << endl; + } else { + B = subs[rand() % subs.size()]; + cout << B << endl; + } + continue; + } + if (line == "a") { + vector subs = B.subsequents(); + if (subs.size() == 0) { + cout << "No possible moves" << endl; + } else { + int maxval = INT_MIN, maxat = -1; + const int multfactor = B.onTurn == WHITE ? 1 : -1; + cout << "["; + for (size_t i = 0; i < subs.size(); i++) { + int v = alphabeta(subs[i], AB_MAXDEPTH); + if (i != 0) cout << ", "; + cout << v << endl; + v *= multfactor; + if (v > maxval) { + maxval = v; + maxat = i; + } + } + cout << "]" << endl; + B = subs[maxat]; + cout << B << endl; + } + continue; + } + try { + Move mv(line.data()); + if (B.isValid(mv)) { + B.apply(mv); + cout << B << endl; + } else { + cout << "Invalid move." << endl; + } + } catch (const runtime_error &e) { + cout << "Unrecognised input, expected move." << endl; + } + } +} diff --git a/minimax.cpp b/minimax.cpp new file mode 100644 index 0000000..3c0793d --- /dev/null +++ b/minimax.cpp @@ -0,0 +1,9 @@ +#include "minimax.h" + + +int evaluate_pieceScore(const Board &board) { + int score = board.pieceScore[WHITE] - board.pieceScore[BLACK]; + // cerr << board << endl; + // cerr << " -> score = " << score << endl; + return score; +} diff --git a/minimax.h b/minimax.h new file mode 100644 index 0000000..ad714fc --- /dev/null +++ b/minimax.h @@ -0,0 +1,93 @@ +#pragma once + +#include +#include +#include +#include "board.h" + + +// >0 white good, <0 black good +template // should return high for white +int alphabeta(const Board &board, int depth); + +int evaluate_pieceScore(const Board &board); + + + +// IMPLEMENTATIONS + +template +static int alphabetaWhite(const Board &board, int depth, int alpha, int beta); + +template +static int alphabetaBlack(const Board &board, int depth, int alpha, int beta) { + if (depth == 0 || board.pieceScore[WHITE] >= Board::worth(KING)) { + return Eval(board); + } + int value = INT_MAX; + vector subs = board.subsequents(); + if (depth >= 2) { + sort(subs.begin(), subs.end(), [](const Board &B1, const Board &B2) { + return Eval(B1) < Eval(B2); + }); + } + for (const Board &B : subs) { + int v = alphabetaWhite(B, depth - 1, alpha, beta); + if (v < value) { + value = v; + if (v < beta) { + beta = v; + if (beta <= alpha) break; + } + } + } + // if (depth == 1) cerr << value << ", "; + // else { + // if (depth == 2) cerr << endl; + // cerr << string(depth, ' ') << "alphabetaBlack: returning " << value << endl; + // } + // if (depth == 1 && abs(value) >= Board::worth(KING) / 10) cerr << board << endl; + // cerr << board << endl; + return value; +} + +template +static int alphabetaWhite(const Board &board, int depth, int alpha, int beta) { + if (depth == 0 || board.pieceScore[BLACK] >= Board::worth(KING)) { + return Eval(board); + } + int value = INT_MIN; + vector subs = board.subsequents(); + if (depth >= 2) { + sort(subs.begin(), subs.end(), [](const Board &B1, const Board &B2) { + return Eval(B1) > Eval(B2); + }); + } + for (const Board &B : subs) { + int v = alphabetaBlack(B, depth - 1, alpha, beta); + if (v > value) { + value = v; + if (v > alpha) { + alpha = v; + if (beta <= alpha) break; + } + } + } + // if (depth == 1) cerr << value << ", "; + // else { + // if (depth == 2) cerr << endl; + // cerr << string(depth, ' ') << "alphabetaWhite: returning " << value << endl; + // } + // if (depth == 1 && abs(value) >= Board::worth(KING) / 10) cerr << board << endl; + // cerr << board << endl; + return value; +} + +template +int alphabeta(const Board &board, int depth) { + if (board.onTurn == WHITE) { + return alphabetaWhite(board, depth, INT_MIN, INT_MAX); + } else { + return alphabetaBlack(board, depth, INT_MIN, INT_MAX); + } +} diff --git a/move.cpp b/move.cpp new file mode 100644 index 0000000..70c7610 --- /dev/null +++ b/move.cpp @@ -0,0 +1,21 @@ +#include +#include "move.h" + + +Move::Move(const char *str) { + if (str[0] >= 'a' && str[0] <= 'h' && + str[1] >= '1' && str[1] <= '8' && + str[2] >= 'a' && str[2] <= 'h' && + str[3] >= '1' && str[3] <= '8' && + str[4] == '\0') { + from = 8 * ('8' - str[1]) + str[0] - 'a'; + to = 8 * ('8' - str[3]) + str[2] - 'a'; + castle = 0; + } else if (strcmp(str, "O-O") == 0) { + castle = 1; + } else if (strcmp(str, "O-O-O") == 0) { + castle = -1; + } else { + throw std::runtime_error("Invalid Move string"); + } +} diff --git a/move.h b/move.h new file mode 100644 index 0000000..ddad16f --- /dev/null +++ b/move.h @@ -0,0 +1,12 @@ +#include + +using namespace std; + + +class Move { +public: + int from, to; + int castle; // -1: queen's side; 1: king's side; 0: none + + Move(const char *str); +}; -- cgit v1.2.3-54-g00ecf