2

我正在寻找一种有效的方式来表示国际象棋的位置。我的“效率”标准是：

  1. 需要尽可能少的内存
  2. 给定一个位置表示和一个合法移动（以通常的方式表示，例如以 pgn 格式表示），很容易计算得到的位置表示。也就是说，函数 new_position = compute_position(old_position, move) 可以（或已经）以非常有效的方式实现（从运行时的角度来看）。
  3. 比较两个位置是否相同很容易

我试图偏离标准表示的原因是我的要求略有不同。具体来说，我不是在尝试开发国际象棋引擎，因此不需要移动生成和相关问题。我只需要关注一些现有的游戏，并代表某些位置，并将它们存储在数据库中。

如果有一个软件包已经提供了这个功能，那就太好了。如果您对如何做有想法，我很乐意开发它:)

谢谢...

4

2 回答 2

0

我将提供一些可能的解决方案，根据您的规范使用“尽可能少的内存”。我知道您可以使其中一些更紧凑，但是这样做会使使用起来更加困难。

  1. 64 位：我不知道您需要能够从表示中检索什么样的信息，但是满足您所有给定要求的技术是Zobrist 散列。它需要很少的内存（您可以使用 64 位密钥，然后在预计发生冲突之前存储 2 32 个位置）。增量更新（按位 XOR 操作）非常简单有效，当然也易于比较。但是，如果您需要显示位置或检索有关棋子的任何信息，这会让您不走运。

  2. 328 位：您可以使用一个片段列表，每个片段（4 位）位于一个正方形（6 位）上。由于有 32 件，您需要跟踪易位权（4 位）、过路文件（3 位）和边移动（1 位）。

  3. 468 位：位板表示。我知道您没有开发国际象棋引擎，但这仍然是一个非常紧凑的表示。您需要 7 个位板（全白、全黑、所有皇后、所有车、所有主教、所有骑士、所有棋子），分别跟踪国王（12 位）以及所有其他杂项信息。是的，这将是一些工作来实现，但这允许您做许多其他表示中不可能的事情，所以如果您需要分析位置，这很好。

于 2013-06-21T21:53:02.680 回答
0

这里有一个免费的 PGN 查看器：http: //chesstempo.com/pgn-viewer.html

关于空间要求，您可以使用您选择的压缩算法来压缩 FEN，而不会失去检查相等性的能力。根据移动的编码方式（g1f3 与 Nf3），您可能需要一个合法的移动生成器来满足要求 2）。

于 2013-06-21T19:05:20.100 回答