summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authortomsmeding <tom.smeding@gmail.com>2019-02-17 00:13:40 +0100
committertomsmeding <tom.smeding@gmail.com>2019-02-17 00:13:40 +0100
commit9d0f4baa7d82d896b9660dfb2fe484129d5cfd13 (patch)
treeefe557b18123c685e4b5e3434b307f9ca785fc73
parenta9e8a7ff0e993d946c719b0bea8735483f0e6a2d (diff)
WIP mm player
-rw-r--r--ai_mm.cpp132
-rw-r--r--ai_mm.h11
-rw-r--r--main.cpp1
3 files changed, 144 insertions, 0 deletions
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"