如何高效地存储国际象棋游戏？

Question

如何高效地存储国际象棋游戏？

databasealgorithmencodingcompressionbit

5

什么是在数据库中存储整个国际象棋游戏最节省空间的方法？考虑到平均游戏长度为50-70步（1步表示两位玩家各走一次），希望所需空间少于800位。

棋子的初始位置可以用6位来存储，而每步移动可能需要2-4位。有没有办法将其存储得更少一些呢？

- Coder shoder

1

你能分享一个“平均”的游戏记录，让人们可以在实际数据上进行测试吗？几十年前我把所有的都丢了... - Spektre

1

你能分享一个“普通”的游戏记录，这样大家就可以用实际数据进行测试吗？我几十年前就把我的都丢了... - undefined

2

请参阅https://lichess.org/blog/Wqa7GiAAAOIpBLoY/developer-update-275-improved-game-compression和https://github.com/lichess-org/compression。 - David Eisenstat

2

请参阅https://lichess.org/blog/Wqa7GiAAAOIpBLoY/developer-update-275-improved-game-compression和https://github.com/lichess-org/compression。 - undefined

https://groups.google.com/g/rec.games.chess/c/RspnvkCEY7s/m/W4kUZ0uH7jMJ?pli=1 - Dave

显示剩余2条评论

5个回答

3

将方格编号为0-63。计算当前一方可以到达的方格数量。使用最少的位数来表示移动到的可到达方格中的哪一个，位数为ceiling(log_2(可到达方格数量))。

当多个棋子可以移动到目标方格时，使用相同的方法选择用于该目标方格的可能源方格之一。

以下是使用Kasparov v Topalov 4/13/13的前几步进行的示例。我以左下角为0开始编号（白方的皇后车从0开始，白方的皇后马从1开始，依此类推）。

e4d6 1100 编码表示这是16个可能位置中的第12个（从0开始计数，所以0000会记录为e3）；由于只有一个棋子可以移动到这里，所以不需要额外的位数。

d4Nf6 1011 编码表示这是16个可能位置中的第11个；同样不需要额外的位数。

Nc3g6 01101 编码表示这是25个可能位置中的第13个；同样不需要额外的位数。

Be3Bg7 10001 编码表示这是17个可能位置中的第14个。在这里，移动可以来自两个位置（马或兵），因此我们需要1位来区分，最终编码为100011。

这需要的每步位数取决于游戏。目标位置最多只需要6位，我相信大多数游戏中的大多数移动只需要5位。除了开局和一些残局情况，我认为我们不应该期望小于等于4位。

解释步骤（即多个方块中的哪一个移动到目标位置）将经常出现。我猜想大多数移动不需要这一步骤，但是在大多数游戏中，会有一些需要1-2位甚至很少需要3位的移动。

因此，如果不进行实现和分析真实国际象棋游戏的工作，我预计每步平均记录大约6位的游戏数据。在一场长时间没有车和象的残局等限制性移动的游戏中，效率会更高。

- Dave

通过手动抽查一些游戏，我没有发现可以移动超过32个方格的位置，所以我猜这是很罕见的情况，而且通常只需要5位（加上消除歧义）。 - Dave

此外，还需为晋升的棋子进行排序（0表示兵，1表示马，...）。 - Dave

1

有趣的想法：消除歧义的步骤。它曾经出现在我的脑海中，但我没有评估过是否实用。如果它可以实现（而你的回答让我觉得它是可行的），那将几乎减少一半我固定编码方案所需的空间。 - Jim Mischel

1

有趣的想法：消除歧义的步骤。我曾经想过，但没有评估过它是否实际可行。如果能够实现（你在这里的回答让我觉得可能可以），这几乎可以将我固定编码想法所需的空间减少一半。 - undefined

也许在某些情况下，首先指定棋子的索引，然后选择其可能的移动方式会更有益。你可以在这两种编码之间切换，根据当前状态清楚明了。 - vlad_tepesch

显示剩余4条评论

1

国际象棋使用简单编码每步需要2*6位：

number_of_moves(7 bits)
start_position (6bits) - target_position (6bits)
start_position (6bits) - target_position (6bits)
...

例如：

70
E2 - E4
D7 - D5
...

每个字母A到H需要3位，数字1到8也需要3位，而每次移动有2个位置。

70 moves * 12 bits + 7 bits = 847 bits = 106 Bytes

这已经接近你期望的800位了。现在只需应用Huffman或LZW压缩。

现在你可以利用每步编码使用10位，因为每方只有16个（0..15 -> 4位）棋子。每局游戏都是由白方开始（奇数步是白方，偶数步是黑方），所以将编码改为：

number_of_moves(7 bits)
white_piece_ix (4bits) - target_position (6bits)
black_piece_ix (4bits) - target_position (6bits)
...

这导致：

70 moves * 10 bits + 7 bits = 707 bits = 89 bytes

这已经低于您的800个比特

如果这还不够，您可以使用变量棋子索引表。因此，每当某个棋子从棋盘上“删除”，您都需要将索引的值进行移动，以便未使用的棋子将被下一个索引使用，并且间隙将位于最后的值上（例如，如果第13号棋子被移除，则14号和15号棋子将成为13号和14号）。这样一来，一方只剩下少于8个棋子时，您可以使用每个索引3个比特，少于4个棋子时使用2个比特，依此类推，最终您将以每步7到10个比特的速度结束。

