程序员难题：在整个游戏过程中编码棋盘状态

这是我将如何对游戏步骤进行编码。对于一个有40个步骤的游戏，大约需要180位。

首先，使用了解所有国际象棋规则的引擎创建所有选择的列表。每一步都要执行以下操作：

1. 枚举所有可以移动的棋子（初始状态下，白方可以移动8个兵和2个马，共计10个）。
2. 存储可行选择的数量和选择本身。
3. 列举所有可能的移动位置。（当选定兵时，可以向前移动1或2个格子，因此有2种可能的选择）。
4. 再次存储可行选择的数量和选择本身。

这将为您提供以下列表：

[[10, 3], # choose white pawn at index #3
 [2, 0],  # move it one step forward
 [10, 2], # choose black pawn #2 
 [2, 1],  # move it two steps forward
 ...
]

等等。要对其进行编码，您只需要存储选择，而不是可能移动的数量。一种存储它的方法是找出每个选择所需的位数：

[[10, 3], # 10 choices => 4 bits
 [2, 0],  # 2 choices => 1 bit
 [10, 2], # 10 choices => 4 bits
 [2, 1],  # 2 choices => 1 bit
 ...
]

前两步总共需要 4+1+4+1=10 个比特。但是有一些比特被浪费了，使用4个比特来表示10种选择会浪费6种可能的选择。

我们可以做得更好：将列表反转，并根据可能的选择和所选的选择计算一个数字：

n = 0         # last position
n = n*2 + 1   # from [2, 1]   n=1
n = n*10 + 2  # from [10, 2]  n=12
n = n*2 + 0   # from [2, 0]   n=24
n = n*10 + 3  # from [10, 3]  n=243

现在我们有数字243，二进制11110011，它只用8位编码了上述所有步骤。
为了解码，我们知道初始开放位置有10个可能的选择。进行计算。

n = 243
choice = n % 10  # we know there are 10 moveable pieces. => choice=3
n /= 10          # n=24
choice = n % 2   # we know 2 possible moves for selected pawn => choice=0
n /= 2           # n=12
choice = n % 10  # 10 moveable pieces for black player. => choice=2
n /= 10          # n=1
choice = n % 2   # 2 possible moves for pawn => choice=1
n /= 2           # n=0, finished decoding

编码非常高效，特别是在游戏的末尾，因为剩下的选择不多。此外，当你只剩下一种可能的移动时，你根本不需要为该移动存储任何内容。

存储棋盘状态

我想到的最简单的方法是首先创建一个8×8位数组来表示每个棋子的位置（如果有棋子则为1，否则为0）。由于这是一个固定长度的数组，因此我们不需要任何终止符。

接下来按照棋子的位置顺序来表示每个棋子。每个棋子使用4个位，这将占用32×4位（总共128位）。这种方法非常浪费空间。

使用二叉树，我们可以在一个字节中表示一个兵，3个字节中表示一个马、车和象，4个字节中表示一个王和一后。由于我们还需要存储棋子的颜色，这需要额外的一个字节，结果如下（如果有错请见谅，我以前从未仔细学习过Huffman编码）：

• 兵：2
• 车：4
• 马：4
• 象：4
• 王：5
• 后：5

给出总计：

2*16 + 4*4 + 4*4 + 4*4 + 2*5 + 2*5 = 100

这比使用固定大小的位集合多出28位。

因此，我发现最好的方法是将其存储在一个8² + 100位数组中。

8*8 + 100 = 164

存储棋步
首先，我们需要知道哪个棋子移动到了哪里。鉴于棋盘上最多有32个棋子，并且我们知道每个棋子是什么，而不是用整数表示方格，我们可以使用表示棋子偏移量的整数，这意味着我们只需要适合32个可能值来表示一个棋子。

不幸的是，有各种特殊规则，比如王车易位或推翻国王并组建共和国（特里·普拉切特的参考），因此在存储要移动的棋子之前，我们需要一个单一的位来指示它是否是特殊移动。

因此，对于每个正常移动，我们有必要的1 + 5 = 6位。（1位类型，5位棋子）

