How can I check for symmetry along the mid column in the board of Connect 4 in javascript when using bitboards?

Question

I have the bitboard representation like this for each player:

00000000 0000000 0000001 0000010 0000100 0010001 0000101 0000000 0000001

00000000 0000000 0000000 0000001 0000011 0001110 0000010 0000000 0000000

Where every section is a column, the rightmost section with 7 bits represents the first column. The rightmost bit in each section represents the first row.

I have a height array that keeps track of the height of where I can place a piece.

I use BigInt in javascript to represent the boards. One for each player.

bitboard = [0n, 0n];
heightBB = [0, 7, 14, 21, 28, 35, 42];

Here is how I make the moves:

playMoveBB(state, col, player) {     
    let move = 1n << BigInt(state.heightBB[col]);
    state.heightBB[col]++;
    state.bitboard[player] = state.bitboard[player] ^  move;
}

Here is how I check for wins:

__isWin(bitboard) {
    if ((bitboard & (bitboard >> 6n) & (bitboard >> 12n) & (bitboard >> 18n)) !== 0n) return true; // diagonal \
    if ((bitboard & (bitboard >> 8n) & (bitboard >> 16n) & (bitboard >> 24n)) !== 0n) return true; // diagonal /
    if ((bitboard & (bitboard >> 7n) & (bitboard >> 14n) & (bitboard >> 21n)) !== 0n) return true; // horizontal
    if ((bitboard & (bitboard >> 1n) & (bitboard >>  2n) & (bitboard >>  3n)) !== 0n) return true; // vertical
    return false;
}   

How can I check for symmetry along the mid column? So that left side of the board is the same as right side of the board, from the perspective of mid column.

How can I achieve this using this bitboard representation of a Connect 4 game?

Answer 1

This is a matter of shifting the three right (higher-bit) columns to their mirrored positions at the low end, and compare that with the three left (lower-bit) columns:

const isSymmetrical = (bitboard) => bitboard.every(b => 
    (b & 0x1FFFFFn) === ((b >> 42n) & 0x00007Fn | 
                         (b >> 28n) & 0x003F80n | 
                         (b >> 14n) & 0x1FC000n)
);

Explanation:

• b & 0x1FFFFFn selects the bits that belong to the first three columns (3 times 7 bits)
• b >> 42n shifts the bits that belong to the last column to the first column. ... & 0x00007Fn throws away any other bits, so that only the bits that arrived in the first column remain
• b >> 28n shifts the bits that belong to the one-but-last column to the second column. ... & 0x003F80n throws away any other bits, so that only the bits that arrived in the second column remain
• b >> 14n shifts the bits that belong to the fifth column to the third column. ... & 0x1FC000n throws away any other bits, so that only the bits that arrived in the third column remain
• | combines the above result so that we have bits in the first, second and third column which correspond to what originally is in the seventh, sixth and fifth column.
• Finally the equality check will verify that this result corresponds to what is already in the first, second and third column, and would indicate the symmetry of the board.

Here is the same code, but using binary notation for the bitmasks:

const isSymmetrical = (bitboard) => bitboard.every(b => 
    (b & 0b111111111111111111111n) === ((b >> 42n) & 0b000000000000001111111n | 
                                        (b >> 28n) & 0x000000011111110000000n | 
                                        (b >> 14n) & 0x111111100000000000000n)
);