我正在寻找的形状看起来像这样:

enter image description here

我有两个位板,代表游戏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
+---------------------+

顶行没有被用于任何特定的东西,但这个设置使它更容易判断胜利.有7列和6行,如连接4游戏.

这些比特的 struct 如下:

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

我不知道如何判断黄色是否也没有在那里玩.

推荐答案

你可以用以下 idea 完成你的is7Trap函数:

  • shapeExists计算"7"底部的位置,如果有一个(或多个,如果有一个以上).你不应该在下一个赋值中重新计算它,所以不要立即将它转换为布尔值,而是保留那个位模式,不要与0n进行比较.

  • << 18n是两个应该是空闲的点顶部的正确移位,但这里不应该执行&操作.相反,取上一步中找到的位,并将其沿相反方向(>> 18n)移动到您想要测试的位置,然后对照(bp | bp)(代表被占用的单元格)进行测试.如果这个结果是0 n,那么你就知道这个点是免费的.

  • 因为你有一个虚拟行在顶部,你应该确保上面的自由点不在它,因为你会得到一个假阳性为它(两个播放器没有一个光盘,所以它会错误地算作"自由")

以下是你的函数的改编:

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

概括

如果你要判断所有类型的箭头形状,它将导致lot的代码.请注意,有颠倒的7个形状,X形状,或两个自由点是between列的形状,这些形状具有制造威胁的圆盘,例如在这些例子中,锯齿突出了两个自由点:

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

用你所采取的方法来检测所有这些变化将是一项艰巨的任务.

我的猜测是,您不仅希望寻找特定的形状,而且实际上希望检测两个彼此叠加的威胁,无论这两个威胁是如何"支持"已播放的光盘.

我建议您设置威胁检测功能,并且在移动过程中保持信息增量更新可能比每次从头开始重新计算更有趣.

为了知道威胁在哪里,引入groups的概念将是有帮助的,即所有可能的四个单元集,代表一个获胜的组合,如果有一个玩家可以占据所有四个单元集.然后递增地跟踪每个组的哪些单元仍然空闲,哪些单元被第一个玩家占用,哪些单元被第二个玩家占用.如果一个移动导致一个小组有三个单元被同一个玩家占据,那么你知道唯一剩余的空闲单元是threat.您可以在为威胁保留的位图中标记此单元格;每个播放器一个——就像您为已经播放过的光盘设置的位板一样.

下面是一个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);
    }
    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方法用字母表示威胁.正如你在这个例子run中看到的,在第三列中,玩家"O"有两个相互叠加的威胁.这些信息在this.threats位图中很容易获得.

注意,两个玩家可能在同一个细胞上有威胁.我没有规定在toString方法中显示这一点,但这不是必需的.this.threats位图提供了这种可能性.

Javascript相关问答推荐

如何按预期聚合SON数据?

如何访问react路由v6加载器函数中的查询参数/搜索参数

无法将nPM simplex-noise包导入在JS项目中工作

当运行d3示例代码时,没有显示任何内容

WebGL 2.0无符号整数输入变量

查找最长的子序列-无法重置数组

Regex结果包含额外的match/group,只带一个返回

不能将空字符串传递给cy.containes()

为什么123[';toString';].long返回1?

如何使用JavaScript拆分带空格的单词

如何在Angular拖放组件中同步数组?

在数组中查找重叠对象并仅返回那些重叠对象

SPAN不会在点击时关闭模式,尽管它们可以发送日志(log)等

Node.js错误: node 不可单击或不是元素

FindByIdAndUpdate在嵌套对象中创建_id

如何在移动设备中使用JAVASSCRIPT移除点击时的焦点/悬停状态

将字体样式应用于material -UI条形图图例

在点击链接后重定向至url之前暂停

验证Java脚本函数中的两个变量

浮动标签效果移除时,所需的也被移除