导语 在棋类研究与组合优化的交叉领域里,一个看似简单的问题吸引了许多爱好者和专业人士的注意:在任何合法且可由起始局面走到的棋局中,轮到一方时最多能有多少合法走法?1964年,棋类创作大师 Nenad Petrović 给出了一个白方可走218步的可达棋局,长期以来这一数值被视为上界或接近上界。2024年,基于整数规划和严格边界分析的工作最终证明了没有可达棋局能超过218步,从而将218确立为可达局面的准确上限。本文从历史、数学、算法与应用角度,详尽解析这一结论为何成立、如何被证明,以及它对棋类理论与工程实践的意义。 历史与概念澄清 在讨论上限前需要澄清两个概念:合法(legal)与可达(reachable)。合法是指在当前棋盘配置下,双方国王不在被吃的状态,并且棋子数与走法规则不违反基本规则。可达则更严格,指该局面能通过一系列合法走步从起始局面演变而来。
一个局面可能合法但不可达。Petrović 在1964年构造了一个可达局面,使得白方有218种合法走法,而这些走法在当时是已知的最大值。长久以来,人们一直在追问是否能够构造出更多走法的可达局面。 问题的挑战性在于组合爆炸:64格上每格可能为空或放置不同颜色与类型的若干棋子,所有合法局面数目极其庞大,穷举不现实。因此要把握结构性约束与上界估计,通过数学证明将搜索空间大幅缩小,最后证明不存在超过218的可达局面。 关键洞察与约束简化 证明的核心在于识别那些对最大走法数没有帮助的局面元素,从而系统性地剔除冗余或"有害"的配置。
若能证明某一类棋子或安排不会增加白方的走法总数,便可在不损失最优性的前提下将其替换或删除。以下为若干决定性观察的通俗化表达。 黑子"无用论证"指出,除非黑子能够被白兵吃从而为该兵带来额外走法、保护黑王从而避免非法白子吃子,或解放某些被钉住的白子,否则黑子的存在不会增加白方走法数。如此一来,许多黑子都可以替为空格或更弱的黑子,从而降低复杂度但不减少上界。 "过强棋子可替换"原则表明,在棋子数允许的前提下,黑方的强力棋子通常可以换成移动范围更小的棋子而不降低白方的可选走法。因为黑子的主要作用是影响白方可落子空间与限制性约束,减少黑方活动范围不会放宽白方的选项,但能避免模糊的多种交互情况。
"避免将军"是另一个根本性约束。若白方或黑方处于被将军状态,会显著压缩可选走法。对于白方的走法数最大化问题,任何让白王或黑王处于被将军的配置都不是优的。由被将引出的走法上界可以通过直接计数得到,远低于218,因此可先排除含有将军的候选局面。 数学建模:把棋局转成优化问题 这些观察使得将问题转化为一个整数线性规划(Integer Linear Programming, ILP)成为可能。每一个棋盘格和每一种棋子类型对应布尔变量,表示该格是否被某种棋子占据。
走法计数被表达为变量与系数的线性组合,目标是在合法约束下最大化白方可走法数。约束包含棋子数量限制、王的唯一性、兵的升变位置约束、不可同时占据等规则。该模型虽简化了许多细节(如细节性走法规则、钉住对移动的限制等),但保留了影响总走法数的关键因素。 直接将完整 ILP 求解仍然困难。因此研究者采用松弛方法,即允许变量取分数值,得到线性松弛问题(LP)。LP 的最优值对整数问题给出上界。
如果即使在允许分数解的情况下也无法超过某个上界,那么实际整数解显然也无法超过该界。这一思路在组合优化中非常常见。为了防止分数解产生的"幻想性"配置(例如半个皇后分布在多个格子以虚增移动数),研究者还引入了额外叠加约束,限制从同一方向进入某一格的可行动量,从而更接近真实棋局的结构。 计算实践:Gurobi 与启发式改造 将模型交给 Gurobi 这样的商用优化器后,研究者进行了多轮实验与约束调整。初始松弛解给出的上界远高于218,原因在于分数解能组合出现实中不可实现的"半棋子"配置。通过加入"冗余但有结构意义"的约束,限制某些类型的重合移动方向、强制棋子数接近整数,LP 的上界被不断收紧。
最终的模型在计算资源与时间的折衷下被求解到证明性强度足以断言不存在可达局面超过218的实数解。 研究过程还包括一系列可证明的剪枝:例如对被将、钉住与兵升变的特殊处理、对黑子功能的归类替换,以及白子可走法按类型(兵的前进、兵的吃子、非兵子移动、王移动)分解来计数。合适的数学不等式和组合计数用于把复杂互动上界化为易于计算的线性形式。 验证下界与可达性 证明上界并非全部工作;要成为完整结论还需展示下界,也就是存在可达局面达到该上限。Petrović 的1964年构造就提供了一个可达的白方218步样本,而现代研究者也通过构造性证谱或证明棋谱可达性来确认这些极端局面的确可从初始局面演变而来。若要质疑上界成立,就需要给出一个可达且走法数更多的局面。
经过广泛数值与逻辑排查后,没有发现超过218步的可达局面,最终确立了218为严格上限。 延伸结果与其他极值问题 在该研究过程中,研究者还利用类似方法证实了其它有趣结论。例如在不允许升变(promotion)的前提下,白方最多可走144步的结论得到了确认;一些非法但合乎某些形式约束的极端局面能达到更高的走法数(例如某些非法构型可达到288),而不可达但合法的构型在极限情况下能接近271等数值。这样的对比帮助厘清"可达"这一额外约束是如何显著改变极值问题的。 理论与工程意义 理论上,这一结果加深了对棋局组合结构的理解,表明在最优设计中许多原本看似复杂的交互可以被替换为更简单的配置,同时不会损失局面丰富性。对于棋谱理论、棋类创作以及复杂性研究都有启发意义。
工程层面上,结论也极具实用价值。许多棋类引擎、数据库存储与压缩算法需要为某种最大走法数分配索引或缓冲空间。知道白方在任何可达局面中的最大走法数为218,使得相关数据结构可以更精确地设计,从而节省内存与网络传输成本。对搜索算法的启发在于,某些极端分支可以被数学上剪枝,而不必在实际搜索时浪费计算资源。 方法局限与未来研究方向 尽管整数规划与松弛方法在此问题上取得了最终成功,但方法本身依赖于仔细的约束设计与大量试验调参。求解器结果的可靠性也要求模型无误以及计算过程没有实现漏洞。
因此在科学传播中需要保持审慎,并鼓励独立复核与代码开源以便同行验证。多个独立小组重复得出相同结论,增强了结果的可信度。 未来研究可以沿着多个方向推进。将同样的思路应用到"最多将军次数""最多吃子次数""最多逼和走法"等问题上,或在特定条件下(例如限制棋子种类、限制升变或限定起手序列)探索极值,都是有吸引力的课题。另一个方向是发展专门的组合上界工具,替代通用求解器,以更高效率处理更复杂的棋类极值问题。 结语 218这一数字看似冷冰冰,但它的确立是数学、计算与棋理三者融合的成果。
通过合理的抽象、严谨的上界估计与现代优化器的计算能力,人们得以将一个原本看似不可穷举的问题转化为可证明的结论。从棋类爱好者到算法研究者,均可从中汲取方法论的启示:面对组合爆炸,合适的结构性观察与松弛上界常常是打开难题的钥匙。对于热衷棋类极值问题的同行而言,接下来的挑战在于把这些方法推广到更广泛的极值问题,并通过开源与同行评审确保结论的稳固与可重复性。愿更多的数学与计算工具继续照亮棋类研究的未知领域。 。