在解码棋子编号后，我们就知道了棋子的类型，每个棋子应该以最有效的方式表示其移动。例如（如果我的国际象棋规则没错），兵有4种可能的移动方式（向左吃子，向右吃子，向前移动一步，向前移动两步）。
因此，要表示兵的移动，我们需要“6 + 2 = 8”位。（6位初始移动头，2位移动方式）

对于女王的移动会更为复杂，最好是有一个方向（8个可能的方向，因此需要3位）以及每个方向可移动的8个可能位置的总数（因此需要另外3位）。因此，要表示女王的移动，需要6 + 3 + 3 = 12位。

我想到的最后一件事是，我们需要存储哪位玩家轮到下一步。这应该是单个位（白方或黑方移动）

结果格式
因此，文件格式应如下所示

[64位] 初始棋子位置
[100位最大值] 初始棋子 [1位] 玩家回合
[n位] 移动

其中，移动是
[1位] 移动类型（特殊或正常）
[n位] 移动详细信息

如果移动是普通移动，则移动详细信息如下
[5位] 棋子
[n位] 特定棋子移动（通常在2到6位之间）

如果它是一个特殊移动
它应该具有整数类型，然后是任何其他信息（如是否是王车易位）。我记不清有多少个特殊移动，所以可能只需要指示它是一个特殊移动（如果只有一个）

Thomas对于编码棋盘的方法是正确的。然而，这应该与ralu的存储移动的方法相结合。列出所有可能的移动，写出表达此数字所需的位数。由于解码器正在执行相同的计算，它知道有多少个可能性，并且可以知道需要读取多少位，因此不需要长度代码。

因此，我们为棋子获得164位，为王车易位信息获得4位（假设我们正在存储游戏的片段，否则可以重建），为过路兵信息获得3位--只需存储移动发生的列（如果无法进行过路兵，则存储无法进行过路兵的列--这样的列必须存在），并为下一步行动者获得1位。

移动通常需要5或6位，但可以从1到8位不等。

另一个快捷方式--如果编码以12个1位开头（无效情况--甚至一个片段也不会有两个国王在一侧），则中止解码，清除棋盘并设置新游戏。下一位将是一个移动位。

算法应该在每个移动时确定性地枚举所有可能的目的地。目的地数量：

• 2个象，每个13个目的地=26
• 2个车，每个14个目的地=28
• 2个马，每个8个目的地=16
• 皇后，27个目的地
• 国王，8个目的地

在最坏情况下（枚举方面），8个兵都可以成为皇后，从而使可能的目的地数量最大化9*27+26+28+16+8=321。因此，任何移动的所有目的地都可以用9位数字枚举。

双方的最大移动次数是100（如果我没记错的话，我不是棋手）。因此，任何游戏都可以记录在900位上。加上每个棋子的初始位置可以使用6位数字记录，总共为32*6=192位。再加上一个“谁先走”的记录位。因此，任何游戏都可以使用900+192+1=1093位记录。

在初始棋盘和随后的移动的基本情况下，请考虑以下内容。
使用象棋程序为所有可能的移动分配概率。例如，e2-e4有40％的可能性，d2-d4有20％的可能性，依此类推。如果某些移动是合法的但未被该程序考虑，则将它们赋予较低的概率。使用算术编码保存所采取的选择，这将是0到0.4之间的一些数字，第二步是0.4和0.6之间等等。
对于另一方面也要做同样的工作。例如，如果响应e2-e4有50％的机会，则编码号将介于0和0.2之间。重复此操作直到游戏结束。结果是一个潜在非常小的范围。找到最适合该范围的最小基数的二进制小数。那就是算术编码。
这比哈夫曼更好，因为它可以被认为是分数位编码（加上一些在游戏结束时舍入为整个位数的位数）。
结果应该比哈夫曼更紧凑，并且没有晋升，吃过路兵，50步规则移动和其他细节的特殊情况，因为它们由象棋评估程序处理。

为了重现，再次使用棋类程序评估棋盘并为每个移动分配所有概率。使用算术编码值确定实际播放的移动。重复此过程直到完成。

如果您的棋类程序足够好，您可以使用双状态编码器获得更好的压缩效果，其中概率基于黑白双方的移动进行定义。在某些极端情况下，有200多个状态，这将对所有可能的国际象棋游戏进行编码，因此不可行。

