summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--ai_mc.cpp82
-rw-r--r--ai_mc.h8
-rw-r--r--main.cpp3
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;