javascriptbit-manipulationbitboard

How do I look for the 7shape in the game of Connect 4 using bitboards for each player?

The shape I am looking for looks like this:

enter image description here

I have two bitboards that represent two players in the game Connect 4. The bits that are used are bits from 0 to 48, so 49 bits in total. The representation looks like this:

  6 13 20 27 34 41 48   55 62     Additional row
+---------------------+ 
| 5 12 19 26 33 40 47 | 54 61     top row
| 4 11 18 25 32 39 46 | 53 60
| 3 10 17 24 31 38 45 | 52 59
| 2  9 16 23 30 37 44 | 51 58
| 1  8 15 22 29 36 43 | 50 57
| 0  7 14 21 28 35 42 | 49 56 63  bottom row
+---------------------+

The top row is not being used for anything particular, but this setup makes it easier to check for wins. There are 7 columns and 6 rows as in the game of Connect 4.

The bits are structured as follows:

... 0000000 0000000 0000010 0000011 0000000 0000000 0000000 // encoding Xs
... 0000000 0000000 0000001 0000100 0000001 0000000 0000000 // encoding Os
      col 6   col 5   col 4   col 3   col 2   col 1   col 0

So we use 7 bits for each column, we ignore the last bit in each column as there are only 6 rows per column.

The position in the picture can be represented with two bits.

Red (player 1) bitboard: 101000011000001100000000. The most significant bit here is the middle column move at the bottom. The first move that red made in the middle of the board.

Here is the bitboard for player 0 (yellow): 1010000000100000010000001. The least significant bit here is the leftmost move by yellow at the bottom of the board.

In order to confirm this 7shape, we need to check that all reds pieces exists, the way it is drawn on the picture, but at the same time make sure that the two crossed positions are not full, but empty.

With this I am able to identify the 7 shape, but I don't know how to check if the two crossed spots are empty, I only know how to check if red has not played there.

is7Trap(bitboard, player) {
    const bp = bitboard[player];
    const bo = bitboard[1 - player];
    const shapeExists = (bp & (bp >> 2n) & (bp << 5n) & (bp << 6n) & (bp << 12n)) !== 0n;
    const topSpotRedFree = (bp & (bp >> 2n) & (bp << 5n) & (bp << 6n) & (bp << 12n) & (bp << 18n)) === 0n;
    const bottomSpotRedFree = (bp & (bp >> 2n) & (bp << 5n) & (bp << 6n) & (bp << 12n) & (bp << 19n)) === 0n;
    console.log("shapeExists", shapeExists);
    console.log("topSpotRedFree", topSpotRedFree);
    console.log("bottomSpotRedFree", bottomSpotRedFree);
    console.log(bp.toString(2));
    console.log(bo.toString(2));
    if (shapeExists && topSpotRedFree && bottomSpotRedFree) {
        return true;
    }
    return false;        
}

I don't know how to check if yellow also has not played there.

Solution

  • You can complete your is7Trap function with the following idea:

    Here is the adaptation of your function:

    const DUMMY_ROW = 0b1000000100000010000001000000100000010000001000000n;

function is7Trap(bitboard, player) {
    const bp = bitboard[player];
    const bo = bitboard[1 - player];
    // Shift (with 18n) the bottom(s) of the found "7" shape(s) to the top spot(s) that should be free
    const topSpot = (bp & (bp >> 2n) & (bp << 5n) & (bp << 6n) & (bp << 12n)) >> 18n;
    const shapeExists = topSpot !== 0n;
    // Verify that the spot and the one below it are both free:
    const bothSpotsFree = ((bo | bp | DUMMY_ROW) & (topSpot | (topSpot >> 1n))) === 0n;
    console.log("shapeExists", shapeExists);
    console.log("bothSpotsFree", bothSpotsFree);
    return shapeExists && bothSpotsFree;
}

    Generalisation

    It will lead to a lot of code if you are going to check all types of arrow-shapes. Realise that there are upside-down 7 shapes, X shapes, or shapes where the two free spots are between columns that have the discs that make the threats, like for instance in these examples where asterisks highlight the two free spots:

    . . . X . . .     . . . . . . .     . . . . . . . 
