获取位棋盘的占用位掩码

Question

获取位棋盘的占用位掩码

artificial-intelligencebit-manipulationchess

4

我正在使用位棋盘(bitboards)来表示国际象棋棋盘并检查合法移动。我卡在了滑动棋子攻击中源方格和目标方格之间的占用计算上。我不想通过查找表来解决问题，所以我正在尝试弄清楚是否可能在没有查找表的情况下获取介于两个方格之间的方格掩码。例如，在以下棋盘中，c4上有一枚车(Rook)：


8 0 0 0 0 0 0 0 0 
7 0 0 0 0 0 0 0 0 
6 0 0 0 0 0 0 0 0 
5 0 0 0 0 0 0 0 0 
4 0 0 R 0 0 0 0 0 
3 0 0 0 0 0 0 0 0 
2 0 0 0 0 0 0 0 0 
1 0 0 0 0 0 0 0 0 
  a b c d e f g h

给定一个表示空位（或占用位）的位棋盘和一个伪有效移动Rf4（车可以从c4移动到f4），如何获得d4-e4方格的掩码（不包括源和目标方格）？

我假设，一旦这个问题清楚了，垂直移动将很容易计算，并且可以通过使用旋转的位棋盘来计算对角线移动。

编辑：位棋盘用ulong/unsigned int64表示，每8位代表实际棋盘的一行/列。

- kateroh

1

如果你已经决定使用位棋盘，就不要浪费时间重复生成它们。在棋盘上只有1953种选择两个坐标的方式。你可以轻松地将它们存储在一个数组中。 - Thomas Ahle

@ThomasAhle 在尝试制作国际象棋引擎后放弃了数组。 - user14248283

3个回答

1

除非进行一些前期计算并生成所有可能的棋子移动掩码（这是一个明确的可能性），否则我预计在运行时构建掩码很可能与简单的“查找每个方格”的方法相比，时间上同样昂贵。

- Will A

这就是为什么问题在于是否能够根据两个正方形以及一个方向（东/西）动态计算掩码。 - kateroh

这是完全可能的 - 但很可能不比替代方案更便宜，更简单。 - Will A

预先计算所有可能性肯定更便宜。 - Mathieu Pagé

@sehe：不，我自己没有对此进行过分析，但这是计算机国际象棋社区中每个人都采用的方法。 - Mathieu Pagé

我知道你夸张了，但也许有一半以上是真的，所以我就不再多说了。我自己找到了一种似乎对我更有效的方法-尽管我必须说它需要修改后的棋盘（想象一下8x8x8），并且仍然需要预先计算移动表。只是没有使用位棋盘的形式。 - sehe

0

获取方向（dx，dy）/ dx的统一向量

在这种情况下，为（1,0）

然后重复使用该向量逐步增加当前位置，直到到达目的地。在途中增加/分配相应的矩阵单元。

- sehe

似乎与从EmptySquares位板进行逐位查找没有什么区别。 - kateroh

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- AShelly · Accepted Answer

我做一些假设：棋盘存储为一个64位数字，每个8字节块代表一行。每一行中的每个位都代表一列（a..h）。您有起始和结束位置作为从零开始的坐标。例如：start = "C4" = [2,3]; end = "F4" = [5,3] 对于水平向右移动，可以计算移动距离：d = (F4-C4 = 3)。减去1排除目的地，然后将d-1位的"trail" t设置为t = (1<<(d-1))-1。将"trail"与源方块相邻的位置移动以获得掩码M：M = t<<(start.row*8 + start.column+1)。

这相当于 M = ((1<<d)-2)<<(start.row*8 + start.column) 对于向左的水平移动：

 d = (C4-F4 = -3)
 t = (1<<(-d-1))-1
 M = (t<<dest.column+1)
 //-or-
 M = ((1<<-d)-2)<<(dest.row*8 + dest.column)

对于垂直上升的移动：

 d = (C7-C4 = 3)
 t=(1<<8)
 (d-1) times: { t |= (t<<8)}
 M = t << (start.row*8 + start.column)

对于垂直向下的移动：

 d = (C4-C7 = 3)
 t=(1<<8)
 (d-1) times: { t |= (t<<8)}
 M = t << (dest.row*8 + start.column)

对于垂直移动，您可以替换对d的循环，通过存储最大的“垂直轨迹” VT = 0x0101010101010101 = 72340172838076673。然后为实际移动屏蔽正确数量的位。

这将计算减少到 M = (VT & ((1<<(d*8)) - 2)) << (row*8+column)。

您可能可以在对角线移动上做类似的事情。从max diagonal trail DT= 0x0102040810204080 开始，应用掩码以将其减少到d设置位，并根据哪个靠近边缘来移动到开始或结束位置。这需要仔细测试，以确保没有边缘情况会在错误行中包裹。

编辑以排除源和目标，并修复一次性错误。