From 1a996c6e016b28e09895aa17201720b63d70bd71 Mon Sep 17 00:00:00 2001 From: tomsmeding Date: Sat, 16 Feb 2019 20:30:21 +0100 Subject: Optimise board edge handling This new organisation assumes that you'll do very few modifications before calling forEachMoves again. --- ai_mc.cpp | 12 ++++++------ ai_rand.cpp | 7 +++---- board.cpp | 53 ++++++++++++++++++++++++++--------------------------- board.h | 16 +++++++++------- main.cpp | 1 + 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 &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 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 &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 -#include #include #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 &f) { - vector eC = edgeCands; - bitset 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& 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 #include +#include #include #include #include @@ -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 &f); + const vector& 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 bd; - // Candidates for edge cells; all cells that can take a stone must be - // elements of this list, but there may be more. - vector 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 edgeCells; - // Whether a particular cell is in edgeCands. - bitset inEdgeCands; + // Where a particular cell is in edgeCells (or -1 if not present). + array 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 #include #include +#include #include #include #include "board.h" -- cgit v1.2.3-54-g00ecf