Initial

1 files changed, 115 insertions, 0 deletions

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 <climits>
+#include <cassert>
+#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;
+}