Bitboard:与邻居一起计算元素

Question

为了表示2D棋盘游戏的状态，我使用带有16位无符号整数的位板。状态被编码为1表示片段存在，0表示其他。

的位板方法是如何计算至少有一个相邻的水平、垂直或对角线的块数？

我发现的算法(非常简化)是：

total = 0
for each bitIndex in bitscanForward(bitboard)
    total += bitPopCount(bitboard & (ADJACENT_MASK << bitIndex))
return total

• bitScanForward函数返回第一位的索引并将其设置为0
• bitPopCount函数返回位数

唯一的限制是板是m行x列，m <= 8。

有没有办法做到这一点，而不重复比特？

Answer 1

获取一个有一点设置IFF的掩码，它上面有一个部件和一些相邻的部件(即有一个直接在左边，或者在右边，或者向上，或者向下，或者对角线)：

mask = board & (left(board) | right(board) | up(board) | down(board) |
                left(up(board)) | left(down(board)) |
                right(up(board)) | right(down(board)))

那就数一数。

关键显然是落实董事会的“转变”，但它们真的很简单。你对方向的选择在位数方面可能会有所不同，这取决于你把比特放在一块板上的顺序。例如，4x4板的包装顺序似乎是合理的：

left(board)  = (board & 0x7777) << 1
right(board) = (board & 0xEEEE) >> 1
up(board)    = board << 4
down(board)  = board >> 4