From 9d0f4baa7d82d896b9660dfb2fe484129d5cfd13 Mon Sep 17 00:00:00 2001
From: tomsmeding <tom.smeding@gmail.com>
Date: Sun, 17 Feb 2019 00:13:40 +0100
Subject: WIP mm player

---
 ai_mm.cpp | 132 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 ai_mm.h   |  11 ++++++
 main.cpp  |   1 +
 3 files changed, 144 insertions(+)
 create mode 100644 ai_mm.cpp
 create mode 100644 ai_mm.h

diff --git a/ai_mm.cpp b/ai_mm.cpp
new file mode 100644
index 0000000..4d9a239
--- /dev/null
+++ b/ai_mm.cpp
@@ -0,0 +1,132 @@
+#include <iostream>
+#include <cassert>
+#include <climits>
+#include "ai_mm.h"
+#include "util.h"
+
+using namespace std;
+
+#define SCORE_WIN 10
+#define SCORE_LOSE (-10)
+#define SCORE_TIE 0
+#define INF (1e34)
+
+#define MAXDEPTH 4
+
+
+static int evaluate(Board &bd, uint8_t myclr) {
+	Bounds bounds = bd.computeBounds();
+
+	int score = 0;
+
+#define CHECK(_xlim1, _xlim2, _ylim1, _ylim2, _dx, _dy) \
+	do { \
+		for (int y = (_ylim1); y <= (_ylim2); y++) { \
+			for (int x = (_xlim1); x <= (_xlim2); x++) { \
+				int idx = BSZ * y + x; \
+				uint8_t clr = bd[idx]; \
+				if (clr == 0) continue; \
+				for (int i = 1; i <= RLEN; i++, x += (_dx), y += (_dy), idx += BSZ * (_dy) + (_dx)) { \
+					if (bd[idx] != clr) break; \
+					score += i * (3 - 2 * clr); \
+				} \
+			} \
+		} \
+	} while (0)
+
+	CHECK(bounds.left           , bounds.right - (RLEN-1), bounds.top, bounds.bottom           ,  1, 0);
+	CHECK(bounds.left           , bounds.right - (RLEN-1), bounds.top, bounds.bottom - (RLEN-1),  1, 1);
+	CHECK(bounds.left           , bounds.right           , bounds.top, bounds.bottom - (RLEN-1),  0, 1);
+	CHECK(bounds.left - (RLEN-1), bounds.right           , bounds.top, bounds.bottom - (RLEN-1), -1, 1);
+
+#undef CHECK
+
+	if (myclr != 1) score = -score;
+	return score;
+}
+
+static float chanceNode(
+		Board &bd, uint8_t myclr, int idx, uint8_t onturn,
+		int depth, float alpha, float beta);
+
+static float playNode(
+		Board &bd, uint8_t myclr, uint8_t onturn,
+		int depth, float alpha, float beta) {
+
+	if (depth == 0 || bd.bag.totalLeft() == 0) {
+		return evaluate(bd, myclr);
+	}
+
+	float value;
+
+	vector<int> edgeCells = bd.getEdgeCells();
+	if (onturn == myclr) {
+		value = -INF;
+		for (int idx : edgeCells) {
+			value = max(value, chanceNode(bd, myclr, idx, onturn, depth, alpha, beta));
+			alpha = max(alpha, value);
+			if (alpha >= beta) break;
+		}
+	} else {
+		value = +INF;
+		for (int idx : edgeCells) {
+			value = min(value, chanceNode(bd, myclr, idx, onturn, depth, alpha, beta));
+			beta = min(beta, value);
+			if (alpha >= beta) break;
+		}
+	}
+
+	return value;
+}
+
+static float chanceNode(
+		Board &bd, uint8_t myclr, int idx, uint8_t onturn,
+		int depth, float alpha, float beta) {
+
+	const float totalLeftF = bd.bag.totalLeft();
+
+	float score = 0;
+
+	for (uint8_t clr = 1; clr <= NC; clr++) {
+		int numLeft = bd.bag.numLeft(clr);
+		if (numLeft == 0) continue;
+
+		float probability = numLeft / totalLeftF;
+
+		bd.bag.drawColour(clr);
+		uint8_t win = bd.putCW(idx, clr);
+		if (win != 0) {
+			score += probability * (win == myclr ? SCORE_WIN : SCORE_LOSE);
+		} else {
+			score += probability * playNode(bd, myclr, NEXTTURN(onturn), depth - 1, alpha, beta);
+		}
+
+		bd.bag.replace(clr);
+		bd.undo(idx);
+	}
+
+	return score;
+}
+
+int MM::calcMove(Board &bd, uint8_t myclr) {
+	assert(bd.bag.totalLeft() > 0);
+
+	// The usage of a single score variable instead of an array works only if
+	// there are only two players.
+	static_assert(NC == 2, "MM only works with 2 players");
+
+	float maxscore = INT_MIN;
+	int maxat = -1;
+
+	vector<int> edgeCells = bd.getEdgeCells();
+	for (int idx : edgeCells) {
+		float score = chanceNode(bd, myclr, idx, myclr, MAXDEPTH, -INF, +INF);
+
+		if (score > maxscore) {
+			maxscore = score;
+			maxat = idx;
+		}
+	}
+
+	return maxat;
+}
diff --git a/ai_mm.h b/ai_mm.h
new file mode 100644
index 0000000..7388f75
--- /dev/null
+++ b/ai_mm.h
@@ -0,0 +1,11 @@
+#pragma once
+
+#include "board.h"
+
+using namespace std;
+
+
+namespace MM {
+	// bd will be unchanged upon return
+	int calcMove(Board &bd, uint8_t myclr);
+}
diff --git a/main.cpp b/main.cpp
index 0c6e0de..57d3bb5 100644
--- a/main.cpp
+++ b/main.cpp
@@ -6,6 +6,7 @@
 #include <sys/time.h>
 #include "board.h"
 #include "ai_mc.h"
+#include "ai_mm.h"
 #include "ai_rand.h"
 #include "ui.h"
 
-- 
cgit v1.2.3