程序员拼图:在整个游戏中编码棋盘状态

fet 发布于 2019-11-10 algorithm 最后更新 2019-11-10 12:10 248 浏览

不是严格的问题,更多的是一个难题... 多年来,我参与了一些新员工的技术访谈。除了询问标准“你是否知道X技术”这个问题之外,我还尝试了解他们如何解决问题。通常,我会在面试前一天通过电子邮件向他们发送问题,并期待他们在第二天提出解决方案。 通常结果会非常有趣 - 错误但很有趣 - 如果他们能解释他们为什么采取特定方法,那么他仍然会得到我的建议。 所以我想我会为Stack Overflow观众抛出我的一个问题。 问题:您可以考虑将国际象棋游戏(或其子集)的状态编码的最节省空间的方式是什么?也就是说,考虑到合法安排棋子的国际象棋棋盘,编码这个初始状态以及游戏中玩家采取的所有后续合法行动。 答案不需要代码,只需要描述您将使用的算法。 编辑:正如其中一个海报已经指出,我没有考虑移动之间的时间间隔。随意作为一个可选的额外的:) 编辑2:只是为了进一步澄清......请记住,编码器/解码器是规则感知的。真正需要存储的唯一东西是播放器的选择 - 编码器/解码器可以假定其他任何东西。 编辑3:这里很难挑选出胜者:)很多很棒的答案!

已邀请:

uid

赞同来自:

问题是为典型的国际象棋游戏提供最有效的编码,还是具有最短最坏情况编码的编码? 对于后者,最有效的方式也是最不透明的:创建所有可能对的枚举(初始板,合法的移动序列),其中,使用三次重复位置并且不超过自上次pawn-move-capture规则以来的-fifty-moves是递归的。那么这个有限序列中的位置索引给出了最短的最坏情况编码,但是对于典型情况也是如此长的编码,并且我预计,计算起来非常昂贵。最长的国际象棋游戏应该是超过5000次移动,每个位置通常有20-30个移动可供每个玩家使用(虽然剩下的部分很少,但是更少) - 这给出了这种编码所需的40000比特。 枚举的概念可用于提供更易处理的解决方案,如Henk Holterman关于编码移动的建议所述。我的建议:不是最小的,但比我上面看到的例子更短,并且合理易懂:

  1. 64位表示占用哪个方块(占用矩阵),加上每个占用方块中的哪些块的列表(对于棋子可以有3位,对于其他块可以有4位):这为开始位置提供190位。由于船上不能超过32件,因此占用矩阵的编码是冗余的。所以可以对常见的电路板位置进行编码,例如33个设置位加上来自普通电路板列表的电路板索引。
  2. 1位说谁先行动
  3. 代码根据Henk的建议移动:通常每对白/黑移动10位,但有些移动将占用0位,当玩家没有其他移动时。
这表示490位代码可以编码典型的30步游戏,并且对于典型游戏来说是一种合理有效的表示。 自上次典当移动或捕获规则以来,阿布斯编码三次重复抽签位置和不超过五十次移动:如果你编码移动回到最后一次移动或捕获,那么你有足够的信息来决定这些规则是否适用:不需要整个游戏历史。

eomnis

赞同来自:

就像他们在书籍和纸张上编码游戏一样:每件作品都有一个符号;因为它是一个“合法”的游戏,所以白色首先移动 - 不需要对白色或黑色进行单独编码,只需计算移动的数量以确定移动的人。此外,每个移动被编码为(片段,结束位置),其中“结束位置”被减少到允许辨别歧义的最少量符号(可以是零)。游戏长度决定了移动次数。人们还可以在每一步编码以分钟为单位的时间(自上次移动以来)。 可以通过为每个符号分配符号(总共32个)或通过为类分配符号来完成对片段的编码,并使用结束位置来理解移动了哪个片段。例如,一个棋子有6个可能的结束位置;但平均来说,每一轮都只有一对可用。因此,从统计上看,通过结束位置进行编码可能最适合此方案。 类似的编码用于计算神经科学(AER)中的尖峰序列。 缺点:你需要重放整个游戏以获得当前状态并生成一个子集,就像遍历链表一样。

ksequi

赞同来自:

我试着使用Huffman encoding。这背后的理论是 - 在每次国际象棋比赛中,都会有一些棋子会移动很多,有些棋子不会移动很多或者很早就被淘汰。如果起始位置已经删除了一些部分 - 那就更好了。对于正方形也是如此 - 一些方块可以看到所有动作,而有些则不会被触及。 因此,我有两个霍夫曼表 - 一个用于碎片,另一个用于方块。它们将通过查看实际游戏来生成。我可以为每个方块配对都有一个大桌子,但我认为这样效率会非常低,因为同一个棋子在同一个方格上移动的次数并不多。 每件作品都有一个指定的ID。由于有32个不同的部分,我只需要5比特的部分ID。作品ID在游戏之间不会发生变化。方形ID也是如此,我需要6位。 霍夫曼树将通过在每个节点按顺序遍历时写下每个节点来编码(即,首先输出节点,然后从左到右输出其子节点)。对于每个节点,将有一个位指定它是叶节点还是分支节点。如果它是叶子节点,则后面将是给出ID的位。 起始位置将简单地由一系列片位对给出。之后,每次移动都会有一个位置对。只需找到两次提到的第一个部分,就可以找到起始位置描述符的结尾(以及移动描述符的开始)。如果pawn被提升,将有2个额外的位指定它变成什么,但是片段ID不会改变。 为了解释在游戏开始时提升棋子的可能性,在霍夫曼树和数据之间也会有一个“促销表”。首先会有4位指定升级的棋子数量。然后对于每个pawn,将有其霍夫曼编码的ID和2位指定它已成为什么。 将通过考虑所有数据(起始位置和移动)和促销表来生成霍夫曼树。虽然通常促销表是空的或只有几个条目。 以图形方式总结:

