从位板生成单个移动

Question

在我使用位棋盘来表示棋局状态的国际象棋引擎中，会一次性生成一大块伪法子着，而位棋盘则是这个结果。例如：

兵：

一些位棋盘的魔术后：

最后的位棋盘仅仅是可能的走法。引擎通常如何从这个位棋盘中获取单个着法？需要我遍历每个位并检查是否设置了吗？然而，遍历一个位棋盘似乎有违使用位棋盘的目的，这也是我有点怀疑的原因。

是否有更好的方法呢？

- Shreyas

Answer 1

然后，通常你会应用 minimax 算法的某些变体来评估棋步的好坏，以便选择（你估计的）最佳棋步。一个简单的变体是 alpha-beta。

这些变体主要处理的是试图引导搜索朝着“可能有用的棋步”和远离搜索空间中无用的区域，因为搜索树非常宽，能够深入探索它对于一个好的国际象棋 AI 非常重要 - 浅层次地探索将使 AI 很容易被“困住”，因为它会做出短期看起来不错但后来证明效果很差的选择。

所以，是的，你将遍历位板。这并不真正违背它们的目的 - 你仍然比如果没有使用位板计算得到的棋步快得多。对于最简单的 AI，你可以使用标准位板技术来选择“第一个”棋步，但是像那样下棋的 AI 将低于新手水平，完全不考虑输赢。

- harold

Answer 2

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

- bloody