你可以用以下 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
位图提供了这种可能性.