快速检查6x6位棋盘中对齐的方法

Question

我正在尝试找到一种快速的方法来检查6x6棋盘中5位在所有方向（对角线，水平，垂直）上的排列情况。棋盘被表示为比特图，因为它们非常快。

比特板如下：

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/）

- JackRubiralta

Answer 1

一些测试可以被分组。

例如，假设板子叫做x，那么m = x & (x >> 1) & (x >> 2) & (x >> 3) & (x >> 4)将计算一个掩码，其中每个位指示其是否为5个水平连续设置位的开头（包括跨越不同行的范围）。如果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次操作，这并不好。虽然它可以通过减少检查数量来帮助，但也可能没有帮助或者更糟。

如您愿意，则可以将获胜位的OR在一起，并进行一次!=0。

- harold