BitBully 0.0.56-a6
Loading...
Searching...
No Matches
Board.h
1#ifndef XBITBULLY__BOARD_H_
2#define XBITBULLY__BOARD_H_
3
4#include <array>
5#include <cassert>
6#include <cstddef>
7#include <cstdint>
8#include <iostream>
9#include <map>
10#include <random>
11#include <sstream>
12#include <vector>
13
14#include "MoveList.h"
15
16// TODO: Move function definitions to .cpp file!
17/*
18 * // https://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel
19 * A generalization of the best bit counting method to integers of bit-widths
20upto 128 (parameterized by type T) is this:
21
22v = v - ((v >> 1) & (T)~(T)0/3); // temp
23v = (v & (T)~(T)0/15*3) + ((v >> 2) & (T)~(T)0/15*3); // temp
24v = (v + (v >> 4)) & (T)~(T)0/255*15; // temp
25c = (T)(v * ((T)~(T)0/255)) >> (sizeof(T) - 1) * CHAR_BIT; // count
26*/
27#if __GNUC__
28#define uint64_t_popcnt __builtin_popcountll
29#else
30#if _MSC_VER
31#include <intrin.h>
32#define uint64_t_popcnt __popcnt64
33#else
34#define uint64_t_popcnt popCountBoard
35#endif
36#endif
37
38namespace BitBully {
39
40#ifndef CHAR_BIT
41constexpr int CHAR_BIT = 8;
42#endif
43
44static constexpr uint64_t getMask(const std::initializer_list<int> bits) {
45 uint64_t bb{UINT64_C(0)};
46 for (const auto i : bits) {
47 // return 0, if index is out of range (0-63)
48 if (i < 0 || i >= 64) {
49 return UINT64_C(0);
50 }
51 bb |= (UINT64_C(1) << i);
52 }
53 return bb;
54}
55
56static constexpr bool isIllegalBit(const int bitIdx) {
57 constexpr int COLUMN_BIT_OFFSET = 9; // TODO: redundant in class below. Fix??
58 constexpr int N_ROWS = 6; // TODO: redundant in class below. Fix??
59 constexpr int COLUMNS = 7; // TODO: redundant in class below. Fix??
60 return bitIdx >= COLUMN_BIT_OFFSET * COLUMNS ||
61 (bitIdx % COLUMN_BIT_OFFSET) / N_ROWS;
62}
63
64static constexpr uint64_t illegalBitMask() {
65 uint64_t bb{UINT64_C(0)};
66 for (size_t i = 0; i < CHAR_BIT * sizeof(uint64_t); ++i) {
67 bb ^= (isIllegalBit(i) ? UINT64_C(1) << i : UINT64_C(0));
68 }
69 return bb;
70}
71
72class Board {
73 friend class BoardTest;
74
75 public:
76 Board();
77 static constexpr int N_COLUMNS = 7;
78 static constexpr int N_ROWS = 6;
79 static constexpr int COLUMN_BIT_OFFSET = 9;
80 enum Player { P_EMPTY = 0, P_YELLOW = 1, P_RED = 2 };
81 static constexpr size_t N_VALID_BOARD_VALUES = 3; // P_EMPTY, P_YELLOW, P_RED
82 using TBitBoard = uint64_t;
83 using TMovesCounter = int;
84 using TBoardArray = std::array<std::array<int32_t, N_ROWS>, N_COLUMNS>;
85 using TBoardArrayT = std::array<std::array<int32_t, N_COLUMNS>, N_ROWS>;
86
87 void inline playMoveFastBB(const TBitBoard mv) {
88 assert(mv != BB_EMPTY);
89 assert((mv & BB_ILLEGAL) == BB_EMPTY);
90 assert((m_bAllTokens & mv) == BB_EMPTY);
91 m_bActivePTokens ^= m_bAllTokens; // Already, switch player
92
93 // However, move is performed for current player (assuming, above switch is
94 // not yet performed)
95 m_bAllTokens ^= mv; // bitwise xor and bitwise or are equivalent here
96 m_movesLeft--;
97 }
98
99 [[nodiscard]] Board inline playMoveOnCopy(const TBitBoard mv) const {
100 Board b = *this;
101 b.playMoveFastBB(mv);
102 return b;
103 }
104
105 [[nodiscard]] Board inline copy() const {
106 Board b = *this;
107 return b;
108 }
109
110 [[nodiscard]] TBitBoard generateMoves() const;
111
112 static constexpr int popCountBoard(uint64_t x) {
113 int count = 0;
114 while (x) {
115 count += static_cast<int>(x & 1);
116 x >>= 1;
117 }
118 return count;
119 }
120
121 [[nodiscard]] inline auto popCountBoard() const {
122 return uint64_t_popcnt(m_bAllTokens);
123 }
124
125 [[nodiscard]] bool isLegalMove(int column) const;
126
127 static uint64_t hash(uint64_t x) {
128 x = (x ^ (x >> 30)) * UINT64_C(0xbf58476d1ce4e5b9);
129 x = (x ^ (x >> 27)) * UINT64_C(0x94d049bb133111eb);
130 x = x ^ (x >> 31);
131 return x;
132 }
133
134 [[nodiscard]] uint64_t uid() const {
135 // the resulting 64-bit integer is a unique identifier for each board
136 // Can be used to store a position in a transposition table
137 return m_bActivePTokens + m_bAllTokens;
138 }
139
140 [[nodiscard]] uint64_t hash() const {
141 return hash(hash(m_bActivePTokens) ^ (hash(m_bAllTokens) << 1));
142 }
143
144 static TBitBoard nextMove(TBitBoard allMoves) {
145 for (const auto p : BB_MOVES_PRIO_LIST) {
146 if (const TBitBoard pvMv = allMoves & p) {
147 allMoves = pvMv;
148 break;
149 }
150 }
151 return lsb(allMoves);
152 }
153
154 bool operator==(const Board& b) const {
155 const bool equal = (b.m_bAllTokens == m_bAllTokens &&
156 b.m_bActivePTokens == m_bActivePTokens);
157
158 // Assert that if board is equal that also movesLeft are equal
159 assert((equal && (b.m_movesLeft == m_movesLeft)) || !equal);
160 return equal;
161 }
162
163 bool operator!=(const Board& b) const { return !(b == *this); }
164
165 TBitBoard findOddThreats(TBitBoard moves);
166
167 bool setBoard(const TBoardArray& board);
168
169 bool setBoard(const TBoardArrayT& board);
170
171 bool setBoard(const std::vector<int>& moveSequence);
172
173 bool setBoard(const std::string& moveSequence);
174
175 [[nodiscard]] TBoardArray toArray() const;
176
177 static bool isValid(const TBoardArray& board);
178
179 bool playMove(int column);
180
181 [[nodiscard]] bool canWin() const;
182
183 [[nodiscard]] bool canWin(int column) const;
184
185 [[nodiscard]] bool hasWin() const;
186
187 [[nodiscard]] std::string toString() const;
188
189 [[nodiscard]] inline TMovesCounter movesLeft() const { return m_movesLeft; }
190
191 [[nodiscard]] inline TMovesCounter countTokens() const {
192 return N_ROWS * N_COLUMNS - m_movesLeft;
193 }
194
195 [[nodiscard]] Board mirror() const;
196
197 [[nodiscard]] MoveList sortMoves(TBitBoard moves) const;
198
199 TBitBoard findThreats(TBitBoard moves);
200
201 static inline TBitBoard lsb(const TBitBoard x) {
202 const auto mvMask = x - UINT64_C(1);
203 return ~mvMask & x;
204 }
205
206 [[nodiscard]] TBitBoard generateNonLosingMoves() const {
207 // Mostly inspired by Pascal's Code
208 // This function might return an empty bitboard. In this case, the active
209 // player will lose, since all possible moves will lead to a defeat.
210 TBitBoard moves = generateMoves();
211 const TBitBoard threats =
212 winningPositions(m_bActivePTokens ^ m_bAllTokens, true);
213 if (const TBitBoard directThreats = threats & moves) {
214 // no way we can neutralize more than one direct threat...
215 moves = directThreats & (directThreats - 1) ? UINT64_C(0) : directThreats;
216 }
217
218 // No token under an opponent's threat.
219 return moves & ~(threats >> 1);
220 }
221
222 [[nodiscard]] TBitBoard doubleThreat(const TBitBoard moves) const {
223 const TBitBoard ownThreats = winningPositions(m_bActivePTokens, false);
224 const TBitBoard otherThreats =
225 winningPositions(m_bActivePTokens ^ m_bAllTokens, true);
226 return moves & (ownThreats >> 1) & (ownThreats >> 2) & ~(otherThreats >> 1);
227 }
228
229 /* [ *, *, *, *, *, *, *]
230 * [ *, *, *, *, *, *, *]
231 * [ *, *, *, *, *, *, *]
232 * [ 5, 14, 23, 32, 41, 50, 59],
233 * [ 4, 13, 22, 31, 40, 49, 58],
234 * [ 3, 12, 21, 30, 39, 48, 57],
235 * [ 2, 11, 20, 29, 38, 47, 56],
236 * [ 1, 10, 19, 28, 37, 46, 55],
237 * [ 0, 9, 18, 27, 36, 45, 54]
238 */
239 [[nodiscard]] int toHuffman() const {
240 // This function is only defined for positions with an even number of tokens
241 // and for positions with less or equal than 12 tokens.
242 if (m_movesLeft < 30 || m_movesLeft & 1) {
243 return 0;
244 }
245 int huff = INT64_C(0);
246
247 for (int i = 0; i < N_COLUMNS; ++i) {
248 auto all = m_bAllTokens;
249 auto active = m_bActivePTokens;
250 all >>= (i * COLUMN_BIT_OFFSET);
251 active >>= (i * COLUMN_BIT_OFFSET);
252 for (int j = 0; j < N_ROWS && (all & 1); j++) {
253 huff <<= 2; // we will insert 2 bits for yellow or red
254 huff |= (active & 1) ? 2 : 3; // yellow-> 10b, red -> 11b
255 all >>= 1;
256 active >>= 1;
257 }
258 huff <<= 1; // insert 0 to indicate the end of the column
259 }
260 // length until here (for 12-ply position): 12*2+7 = 31
261 return huff << 1; // add one 0-bit to fill up to a full byte
262 }
263
264 static std::pair<Board, std::vector<int>> randomBoard(
265 const int nPly, const bool forbidDirectWin = true) {
266 if (nPly < 0 || nPly > N_COLUMNS * N_ROWS) {
267 return {};
268 }
269
270 auto [b, mvList] = randomBoardInternal(nPly);
271
272 while (mvList.size() != static_cast<decltype(mvList.size())>(nPly) ||
273 (forbidDirectWin && b.canWin())) {
274 std::tie(b, mvList) = randomBoardInternal(nPly);
275 }
276
277 return std::make_pair(b, std::move(mvList));
278 }
279
280 [[nodiscard]] std::vector<Board> allPositions(const int upToNPly,
281 bool exactlyN) const {
282 // https://oeis.org/A212693
283 std::map<uint64_t, Board> positions;
284 positions.insert({uid(), *this}); // add empty board
285 addAfterStates(positions, *this, upToNPly);
286
287 std::vector<Board> boardVector;
288 boardVector.reserve(positions.size()); // Optimize memory allocation
289
290 for (const auto& [key, board] : positions) {
291 if (!exactlyN || board.countTokens() == upToNPly)
292 boardVector.push_back(board); // Copy each board into the vector
293 }
294 return boardVector;
295 }
296
297 private:
298 /* [ *, *, *, *, *, *, *]
299 * [ *, *, *, *, *, *, *]
300 * [ *, *, *, *, *, *, *]
301 * [ 5, 14, 23, 32, 41, 50, 59],
302 * [ 4, 13, 22, 31, 40, 49, 58],
303 * [ 3, 12, 21, 30, 39, 48, 57],
304 * [ 2, 11, 20, 29, 38, 47, 56],
305 * [ 1, 10, 19, 28, 37, 46, 55],
306 * [ 0, 9, 18, 27, 36, 45, 54]
307 */
308 static constexpr auto BOTTOM_ROW_BITS = {54, 45, 36, 27, 18, 9, 0};
309 static constexpr TBitBoard BB_BOTTOM_ROW = getMask(BOTTOM_ROW_BITS);
310 static constexpr auto TOP_ROW_BITS = {59, 50, 41, 32, 23, 14, 5};
311 static constexpr TBitBoard BB_TOP_ROW = getMask(TOP_ROW_BITS);
312 static constexpr TBitBoard BB_ILLEGAL = illegalBitMask();
313 static constexpr TBitBoard BB_ALL_LEGAL_TOKENS = ~BB_ILLEGAL;
314 static constexpr TBitBoard BB_EMPTY{UINT64_C(0)};
315
316 // These two center fields generally are the most promising ones:
317 static constexpr TBitBoard BB_MOVES_PRIO1 = getMask({29, 30});
318
319 // After {29, 30}, we should consider these moves, and so on:
320 static constexpr TBitBoard BB_MOVES_PRIO2 = getMask({31, 21, 20, 28, 38, 39});
321 static constexpr TBitBoard BB_MOVES_PRIO3 = getMask({40, 32, 22, 19, 27, 37});
322 static constexpr TBitBoard BB_MOVES_PRIO4 = getMask({47, 48, 11, 12});
323 static constexpr TBitBoard BB_MOVES_PRIO5 =
324 getMask({49, 41, 23, 13, 10, 18, 36, 46});
325 static constexpr TBitBoard BB_MOVES_PRIO6 = getMask({45, 50, 14, 9});
326 static constexpr auto BB_MOVES_PRIO_LIST = {BB_MOVES_PRIO1, BB_MOVES_PRIO2,
327 BB_MOVES_PRIO3, BB_MOVES_PRIO4,
328 BB_MOVES_PRIO5, BB_MOVES_PRIO6};
329
330 /* Having a bitboard that contains all stones and another one representing the
331 * current active player has the advantage that we do not have to do any
332 * branching to figure out which player's turn it is. After each move we
333 * simply apply an XOR-operation to switch players. */
334 /* [ *, *, *, *, *, *, *]
335 * [ *, *, *, *, *, *, *]
336 * [ *, *, *, *, *, *, *]
337 * [ 5, 14, 23, 32, 41, 50, 59],
338 * [ 4, 13, 22, 31, 40, 49, 58],
339 * [ 3, 12, 21, 30, 39, 48, 57],
340 * [ 2, 11, 20, 29, 38, 47, 56],
341 * [ 1, 10, 19, 28, 37, 46, 55],
342 * [ 0, 9, 18, 27, 36, 45, 54]
343 */
344 TBitBoard m_bAllTokens, m_bActivePTokens;
345 TMovesCounter m_movesLeft;
346
347 static TBitBoard winningPositions(TBitBoard x, bool verticals);
348
349 auto static inline constexpr getColumnMask(const int column) {
350 assert(column >= 0 && column < N_COLUMNS);
351 return (UINT64_C(1) << (column * COLUMN_BIT_OFFSET + N_ROWS)) -
352 (UINT64_C(1) << (column * COLUMN_BIT_OFFSET));
353 }
354
355 auto static inline constexpr getRowMask(const int row) {
356 assert(row >= 0 && row < N_ROWS);
357 TBitBoard mask{0};
358 for (int i = 0; i < N_COLUMNS; ++i) {
359 mask |= (UINT64_C(1) << (i * COLUMN_BIT_OFFSET + row));
360 }
361 return mask;
362 }
363
364 /* [ *, *, *, *, *, *, *]
365 * [ *, *, *, *, *, *, *]
366 * [ *, *, *, *, *, *, *]
367 * [ 5, 14, 23, 32, 41, 50, 59],
368 * [ 4, 13, 22, 31, 40, 49, 58],
369 * [ 3, 12, 21, 30, 39, 48, 57],
370 * [ 2, 11, 20, 29, 38, 47, 56],
371 * [ 1, 10, 19, 28, 37, 46, 55],
372 * [ 0, 9, 18, 27, 36, 45, 54]
373 */
374 auto static constexpr mirrorBitBoard(const TBitBoard x) {
375 // TODO: It should be possible to do it in x only (using XORS). But,
376 // premature optimization is the root of all evil. Try this later.
377 // TODO: Any difference using XOR instead of OR? (probably not)...
378 TBitBoard y{UINT64_C(0)};
379 // move left-most column to right-most and vice versa:
380 y |= ((x & getColumnMask(6)) >> 6 * COLUMN_BIT_OFFSET);
381 y |= ((x & getColumnMask(0)) << 6 * COLUMN_BIT_OFFSET);
382
383 // Same with columns 1 & 5...
384 y |= ((x & getColumnMask(5)) >> 4 * COLUMN_BIT_OFFSET);
385 y |= ((x & getColumnMask(1)) << 4 * COLUMN_BIT_OFFSET);
386
387 // Same with columns 2 & 4
388 y |= ((x & getColumnMask(4)) >> 2 * COLUMN_BIT_OFFSET);
389 y |= ((x & getColumnMask(2)) << 2 * COLUMN_BIT_OFFSET);
390
391 // column 3 stays where it is...
392 return y | (x & getColumnMask(3));
393 }
394
395 static constexpr uint64_t getMaskColRow(const int column, const int row) {
396 assert(column >= 0 && column < N_COLUMNS);
397 assert(row >= 0 && row < N_ROWS);
398 return UINT64_C(1) << (column * COLUMN_BIT_OFFSET + row);
399 }
400
401 static constexpr Player opponent(Player p) {
402 return static_cast<Player>(3 - p);
403 }
404
405 void inline playMoveFast(const int column) {
406 assert(column >= 0 && column < N_COLUMNS);
407 const TBitBoard columnMask = getColumnMask(column);
408 assert(uint64_t_popcnt(columnMask) == N_ROWS);
409 const auto mvMask = (m_bAllTokens + BB_BOTTOM_ROW) & columnMask;
410 playMoveFastBB(mvMask);
411 }
412
413 static void addAfterStates(std::map<uint64_t, Board>& boardCollection,
414 const Board& b, const int nPly) {
415 if (b.countTokens() >= nPly) {
416 return;
417 }
418
419 auto moves = b.generateMoves();
420
421 while (moves) {
422 const auto mv = b.nextMove(moves);
423 assert(uint64_t_popcnt(mv) == 1);
424 if (auto newB = b.playMoveOnCopy(mv);
425 boardCollection.find(newB.uid()) == boardCollection.end() &&
426 !b.hasWin()) {
427 // We have not reached this position yet
428 boardCollection.insert({newB.uid(), newB});
429 addAfterStates(boardCollection, newB, nPly);
430 }
431
432 moves ^= mv;
433 }
434 }
435
436 static std::pair<Board, std::vector<int>> randomBoardInternal(
437 const int nPly) {
438 if (nPly < 0 || nPly > N_COLUMNS * N_ROWS) {
439 return {};
440 }
441 Board b;
442
443 // Create a random device to seed the random number generator
444 static std::random_device rd;
445
446 // Create a Mersenne Twister random number generator
447 static std::mt19937 gen(rd());
448
449 // Create a uniform integer distribution for the desired range
450 static std::uniform_int_distribution<> nextUniform(0, N_COLUMNS);
451
452 std::vector<int> mvSequence;
453 static constexpr int MAX_TRIES = 20;
454 for (int j = 0; j < nPly; ++j) {
455 int randColumn, tries = 0;
456 do {
457 randColumn = nextUniform(gen);
458 tries++;
459 } while (tries < MAX_TRIES &&
460 (!b.isLegalMove(randColumn) || b.canWin(randColumn)));
461 if (tries >= MAX_TRIES) {
462 return {};
463 }
464 b.playMove(randColumn);
465 mvSequence.emplace_back(randColumn);
466 }
467
468 assert(b.countTokens() == nPly);
469
470 return {std::move(b), std::move(mvSequence)};
471 }
472
473 static TBoardArray transpose(const TBoardArrayT& board);
474};
475
476} // namespace BitBully
477
478#endif // XBITBULLY__BOARD_H_