Initial

1 files changed, 93 insertions, 0 deletions

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);
+	}
+}