From 3711c92f43eedbd698a9c477e3248fb87892fbd9 Mon Sep 17 00:00:00 2001
From: Tom Smeding <tom.smeding@gmail.com>
Date: Fri, 15 Feb 2019 11:32:44 +0100
Subject: Multiple AI's (+RAND)

---
 ai_mc.cpp | 79 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 79 insertions(+)
 create mode 100644 ai_mc.cpp

(limited to 'ai_mc.cpp')

diff --git a/ai_mc.cpp b/ai_mc.cpp
new file mode 100644
index 0000000..6175d96
--- /dev/null
+++ b/ai_mc.cpp
@@ -0,0 +1,79 @@
+#include <iostream>
+#include <cassert>
+#include <climits>
+#include "ai_mc.h"
+#include "util.h"
+
+using namespace std;
+
+#define NPLAYOUTS 1000
+#define SCORE_WIN 1
+#define SCORE_LOSE (-1)
+#define SCORE_TIE 0
+
+
+// Takes copy of board, since it probably isn't worth it to undo the whole rest
+// of the game.
+// TODO: Multiply the playout score with its cumulative probability (which is
+// pretty small!) to get a probabilistically correct estimate of the expected
+// score.
+static int playout(Board bd, uint8_t myclr) {
+	// cerr << "  PLAYOUT" << endl;
+	while (bd.bag.totalLeft() > 0) {
+		uint8_t clr = bd.bag.drawRandom();
+
+		int moves[BSZ * BSZ], nmoves = 0;
+		bd.forEachMove([&moves, &nmoves](int idx) { moves[nmoves++] = idx; });
+
+		assert(nmoves > 0);
+		int idx = moves[random() % nmoves];
+
+		// cerr << "    idx = " << Idx(idx) << " clr=" << (unsigned)clr << endl;
+
+		uint8_t win = bd.putCW(idx, clr);
+		if (win != 0) {
+			return win == myclr ? SCORE_WIN : SCORE_LOSE;
+		}
+	}
+
+	return SCORE_TIE;
+}
+
+
+int MC::calcMove(Board &bd, uint8_t myclr) {
+	assert(bd.bag.totalLeft() > 0);
+
+	float maxscore = INT_MIN;
+	int maxat = -1;
+
+	bd.forEachMove([&bd, myclr, &maxscore, &maxat](int idx) {
+		// cerr << "MC::calcMove: trying idx=" << Idx(idx) << endl;
+		float score = 0;
+
+		for (int i = 0; i < NPLAYOUTS; i++) {
+			// cerr << "playout " << i << endl;
+
+			uint8_t clr = bd.bag.peekRandom();
+			float probability = (float)bd.bag.numLeft(clr) / bd.bag.totalLeft();
+			bd.bag.drawColour(clr);
+
+			// cerr << "  random clr=" << (unsigned)clr << endl;
+			uint8_t win = bd.putCW(idx, clr);
+			if (win != 0) {
+				score += probability * (win == myclr ? SCORE_WIN : SCORE_LOSE);
+			} else {
+				score += probability * playout(bd, myclr);
+			}
+
+			bd.bag.replace(clr);
+			bd.undo(idx);
+		}
+
+		if (score > maxscore) {
+			maxscore = score;
+			maxat = idx;
+		}
+	});
+
+	return maxat;
+}
-- 
cgit v1.2.3-70-g09d2