我正在开始创建一个国际象棋引擎。当我创建一个检查移动是否合法的函数时，首先我必须进行移动，然后检查移动是否使我的国王受到控制，然后取消它。
在考虑了如何制作一个取消移动的功能之后，我决定复制棋盘并在复制的棋盘上进行假设移动要简单得多，因此它根本不会改变原始棋盘结构。
但我担心这可能不是一个好主意，因为当我进入 AI 部分时，我必须完全复制电路板，这可能会减慢我的引擎速度。是这样吗？您能否分享您对此的想法，因为我对算法复杂性和这类东西知之甚少。
谢谢你。
问问题
1868 次
2 回答
5
正如您所说，复制整个电路板可能会大大降低速度。我建议制作一个撤消列表，您可以在其中添加您所做的每一步的反向操作。然后要撤消，只需重复从列表中弹出移动并应用它们直到列表为空。这样，您的 AI 可以通过使用带有 maxdepth 参数的简单递归函数来探索所有可能性。
回复：博的评论
我恭敬地不同意。
对于用低级语言编写的程序，一个板副本可能相当于一个 memcpy，然后它可能会更快。但是对于一个面向对象的 python 程序，每个棋子有一个对象，加上元数据，一个完全独立的游戏状态副本几乎肯定比创建一个新的“撤消”对象并将其添加到列表要慢得多。
请注意，这与结构的大小无关，更多的是与复制该结构所需的操作数量有关。特别是在 python 中，函数调用会增加大量开销。根据这个答案（我自己的），在 CPython 中实例化 32 个对象相当于 83 个函数调用，并且假设它们除了object. 然后数据分配和复制是最重要的。
如果板是 16x16 numpy 数组，我同意板副本可能会更快。
于 2012-07-26T11:58:39.167 回答
5
通常使用 unmake 方法更多，因为它避免了不必要的电路板复制。如果您想在Position课堂上以两种不同的形式保留作品，则尤其如此；作为传统的 8x8 数组和一组 64 位无符号整数（位板）。
您需要创建一个类来存储您的UnmakeMoveInfo哪些持有：
- 移动的起点/终点。
- 前一个位置哈希。
- “半步时钟”。
- 过路人面具。
- 捕获的片断。
- 先前位置标志（检查、ep_move、castling 权利）。
这样您就拥有取消移动所需的所有信息。
于 2012-07-26T12:00:10.263 回答