如何使用每个玩家的位板在 Connect 4 游戏中查找 7shape？

Question

我正在寻找的形状如下所示：

我有两个位板，代表 Connect 4 游戏中的两个玩家。使用的位是从 0 到 48 的位，因此总共 49 位。表示如下：

  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
+---------------------+

顶行没有用于任何特殊用途，但这种设置可以更轻松地检查获胜情况。与 Connect 4 游戏一样，有 7 列和 6 行。

这些位的结构如下：

... 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

因此我们每列使用 7 位，我们忽略每列中的最后一位，因为每列只有 6 行。

图片中的位置可以用两位来表示。

红色（玩家 1）位板：

101000011000001100000000

。这里最重要的一点是底部的中间列移动。红方在棋盘中间的第一步棋。

这是玩家 0（黄色）的位板：

1010000000100000010000001

。这里最不重要的一点是棋盘底部最左边的黄色棋步。

为了确认这个7形状，我们需要检查所有红色棋子是否存在，就像它在图片上绘制的方式一样，但同时确保两个交叉的位置不是满的，而是空的。

有了这个，我能够识别7形状，但我不知道如何检查两个交叉点是否为空，我只知道如何检查红色是否没有在那里发挥。

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;        
}

我不知道如何检查黄色是否也没有在那里玩过。

Answer 1

我的猜测是，您不仅想要寻找该形状，而且实际上想要检测彼此重叠的两个威胁。这不仅适用于您呈现的形状，而且也适用于此形状（对于玩家“O”）：

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

我建议您设置威胁检测，并且随着移动的进行而不断更新信息可能比每次从头开始重新计算更有趣。

要了解威胁在哪里，引入“组”的概念将很有帮助，即所有可能的四个单元格集合，如果一个玩家可以占据所有四个单元格，则代表获胜组合。然后逐步跟踪每个组哪些单元格仍然空闲，哪些单元格被第一个玩家占用，哪些单元格被第二个玩家占用。如果一次移动导致一个组的三个单元格被同一玩家占据，那么您就知道唯一剩余的空闲单元格是威胁。您可以在为威胁保留的位图中标记此单元格；每个播放器一个 - 就像您为已播放的光盘所拥有的位板一样。 这是一个可运行的 JavaScript 实现。它在

static

块中进行一些预处理，以识别所有组以及这些组中的单元格。我意识到我可能没有使用与您可能使用的完全相同的表示形式，但将其转换为您的设置应该不难：

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);
    }
    undo() {
        if (!this.moves.length) throw "Cannot undo";
        const col = this.moves.pop();
        const row = --this.heights[col];
        const player = this.moves.length % 2;
        const cellId = row + col * 7;
        const bit = 1n << BigInt(cellId);
        this.bitboard[player] ^= bit;
        this.gameOver = false;
        for (const groupId of Connect4.cellToGroups[cellId]) {
            const group = this.groupOccupation[groupId];
            if (group[player].length === 3 && group[2].length) { // Losing a threat!
                this.threats[player] ^= 1n << BigInt(group[2][0]);
            }
            // In this group, mark the cell as no longer taken by this player
            group[2].push(group[player].pop());
        }
    }
    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);

toString

方法用小写字母呈现威胁。正如您在此示例运行中所看到的，第二列中的玩家“O”有两个相互重叠的威胁。此信息可以在

this.threats

位图中轻松获得。请注意，两名玩家可能对同一个牢房产生威胁。我没有提供在

toString

方法中显示它，但这不是必需的。

this.threats

位图提供了这种可能性。