bit-manipulation - 从移动位板生成单个移动

Question

在我的国际象棋引擎中，它使用位板来表示棋盘的状态，一次生成一大块伪合法的移动，结果就是一个位板。例如：

棋子：

稍后一点点位板魔术：

最后的位板只是一大块可能的动作。引擎通常如何获取这个位板并从中生成单独的移动？我是否必须遍历每一位以检查它是否已设置？不过，在位板上进行迭代似乎违背了使用位板的目的，这就是为什么我有点怀疑的原因。

有没有更好的办法？

Answer 1

然后，通常你会应用一些极小极大算法的变体来评估这些动作的好坏，这样你就可以选择（你估计是什么）最好的动作。例如，一个简单的变体是alpha-beta。

这些变体主要处理尝试将搜索引导到“可能有用的移动”并远离搜索空间的无用区域，因为搜索树非常宽，并且您深入探索它的能力对于一个好的国际象棋人工智能非常重要 - 探索它使人工智能很容易被“陷阱”，因为它会做出在短期内看起来不错的选择，即使它们后来效果不佳。

所以是的，您将遍历位板。这并没有真正违背他们的目的——你仍然（可能）比不使用位板时更快地计算移动。对于最简单的人工智能，你可以使用标准的位板技术采取“第一步”，但这样玩的人工智能将低于新手水平，根本不考虑输赢。

Answer 2

您不必遍历 64 个单个位。例如，您可以准备/预定义一个 256 大小的查找数组，其中包含所有可能的移动列表，其中 8 位索引表示单个等级上的一块攻击集。然后，您只能使用按位移位操作迭代 8 次，(bitboard >> 8)以将后续的 rank-attack-sets 作为索引传递给数组并提取移动列表。与一位步进循环相比，它将加速大约 8 倍。也许您应该增强此数组以[8][256]实际传递一个排名号本身并x,y根据您的需要提取最终的移动列表（带坐标）。内存成本仍然微不足道。