Work on mm ai's

5 files changed, 188 insertions, 2 deletions

diff --git a/.gitignore b/.gitignore
index 76d63a9..c5563e2 100644
--- a/.gitignore
+++ b/.gitignore
@@ -1,5 +1,7 @@
 aimc
 airand
 aimm
+aimm2
 .objs/
 competition/
+*.dSYM
diff --git a/ai_mm.cpp b/ai_mm.cpp
index 4d9a239..d74f7c7 100644
--- a/ai_mm.cpp
+++ b/ai_mm.cpp
@@ -26,7 +26,7 @@ static int evaluate(Board &bd, uint8_t myclr) {
 				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)) { \
+				for (int i = 1; i <= RLEN; i++, idx += BSZ * (_dy) + (_dx)) { \
 					if (bd[idx] != clr) break; \
 					score += i * (3 - 2 * clr); \
 				} \
@@ -37,7 +37,7 @@ static int evaluate(Board &bd, uint8_t myclr) {
 	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);
+	CHECK(bounds.left + (RLEN-1), bounds.right           , bounds.top, bounds.bottom - (RLEN-1), -1, 1);
 
 #undef CHECK
 
diff --git a/ai_mm2.cpp b/ai_mm2.cpp
new file mode 100644
index 0000000..93b40b2
--- /dev/null
+++ b/ai_mm2.cpp
@@ -0,0 +1,166 @@
+#include <iostream>
+#include <cstring>
+#include <cassert>
+#include <climits>
+#include "ai_mm2.h"
+#include "util.h"
+
+using namespace std;
+
+#define SCORE_WIN 10
+#define SCORE_LOSE (-10)
+#define SCORE_TIE 0
+#define INF (1e34)
+
+#define MAXDEPTH 3
+
+
+static int scoreTable[ipow(3, RLEN)];
+
+__attribute__((constructor))
+static void initScoreTable() {
+	int len = sizeof(scoreTable) / sizeof(scoreTable[0]);
+	uint8_t values[RLEN];
+	memset(values, 0, RLEN);
+
+	for (int i = 0; i < len; i++) {
+		int numempty = 0;
+		uint8_t clr = 0;
+		for (int j = 0; j < RLEN; j++) {
+			if (values[j] == 0) numempty++;
+			else if (clr == 0) clr = values[j];
+			else if (clr != values[j]) {scoreTable[i] = 0; goto nope;}
+		}
+
+		if (numempty == RLEN) {
+			scoreTable[i] = 0;
+		} else {
+			scoreTable[i] = (3 - 2 * clr) * (1 << (RLEN - 1 - numempty));
+		}
+
+	nope:
+		for (int j = 0; j < RLEN; j++) {
+			values[j]++;
+			if (values[j] == 3) values[j] = 0;
+			else break;
+		}
+	}
+}
+
+
+static int evaluate(Board &bd, uint8_t myclr) {
+	Bounds bounds = bd.computeBounds();
+
+	int score = 0;
+
+#define CHECK(_ident, _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; \
+				int scidx = 0; \
+				for (int i = 1; i <= RLEN; i++, idx += BSZ * (_dy) + (_dx)) { \
+					scidx *= 3; \
+					scidx += bd[idx]; \
+				} \
+				score += scoreTable[scidx]; \
+			} \
+		} \
+	} while (0)
+
+	CHECK(1, bounds.left           , bounds.right - (RLEN-1), bounds.top, bounds.bottom           ,  1, 0);
+	CHECK(2, bounds.left           , bounds.right - (RLEN-1), bounds.top, bounds.bottom - (RLEN-1),  1, 1);
+	CHECK(3, bounds.left           , bounds.right           , bounds.top, bounds.bottom - (RLEN-1),  0, 1);
+	CHECK(4, 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 MM2::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_mm2.h b/ai_mm2.h
new file mode 100644
index 0000000..44662a8
--- /dev/null
+++ b/ai_mm2.h
@@ -0,0 +1,11 @@
+#pragma once
+
+#include "board.h"
+
+using namespace std;
+
+
+namespace MM2 {
+	// bd will be unchanged upon return
+	int calcMove(Board &bd, uint8_t myclr);
+}
diff --git a/util.h b/util.h
index 52c37ae..2142c8f 100644
--- a/util.h
+++ b/util.h
@@ -18,3 +18,10 @@ struct Idx {
 inline ostream& operator<<(ostream &os, const Idx &obj) {
 	return os << '(' << obj.x << ',' << obj.y << ')';
 }
+
+
+inline constexpr int ipow(int b, int e) {
+	int r = 1;
+	for (int i = 0; i < e; i++) r *= b;
+	return r;
+}