国际象棋编程中的移动取消与局面复制

Question

我正在创建一个国际象棋引擎。当我创建了一个检查移动是否合法的函数时，首先我必须执行这个移动并检查它是否将我的国王置于被攻击状态，然后再撤销这个移动。

在考虑如何创建一个撤销移动的函数时，我决定更简单的方法是复制棋盘并在复制的棋盘上进行假想移动，这样就不会改变原始棋盘结构。

但我担心这可能是个坏主意，因为当我到达AI部分时，我必须完全复制棋盘，这可能会减慢我的引擎速度。这是真的吗？由于我对算法复杂性和相关知识不太了解，请您分享一下您的想法。

谢谢。

- stensootla

---

你可能想要查看这个链接：http://en.wikipedia.org/wiki/Memento_pattern - aisbaa

@geekkid - 这很大程度上取决于您的棋盘结构的大小以及需要进行多少个字段更新来制作和取消移动。并不确定哪种方法最快，因此请使用您感到最舒适的方法。 - Bo Persson

请查看http://chessprogramming.wikispaces.com/Copy-Make。 - TemplateRex

Answer 1

正如你所说的，复制整个棋盘可能会使事情变得很慢。我建议创建一个撤销列表，在其中添加您进行的每个移动的反向。然后，只需重复弹出列表中的移动并应用它们，直到列表为空为止以进行撤销。这样，您的AI可以使用具有maxdepth参数的简单递归函数来探索所有可能性。

回复Bo的评论：

我不同意这种观点。

对于用低级语言编写的程序，复制一个棋盘可能等同于一个memcpy，那么它可能会更快。但对于一个面向对象的Python程序而言，每个棋子都有一个对象加上元数据，完全独立的游戏状态副本几乎肯定比创建一个新的“撤销”对象并将其添加到列表中要慢得多。

请注意，这与结构的大小关系不大，而是与复制该结构所需的操作数量有关。特别是在Python中，函数调用会增加大量开销。根据我的答案，在CPython中实例化32个piece对象相当于83个函数调用，而这是假设它们除了object之外没有任何子类。然后进行数据分配和复制。

如果棋盘是16x16的numpy数组，我同意复制棋盘可能更快。

- Lauritz V. Thaulow

---

复制棋盘并不一定会更慢。这在很大程度上取决于棋盘状态结构的大小。使用复制丢弃可以使撤销功能极快，这可以节省比复制棋盘更多的时间。这两种方法都被用于真实的国际象棋程序中。 - Bo Persson

我从未使用Python编写过国际象棋程序，但我曾在C++中完成了这项工作。在C++中，可以使用复制构造函数等方法来提高复制的速度。然而，数据结构的大小会影响可用的内存带宽，这是一个限制因素。 - Bo Persson

这取决于架构。Robert Hyatt是Cray Blitz的作者，后来成为Crafty，他最初使用copy/make，因为在Cray上复制内存非常快。后来，在将其移植到PC时，他不得不切换到make/unmake，因为它在那里成为主要瓶颈（由于缓存污染）。我认为现在大多数引擎都在使用make/unmake。（虽然我不知道Python中的性能调优情况。） - Philipp Claßen

Answer 2

通常采用撤销操作的方法更多，因为它避免了不必要的棋盘复制。特别是如果您想在Position类中以两种不同的形式保存您的棋子;作为传统的8x8数组和64位无符号整数（位板）集合。

您需要创建一个类来存储UnmakeMoveInfo，其中包含：

• 移动的起点/终点。
• 上一次位置的哈希值。
• '半步钟'。
• 可吃过路兵的掩码。
• 被吃掉的棋子。
• 先前的位置标志（检查、ep_move、王车易位权利）。

这样您就有了撤销移动所需的所有信息。

- trojanfoe