Add monte carlo player

3 files changed, 92 insertions, 1 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;
+}
diff --git a/ai_mc.h b/ai_mc.h
new file mode 100644
index 0000000..c2e1bbb
--- /dev/null
+++ b/ai_mc.h
@@ -0,0 +1,8 @@
+#pragma once
+
+#include "board.h"
+
+
+namespace AI::MC {
+	Move findMove(const Board &bd, int player);
+}
diff --git a/main.cpp b/main.cpp
index 5eeb318..4fb66a9 100644
--- a/main.cpp
+++ b/main.cpp
@@ -2,6 +2,7 @@
 #include <cassert>
 #include <sys/time.h>
 #include "board.h"
+#include "ai_mc.h"
 #include "ai_mm.h"
 #include "ai_rand.h"
 
@@ -14,7 +15,7 @@ static void skipLine(istream &stream) {
 
 static Move findMove(const Board &bd, int player) {
 	clock_t start = clock();
-	Move mv = AI::MM::findMove(bd, player);
+	Move mv = AI::MC::findMove(bd, player);
 	clock_t diff = clock() - start;
 	cerr << "Time taken: " << (double)diff / CLOCKS_PER_SEC << " seconds" << endl;
 	return mv;