<Game> := <Pieces huffman tree> <squares huffman tree> <promotion table> <initial position> (<moves> | <1 bit for next move - see Added 2 below>)
<Pieces huffman tree> := <pieces entry 1> <pieces entry 2> ... <pieces entry N>
<pieces entry> := "0" | "1" <5 bits with piece ID>
<squares huffman tree> := <squares entry 1> <squares entry 2> ... <squares entry N>
<Squares entry> := "0" | "1" <6 bits with square ID>
<promotion table> := <4 bits with count of promotions> <promotion 1> <promotion 2> ... <promotion N>
<promotion> := <huffman-encoded piece ID> <2 bits with what it becomes>
<initial position> := <position entry 1> <position entry 2> ... <position entry N>
<moves> := <position entry 1> <position entry 2> ... <position entry N>
<position entry> := <huffman-encoded piece ID> <huffman-encoded squre ID> (<2 bits specifying the upgrade - optional>)
补充:这仍然可以优化。每件作品都只有一些法律举措。不是简单地对目标方块进行编码,而是可以为每个块的可能移动提供基于0的ID。每个部分都会重复使用相同的ID,因此总共不会有超过21个不同的ID(女王最多可以有21个不同的移动选项)。把它放在霍夫曼表而不是字段中。 然而,这将难以表示原始状态。人们可能会产生一系列动作来将每件作品放置到位。在这种情况下,有必要以某种方式标记初始状态的结束和移动的开始。 或者,可以使用未压缩的6位方形ID放置它们。 这是否会导致整体尺寸减小 - 我不知道。可能,但应该试验一下。 补充2:另一个特例。如果游戏状态没有移动,那么区分下一步移动就变得很重要。最后再添加一位。 :)

wsed

赞同来自:

有64个可能的电路板位置,因此每个位置需要6位。有32个初始块,所以到目前为止总共有192位,其中每6位表示给定块的位置。我们可以预先确定作品出现的顺序,因此我们不必说出哪个是哪个。 如果一件不在板上怎么办?好吧,我们可以在同一个地方放置一块作为另一块,以表明它不在板上,因为否则这将是非法的。但我们也不知道第一件作品是否会在棋盘上。所以我们添加5位表示哪一块是第一块(32种可能性= 5位代表第一块)。然后我们可以将该点用于后续的棋子。这使我们总共达到197位。电路板上必须至少有一块,这样才能工作。 然后我们需要一个轮到它 - 将我们带到198位。 典当促销怎么样?我们可以通过每个加入3位加上42位来做坏事。但是我们可以注意到,大部分时间,典当都没有升职。 因此,对于板上的每个pawn,位“0”表示它未被提升。如果棋盘上没有棋子那么我们就不需要了。然后我们可以使用可变长度的位串来进行促销。最常见的是女王,所以“10”可能意味着女王。然后“110”表示车,“1110”表示主教,“1111”表示骑士。 初始状态将需要198 + 16 = 214位,因为所有16个棋子都在板上并且没有被启动。一个有两个升级的典当女王的结局游戏可能需要198 + 4 + 4,这意味着4个棋子活着但没有晋升,2个女王棋子,总共206比特。看起来非常强大!

正如其他人所指出的,霍夫曼编码将是下一步。如果您观察了几百万个游戏,您会发现每个游戏更有可能出现在某些方块上。例如,在大多数情况下,棋子保持直线,或者一个保持在左边/一个保持在右边。国王通常会坚持在家里。 因此,为每个单独的位置设计霍夫曼编码方案。 Pawns可能只占平均3-4位而不是6位。国王也应该占用少量位。 同样在这个方案中,包括“采取”作为可能的位置。这也可以非常强大地处理铸造 - 每个车和国王将有一个额外的“原始位置,移动”状态。你也可以用这种方式在棋子中编码en passant - “原始位置,可以通过”。 有足够的数据,这种方法应该产生非常好的结果。

adolor

赞同来自:

昨晚我看到了这个问题,这引起了我的兴趣,所以我坐在床上思考解决方案。我的最终答案实际上与int3非常相似。

基本解决方案 假设一个标准的国际象棋游戏,你不编码规则(像白方总是先行),那么你可以通过编码每件作品的动作来节省很多。 总共有32个,但每次移动时你都知道什么颜色在移动,所以只有16个方格需要担心,这是4个位,这个位于此回合移动。 每件作品只有一个有限的移动设置,你可以用某种方式枚举。
  • Pawn:4个选项,2位(向前1步,向前2步,每对角1对)
  • Rook:14个选项,4位(每个方向最多7个)
  • Bishop:13个选项,4位(如果你在一个对角线上有7个,你在另一个中只有6个)
  • 骑士:8个选项,3位
  • 女王:27个选项,5位(Rook + Bishop)
  • King:9个选项,4位(8个一步移动,加上castling选项)
对于促销,有4件可供选择(Rook,Bishop,Knight,Queen),所以我们会添加2位来指定。我认为所有其他规则都是自动涵盖的(例如en passant)。

