chess - 在编程计算机下棋时如何对棋盘进行建模？

Question

您将使用什么数据结构来表示计算机国际象棋程序的棋盘？

Answer 1

对于一个严肃的国际象棋引擎，使用位板是在内存中表示国际象棋棋盘的有效方法。位板比任何基于数组的表示更快，特别是在 64 位架构中，其中位板可以放入单个 CPU 寄存器中。

位板

位板的基本思想是以 64 位表示每种棋子类型。在 C++/C# 中，它将是 ulong/UInt64。因此，您将维护 12 个 UInt64 变量来表示您的棋盘:每种棋子类型有两个(一黑一白)，即兵、车、马、象、后和王。 UInt64 中的每一位都对应于棋盘上的一个方 block 。通常，最低有效位是 a1 平方，接下来是 b1，然后是 c1，以行优先方式依此类推。棋盘上棋子位置对应的位将设置为 1，所有其他位将设置为 0。例如，如果 a2 和 h1 上有两只白车，那么白车位板将如下所示:

0000000000000000000000000000000000000000000000000000000110000000

现在，例如，如果您想在上面的示例中将车从 a2 移动到 g2，您所需要做的就是对位板进行异或:

0000000000000000000000000000000000000000000000000100000100000000

位板在移动生成方面具有性能优势。位板表示还具有其他性能优势。例如，您可以使用 lockless hash tables在并行化搜索算法时，这是一个巨大的优势。

进一步阅读

国际象棋引擎开发的终极资源是 Chess Programming Wiki 。我最近写过this chess engine它在 C# 中实现了位板。更好的开源国际象棋引擎是 StockFish它也实现了位板，但是是用 C++ 实现的。