1 files changed, 82 insertions, 0 deletions
diff --git a/ai_mc.cpp b/ai_mc.cpp
new file mode 100644
index 0000000..7fbb9e0
--- /dev/null
+++ b/ai_mc.cpp
@@ -0,0 +1,82 @@
+#include <climits>
+#include "ai_mc.h"
+
+
+static const int mc_ngames = 500;
+
+
+static int playout(Board &bd, int player) {
+	Move poss[N * N * N];
+
+	while (true) {
+		int nposs = 0;
+		int winidx = -1;
+		bd.forEachMove(player, [&bd, &poss, &nposs, &winidx, player](Move mv) {
+			Board bd2 = bd;
+			int win = bd2.applyCW(mv);
+			if (win * player >= 0) {
+				poss[nposs++] = mv;
+				if (win != 0) {
+					winidx = nposs - 1;
+					return true;
+				}
+			}
+			return false;
+		});
+
+		if (nposs == 0) return -player;
+
+		int index = winidx == -1 ? rand() % nposs : winidx;
+
+		int win = bd.applyCW(poss[index]);
+		if (win != 0) return win;
+
+		player = -player;
+	}
+}
+
+Move AI::MC::findMove(const Board &bd, int player) {
+	// 'maxscore' and 'score' below have high values for 'player'.
+	int maxscore = INT_MIN;
+	Move maxmove = Move(-1, -1);
+
+	cerr << '[';
+
+	bd.forEachMove(player, [&bd, &maxscore, &maxmove, player](Move mv) {
+		int score = 0;
+
+		Board bd2 = bd;
+		int win = bd2.applyCW(mv);
+		if (win == player) {
+			maxscore = INT_MAX;
+			maxmove = mv;
+			cerr << "Found winning move!";
+			return true;
+		} else if (win == -player) {
+			return false;
+		}
+
+		for (int i = 0; i < mc_ngames; i++) {
+			Board bd3 = bd;
+			bd3.apply(mv);
+			score += playout(bd3, -player);
+		}
+
+		score *= player;  // fix sign
+
+		cerr << score << ',';
+
+		if (score > maxscore) {
+			maxscore = score;
+			maxmove = mv;
+		}
+
+		return false;
+	});
+
+	cerr << ']' << endl;
+
+	cerr << "Chose move with score " << maxscore << endl;
+
+	return maxmove;
+}