1 files changed, 91 insertions, 0 deletions
diff --git a/minimax.cpp b/minimax.cpp
new file mode 100644
index 0000000..c4011da
--- /dev/null
+++ b/minimax.cpp
@@ -0,0 +1,91 @@
+#include <array>
+#include <memory>
+#include "minimax.h"
+
+using namespace std;
+
+#define LARGE MINIMAX_LARGE
+
+
+static int win_score[4] = {
+	[WIN_NONE] = 0,
+	[WIN_P0] = 1,
+	[WIN_P1] = -1,
+	[WIN_DRAW] = -1,
+};
+
+struct TransItem {
+	Board B = Board::empty();
+	int score = 0;
+};
+
+static unique_ptr<array<TransItem, 10000019>> transTable =
+	make_unique<decltype(transTable)::element_type>();
+
+static void transTableStore(uint64_t index, const Board &B, int score) {
+	TransItem &entry = (*transTable)[index];
+	// if (entry.B.isEmpty() || B.numFilled() < entry.B.numFilled()) {
+		entry.B = B;
+		entry.score = score;
+	// }
+}
+
+static uint64_t transHits = 0, transTotal = 0;
+static uint64_t transHitDepthSum = 0;
+
+template <int player>
+int minimax(const Board &B, int alpha, int beta, int depth) {
+	uint64_t transIndex = B.hash() % transTable->size();
+	transTotal++;
+	if (!B.isEmpty() && (*transTable)[transIndex].B == B) {
+		transHits++;
+		transHitDepthSum += depth;
+		return (*transTable)[transIndex].score;
+	}
+
+	win_t win = B.checkWin();
+	if (win != WIN_NONE) {
+		transTableStore(transIndex, B, win_score[win]);
+		return win_score[win];
+	}
+
+	if (depth == 0) return win_score[WIN_NONE];
+
+	if (depth >= 42) {
+		printf("depth=%d alpha=%d beta=%d transHitrate=%lf (avg depth %lf)\n",
+				depth, alpha, beta,
+				(double)transHits / transTotal, (double)transHitDepthSum / transTotal);
+	}
+
+	int best = player == 0 ? -LARGE : LARGE;
+
+	// Returns true if iteration should be stopped
+	auto tryMove = [&](int i) {
+		if (B.stkFull(i)) return false;
+
+		Board C(B);
+		C.drop(i, player);
+
+		int sc = minimax<1 - player>(C, alpha, beta, depth - 1);
+
+		if constexpr (player == 0) {
+			best = max(sc, best);
+			alpha = max(best, alpha);
+		} else {
+			best = min(sc, best);
+			beta = min(best, beta);
+		}
+
+		return beta <= alpha;
+	};
+
+	for (int i = 0; i < 16; i++) {
+		if (tryMove(i)) break;
+	}
+
+	transTableStore(transIndex, B, best);
+	return best;
+}
+
+template int minimax<0>(const Board &B, int alpha, int beta, int depth);
+template int minimax<1>(const Board &B, int alpha, int beta, int depth);