From 6175cb1c53772cc92d91a39a254c38bdf8f64905 Mon Sep 17 00:00:00 2001
From: Tom Smeding <tom.smeding@gmail.com>
Date: Wed, 13 Feb 2019 21:08:37 +0100
Subject: Initial: working monte carlo AI

---
 board.cpp | 216 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 216 insertions(+)
 create mode 100644 board.cpp

(limited to 'board.cpp')

diff --git a/board.cpp b/board.cpp
new file mode 100644
index 0000000..c84e72f
--- /dev/null
+++ b/board.cpp
@@ -0,0 +1,216 @@
+#include <cstdlib>
+#include <cstring>
+#include <cassert>
+#include "board.h"
+#include "util.h"
+
+using namespace std;
+
+
+Bag Bag::uninitialised() {
+	return Bag();
+}
+
+Bag Bag::makeFull() {
+	Bag bag;
+	for (int i = 0; i < NC; i++) bag.num[i] = N;
+	bag.sum = N * NC;
+	return bag;
+}
+
+int Bag::numLeft(uint8_t clr) const {
+	return num[clr - 1];
+}
+
+int Bag::totalLeft() const {
+	return sum;
+}
+
+uint8_t Bag::peekRandom() const {
+	assert(sum != 0);
+
+	int i = random() % sum;
+	int accum = 0;
+	for (int clr = 1; clr <= NC; clr++) {
+		accum += num[clr - 1];
+		if (i < accum) {
+			return clr;
+		}
+	}
+
+	assert(false);
+}
+
+uint8_t Bag::drawRandom() {
+	uint8_t clr = peekRandom();
+	num[clr - 1]--;
+	sum--;
+	return clr;
+}
+
+void Bag::drawColour(uint8_t clr) {
+	assert(num[clr - 1] != 0);
+	num[clr - 1]--;
+	sum--;
+}
+
+void Bag::replace(uint8_t clr) {
+	num[clr - 1]++;
+	sum++;
+}
+
+
+Board Board::makeEmpty() {
+	static_assert(NC + 1 <= 256, "Too many colours");
+
+	Board bd;
+	bd.bag = Bag::makeFull();
+	memset(bd.bd, 0, BSZ * BSZ);
+	return bd;
+}
+
+// Do not call with clr == 0
+int Board::countStones(uint8_t clr, int idx, int delta) const {
+	// Since clr != 0 and the stones will never reach the edge of the board
+	// (it's too large for that), this loop will always terminate before
+	// accessing invalid memory.
+	int num = 0;
+	while (bd[idx] == clr) {
+		num++;
+		idx += delta;
+	}
+	return num;
+}
+
+void Board::newEdgeCand(int idx) {
+	// cerr << "(newEdgeCand(" << Idx(idx) << "))" << endl;
+	if (!inEdgeCands.test(idx)) {
+		edgeCands.push_back(idx);
+		inEdgeCands.set(idx);
+	}
+}
+
+void Board::put(int idx, uint8_t clr) {
+	bd[idx] = clr;
+
+	newEdgeCand(idx - 1);
+	newEdgeCand(idx + 1);
+	newEdgeCand(idx - BSZ);
+	newEdgeCand(idx + BSZ);
+}
+
+void Board::undo(int idx) {
+	bd[idx] = 0;
+
+	newEdgeCand(idx);
+}
+
+uint8_t Board::putCW(int idx, uint8_t clr) {
+	put(idx, clr);
+
+	int count[8];
+#define DO_COUNT_STONES(_i, _dx, _dy) do { int _delta = BSZ * (_dy) + (_dx); count[_i] = countStones(clr, idx + _delta, _delta); } while (0)
+	DO_COUNT_STONES(0,  0, -1);
+	DO_COUNT_STONES(1,  1, -1);
+	DO_COUNT_STONES(2,  1,  0);
+	DO_COUNT_STONES(3,  1,  1);
+	DO_COUNT_STONES(4,  0,  1);
+	DO_COUNT_STONES(5, -1,  1);
+	DO_COUNT_STONES(6, -1,  0);
+	DO_COUNT_STONES(7, -1, -1);
+#undef DO_COUNT_STONES
+
+	for (int i = 0; i < 4; i++) {
+		if (1 + count[i] + count[4 + i] >= RLEN) return clr;
+	}
+
+	return 0;
+}
+
+bool Board::checkEdge(int idx) const {
+	// Because there are always two spaces free at the ends of the board, we
+	// can safely inspect the neighbours of this cell. This is because we only
+	// call this function on cells that have either had or neighboured a stone.
+	return bd[idx - 1] || bd[idx + 1] || bd[idx - BSZ] || bd[idx + BSZ];
+}
+
+void Board::forEachMove(const function<void(int idx)> &f) {
+	vector<int> eC = edgeCands;
+	bitset<BSZ * BSZ> iEC = inEdgeCands;
+
+	size_t j = 0;
+	for (size_t i = 0; i < eC.size(); i++) {
+		int idx = eC[i];
+		// cerr << "(fEM: candidate " << Idx(idx) << "; ";
+		if (bd[idx] == 0 && checkEdge(idx)) {
+			// cerr << "edge)" << endl;
+			f(idx);
+			eC[j++] = idx;
+		} else {
+			// cerr << "-)" << endl;
+			iEC.reset(idx);
+		}
+	}
+
+	eC.resize(j);
+
+	swap(edgeCands, eC);
+	swap(inEdgeCands, iEC);
+}
+
+Bounds Board::computeBounds() const {
+	Bounds bounds;
+
+	for (int y = 1; y < BSZ - 1; y++) {
+		for (int x = 1; x < BSZ - 1; x++) {
+			int idx = BSZ * y + x;
+			if (bd[idx] != 0 || checkEdge(idx)) {
+				bounds.left = min(bounds.left, x);
+				bounds.right = max(bounds.right, x);
+				bounds.top = min(bounds.top, y);
+				bounds.bottom = max(bounds.bottom, y);
+			}
+		}
+	}
+
+	return bounds;
+}
+
+void Board::write(ostream &os) const {
+	static const char *edgeStr = "\x1B[36m+\x1B[0m";
+	static const char *openStr = "·";
+
+	Bounds bounds = computeBounds();
+
+	for (int y = bounds.top; y <= bounds.bottom; y++) {
+		for (int x = bounds.left; x <= bounds.right; x++) {
+			if (x != bounds.left) os << ' ';
+
+			int idx = BSZ * y + x;
+			if (bd[idx] != 0) os << Stone(bd[idx]);
+			else if (checkEdge(idx)) os << edgeStr;
+			else os << openStr;
+		}
+		os << endl;
+	}
+}
+
+ostream& operator<<(ostream &os, Stone stone) {
+	static const char *alphabet[] = {
+		"\x1B[1;31mR\x1B[0m",
+		"\x1B[1;34mB\x1B[0m",
+		"\x1B[1;33mY\x1B[0m",
+	};
+	static_assert(
+			NC <= sizeof(alphabet) / sizeof(alphabet[0]),
+			"Increase alphabet in Board::write");
+
+	uint8_t clr = stone.clr;
+	assert(1 <= clr && clr <= NC);
+	return os << alphabet[clr - 1];
+}
+
+ostream& operator<<(ostream &os, const Board &bd) {
+	bd.write(os);
+	return os;
+}
-- 
cgit v1.2.3-54-g00ecf