Initial

9 files changed, 656 insertions, 0 deletions

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 <cstdlib>
+#include <cassert>
+#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> Board::subsequents() const {
+	vector<Board> 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 <iostream>
+#include <vector>
+#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 <typename F>  // 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<Board> 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 <iostream>
+#include <string>
+#include <stdexcept>
+#include <time.h>
+#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<Board> 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<Board> 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<evaluate_pieceScore>(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 <iostream>
+#include <string>
+#include <climits>
+#include "board.h"
+
+
+// >0 white good, <0 black good
+template <int (*Eval)(const Board&)>  // should return high for white
+int alphabeta(const Board &board, int depth);
+
+int evaluate_pieceScore(const Board &board);
+
+
+
+// IMPLEMENTATIONS
+
+template <int (*Eval)(const Board&)>
+static int alphabetaWhite(const Board &board, int depth, int alpha, int beta);
+
+template <int (*Eval)(const Board&)>
+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<Board> 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<Eval>(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 <int (*Eval)(const Board&)>
+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<Board> 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<Eval>(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 (*Eval)(const Board&)>
+int alphabeta(const Board &board, int depth) {
+	if (board.onTurn == WHITE) {
+		return alphabetaWhite<Eval>(board, depth, INT_MIN, INT_MAX);
+	} else {
+		return alphabetaBlack<Eval>(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 <cassert>
+#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 <string_view>
+
+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);
+};