进一步优化 首先,在捕获了8个单色之后,可以将片段编码减少到3位,然后将2位减少为4个,依此类推。 但主要的优化是仅枚举游戏中每个点的可能移动。假设我们将Pawn的移动存储为{00, 01, 10, 11},前进1步,前进2步,左对角线和右对角线。如果无法进行某些移动,我们可以在本回合中将其从编码中删除。 我们知道每个阶段的游戏状态(从跟随所有移动),所以在读完哪个部分后,我们总能确定需要读取多少比特。如果我们意识到一个棋子在这一点上的唯一移动是对角线向右捕捉或向前移动一个,我们知道只读取1位。 简而言之,上面列出的每个部分的位存储仅是最大值。几乎所有的举动都会有更少的选择,通常会有更少的比特。

set

赞同来自:

我已经考虑了很长一段时间(+ - 2小时)。而且没有明显的答案。 假设:

  1. 忽略时间状态(玩家没有使用时间限制,因此可以通过不玩来强制抽奖)
  2. 比赛什么时候开始?!?这很重要,因为规则随着时间的推移而发生了变化(因此在现代游戏的后续版本中假设现代游戏......)请参考死亡典当规则(维基百科有一个非常着名的问题显示它),如果你想要的话回到过去好运主教以前只能慢慢移动和骰子过去常用。洛尔。