现在您还可以应用压缩（LZW或Huffman），我建议使用LZW，因为Huffman还需要传递概率分布表，而这可能会是：

16 * ceil(log2(2*70)) bits = ~ 128 bits

相对于800位的限制，这是数据中的相当大部分，而LZW在运行时构建其词典，它的大小可以任意选择（所以即使有小内存也不应该是一个大问题）

- Spektre

1

你需要描述晋升动作的编码。 - trincot

1

你需要描述晋升动作的编码方式。 - undefined

@trincot 你的方法很有趣 +1，但需要相对较大的查找表来预先计算... 顺便说一下，我在计算中出现了一个错误，每次移动是10位而不是11位... 我真的需要喝上早茶 :) - Spektre

@trincot 你的方法很有趣+1，但需要相对较大的查找表来预先计算... 顺便说一下，我在计算中出现了一个错误，每步需要10位而不是11位... 我真的需要喝上早茶 :) - undefined

根据想要移动的棋子，你可以大幅减少比特数。这可以基于棋子的一般移动规则静态地进行，或者更好的是，基于当前局势进行。 - vlad_tepesch

0

有32个棋子和64个方格。因此，需要11位来存储一个棋子及其位置：5位用于表示棋子，6位用于表示位置。

起始位置是固定的，所以不需要存储它。之后，你只需要存储移动的棋子的位置：每个棋子需要11位。也就是说，你存储的游戏只记录了每个棋子的移动。你知道棋子的起始位置，所以你只需要存储棋子的最终位置。

大多数移动只需使用11位（一个棋子移动）。有趣的是，通过更新被吃掉的棋子的位置可以编码捕获。游戏逻辑可以判断两个棋子是否占据同一空间，并从棋盘上移除被吃掉的棋子。这是件好事，因为没有第65个空间（即“不在棋盘上”）可以放置被吃掉的棋子：你没有相应的位数。吃过路兵也可以用类似的方式进行编码：让游戏逻辑理解它。我最初认为王车易位需要编码两个棋子的移动，但实际上并不需要。国王总是移动两个空间，而在其他任何情况下都是非法移动。你的逻辑可以轻松识别这个“非法”移动并执行正确的操作。

兵升变成一个问题。走法不是问题，但你需要一种方式来指代新创建的棋子。棋子只有5个比特位，而这些已经被使用完了。考虑将你的国王的马兵从G7移动到G8。通常情况下，你会存储[14,62]（即棋子编号14移动到位置62）。你需要一种方式来表示，嘿，棋子编号14现在是一个皇后而不是一个兵。这是可以做到的，但需要额外的比特位。

所以在70步棋的最佳情况下，每步棋需要11个比特位，总共770个比特位。在50步棋的情况下，需要550个比特位。

这可能会很紧凑，但我认为你所问的在添加任何压缩或复杂逻辑之前可能是可行的。对于50到70步棋的游戏，平均每场游戏可能需要800个比特位。

- Jim Mischel

0

很多聪明的答案，但每回合最多只有16个棋子可以移动，每个棋子的移动次数少于32次（将车易位算作国王的一步，晋升算作兵的一步）。

这就是4位用于表示棋子，5位用于表示移动方式——每回合需要9位。轻而易举。

- Matt Timmermans

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- trincot · Accepted Answer

你可以列举出给定位置的所有合法走法，并按照约定的方式进行排序（比如按起始方格、目标方格、晋升棋子等排序）。然后通过在这个排序好的合法走法列表中的索引来标识每一步走法。

理论上，拥有最多合法走法的位置有218种。我们可以确信没有超过256种合法走法的位置存在，因此8位足以编码一个单独的走法。

使用这种编码方式，一个70步的游戏将需要560位。

动态位数

然而，显然大多数位置的合法走法数量更接近40而不是218，因此我们可以根据可用的合法走法数量动态地确定下一个编码走法所需的位数。

由于起始位置只有20种走法，第一次白方走法只需要5位；第一次黑方走法也是如此。随着游戏的进行，很快就会出现一个拥有超过32种合法走法的位置，因此将使用6位。例如，在...之后。

1. e3 e5
2. Qg4 d6

...白方有46个合法的着法，因此他们的着法将使用6位编码。对于编码这前四个着法，我们已经节省了3 x 4 = 12位（相比每个着法8位）。

在编码过程中，算法首先会检查有多少个合法的着法，然后使用相应数量的位来编码下一个着法。解码器也可以知道合法着法的数量，并从编码流中消耗相应数量的位。

我不知道在所需位数方面，最坏情况下的70步棋局是什么样的（无法在合理时间内计算），但它肯定远低于500位。

为合理的棋局进行最小化

上述推导出的限制适用于任何棋局，即使是玩家走最差的着法的棋局。然而，如果你想专注于合理的棋局，你可以进一步优化内存占用。

使用确定性的国际象棋引擎，为每个合法着法产生一个得分，并将该得分作为实际进行该着法的概率。重要的是，它在相同的游戏状态下始终产生相同的着法得分。使用Huffman编码相应地对着法进行编码。这意味着好的着法所需的位数比坏的着法少。例如，如果可以捕获皇后，这可能只需要1位的着法。愚蠢的着法所需的位数可能比平均值多，甚至可能超过8位（当有很多合法着法且其中包含非常好和非常差的着法时）。几乎所有着法都是不好的的70着法游戏可能占用比非Huffman编码算法更多的位数，但合理的游戏则会使用更少的位数。