快速检查6x6位比对齐方式的方法
我正在尝试找到一种快速的方法来检查 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
我尝试循环遍历每个可能的位板获胜位置并检查是否 ((winingPosition & currentPosition) != 0) 正如我在许多抽奖中看到的那样位板的 Tac Toe 实现。这里的问题是，与我见过的其他游戏（例如连接四）的其他解决方案相比，此实现非常慢（https://spin.atomicobject.com/2017/07/08/game-playing-ai-bitboards/)
I am trying to find a quick and fast way to check for alignment of 5 bits in a 6x6 board in all directions (diagonal, horizontal, vertical). The board is represented as a bitboard as they are very fast.
The bitboard is like this:
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
Some examples of alignment:
// 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
I have tried looping through every possible bitboard winning position and checked if ((winningPosition & currentPosition) != 0) as I have seen that in many tic tac toe implementations of bitboards. The issue here is that this implementation is very slow compared to other solutions I have seen for other games such as connect four (https://spin.atomicobject.com/2017/07/08/game-playing-ai-bitboards/)
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
一些测试可以分组在一起。
例如，假设板称为
x，然后m = x＆amp; （x＆gt;＆gt; 1）＆amp; （x＆gt;＆gt; 2）＆amp; （x＆gt;＆gt; 3）＆amp; （x＆gt;＆gt; 4）计算一个掩码，其中每个位指示它是否是5个水平连续的设置位的开始（包括包裹在不同行的范围）。如果m在前两个列中具有任何位，则意味着该位是获胜位置的第一个位。这是一个便宜的测试：（M＆amp; 0b0000110011001100110011001100110011）！= 0。共同考虑在10个行动中检查12个获胜职位。可以使用相同的方法进行垂直对齐，但是偏移量变为6、12、18、24，而不是1、2、3、4，蒙版变为
0b00000000000000000000000000000000111111111111111111111111111111111111111111111111朗亚军adadedaded。对角度也可以使用相同的方法，
0b000011000011偏移量的5、10、15、20 0B110000110000，但只有8个对角线的胜利位置，最终要花费20个操作来以这种方式检查它们，这不是很好。由于减少了检查的数量，即使它是更多的操作，但它也可能无济于事，也可能无济于事，这仍然可能会有所帮助。
如果您愿意，可以将支票数减少到1，通过将获胜位置位分配在一起，并仅执行一个
！= 0。Some tests could be grouped together.
For example, let's say the board is called
x, thenm = x & (x >> 1) & (x >> 2) & (x >> 3) & (x >> 4)computes a mask where every bit indicates whether it is the start of 5 horizontally-consecutive set bits (including ranges that wrap across different rows). Ifmhas any of the bits in the first two columns set, then that means that that bit is the first bit of a winning position. That's a cheap test:(m & 0b000011000011000011000011000011000011) != 0. Together that takes care of checking 12 winning positions in 10 operations.The same approach can be used for vertical alignment, but the shift amounts become 6, 12, 18, 24 instead of 1, 2, 3, 4 and the mask becomes
0b000000000000000000000000111111111111.The same approach can also be used for the diagonals,
0b0000110000110b110000110000But there are only 8 diagonal winning positions and it ends up costing 20 operations to check them this way, which isn't that good. It may still help thanks to reducing the number of checks even though it's more operations, but it may also not help, or be worse.
The number of checks can be reduced to 1 if you prefer, by ORing together the winning-position bits and doing just one
!= 0.