I found this great answer by Gary C, which uses bitwise operators and minimal number of comparisons to check for a win in Tic-tac-toe. The only issue is that the value of each cell needs to be hardcoded at the start.
For example as he says that the cell[0][0] would be given the value of
100 0 000 0 000 0 100 0 000 0 000 100 0 000 0
where each group of 3 bits represents
row1 0 row2 0 row3 0 column1 0 column2 0 column3 0 diag 0 antiDiag 0
, and the following 0 acts as a padding (important for the rest of his solution). This is due to the fact that cell[0][0] occupies the first position of row1, column1 as well as the diagonal.
This task, although cumbersome, is certainly doable for a 3x3 board, however the question arises how to do this for a general nxn board.
I assume that the inputs we will have to go off of are: a)the row and column index of the cell. b)the value of n, which tells us that each group must have n bits, and one additional bit for padding.
I understand that this is a very specific scenario in a very specific solution. However his answer is quite brilliant, and one cannot but wonder how to actually implement it all the way. Half-answers and suggestions are also appreciated, as it will aid the discussion.
CodePudding user response：
Short Answer...
Believe the best course is a hybrid between Gary C and alexsalo, specifically make use of alexsalo's bitboard representation of the X's and O's, but employ a similar technique as Gary C's method for determining a winning position. This requires more bit twiddling to determine if the last move was a winner, but is readily extensible for N x N tic-tac-toe...
Number of Bits Required for N x N tic-tac-toe by Gary C
With the scheme from Gary C, an N x N tic-tac-toe will involve the bits representing the rows, columns, and diagonals, in addition to the spacer bits. And this bitwise representation will be required for both the X's and O's. With a bit of math, we can determine the number of bits required for each player. First, the number of bits representing rows, columns, and diagonals...
- N rows * N cols * ( 1 set of rows 1 set of cols ) 2 diags * N
...plus the number of bits representing spacers...
- N rows N cols 2 diags
The following table shows the total number of bits required per player for a N x N version of tic tac toe:
| N | Bits Required | Spacer | Total |
|---|---|---|---|
| 3 | 24 | 8 | 32 |
| 4 | 40 | 10 | 50 |
| 5 | 60 | 12 | 72 |
| 6 | 84 | 14 | 98 |
| 7 | 112 | 16 | 128 |
| 8 | 144 | 18 | 162 |
| 9 | 180 | 20 | 200 |
| 10 | 220 | 22 | 242 |
| 11 | 264 | 24 | 288 |
| 12 | 312 | 26 | 338 |
| 13 | 364 | 28 | 392 |
| 14 | 420 | 30 | 450 |
| 15 | 480 | 32 | 512 |
| 16 | 544 | 34 | 578 |
Outside of using BigInt, the largest integer that Javascript supports is the 64 bit BigUint64Array value type, so already beginning at a 5 x 5 board the forthcoming bitwise shift operations will already require shifting across individual binary numbers. Of course one can make use of BigInt, although likely with a performance hit.
Number of Bits Required for N x N tic-tac-toe by alexsalo
The scheme from alexsalo simply requires one bit per square, and thus the number of bits to represent either the X's or O's for a N x N board is...
| N | Bits Required |
|---|---|
| 3 | 9 |
| 4 | 16 |
| 5 | 25 |
| 6 | 36 |
| 7 | 49 |
| 8 | 64 |
| 9 | 81 |
| 10 | 100 |
| 11 | 121 |
| 12 | 144 |
| 13 | 169 |
| 14 | 196 |
| 15 | 225 |
| 16 | 256 |
In this case, up to an 8 x 8 board can be handled by a single BigUint64Array value. Again, after that, multiple binary values will be required unless using BigInt.
Testing for Winner
The trade off, of course, is that with a simpler data structure, the test for a winner is a bit more costly, but as indicated earlier, this is more easily extensible for a variable size tic-tac-toe board. By example, a 4 x 4 tic-tac-toe board will be used to show the algorithms to check for a winner by Row, Column, and Diagonal. These algorithms are O(N) in nature, so easy to extend algorithmically for larger boards, particularly if using BigInt. If using, say, BigUint64Array values, then any bit shifting will involve overflow between the underlying integer values, making the bitwise algorithms a bit more complex, but not overly so.
Eg, bit shifting a 64 bit Uint is straightforward, but not so with a 128 bit Uint, as there is no internal representation of a 128 bit number, other than BigInt in which case there will likely be a performance hit. To represent a 128 bit Uint with two 64 bit Uints is possible, but if, say, shifting right 10 bits in the first 64 bit Uint, the 10 right most bits must then be shifted into the second 64 bit Uint...
Back to testing for a winner by example, let's say our 4 x 4 board game state is currently...
a b c d
- - - -
1: O X O O
2: X X X
3: X X O O
4: X
Then the representation of X's and O's will be...
- X bitboard: 0100 0111 1100 0100
- O bitboard: 1011 0000 0011 0000
Check for winner in Row...
Determine if a player has 4 in the same Row by simply ANDing the bits in a Row together and then checking if the result is non-zero.
( bitboard >>> 3) & (bitboard >>> 2) & (bitboard >>> 1) & bitboard & 0001 0001 0001 0001
For example, checking the X bitboard for 4 in a Row...
abcd abcd abcd abcd
-------------------------------------
bitboard >>> 3: 0000 1000 1111 1000
bitboard >>> 2: 0001 0001 1111 0001
bitboard >>> 1: 0010 0011 1110 0010
bitboard: 0100 0111 1100 0100
mask: 0001 0001 0001 0001
-------------------------------------
ANDed together: 0000 0000 0000 0000 => there are no 4 X's in a single Row.
Looking down each column 'd' will show the same sequence as the bitboard row. Ie, the first set column 'd' is 0100, second is 0111, etc which is the same as the X bitboard groups of 4 bits representing each row...
Notice too that without the Gary C spacer bit, even with 5 consecutive 1's we still get the correct result, because effectively the bits are being shifted and ANDed into column 'd' and then the final mask ensures that we are only considering column 'd', and not the false positive in the third set where column 'a' appears to have 4 in a row.
Check for winner in Column
Determine if a player has 4 in a column by simply shifting and ANDing all bits in the same column and then checking if the result is non-zero.
bitboard & (bitboard >>> 4) & (bitboard >>> 8) & (bitboard >>> 12)
For example, checking the X bitboard for 4 in a Column...
abcd abcd abcd abcd
-------------------------------------
bitboard: 0100 0111 0100 0100
bitboard >>> 4: 0000 0100 0111 0100
bitboard >>> 8: 0000 0000 0100 0111
bitboard >>> 12: 0000 0000 0000 0100
-------------------------------------
ANDed together: 0000 0000 0000 0100 => column 'b' has 4 in a col.
Note that the logic for determining whether a player has 4 in a Column can be optimized to O(log N)...
Check for winner in Diagonal
Similar to checking for a winner in a Column, but instead consolidates the diagonal bits into columns 'a' and 'd'...
(bitboard >>> 12) & (bitboard << 1 | bitboard >>> 1) >>> 8 & (bitboard << 2 | bitboard >>> 2) >>> 4 & (bitboard << 3 | bitboard >>> 3)
...and like the Column check, the result will be in the lowest order 4 bits, specifically columns 'a' and 'd'.
Underlying implementation...
Suggest starting with BigInt representation of the bitboards, as this will ease the effort of hammering out the specific algorithms based on a N x N board, and then port to making use of 32 or 64 bit Uints if seeking the best performance.