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)，正如我在许多tac位板实现中所看到的那样。这里的问题是，与我为其他游戏(如连接四(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个水平连续设置位的开始(包括跨不同行的范围)。如果m在前两列中有任何位，那么这就意味着该位是获胜位置的第一个位。这是一个廉价的测试：(m & 0b000011000011000011000011000011000011) != 0。一起负责检查10个业务中的12个中标位置。

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

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

0b000011000011

• shift量为5，10，15，20的0b110000110000

掩模的

• 移位量为7，14，21，28

但只有8个对角线获胜位置，它最终花费了20个操作来检查他们这样做，这不是很好。尽管它的操作更多，但由于减少了检查的数量，它可能仍然有帮助，但也可能没有帮助，或者更糟。

如果您愿意的话，检查的次数可以减少到1，通过ORing将获胜的位置位合并在一起，只执行一个!= 0。