How do I model a chessboard when programming a computer to play chess?您将使用什么数据结构表示计算机国际象棋程序的国际象棋棋盘？ 对于严肃的国际象棋引擎，使用位板是在内存中表示国际象棋棋盘的一种有效方法。位板比任何基于数组的表示形式都快，特别是在64位体系结构中，位板可以容纳在单个CPU寄存器中。 位板 位板的基本思想是用64位表示每种棋子类型。在C / C#中，它将为
现在，例如，如果您想在上面的示例中将车从a2移到g2，您要做的就是对位板进行XOR：
位板在移动生成方面具有性能优势。从位板表示中自然也会产生其他性能优势。例如，您可以使用无锁哈希表，这在并行化搜索算法时具有巨大优势。 进一步阅读 国际象棋引擎开发的最终资源是国际象棋编程维基。我最近写了这个国际象棋引擎，该引擎在C#中实现了位板。更好的开源国际象棋引擎是StockFish，它也实现了位板，但使用C语言。 最初，使用8 * 8整数数组表示国际象棋棋盘。 您可以使用此符号开始编程。给出零件的点值。例如：
等(请注意，以上给出的要点是每个棋子的交易能力的近似值) 在开发了应用程序的基本Backbone 并清楚地了解所使用算法的工作原理之后，请尝试通过使用位板来提高性能。 在位板中，使用八个8位字表示板。此表示法每个棋子都需要一块棋盘。在一个位板上，您将存储车的位置，而在另一个位中，您将存储骑士的位置...等等 位板可以极大地提高应用程序的性能，因为使用位板操纵零件非常容易和快速。 正如您指出的那样，
简单的方法是使用8x8整数数组。使用0表示空白方块，并为片段分配值：
可以通过使用数组索引来计算零件移动。例如，白色棋子通过将行索引增加1来移动，如果它是棋子的第一步，则将行索引增加2。因此，[2] [1]上的白色棋子可以移动到[3] [1]或[4] [1]。 但是，这种具有棋盘格的简单8x8数组表示法存在一些问题。最值得注意的是，当您移动"滑动"的棋子(如菜鸟，主教和皇后)时，您需要不断检查索引，以查看棋子是否已移出棋盘。 当今大多数国际象棋程序，特别是那些在64位CPU上运行的象棋程序，都使用位图表示法来表示棋盘并生成动作。 x88是用于没有64位CPU的计算机的备用主板型号。 120个字节的数组。 这是一个8x8的棋盘，周围有前哨正方形(例如255，表示棋子无法移动到该正方形)。前哨的深度为2，因此骑士无法跳过。 向右移动添加1.向左移动添加-1。上10，下-10，上和右对角线11等。正方形A1是索引21。H1是索引29。H8是索引99。 所有设计都是为了简化。但是它永远不会像位板那么快。 创建国际象棋引擎时，我最初采用[8] [8]方法，但是最近我更改了代码，以使用64个项目的数组表示国际象棋棋盘。我发现，至少就我而言，此实现的效率提高了大约1/3。 在进行[8] [8]方法时，您要考虑的一件事是描述职位。例如，如果您想描述棋子的有效举动，则需要2个字节。当使用[64]项目数组时，您可以用一个字节来完成。 要从[64]板上的位置转换为[8] [8]板上的位置，您只需使用以下计算即可： 行=(字节)(索引/ 8) Col =(字节)(索引％8) 尽管我发现在性能敏感的递归移动搜索过程中，您不必这样做。 有关构建国际象棋引擎的更多信息，请随时访问我的博客，从头开始描述该过程：www.chessbin.com 亚当·贝伦特 好吧，不确定是否有帮助，但是Deep Blue使用单个6位数字表示板上的特定位置。与使用64位位板的竞争对手相比，这有助于节省芯片上的占用空间。 这可能无关紧要，因为很有可能您的目标硬件上已经有64位寄存器。 当然，代表棋盘的方式有很多种，最好的方式取决于对您来说最重要的东西。 您的两个主要选择是速度和代码清晰度。 如果速度是您的首要任务，那么您必须在板上的每组棋子中使用64位数据类型(例如，白色棋子，黑色皇后棋子，传人棋子)。然后，您可以在生成移动并测试移动合法性时利用本机按位操作。 如果代码的清晰性是优先考虑的事情，那么请忽略位改组，而像其他人已经建议的那样，选择很好的抽象数据类型。请记住，如果采用这种方式，您可能会更快达到性能极限。 首先，请查看Crafty(C)和SharpChess(C#)的代码。 10x12邮箱是标准8x8电路板的替代品(之所以这么称呼，是因为嗯，我想它看起来像一个邮箱)。这是一维数组，在其"边界"周围包括哨兵，以协助进行移动生成。看起来像这样：
您可以这样生成数组(在JavaScript中)：
当然，在实际的实现中，您会将实际的块对象放置在板标签所在的位置。但是您要保留负面的(或类似的东西)。这些位置使生成移动的痛苦减轻了很多，因为您可以通过检查该特殊值来轻松判断何时出局。 让我们首先看看为骑士(防滑的棋子)生成合法动作：
我们知道有效的Knight移动距离棋子的起点有固定的距离，因此我们只需要检查这些位置是否有效(即不是前哨正方形)即可。 滑动件并不难。让我们看一下主教：
以下是一些示例：
请注意， 使用位板是表示棋盘状态的有效方法。基本思想是，您使用64位位集表示板上的每个正方形，其中第一个位通常代表A1(左下角的正方形)，而第64个位代表H8(对角相对的正方形)。每个玩家(黑，白)的每种棋子(棋子，国王等)都有自己的位板，所有这12个板都构成游戏状态。有关更多信息，请查看此Wikipedia文章。 我将使用多维数组，以便数组中的每个元素都是对板上正方形的网格参考。 因此
然后板子[A] [1]是板子正方形A1。 实际上，您将使用数字而不是字母来帮助保持您的数学逻辑，以允许将片段移动到简单的地方。 我知道这是一个非常古老的帖子，在使用国际象棋编程时偶然发现了几次，但是我觉得我必须提到用一维数组(例如1D数组)对国际象棋棋盘建模是完全可行的。棋盘[64]; 我会说这是最简单的棋盘表示方法……但是，这当然是一种基本方法。 一维棋盘阵列结构是否比二维数组(需要嵌套的for循环访问和操作索引)效率更高？ 还可以使用具有超过64个正方形的1D数组来表示OffBoard正方形，例如棋盘[120]; (正确初始化了数组哨兵和棋盘游戏方块)。 最后，为了完整起见，我觉得我必须提到0x88电路板阵列表示形式。这是表示棋盘的一种很流行的方式，该棋盘也占了外侧的正方形。 我实际上不会为国际象棋棋盘建模，我只是为棋子的位置建模。
对白色使用正整数，对黑色使用负整数 数组可能很好。如果您想使用更方便的"遍历"电路板的方法，则可以轻松地构建一些方法来抽象出数据结构实现的细节。 |
