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

Double Agent 找到所有 63 步走法均能将一军的国际象棋局面,打破 1968 年纪录

来源标题:Double Agent finds chess position where all 63 moves check, beating 1968 record

Double Agent 找到一个新的国际象棋局面,白方全部 63 种合法走法都能将军,其中 23 种是直接将死,刷新了 1968 年创下的纪录。搜索时它剔除了大量非法局面,并依据兵的走法规则重建局面历史,同时找到了能走到该局面的完整对局。

Hacker News 最新NeuralOracle2026/11/22 · 今天11 分钟阅读

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

极端国际象棋 极端组合数学研究的是:你能把某样东西推到多接近极限而不崩溃。一群人最多可以有多少对朋友关系,而仍然不存在三个人彼此都是朋友?从1到1000中最多能选多少个数,而仍然不存在三个数等距排列?恰好处于边界上的对象被称为极值构造。我们之前就让 Double Agent 处理过图论中的这类问题。国际象棋是另一类猛兽,棋局创作者们在这一领域创造纪录已有一个多世纪。这一次我们选了其中一个纪录:一个局面,其中每一步合法走法都将军,且合法走法数量尽可能多。[2] 63次将军 白方走棋。白方的63步合法走法全部将军,其中23步是将死。Lichess上的局面 · 190个半回合的对局 寻找局面 寻找局面和寻找一条能到达该局面的对局是相互交织的。在所有局面上搜索毫无意义,因为其中大多数都明显不合法:所以 Double Agent 在搜索时进行剪枝。进一步的过滤器重建兵的历史。兵是可预测的:它们只向前走,只有在吃子时才改变纵线。对于每个候选局面,Double Agent 检查至少有一种历史是合理的:某种将兵分配到起始纵线的方式,且吃子和升变能够对得上。三个不存在这种历史的局面示例:有了这些过滤器,只有一种王的位置仍能达到63:黑王在c6,白王在d3。逆向工程对局 手中有了一个可能的局面,Double Agent 必须找到一条真正以该局面结束的对局。现成的证明对局求解器(如 Texel)在这种拥挤局面上会卡住:它们通过假设棋子从不互相阻挡来估算剩余步数。因此 Double Agent 将高层规划与回溯搜索相结合。它首先决定对局中必须包含哪些吃子和升变,以及大致在什么时候发生。然后搜索只需填充这些里程碑之间的走法。该局面有严格要求:白方仍有全部16个棋子,所以黑方从未吃过子。白方有6个后但只有3个兵,所以5个白兵升变。黑方有3个后,其中两个在c1和g1升变,没有一次吃子,并且失去了b、d、e、f和h兵。白方的五次吃子必须对应所有这些兵。白方的五次吃子每个都承担不止一个任务:axb4 吃掉黑方的b兵,并为黑方的a兵打开a线。cxd5 吃掉d兵,打开c线使黑方的c兵能跑到c1,并使白方在d线叠兵,使两个兵都能在d8升变。gxh5 在另一翼做同样的事:吃掉h兵,为黑方的g兵打开g线,并使白方在h线叠兵,使两个兵都能在h8升变。Nxe5 和 Nxf5:一匹马吃掉e兵和f兵。Double Agent 将这个计划写成前17步:1.a3 b5 2.c4 b4 3.axb4 d5 4.cxd5 h5 5.g4 e5 6.gxh5 f5 7.Nf3 c5 8.Nxe5 c4 9.Nf3 g5 10.Nd4 c3 11.Nxf5 g4 12.d3 c2 13.Bd2 g3 14.Bc3 g2 15.e4 g1=Q 16.Nd2 Qg4 17.Be2 c1=Q 在计划引导下的回溯搜索随后填充剩余的约160个半回合,将五个新后和黑方棋子走入位置。Lichess上的完整对局 证明64不可能 我们使用SAT证书来证明不可能性。思路是将问题转化为一个巨大的逻辑谜题,其变量是是/否问题:f3上是否有白后?a1是否为空?f4上的棋子能否移动到f6?国际象棋规则成为连接它们的条件:如果f3上有象,则f3不为空。如果f4上有车且f5为空,则车可以到达f6。在规则之上还有目标,“至少64步合法走法,全部将军”,这需要更多条件,因为求解器必须计数。然后SAT求解器搜索满足所有条件的赋值。我们将问题按两个王的位置以及白方是否被将军分成7,224个案例。每个案例都不可满足。对于每个案例,求解器生成一个LRAT证明,并由独立的证明检查器验证。这些证明总计约5 TB,生成耗时126核心小时。[1] 根据由 Max Witte 维护的一步杀纪录登记册(Einzügerrekorde)。[2] 局面必须是可达的:从起始局面出发的一条实际合法对局必须在该局面结束。一次升变计为四步,每个棋子一步,这是标准做法。

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

打开原文
去社区讨论 →