这基本上是以不同的方式表达Darius已经写过的内容，只是带有一些算术编码可能如何工作的示例，以及使用现有的棋类程序来帮助评估下一个移动的概率的真实示例。

棋盘上有32个棋子。每个棋子都有一个位置（在64个方格中的一个）。 因此，您只需要32个正整数。

我知道64个位置可以用6位表示，但我不会这样做。我会将最后几位保留给一些标志（被吃掉的棋子，升变为皇后的兵等）。

cletus的回答很好，但他忘记了编码轮到谁了。这是当前状态的一部分，如果您正在使用该状态来驱动搜索算法（如alpha-beta派生算法），则是必需的。

我不是国际象棋玩家，但我相信还有一个特殊情况：重复了多少次移动。每个玩家都做出相同的移动三次后，游戏就会以平局结束，对吗？如果是这样，那么您需要在状态中保存该信息，因为在第三次重复之后，状态现在是终止状态。

正如其他一些人所提到的，您可以对于每个32个棋子，存储它们所在的方格以及它们是否在棋盘上，这需要32 * (log2(64) + 1) = 224位。

然而，象只能占据黑色或白色的方块，因此对于这些象，您只需要使用log2(32)位表示其位置，即28 * 7 + 4 * 6 = 220位。

而且，由于兵并不是从后面开始，只能向前移动，因此它们只能在56个方格上，应该可以利用这种限制来减少兵所需的位数。

每个棋子可以用4位表示（兵到王，6种类型），黑/白 = 12个值

棋盘上的每个方格可以用6位表示（x坐标，y坐标）。

初始位置最多需要320位（32个棋子，4 + 6位）

每个后续移动可以用16位表示（起始位置，目标位置，棋子）。

王车易位需要额外的16位，因为它是双重移动。

升变的兵可以用4位中的4个备用值之一表示。

没有详细计算，与存储32 * 7位（预定义的棋子数组）或64 * 4位（预定义的方格分配）相比，这开始在第一步后节省空间

双方各走10步后，最大所需空间为640位

...但是，如果我们唯一地识别每个棋子（5位）并添加第六位以标记升变的兵，那么我们每次只需要棋子ID + 目标位置。这将改变计算方式...

初始位置 = 最大384位（32个棋子，6 + 6位） 每步移动 = 12位（目标位置，棋子ID）

然后，在双方各走10步之后，最大所需空间为624位。

一个棋盘有64个方格，可以用64位表示一个方格是否为空。我们只需要知道一个方格上是否有棋子。由于玩家+棋子需要4位（如前所示），因此我们可以在64 + 4 * 32 = 192位中获取当前状态。再加上当前回合，就有193位。
然而，我们还需要为每个棋子编码合法移动。首先，我们计算每个棋子的合法移动次数，并将这些位附加到完整方格的棋子标识符后面。我计算如下：
兵：向前、第一次走两步向前、吃过路兵*2、升变=7位。你可以将第一次向前和升变合并成一个位，因为它们不能从同一位置发生，所以你有6位。 车：7个垂直方格，7个水平方格=14位 马：8个方格=8位 象：2个对角线*7=14位 后：7个垂直、7个水平、7个对角线、7个对角线=28位 王：8个周围的方格
这仍然意味着您需要根据当前位置映射目标方格，但这应该是一个简单的计算。

由于我们有16个兵，4个车/马/象和2个皇后/国王，因此总共需要312个比特，即16 * 6 + 4 * 14 + 4 * 8 + 4 * 14 + 2 * 28 + 2 * 8，使总位数达到505位。

至于每个棋子可能移动所需的位数，可以添加一些优化来减少位数，我只是使用易于处理的数字。例如，对于滑动棋子，您可以存储它们可以移动的距离，但这将需要额外的计算。

长话短说：仅在一个方格被占用时存储额外数据（棋子等），并且仅存储每个棋子的最小位数以表示其合法移动。

编辑1：忘记了王车易位和兵升变为任何棋子。这可能会导致总共557个移动（兵需要3个比特，国王需要2个比特）。