返回资讯中心
外部精选
软件工程
#开发者实时流

如何用26字节存储国际象棋棋盘局面

来源标题:How to store a chess position in 26 bytes using bit-level magic

作者介绍了一种用bit级技巧存储国际象棋局面的方法:棋盘上32个棋子各用6位表示所在格,共需192位即24字节,再叠加被吃棋子、易位权、吃过路兵目标和升变等信息后总计26字节。该方法源自作者对Nicole Tietz-Sokolskaya一篇博客文章的延伸思考。

Hacker News 最新kurinikku2026/11/18 · 今天12 分钟阅读

以下正文由 AI 翻译自 Hacker News 最新(原文版权归原站所有),可能存在偏差,重要内容请以原文为准。

作者注:本文改编自 Recurse Center 的一次演讲。Hacker News 评论见此。 这次探索始于 Nicole Tietz-Sokolskaya 的博客文章。 我不禁想问——情况真的如此吗? 棋盘上有 32 个棋子。我们把它们并排放置。 每个棋子可以占据 64 个格子之一。我们用 0 到 63 之间的数字来表示每个棋子,以代表其所在的格子。 由于每个位置需要 6 位(2^6=64),6 位乘以 32 个棋子,我们得到 192 位 / 24 字节(1 字节 = 8 位)。 除了位置之外,我们还需要记录被吃掉的棋子,因为这些棋子不会出现在棋盘上。 我们需要记录王翼、后翼或两侧是否都可以易位。特别地,如果王或车之前移动过,则不允许易位。 吃过路兵只允许在对方兵进行双步移动后的紧接着的一回合进行。吃子的兵移动到对方兵后面的格子;这个格子称为过路兵目标格。 当兵到达最后一行时会发生升变,然后被替换为马、象、车或后。 我们可以用一个 32 位的位图来记录被吃掉的棋子,每一位代表一个棋子。我们同样可以用位图来表示易位可用性和过路兵目标格,分别需要 4 位和 16 位(每个车 1 位,每个兵 1 位)[2]。 升变需要多一点空间。对于每个兵,我们需要 3 位:1 位表示它是否已经升变,加上 2 位表示它升变成了什么棋子。总共是 48 位。 第一个观察是,棋盘上不可能有两个棋子占据同一个格子。 我们可以将其应用于被吃掉的棋子,用对方王的位置来表示该棋子被吃。 Adam Kelly 指出,我们可以进一步利用己方王的位置。对于易位,我们直接替换车的位置。由于只有在车未移动过的情况下才允许易位,我们知道车会在其初始位置。 对于过路兵,我们知道刚刚进行双步移动的兵在其初始纵线上,并且处于特定的横线(白方为 4,黑方为 5)。我们同样用己方王的位置替换该兵的位置。 通过使用这个技巧,我们可以免费存储被吃掉的棋子、易位可用性和过路兵目标格! 第二个观察是,升变兵的顺序可以被唯一化。 在这个说明性示例中,一个兵升变为后,另一个升变为车。右侧顶行表示白兵位置,而底部各行表示升变编码(每个白兵 3 位)[3]。 这给了我们字符串 00000034,可以唯一地表示这组特定的升变,而不会丢失信息。 有多少种可能的字符串?通过暴力枚举,我们最终得到 495 个不同的字符串 [5]。 len( set( tuple(sorted((a, b, c, d, e, f, g, h))) for a in [0, 1, 2, 3, 4] for b in [0, 1, 2, 3, 4] for c in [0, 1, 2, 3, 4] for d in [0, 1, 2, 3, 4] for e in [0, 1, 2, 3, 4] for f in [0, 1, 2, 3, 4] for g in [0, 1, 2, 3, 4] for h in [0, 1, 2, 3, 4] ) ) 每方可以用 9 位来存储 [6]。 我们将其加到位置的 24 字节上,最终总共约 26 字节! 欢迎在 Replit 上试试!代码可以在 Github 上找到。 国际象棋编码(以及一般的压缩!)是一个深奥而迷人的话题。这篇文章讨论了使用 Huffman 编码来高效存储棋局。 如果这听起来有趣,你应该申请 Recurse Center!下一期将于 2023 年 1 月 3 日开始,信息说明会于 2022 年 12 月 9 日举行。 如果你对我的看法感兴趣,可以在这里联系我。其他 RC 文章可以在这里和这里找到。 [1] Forsyth-Edwards 记谱法存储位置、活动颜色、易位可用性、目标格、半步时钟和全步数。 [2] 由于最多只有 1 个兵可用于吃过路兵,我们实际上可以使其更紧凑。我们需要 1 位表示是否可用,加上 4 位表示 16 个兵,总共 5 位。 [3] 我们用 n、b、r 和 q 分别表示升变为马、象、车和后。这是特意选择的,以与后面的 0 - 4 表示形成对比。 [4] 对于过路兵,我们需要兵留在其初始纵线上。因此,如果该兵可以被吃过路兵,我们将其排除在这一步之外。被吃掉的棋子可以出现在任何纵线上。 [5] Ben Zinberg 使用球与瓮的论证得出了 495。 [6] 每方限制为 8 位时,我们最多可以完整跟踪 4 个升变兵。或者我们注意到升变总是涉及吃子;我们可以通过约定将被吃棋子表示为最左或最右来潜在地回收 1 位。

正文由 探How 从来源站点 RSS 同步,内容未经改写;遇到排版缺失或需要图片、视频时请以原文为准。

打开原文
去社区讨论 →