检查 6x6 位板对齐的快速方法

Question

我正在尝试找到一种快速检查 5 位 在 6x6 板 中各个方向对齐的方法（对角线、水平、垂直）。该板表示为位板，因为它们非常快。

位板是这样的：

00 01 02 03 04 05   
06 07 08 09 10 11
12 13 14 15 16 17
18 19 20 21 22 23
24 25 26 27 28 29
30 31 32 33 34 35

一些对齐示例：

// Vertical Alignment
0 1 0 0 0 0   
0 1 0 0 0 0   
0 1 0 0 0 0   
0 1 0 0 0 0   
0 1 0 0 0 0   
0 0 0 0 0 0 

// Diagonal Alignment
0 0 0 0 0 0   
0 0 0 0 0 1   
0 0 0 0 1 0   
0 0 0 1 0 0   
0 0 1 0 0 0   
0 1 0 0 0 0

我已经尝试遍历每个可能的位板获胜位置并检查是否 ((winningPosition & currentPosition) != 0) 正如我在许多位板的井字游戏实现中看到的那样。这里的问题是，与我在其他游戏中看到的其他解决方案相比，此实现非常慢，例如连接四 (https://spin.atomicobject.com/2017/07/08/game-playing-ai-bitboards/)

Answer 1

一些测试可以组合在一起。

例如，假设棋盘名为 x，则 m = x & (x >> 1) & (x >> 2) & (x >> 3) & (x >> 4) 计算一个掩码，其中每一位表示它是否是 5 horizontally-consecutive 组位（包括范围）的开始环绕不同的行）。如果 m 设置了前两列中的任何一位，则表示该位是获胜位置的第一位。这是一个廉价的测试：(m & 0b000011000011000011000011000011000011) != 0。一起负责检查 10 个操作中的 12 个获胜位置。

同样的方法可以用于垂直对齐，但是偏移量变成了 6, 12, 18, 24 而不是 1, 2, 3, 4 并且掩码变成了 0b000000000000000000000000111111111111.

同样的方法也可以用于对角线，

偏移量 7、14、21、28，掩码 0b000011000011
偏移量为 5、10、15、20，掩码为 0b110000110000

但是只有8个对角线获胜位置，最终要花费20次操作来检查它们，这不是很好。由于减少了检查的数量，它可能仍然有帮助，即使它是更多的操作，但它也可能无济于事，或者更糟。

如果您愿意，可以将检查次数减少到 1，方法是将 winning-position 位组合在一起并只执行一个 != 0.

检查 6x6 位板对齐的快速方法

Fast way of checking for alignment of in a 6x6 bitboard

bit-manipulation

bitmap

bit-shift

bit

bitboard