Optimise board edge handling

This new organisation assumes that you'll do very few modifications
before calling forEachMoves again.

5 files changed, 45 insertions, 44 deletions

diff --git a/ai_mc.cpp b/ai_mc.cpp
index 6175d96..2c95222 100644
--- a/ai_mc.cpp
+++ b/ai_mc.cpp
@@ -22,11 +22,10 @@ static int playout(Board bd, uint8_t myclr) {
 	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; });
+		const vector<int> &moves = bd.getEdgeCells();
 
-		assert(nmoves > 0);
-		int idx = moves[random() % nmoves];
+		assert(moves.size() > 0);
+		int idx = moves[random() % moves.size()];
 
 		// cerr << "    idx = " << Idx(idx) << " clr=" << (unsigned)clr << endl;
 
@@ -46,7 +45,8 @@ int MC::calcMove(Board &bd, uint8_t myclr) {
 	float maxscore = INT_MIN;
 	int maxat = -1;
 
-	bd.forEachMove([&bd, myclr, &maxscore, &maxat](int idx) {
+	vector<int> edgeCells = bd.getEdgeCells();
+	for (int idx : edgeCells) {
 		// cerr << "MC::calcMove: trying idx=" << Idx(idx) << endl;
 		float score = 0;
 
@@ -73,7 +73,7 @@ int MC::calcMove(Board &bd, uint8_t myclr) {
 			maxscore = score;
 			maxat = idx;
 		}
-	});
+	}
 
 	return maxat;
 }
diff --git a/ai_rand.cpp b/ai_rand.cpp
index 7479d01..c4df24e 100644
--- a/ai_rand.cpp
+++ b/ai_rand.cpp
@@ -11,9 +11,8 @@ int RAND::calcMove(Board &bd, uint8_t myclr) {
 	(void)myclr;
 	assert(bd.bag.totalLeft() > 0);
 
-	int moves[BSZ * BSZ], nmoves = 0;
-	bd.forEachMove([&moves, &nmoves](int idx) { moves[nmoves++] = idx; });
+	const vector<int> &moves = bd.getEdgeCells();
 
-	assert(nmoves > 0);
-	return moves[random() % nmoves];
+	assert(moves.size() > 0);
+	return moves[random() % moves.size()];
 }
diff --git a/board.cpp b/board.cpp
index 822fddd..b3820a0 100644
--- a/board.cpp
+++ b/board.cpp
@@ -1,5 +1,4 @@
 #include <cstdlib>
-#include <cstring>
 #include <cassert>
 #include "board.h"
 #include "util.h"
@@ -65,7 +64,9 @@ Board Board::makeEmpty() {
 
 	Board bd;
 	bd.bag = Bag::makeFull();
-	memset(bd.bd, 0, BSZ * BSZ);
+	bd.bd.fill(0);
+	bd.edgeCells.reserve(BSZ * BSZ);
+	bd.inEdgeCells.fill(-1);
 	return bd;
 }
 
@@ -84,15 +85,29 @@ int Board::countStones(uint8_t clr, int idx, int delta) const {
 
 void Board::newEdgeCand(int idx) {
 	// cerr << "(newEdgeCand(" << Idx(idx) << "))" << endl;
-	if (!inEdgeCands.test(idx)) {
-		edgeCands.push_back(idx);
-		inEdgeCands.set(idx);
+	if (inEdgeCells[idx] == -1 && bd[idx] == 0 && checkEdge(idx)) {
+		inEdgeCells[idx] = edgeCells.size();
+		edgeCells.push_back(idx);
+	}
+}
+
+void Board::removeEdgeCell(int idx) {
+	// cerr << "(removeEdgeCell(" << Idx(idx) << "))" << endl;
+	int pos = inEdgeCells[idx];
+	if (pos != -1) {
+		inEdgeCells[idx] = -1;
+		if ((unsigned)pos < edgeCells.size() - 1) {
+			int val = edgeCells[pos] = edgeCells.back();
+			inEdgeCells[val] = pos;
+		}
+		edgeCells.pop_back();
 	}
 }
 
 void Board::put(int idx, uint8_t clr) {
 	bd[idx] = clr;
 
+	removeEdgeCell(idx);
 	newEdgeCand(idx - 1);
 	newEdgeCand(idx + 1);
 	newEdgeCand(idx - BSZ);
@@ -103,6 +118,10 @@ void Board::undo(int idx) {
 	bd[idx] = 0;
 
 	newEdgeCand(idx);
+	removeEdgeCell(idx - 1);
+	removeEdgeCell(idx + 1);
+	removeEdgeCell(idx - BSZ);
+	removeEdgeCell(idx + BSZ);
 }
 
 uint8_t Board::putCW(int idx, uint8_t clr) {
@@ -134,28 +153,8 @@ bool Board::checkEdge(int idx) const {
 	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);
+const vector<int>& Board::getEdgeCells() const {
+	return edgeCells;
 }
 
 Bounds Board::computeBounds() const {
diff --git a/board.h b/board.h
index 6fad1e1..06540ee 100644
--- a/board.h
+++ b/board.h
@@ -2,6 +2,7 @@
 
 #include <iostream>
 #include <vector>
+#include <array>
 #include <bitset>
 #include <functional>
 #include <cstdint>
@@ -53,7 +54,7 @@ public:
 	uint8_t putCW(int idx, uint8_t clr);
 
 	// The callback may modify the board, but must leave it as it was after returning.
-	void forEachMove(const function<void(int idx)> &f);
+	const vector<int>& getEdgeCells() const;
 
 	void write(ostream &os) const;
 
@@ -62,19 +63,20 @@ public:
 
 private:
 	// 0 = empty, 1...NC = coloured stones
-	uint8_t bd[BSZ * BSZ];
+	array<uint8_t, BSZ * BSZ> bd;
 
-	// Candidates for edge cells; all cells that can take a stone must be
-	// elements of this list, but there may be more.
-	vector<int> edgeCands;
+	// The cells that are neighbour to a stone on the board, i.e. those cells
+	// that can take a stone in the next move.
+	vector<int> edgeCells;
 
-	// Whether a particular cell is in edgeCands.
-	bitset<BSZ * BSZ> inEdgeCands;
+	// Where a particular cell is in edgeCells (or -1 if not present).
+	array<int, BSZ * BSZ> inEdgeCells;
 
 	Board() = default;
 
 	int countStones(uint8_t clr, int idx, int delta) const;
 	void newEdgeCand(int idx);
+	void removeEdgeCell(int idx);
 };
 
 struct Stone {
diff --git a/main.cpp b/main.cpp
index ec4775a..0c6e0de 100644
--- a/main.cpp
+++ b/main.cpp
@@ -1,6 +1,7 @@
 #include <iostream>
 #include <sstream>
 #include <cstdlib>
+#include <cstring>
 #include <unistd.h>
 #include <sys/time.h>
 #include "board.h"