0

为了表示 2D 棋盘游戏的状态，我使用了16 位无符号整数的位板。状态编码为 1 表示存在，否则为 0。

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

我发现的算法（非常简化）是：

total = 0
for each bitIndex in bitscanForward(bitboard)
    total += bitPopCount(bitboard & (ADJACENT_MASK << bitIndex))
return total
  • bitScanForward 函数返回第一位的索引并将其设置为 0
  • bitPopCount 函数返回位数

唯一的限制是板是 m 行 xm 列且 m <= 8。

有没有办法在不循环比特的情况下做到这一点？

4

1 回答 1

2

获取一个设置了位的掩码 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
于 2018-03-19T21:45:49.070 回答