......所以最新的现代规则是。首先不论重复和移动重复限制。 -C 25字节舍入(64b + 32 * 4b + 5b = 325b) = 64位(有/无) + 32 * 4位[1bit = color {black / withe}         + 3bit =棋子类型{King,Queen,Bishop,kNight,Rook,Pawn,MovedPawn}注意:移动棋子......例如,如果它是上一轮中最后一个移动的棋子,表示'en passant'是可行的。        ] + 5bit用于实际状态(轮到谁了,en passant,是否可以在两边开火) 到现在为止还挺好。可能会增强但是会有可变长度和促销来考虑!? 现在,以下规则仅适用于玩家参加抽奖的情况,这不是自动的!因此,如果没有球员要求平局,那么考虑这90次移动没有捕获或典当移动是可行的!意味着需要记录所有动作......并且可用。 -D重复位置......例如上面提到的董事会状态(见C)与否......(见关于FIDE规则的以下内容) -E这就留下了50移动限额的复杂问题而没有捕获或典当移动那里需要一个计数器......但是。 那么你如何应对呢?......真的没有办法。因为任何一个玩家都不想画画,或者意识到它已经发生了。 现在,如果E计数器可能就足够了......但这是诀窍,甚至阅读FIDE规则(http://www.fide.com/component/handbook/?id=124&view=article)我不能找到一个答案...如何丧失呕吐的能力。那是重复吗?我想不是,但这是一个模糊的主题没有得到解决,没有澄清。 所以这里有两个复杂或未定义的规则,甚至试图编码...干杯。 因此,真正编码游戏的唯一方法是从开始记录所有...然后与“板状态”问题冲突(或不冲突?)。 希望这有帮助......不要太多数学:-)只是为了表明一些问题不是那么容易,对于解释或预先知识来说太开放是正确和有效的。我不会考虑面试,因为它打开了太多的蠕虫病毒。

nquae

赞同来自:

这就是我对游戏步骤进行编码的方式。对于具有40步的游戏,这将花费大约180位左右。 首先,使用知道所有国际象棋规则的引擎创建所有选项的列表。每一步,这样做:

  1. 列举所有可能移动的棋子(开始时,白棋可以移动8个棋子和2个骑士,总计10个。
  2. 存储可能的选择数量和选择本身。
  3. 列举所有可能的移动位置。 (当在开始时选择pawn时,你可以向前移动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
编码非常有效,尤其是最终游戏,因为没有太多可能的选择。此外,当您只剩下一个可能的移动时,您根本不需要任何存储空间。

wiusto

赞同来自:

很棒的拼图! 我看到大多数人都在存放每件作品的位置。如何采取更简单的方法,并存储每个方块的内容?它负责促销和自动捕获件。 它允许霍夫曼编码。实际上,棋盘上棋子的初始频率几乎是完美的:一半的正方形是空的,剩下的一半正方形是棋子等等。 考虑到每件作品的频率,我在纸上构建了一个Huffman tree,我在此不再赘述。结果,其中c代表颜色(白色= 0,黑色= 1):

  • 0表示空方格
  • 1c0 for pawn
  • 1c100 for rook
  • 1c101 for knight
  • 1c110 for bishop
  • 1c1110 for queen
  • 1c1111 for king
对于整个董事会的初始情况,我们有
  • 空方块:32 * 1位= 32位
  • pawn:16 * 3位= 48位
  • rooks / knights / bishops:12 * 5 bits = 60 bits
  • queens / kings:4 * 6 bits = 24 bits
总计:初始板状态为164位。显着低于当前最高投票答案的235位。随着游戏的进行,它只会变小(除了促销之后)。 我只看着棋盘上棋子的位置;附加状态(轮到谁,谁已经阉割,通过,重复移动等)将必须单独编码。也许最多16位,因此整个游戏状态为180位。 可能的优化:
  • 省去不太频繁的碎片,并分别存放它们的位置。但这无济于事......用一个空方格替换国王和王后会节省5位,这正是你需要用另一种方式编码位置所需的5位。
  • “后排没有棋子”很容易通过使用不同的Huffman表来编码后排,但我怀疑它有多大帮助。你可能仍然会得到同样的霍夫曼树。
  • “一个白色,一个黑色主教”可以通过引入没有c位的额外符号进行编码,然后可以从主教所在的方格推导出。 (Pawns晋升为主教会扰乱这一计划......)
  • 空方块的重复可以通过引入额外的符号进行行程编码,例如,“连续2个空方块”和“连续4个空方块”。但估计这些频率并不容易,如果你弄错了,那就会伤害而不是帮助。

nut

赞同来自:

内容太长未翻译

nut

赞同来自:

托马斯有正确的方法来编码电路板。然而,这应该与ralu用于存储移动的方法相结合。列出所有可能的移动,写出表达此数字所需的位数。由于解码器正在进行相同的计算,因此它知道有多少可能并且可以知道要读取多少位,不需要长度代码。 因此,我们得到164位的碎片,4位用于铸造信息(假设我们存储游戏的片段,否则它可以重建),3位用于传递资格信息 - 只需存储移动发生的列(如果en passant不可能存储一个不可能的列 - 这些列必须存在)和1表示要移动的列。 移动通常需要5或6位,但可以从1到8不等。 一个额外的快捷方式 - 如果编码以12 1位开始(无效情况 - 甚至片段在一侧都没有两个国王),您将中止解码,擦除电路板并设置新游戏。下一位将是移动位。

qenim

赞同来自:

最好只以人类可读的标准格式存储国际象棋游戏。 Portable Game Notation采用标准起始位置(尽管它是doesn't have to)并且只是轮流列出移动。紧凑,人性化的标准格式。 例如。

[Event "F/S Return Match"]
[Site "Belgrade, Serbia Yugoslavia|JUG"]
[Date "1992.11.04"]
[Round "29"]
[White "Fischer, Robert J."]
[Black "Spassky, Boris V."]
[Result "1/2-1/2"]
1. e4 e5 2. Nf3 Nc6 3. Bb5 {This opening is called the Ruy Lopez.} 3... a6
4. Ba4 Nf6 5. O-O Be7 6. Re1 b5 7. Bb3 d6 8. c3 O-O 9. h3 Nb8  10. d4 Nbd7
11. c4 c6 12. cxb5 axb5 13. Nc3 Bb7 14. Bg5 b4 15. Nb1 h6 16. Bh4 c5 17. dxe5
Nxe4 18. Bxe7 Qxe7 19. exd6 Qf6 20. Nbd2 Nxd6 21. Nc4 Nxc4 22. Bxc4 Nb6
23. Ne5 Rae8 24. Bxf7+ Rxf7 25. Nxf7 Rxe1+ 26. Qxe1 Kxf7 27. Qe3 Qg5 28. Qxg5
hxg5 29. b3 Ke6 30. a3 Kd6 31. axb4 cxb4 32. Ra5 Nd5 33. f3 Bc8 34. Kf2 Bf5
35. Ra7 g6 36. Ra6+ Kc5 37. Ke1 Nf4 38. g3 Nxh3 39. Kd2 Kb5 40. Rd6 Kc5 41. Ra6
Nf2 42. g4 Bd3 43. Re6 1/2-1/2
如果你想让它变小,那么just zip it。任务完成!

zex

赞同来自:

内容太长未翻译

sit_in

赞同来自:

电路板上的位置可以定义为7位(0-63,并且1个值指定它不再在电路板上)。 因此,对于电路板上的每个部件,请指定它所在的位置。 32个* 7位= 224位 编辑: 正如卡德里安指出的那样......我们也有'促进典当到女王'的案子。我建议我们在末尾添加额外的位来指示哪个pawn已被提升。 因此,对于已经提升的每个pawn,我们遵循224位,其中5位表示已经提升的pawn的索引,如果它是列表的末尾则是11111。 所以最小的情况(没有促销)是224位+5(没有促销)。为每个升级的pawn添加5位。 编辑: 如同毛茸茸的青蛙指出的那样,我们需要在最后指出另一点来表明它的转向; ^)

punde

赞同来自:

攻击在初始位置编码后对步骤进行编码的子问题。方法是创建步骤的“链表”。 游戏中的每个步骤都被编码为“旧位置 - >新位置”对。你知道国际象棋比赛开始时的初始位置;通过遍历链接的步骤列表,您可以在X移动后进入状态。 对于每个步骤的编码,您需要64个值来编码起始位置(板上64个方块的6位 - 8x8方块),以及最终位置的6位。 16位,每侧1次移动。 然后,编码给定游戏的空间量将与移动的数量成比例: 10 x(白移动次数+黑移动次数)位。 更新:促进典当的潜在并发症。需要能够说明pawn被提升为什么 - 可能需要特殊位(为了节省空间,将使用格雷码,因为典当促销极为罕见)。 更新2:您不必编码结束位置的完整坐标。在大多数情况下,被移动的棋子可以移动到不超过X个位置。例如,pawn在任何给定点最多可以有3个移动选项。通过实现每个片段类型的最大移动次数,我们可以节省“目的地”的编码位。

Pawn: 
   - 2 options for movement (e2e3 or e2e4) + 2 options for taking = 4 options to encode
   - 12 options for promotions - 4 promotions (knight, biship, rook, queen) times 3 squares (because you can take a piece on the last row and promote the pawn at the same time)
   - Total of 16 options, 4 bits
Knight: 8 options, 3 bits
Bishop: 4 bits
Rook: 4 bits
King: 3 bits
Queen: 5 bits
因此,黑色或白色的每次移动的空间复杂性变为 6位用于初始位置+(基于移动物的类型的可变位数)。

xillum

赞同来自:

板上有32件。每件都有一个位置(一个64个方格)。 所以你只需要32个正整数。 我知道64位持有6位,但我不会这样做。我会保留几个标志的最后几位(掉落的棋子,皇后棋子)

et_qui

赞同来自:

在初始板的基本情况下以及随后的移动中,请考虑以下内容。 使用国际象棋程序为所有可能的移动分配概率。例如,e2-e4为40%d2-d4为20%,依此类推。如果某些举措是合法的但是该程序没有考虑,请给它们一些低概率。使用算术编码来保存所选择的选项,对于第一次移动将是0到0.4之间的某个数字,对于第二次移动将是0.4和0.6,依此类推。 对另一方做同样的事情。例如,如果e7-e5有50%的几率作为对e2-e4的响应,那么编码的数字将在0和0.2之间。重复直到游戏完成。结果可能是非常小的范围。找到适合该范围的最小基数的二元分数。这是算术编码。 这比Huffman更好,因为它可以被认为是分数位编码(在游戏结束时加上一些可以整合到一点)。 结果应该比Huffman更紧凑,并且没有特殊情况可以促销,传递,50规则移动和其他细节,因为它们由国际象棋评估程序处理。 要重播,再次使用国际象棋程序评估棋盘并为每次移动分配所有概率。使用算术编码值来确定实际播放的移动。重复直到完成。 如果您的国际象棋程序足够好,您可以使用双状态编码器获得更好的压缩,其中概率基于黑色和白色的移动来定义。在大约200多个州的最极端的情况下,这编码了所有可能的国际象棋游戏的整个集合,因此是不可行的。 这几乎是说出大流士已经写过的东西的不同方式,只是通过算术编码如何工作的一些例子,以及使用现有的国际象棋程序来帮助评估下一步行动概率的真实例子。

wiusto

赞同来自:

克莱图斯的回答是好的,但他忘了也编码轮到它了。它是当前状态的一部分,如果您使用该状态来驱动搜索算法(如alpha-beta衍生物),则是必需的。 我不是国际象棋选手,但我相信还有一个角落案例:已经重复了多少次。一旦每个玩家进行三次同样的动作,游戏就是平局,不是吗?如果是这样,那么你需要在状态中保存该信息,因为在第三次重复之后,状态现在是终端。

fet

赞同来自:

存储板状态 我想到的最简单的方法是首先有一个8 8位的数组,表示每个棋子的位置(如果有一个棋子,则为1,如果没有,则为0)。由于这是固定长度,我们不需要任何终止符。 接下来按照其位置的顺序表示每个棋子。每个使用4位,这需要32 4位(总共128位)。这真的很浪费。 使用二叉树,我们可以在一个字节中表示一个pawn,在3中表示骑士和车和主教以及在4中表示一个国王和王后。因为我们还需要存储该部分的颜色,这需要一个额外的字节它最终as(原谅我,如果这是错的,我以前从未详细研究过Huffman coding):

  • Pawn:2
  • Rook:4
  • 骑士:4
  • 主教:4
  • King:5
  • 女王:5
鉴于总数:
2*16 + 4*4 + 4*4 + 4*4 + 2*5 + 2*5 = 100
其中使用固定大小的位组乘以28位。 所以我发现的最好的方法是将它存储在8 2 + 100位数组中
8*8 + 100 = 164


存储动作
我们需要知道的第一件事是哪一块移动到哪里。鉴于板上最多有32块,我们知道每块是什么,而不是表示方块的整数,我们可以有一个表示块偏移的整数,这意味着我们只需要拟合32个可能的值来表示片。 不幸的是,有各种特殊的规则,如铸造或推翻国王和形成一个共和国(Terry Pratchett参考),所以在我们存储要移动的部分之前,我们需要一个位来指示它是否是一个特殊的移动。 因此,对于每个正常移动,我们有一个必要的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位]移动细节 如果Move是正常移动,则Move Detail看起来像
[5位]件
[n位]特定的一块移动(通常在2到6位的范围内) 如果这是一个特殊的举动
它应该有一个整数类型,然后是任何其他信息(如果它是castling)。我不记得特殊动作的数量,所以可能只是表明它是一个特殊的动作(如果只有一个)

nsequi

赞同来自:

正如其他几个人所提到的,你可以为32件中的每件件存储它们所在的哪个方块,如果它们在板上或不在板上,则得到32 (log2(64)+ 1)= 224位。 然而,主教只能占据黑色或白色方块,所以对于这些你只需要log2(32)位作为位置,这给出了28 7 + 4 * 6 = 220位。 并且由于棋子不是从后面开始并且只能向前移动,它们只能在56上,所以应该可以使用这个限制来减少棋子所需的比特数。

ut_sit

赞同来自:

我使用行程编码。有些作品是独一无二的(或仅存在两次),所以我可以省略它们之后的长度。像cletus一样,我需要13个独特的状态,所以我可以使用半字节(4位)来编码。初始板将如下所示:

White Rook, W. Knight, W. Bishop, W. Queen, W. King, W. Bishop, W. Knight, W. Rook,
W. Pawn, 8,
Empty, 16, Empty, 16
B. Pawn, 8,
B. Rook, B. Knight, B. Bishop, B. Queen, B. King, B. Bishop, B. Knight, B. Rook
这留给我8 + 2 + 4 + 2 + 8个半字节= 24个半字节= 96位。我不能用半字节编码16,但由于“空,0”没有意义,我可以将“0”视为“16”。 如果棋盘是空的,但是对于左上角的一个棋子,我得到“Pawn,1,Empty,16,Empty,16,Empty 16,Empty,15”= 10个半字节= 40位。 最糟糕的情况是每件作品之间有一个空的正方形。但是对于片段的编码,我只需要16个值中的13个,所以也许我可以使用另一个来说“Empty1”。然后,我需要64个半字节== 128位。 对于运动,我需要3个比特(颜色由白色总是首先移动的事实给出)加上5比特(0..63)用于新位置=每个运动一个字节。大多数时候,我不需要旧的位置,因为只有一件将在范围内。对于奇数情况,我必须使用单个未使用的代码(我只需要7个代码来编码该部分)然后使用5位用于旧位,5位用于新位置。 这使得我能够以13个叮咬编码阉割(我可以将国王移向白嘴鸦,这足以说明我的意图)。 [编辑]如果你允许一个智能编码器,那么我需要0位用于初始设置(因为它不需要以任何方式编码:它是静态的)加上每次移动一个字节。 [EDIT2]离开典当转换。如果一个pawn到达最后一行,我可以将它移动到位以说“变换”,然后为它所替换的部分添加3位(你不必使用女王;你可以用任何东西替换pawn但国王)。

tquod

赞同来自:

算法应确定性地枚举每次移动时的所有可能目的地。目的地数量:

  • 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位来记录任何游戏。

gvel

赞同来自:

大多数人一直在编码板状态,但关于移动本身..这是一个位编码描述。 每件钻头:

  • Piece-ID:最多4位,用于识别每边16件。可以推断白/黑。在件上定义了一个订单。当碎片数量低于2的相应功率时,使用较少的位来描述剩余的碎片。
  • Pawn:第一次移动有3种可能性,所以+2位(向前移动一个或两个正方形,通过。)后续移动不允许向前移动2,所以+1位就足够了。通过注意当棋子何时达到最后一个等级,可以在解码过程中推断出促销。如果知道pawn被提升,解码器将期望另外2位指示它已被提升到的4个主要部分中的哪一个。
  • Bishop:使用对角线+1位,沿对角线距离最多+4位(16种可能性)。解码器可以推断出该块可以沿着该对角线移动的最大可能距离,因此如果它是较短的对角线,则使用较少的位。
  • Knight: 8种可能的动作,+ 3位
  • Rook:水平/垂直+1位,沿线距离+4位。
  • King: 8种可能的动作,+ 3位。用“不可能”的动作表示铸造 - 因为只有当国王处于第一等级时才能进行铸造,用一条指令对这一动作进行编码,使国王向后移动 - 即离开董事会。
  • 女王: 8个可能的方向,+ 3位。沿着线/对角线的距离最多+4位(如果对角线更短,则更少,如主教的情况)
假设所有棋子都在棋盘上,这些是每次移动的位数:Pawn - 首先移动6位,随后移动5位。 7如果晋升。主教:9位(最大),骑士:7,鲁克:9,国王:7,女王:11(最大)。

znihil

赞同来自:

像Robert G一样,我倾向于使用PGN,因为它是标准的,可以被各种工具使用。 但是,如果我正在玩一个远程太空探测的国际象棋AI,因此每一点都很珍贵,这就是我为这些动作所做的。我稍后会来编码初始状态。 这些动作不需要记录状态;解码器可以跟踪状态以及在任何给定点上哪些动作是合法的。需要记录的所有举措都是选择了哪种法律选择。由于玩家交替,移动不需要记录玩家颜色。由于玩家只能移动他们自己的颜色棋子,所以第一选择是玩家移动的棋子(我将回到后来使用另一种选择的替代方案)。最多16个,最多需要4位。当玩家丢失棋子时,选择的数量会减少。此外,特定游戏状态可能限制棋子的选择。如果国王不能在不加以检查的情况下移动,则选择的数量减少一个。如果国王被检查,任何无法让国王无法检查的作品都不是可行的选择。从a1开始的行主要部分编号(h1在a2之前)。 一旦指定了该片段,它将只有一定数量的合法目的地。确切的数字高度依赖于棋盘布局和游戏历史,但我们可以计算出某些最大值和期望值。对于除了骑士之外的所有人以及在铸造过程中,一件作品都无法穿过另一件。这将是移动限制的重要来源,但很难量化。一块不能离开板,这也将在很大程度上限制目的地的数量。 我们通过按以下顺序对线进行编号来编码大多数块的目的地:W,NW,N,NE(黑色边是N)。一条线在给定方向最远的方形开始,这是合法的移动到并继续前进。对于未受阻碍的国王,移动列表是W,E,NW,SE,N,S,NE,SW。对于骑士,我们从2W1N开始顺时针进行; destination 0是此顺序中的第一个有效目标。

  • Pawns:一个不动的pawn有2个目的地选择,因此需要1位。如果pawn可以捕获另一个,无论是正常的还是en passant(解码器可以确定,因为它跟踪状态),它也有2或3个移动选择。除此之外,pawn只能有1个选择,不需要任何位。当一个棋子处于其7 th 等级时,我们也会选择促销选择。由于典当通常被提升为女王,其次是骑士,我们将选择编码为:
    • 女王:0
    • 骑士:10
    • 主教:110
    • rook:111
  • Bishop:最多13个目的地,{d,e} {4,5}为4位。
  • Rook:最多14个目的地,4位。
  • 骑士:最多8个目的地,3位。
  • 国王:当选择国王时,国王让它回到S并且不能向下移动;这总共提供了7个目的地。剩下的时间里,一个国王最多有8次移动,最多可以有3位。
  • 女王:与主教或车的选择相同,共有27个选择,即5位
由于选择的数量并不总是2的幂,上述仍然会浪费比特。假设选择的数量是C并且特定选择被编号为c,并且n = ceil(lg(C))(编码选择所需的比特数)。我们通过检查下一个选择的第一位来利用这些否则浪费的值。如果是0,则什么也不做。如果它是1并且c + C <1。 2 n ,然后将C添加到c。对数字进行解码会使此反转:如果接收到的c> = C,则减去C并将下一个数字的第一位设置为1。然后将下一个数字的第一位设置为0.如果2 n -C <= c <1。 C,然后什么都不做。将此方案称为“饱和度”。 另一种可能缩短编码的潜在选择是选择要捕获的对手。这增加了移动的第一部分选择的数量,选择一块,最多一个额外的位(确切的数量取决于当前玩家可以移动多少块)。这个选择之后是选择捕获件,这可能远小于任何给定玩家件的移动次数。一件作品只能从任何基本方向加上骑士一件攻击,总共最多10件攻击件;这为捕获移动提供了总共9位,但我平均预计会有7位。这对于女王的捕获特别有利,因为它通常会有相当多的合法目的地。 随着饱和,捕获编码可能无法提供优势。我们可以允许两个选项,在初始状态中指定使用的选项。如果不使用饱和,则游戏编码还可以使用未使用的选择号(C <= c <2 n )来改变游戏期间的选项。任何时候C是2的幂,我们都无法改变选项。

verror

赞同来自:

大多数答案忽略了3倍的重复。不幸的是,重复3次你必须存储到目前为止所有的位置...... 这个问题要求我们以空间有效的方式存储,所以我们真的不需要存储位置,只要我们可以从移动列表构建它(假设我们有标准的起始位置)。我们可以优化PGN,这就是我们所做的。贝娄是一个简单的计划。 板上有64个方块,64 = 2 ^ 6.如果我们只存储每个移动的初始和最终方格,需要12位(促销将在稍后处理)。需要注意的是,这个方案已经涵盖了玩家移动,重力,捕获,铸造等;这些可以通过重播移动列表来构建。 对于促销,我们可以保留一个单独的向量数组,这些向量可以说“在移动N处促进到XYZ”。我们可以保持(int,byte)的向量。 由于许多这些(To,From)矢量在国际象棋中不具备,因此很容易优化(To,From)矢量。例如。不会有从e1到d8等的转移。但是我无法想出任何计划。任何进一步的想法都受到欢迎。

cvitae

赞同来自:

如果计算时间不是问题,那么您可以使用确定性可能的位置生成器为给定位置分配唯一ID。 从给定位置首先在确定性庄园中产生多个可能的位置,例如,从左下方开始向右上方移动。这决定了下次移动所需的位数,有些情况可能只有一个。然后,当移动时,只存储该移动的唯一ID。 只要以确定的方式处理促销和其他规则,它们就算作有效的移动,例如,对女王来说,开车,把每个伯爵都作为一个单独的举动。 初始位置最难,可能产生大约2.5亿个可能的位置(我认为),这需要大约28位加一个额外的位来确定它的移动。 假设我们知道轮到谁(每一圈从白色翻转到黑色),确定性生成器看起来像:

for each row
    for each column
        add to list ( get list of possible moves( current piece, players turn) )
'获取可能的移动列表'将执行以下操作:
if current piece is not null 
    if current piece color is the same as the players turn
        switch( current piece type )
            king - return list of possible king moves( current piece )
            queen - return list of possible queen moves( current piece )
            rook - return list of possible rook moves( current piece )
            etc.
如果国王正在检查中,则每个“可能的xxx移动列表”仅返回改变检查情况的有效移动。

eipsum

赞同来自:

每件可用4位(pawn to king,6种类型),黑/白= 12值表示 板上的每个方块可以用6位(x coord,y coord)表示。 初始位置最多需要320位(32位,4 + 6位) 每个后续移动可以由16位(从位置到位置,片段)表示。 Castling需要额外的16位,因为这是双重动作。 队列中的棋子可以用4位中的4个备用值中的一个来表示。 在没有详细计算数学的情况下,与存储32 7位(预定义的数组)或64 4位(预定义的方块分配)相比,这在第一次移动后开始节省空间 在两侧移动10次后,所需的最大空间为640位 ......但话又说回来,如果我们唯一地标识每个部分(5位)并添加第六位用于标记已编码的棋子,那么我们只需要每次移动的棋子ID +位置。这会将计算更改为...... 初始位置=最大384位(32位,6 + 6位) 每次移动= 12位(到位,片段ID) 然后在每侧10次移动后,所需的最大空间为624位

set

赞同来自:

它增加了对人类玩典型游戏的平均大小优化的兴趣,而不是最坏的情况。 (问题陈述没有说明哪个;大多数回答都假设最坏情况。) 对于移动序列,有一个好的国际象棋引擎从每个位置生成移动;它会产生一系列可能的动作,按其质量等级排序。人们通常比随机移动更频繁地选择好的移动,因此我们需要学习从列表中的每个位置到人们选择“好”移动的概率的映射。使用这些概率(基于来自某些互联网国际象棋数据库的游戏语料库),使用arithmetic coding对移动进行编码。 (解码器必须使用相同的国际象棋引擎和映射。) 对于起始位置,ralu的方法可行。我们也可以通过算术编码来改进它,如果我们有办法通过概率加权选择—例如碎片经常出现在相互保护的配置中,而不是随意的。看到一种简单的方法来融入这些知识就更难了。一个想法:改为回到上面的移动编码,从标准的开始位置开始,找到一个以所需的板结束的序列。 (您可以尝试A 搜索,其启发距离等于碎片与其最终位置的距离之和,或沿着这些线的某些东西。)这会因为过度指定移动序列与利用国际象棋游戏的效率而产生一些低效率知识。 (你可以通过消除可能导致A 搜索中先前探索的位置的移动选择来回退一些低效率:这些在算术代码中可以得到权重0。) 如果没有从实际语料库中收集一些统计数据,那么在平均情况下复杂性也会很难估计会给你带来多少节省。但是我认为所有动作的起点同样可能已经超过了大多数提议:算术编码每次移动不需要整数位。

uharum

赞同来自:

非常大的查找表方法 位置 - 18字节
Estimated number of legal positions is 10 43
只需枚举它们,位置就可以只存储143位。需要再多1位来指示下一个要播放的一侧 枚举当然不实用,但这表明至少需要144位。 移动 - 1个字节
每个职位通常有大约30-40个法定动作,但数量可能高达218 让我们列举每个职位的所有法律动作。现在每个移动可以编码为一个字节。 我们仍有足够的空间进行特殊动作,例如0xFF来代表辞职。

mex

赞同来自:

Yacoby解决方案中起始位置的可能改进 没有合法的位置每种颜色超过16件。在64个方格上放置16个黑色和16个白色部分的方法数量约为3.63e27。 LOG2(3.63e27)= 91.55。这意味着您可以用92位编码所有部分的位置和颜色。对于Yacoby的解决方案所需的颜色,这小于64位的位置+最多32位。在最坏的情况下,您可以节省4位,但代价是编码相当复杂。 另一方面,它增加了缺少5个或更多件的位置的尺寸。这些位置仅占所有位置的<4%,但它们可能是您想要记录不同于初始位置的起始位置的大多数情况。 这导致了完整的解决方案

  1. 根据上述方法对片段的位置和颜色进行编码。 92位。
  2. 要指定每件作品的类型,请使用霍夫曼代码: 典当:'0',车:'100',骑士:'101',主教:'110',女王:'1110',国王:'1111'。 对于全套件,这需要(16 * 1 + 12 * 3 + 4 * 4)= 68位。 全板位置可以编码为92 + 68 =最大160位。
  3. 添加其他游戏状态: 转:1位,可以进行转换:4位,“en passant”可能:最多4位(1位表示情况,3位表示哪一位)。 起始位置编码为= 160 + 9 = 169位
  4. 对于移动列表,枚举给定位置的所有可能移动并将移动的位置存储在列表中。移动列表包括所有特殊情况(castling,en passant和resigning)。仅使用尽可能多的位来存储最高位置。平均每次移动不应超过7位(平均每件16件可能的件和8件合法移动件)。在某些情况下,当强制移动时,它只需要1位(移动或辞职)。

ut_quo

赞同来自:

一块板有64个方块,可以用64位表示,显示方块是否为空。如果正方形有一块,我们只需要片段信息。由于播放器+片段需要4位(如前所示),我们可以获得64 + 4 32 = 192位的当前状态。扔在当前转弯,你有193位。 但是,我们还需要对每件作品的合法移动进行编码。首先,我们计算每件作品的合法移动次数,并在完整正方形的作品标识符之后追加许多位。我计算如下: Pawn:前锋,先前两个前锋,en passant 2,晋升= 7位。你可以将第一个前转和升级合并为一个位,因为它们不能从同一个位置发生,所以你有6个。 白嘴鸦:7个垂直方块,7个水平方块= 14位 骑士:8个方格= 8位 主教:2对角线 7 = 14位 女王:7垂直,7水平,7对角线,7对角线= 28位 国王:8个周围的广场 这仍然意味着您需要根据当前位置映射目标方块,但它(应该)是一个简单的计算。 由于我们有16个棋子,4个车/骑士/主教和2个女王/国王,这是16 6 + 4 14 + 4 8 + 4 14 + 2 28 + 2 * 8 = 312多位,带来总计为505位。 至于可能移动的每个片段所需的位数,可以添加一些优化,并且可能减少位数,我只使用简单的数字来处理。例如,对于滑动件,您可以存储它们可以移动的距离,但这需要额外的计算。 长话短说:仅在占用方块时存储额外数据(片段等),并且仅存储每个片段的最小位数以表示其合法移动。 编辑1:忘记任何一块铸造和典当促销。这可以带来明确位置的总数为557次移动(对于棋子为3位,对于国王为2位)

cut

赞同来自:

[正确阅读问题后编辑]如果您假设可以从初始位置(这可能是“合法”的定义)到达每个合法位置,那么任何位置都可以表示为从一开始的移动顺序。从非标准位置开始的一段播放可以表示为到达开始所需的移动顺序,打开相机以打开相机,然后是后续移动。 因此,让我们将初始板状态称为单个位“0”。 从任何位置移动都可以通过对方块进行编号并按(开始,结束)对移动进行排序来进行枚举,传统的2平方跳跃指示铸造。不需要对非法移动进行编码,因为板位置和规则始终是已知的。打开相机的标志可以表示为特殊的带内移动,或者更合理地表示为带外移动数。 每侧有24个开口移动,每个可以容纳5位。后续移动可能需要更多或更少的位,但合法移动始终是可枚举的,因此每次移动的宽度可以愉快地增长或扩展。我没有计算,但我想7位的位置很少见。 使用该系统,可以以大约500比特编码100个半移动游戏。 但是,使用一本开头书可能是明智之举。假设它包含一百万个序列。然后,初始值0表示从标准板开始,1后跟20位数字表示从该打开序列开始。具有某种传统开口的游戏可以缩短20个半移动或100位。 这不是最大可能的压缩,但是(如果没有开头的书),如果你已经有一个国际象棋模型,那么它将非常容易实现。 为了进一步压缩,您需要根据可能性而不是以任意顺序对移动进行排序,并且以较少的比特编码可能的序列(使用例如人们已经提到的霍夫曼令牌)。