4

我正在玩比特板来代表棋盘并检查合法动作。我坚持的事情是计算滑动块攻击中源方格和目标方格​​之间的占用率。我不想通过查找来做到这一点，所以我试图弄清楚是否有可能在没有查找的情况下获得中间方块的掩码。例如，在以下棋盘中，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（Rook 可以从 c4 移动到 f4），如何获得方格 d4-e4 的掩码（不包括源方格和目标方格​​） ?

我假设，一旦这一点很清楚，垂直移动就会很容易，并且可以通过使用旋转的位板来计算对角线移动。

编辑：位板用 ulong/unsigned int64 表示，每包 8 位代表实际板的一个等级/行。

4

3 回答 3

4

我将在这里做一些假设：板存储为 64 位数字，每个 8 字节块代表一行。行中的每一位代表一列 (a..h)。您将开始和结束位置作为从零开始的坐标。IE：start = "C4" = [2,3]; end = "F4" = [5,3]

对于列增加的水平移动，您可以计算移动的距离： d = (F4-C4 = 3)。减去 1 以排除目的地，则 d-1 位的“轨迹”t 为t = (1<<(d-1))-1。移动与源片段相邻的轨迹以获得掩码 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)

对于垂直移动，您可以通过存储最大 "vertical trail" 来替换 d 上的循环 VT = 0x0101010101010101 = 72340172838076673。然后为实际移动屏蔽正确的位数。

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

您可能可以为对角线移动做类似的事情。从最大对角线轨迹 DT = 开始0x0102040810204080，应用掩码将其减少以d设置位，然后移动到开始或结束位置，具体取决于哪个更靠近边缘。这需要仔细测试以确保没有边缘情况缠绕到错误的行中。

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

于 2011-06-27T20:04:25.753 回答
1

如果没有进行一些预先计算并为棋子移动生成所有可能的掩码（绝对有可能），我希望在运行时构建掩码很可能与简单的“查找每个方块”一样耗费时间' 方法。

于 2011-06-24T06:20:12.477 回答
0

获取方向的统一向量 (dx,dy)/dx

在这种情况下，(1,0)

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

于 2011-06-24T06:45:09.233 回答