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