. . . X . . .     . . . . . . .     . . . . . . .
. . . O . . .     . . . . . O .     . . O . X O .
O * O O . . .     . . . . * X X     . . X * O X .
X * X O . . .     . . X O * O O     . . X * O X .
O . X X . . .     . X O O . X X     . . O . X O .

    To detect all these variations with the approach you have taken is going to be a enormous task.

    My guess is that you don't only want to look for particular shapes, but actually want to detect two threats on top of each other, no matter how these two threats are "supported" by the already played discs.

    I would suggest that you have threat detection set up, and possibly it is more interesting to keep that information incrementally updated as moves are made, than to have to recalculate that each time from scratch.

    To know where the threats are, it will be helpful to introduce the concept of groups, i.e. all possible sets of four cells that represent a winning combination if ever one player can occupy all four of them. Then incrementally keep track for each group which cells are still free, which are occupied by the first player, and which by the second player. If a move results in a group that has three of its cells occupied by the same player, then you know that the only remaining free cell is a threat. You could flag this cell in a bitmap reserved for threats; one per player -- just like the bitboard you have for the already played discs.

    Here is a runnable implementation in JavaScript. It has some preprocessing going on in a static block to identify all the groups and the cells in those groups. I realise I might not have used the exact same representation as you might have, but it should not be difficult to translate this to your set up:

    class Connect4 {
    static {
        // Two static variables:
        this.cellToGroups = Array.from({length: 7*7}, () => []);
        this.groupToCells = [];
        
        const register = (row, col, shift) => {
            let cellId = row + col * 7;
            const group = [];
            // Collect the four cells that make up the group
            // And for each cell add a the id of the group it is in
            for (let i = 0; i < 4; i++) {
                group.push(cellId);
                this.cellToGroups[cellId].push(this.groupToCells.length);
                cellId += shift;
            }
            this.groupToCells.push(group);
        };
        // All vertical groups
        for (let row = 0; row < 3; row++) {
            for (let col = 0; col < 7; col++) {
                register(row, col, 1);
            }
        }
        // All horizontal groups
        for (let row = 0; row < 7; row++) {
            for (let col = 0; col < 4; col++) {
                register(row, col, 7);
            }
        }
        // All diagonal groups
        for (let row = 0; row < 3; row++) {
            for (let col = 0; col < 4; col++) {
                register(row, col, 8);
                register(5 - row, col, 6);
            }
        }
    }
    constructor() {
        this.bitboard = [0n, 0n];
        this.heights = [0, 0, 0, 0, 0, 0, 0];
        // For each group: array with cells taken by X, taken by O, taken by neither
        this.groupOccupation = Connect4.groupToCells.map(cells => [[], [], [...cells]]); 
        this.threats = [0n, 0n]; // Same structure as bitboard: a 1 indicates a winning move (if reachable)
        this.moves = []; // History of played moves (columns)
    }
    move(col) {
        const row = this.heights[col];
        if (row == 6) throw "Invalid move";
        const player = this.moves.length % 2;
        const cellId = row + col * 7;
        const bit = 1n << BigInt(cellId);
        this.heights[col]++;
        this.bitboard[player] |= bit;
        // Incrementally update the occupation this player has in the groups
        //    that this cell is part of
        for (const groupId of Connect4.cellToGroups[cellId]) {
            const group = this.groupOccupation[groupId];
            // In this group, mark the cell as taken by this player
            let i = group[2].indexOf(cellId);
            group[player].push(...group[2].splice(i, 1));
            // Check if this group is completed or becomes a threat
            if (group[player].length === 4) this.gameOver = true;
            if (group[player].length === 3 && group[2].length) { // Making a threat!
                this.threats[player] |= 1n << BigInt(group[2][0]);
            }
        }
        this.moves.push(col);
    }
    toString() {
        return Array.from({length: 6}, (_, top) =>
            Array.from({length: 7}, (_, col) => {
                const bit = BigInt(5 - top + col * 7);
                return (this.bitboard[0] >> bit) & 1n ? "X" 
                     : (this.bitboard[1] >> bit) & 1n ? "O" 
                     // Output the threats with small letters
                     : (this.threats[0] >> bit) & 1n ? "x"
                     : (this.threats[1] >> bit) & 1n ? "o"
                     : ".";
            }).join(" ")
        ).join("\n");
    }
}

// Demo
const game = new Connect4();
const moves = [3, 3, 3, 3, 3, 0, 1, 1, 0, 4, 0, 4];
for (const move of moves) game.move(move);
console.log("" +game);

    The toString method renders threats with lowercase letters. As you can see in this example run, there are two threats on top of each other for player "O" in the third column. This information is readily available in the this.threats bitmaps.

    Note that both players could have a threat on the same cell. I did not provide for displaying that in the toString method, but that is not essential. The this.threats bitmaps provide for that possibility.