这个问题我琢磨了很久起因是有朋友看完一场顶级象棋人机大战后问我“AI是不是已经能算出国际象棋所有变化所以逻辑上完全正确了”我当时的回答让他有点意外国际象棋的局面数大到超乎想象而“逻辑正确的程序”更是一个在数学意义上根本不成立的目标。这篇文章就把这两件事彻底说透顺便聊聊我们现实中的象棋程序到底是怎么“变强”的。先给结论国际象棋的合法局面数约有 (10^{43}) 至 (10^{47}) 量级而完全搜索整棵博弈树的分支数量则达到 (10^{123})这个数字就是著名的“香农数”。至于“逻辑正确”的程序如果指的是“每一步都能被证明是全局最优”那在可预见的未来无论用什么硬件都做不到因为它等价于要穷举所有可能而 (10^{123}) 这个规模已经超越了物理宇宙中原子总数约 (10^{80})的极限。这篇文章适合三类人看一是下棋多年、想搞懂“引擎为什么这么走”的棋友二是写代码时对博弈算法感兴趣、想动手做个象棋AI的开发者三是纯粹被这个数学问题吸引、想知道“大数”到底有多大的好奇者。我会把局面数怎么算、为什么“逻辑正确”无从谈起、现实中的程序靠什么变强、以及常见理解误区一次讲清楚。1. 国际象棋的局面数到底怎么算出来的很多文章一上来就抛出一个天文数字但从不解释这个数字从哪来。第一次看的时候我也觉得是忽悠后来翻了资料、自己试着推演才明白这个估算其实有清晰的数学逻辑只不过中间要绕几个弯。1.1 先分清楚“合法局面”和“任意摆放”国际象棋有多少种局面严格说分两种一种是“把棋子随便摆在棋盘上不管合不合理”另一种是“实际对局中可能出现的局面”。后者叫合法局面前者叫理论摆放二者差了不是一星半点。理论摆放很好算粗账。棋盘有64个格每种棋子王、后、车、象、马、兵有固定数量。不考虑任何规则限制光算“这些棋子往64个格子里放”的组合数量级大约在 (10^{45}) 到 (10^{48}) 之间具体数字取决于你是否区分同色同类棋子。可这种纯排列毫无意义因为你会摆出“双方都没有王”“两个王紧挨着互相将军”“兵在底线”这种现实里永远不可能出现的盘面。所以专家们关心的是合法局面数。定义很严格双方各有一个王最多16个棋子棋子分布必须符合走子规则的历史可能比如兵的个数、位置要能被解释而且不能出现双方同时被将军等自相矛盾的状态。基于这些约束目前学界公认的合法局面数上限大约在 (4.8\times 10^{44}) 左右。注意这个 (4.8\times 10^{44}) 是“上限”不是精确值。国际象棋有没有被完全穷举所有的合法局面据我所知答案是“没有”。这个问题在组合数学上至今仍是开放难题因为约束条件太多很难精确枚举。1.2 香农数从具体局面换算成全盘变化真正在人工智能论文里经常被引用的是另一个数字香农数。1950年信息论创始人克劳德·香农发表了一篇论文《Programming a Computer for Playing Chess》这是计算机下棋的奠基之作。他算了一笔账一盘棋平均每步约有30种合法着法。一盘棋平均每方约走40步双方合计80个半回合。那么整棵博弈树的分支数大约是 (30^{80})约等于 (10^{118}) 到 (10^{123})。后来更精细的估算把上限推到约 (10^{123})业界干脆用“香农数”来代指这个数字。需要强调香农数描述的不是“局面总数”而是“从初始局面出发所有可能对局路线的总和”。局面总数是静态的节点数香农数是动态的路径数路径数通常远大于节点数。我用一个生活化类比帮大家感受差距假设宇宙里每个原子都是一台超级计算机每台计算机每秒能处理一亿亿次运算从宇宙诞生一直算到现在算完的总次数也远远够不着 (10^{123})。换句话说香农数不是“工程上难以完成”而是“物理上就不可能完成”。1.3 一个容易混淆的概念节点数和路径数很多人会把“局面数 (10^{43})”和“博弈树分支数 (10^{123})”搞混我最初也踩过这个坑。简单理一下一棵树的节点是棋局中可能出现的盘面路径是从根节点到叶子节点的完整走法序列。国际象棋的合法局面数约 (10^{43}) 到 (10^{47})这只是一棵树里的节点总量上限而路径数是所有可能棋局的完整走法组合动辄 (10^{123})。这两者之间的关系有点像地图上的“路口数”和“从家到公司的所有路线数”。城市路口是有限的但你可以绕圈、走回头路路线的组合数会远超路口数。国际象棋更是如此因为规则允许重复局面三次重复局面才算和棋但在此之前局面可以反复出现所以路径可以无限延伸甚至严格来说博弈树深度没有上限——只要双方都不提和、不重复到三次理论上可以一直走下去。正因如此“完全遍历整棵博弈树”在数学上就是一场注定失败的追击战。2. “逻辑正确”为什么是一个伪命题搞清楚局面规模之后第二个问题就来了既然局面数大得离谱那“写出逻辑正确的国际象棋程序”为什么不可能有人可能想局面数大归大但规则是有穷的程序逻辑总可以覆盖所有规则吧这里就要从两个层面打破这个幻想。2.1 逻辑正确意味着“每一步都能被证明最优”先定义清楚什么叫“逻辑正确”。如果你说的是“程序不走违反规则的棋、不在已知知识里犯低级错误”那现代引擎早就做到了这根本不稀奇。但如果你的意思是——程序在任意局面下都能走出“绝对最优”的一步并且这个“最优”可以被严格证明——那要求完全不同。要证明一步棋最优最可靠的办法是对这步棋之后的所有变化做穷举对手每一步怎么应对我每一步怎么反制直到对局终止。然后在所有可能性里选出必胜、必和或者至少不吃亏的那条线。这个“穷举全部后续变化”的动作恰恰就是要遍历以当前局面为根节点的整棵博弈子树。而刚才说了这个子树的规模在一个中盘局面下依然可能是 (10^{80}) 甚至更高不是“算得完算不完”的问题是“物理定律不允许”的问题。有人会问那残局呢残局子力少总该能穷举吧这反而是对的思考方向。确实有例外——我下面会讲到残局表库它用逆向归纳法直接算出了某些残局的全部精确结果。比如王单兵对王、王车对王这类残局子力少到可以穷举程序在这些局面下是“逻辑正确”的。但一旦子力超过六七颗状态数又会指数爆炸残局表库的体积也会随之失控。所以逻辑正确只在极小范围内成立远不足以覆盖全局。2.2 更致命的问题很多象棋概念没有唯一逻辑定义就算抛开计算量还有一层更根本的困难国际象棋术语的语义模糊性。“优势”“攻势”“好位置”“主动权”这些概念人类棋手靠直觉理解但程序只有数值。要给“逻辑正确”下一个完整定义你必须把这些模糊概念全部翻译成精确数学语言可这几乎做不到。举个例子“王的安全”怎么定义是王周围兵的数量还是敌后子力到王的距离加权不同棋手看法不同。“空间优势”怎么量化是己方棋子能控制的格子数与对方之差吗这种量化方案可以有十几种而没有哪一种能宣称是“唯一正确”的。程序里的评估函数本质上是一堆权重相加子力、位置、兵型、王的安全等这些权重是工程师调出来的带着大量主观取舍根本没有“绝对正确”的标准可言。香农在1950年的论文里就点破了这一层他建议用“分数”来评估局面把每个因素加权求和然后靠搜索找到分数最高的路线。他明确知道这套方案不是逻辑上完备的只是为了在有限资源下“实用”。所以你问“程序逻辑是否正确”程序只会回答“在某种评估定义下这条路分数最高”。换一套权重答案可能就变了这哪来的绝对正确。2.3 数学背景可计算与可判定的边界从理论计算机科学的角度看下国际象棋问题本身的可判定性是成立的规则有穷游戏必然终止所以理论上存在一个算法可以判定任意局面的胜负除非涉及无限重复的极端情况。但“理论上存在算法”和“工程上能实现算法”是两回事。这里牵扯到一个叫“复杂性类”的概念国际象棋属于EXPTIME-complete问题意思是它的最优走法求解在最坏情况下需要指数级时间而且人们普遍相信不存在多项式时间的高效算法。打个比方一个问题“理论上能解”相当于你知道从北京到上海有路可走但“实际无法完成”相当于那条路需要绕行全宇宙那么长的距离。两者不矛盾只是后者告诉我们所谓“逻辑正确的程序”只能存在于教科书证明里现实中大家都是靠各种聪明近似在夹缝中求胜。这时肯定有人反驳现在顶尖的象棋引擎不是已经碾压人类世界冠军了吗难道它们不是“近乎正确”答案稍后揭晓——引擎的强来自另一套完全不同的思路。3. 现实中程序是怎么“变强”的既然“逻辑正确”不可行那今天这些超级引擎凭什么能赢人类秘密在于它们走了一条完全务实的路线不追求“绝对最优”而是追求“在有限资源里找尽量好的着法”。这条路线绕开了逻辑完备性的死胡同靠工程手段把战斗力拉到惊人的高度。3.1 三步核心框架搜索、评估、剪枝现实中的象棋引擎框架一句话概括就是“深度有限搜索 启发式评估”。程序往前推演若干步比如12步、20步在推演树的叶子节点用评估函数打分再倒推回来决定根节点走哪步。倒推用的算法叫极小化极大Minimax我取对我最有利的分支对手取对我不利的分支层层传递。如果节点多到算不完就用阿尔法-贝塔剪枝砍掉明显没希望的分支。关键点在于“推演若干步”这个“若干”。现代引擎一步棋通常能搜到20到30个半回合甚至更深具体深度取决于局面复杂度、硬件的计算能力和行棋时限。但无论多深它都是有限深度永远比不了无穷大的完整博弈树。评估函数的设计更是直接决定棋力好坏子力价值后9、车5、象马3、兵1这只是基准、棋子位置活性、兵型结构、王的安全、通路兵等统统加权求和权重的微小差异都会导致棋风天差地别。我自己试过写简易引擎最深切的感觉是评估函数就像人类棋手的世界观。有的人觉得“弃子攻王”划算有的人觉得“多兵残局”实在你给机器的权重就表达了你的偏好。我早期给象的机动性权重设得过高引擎下出来的棋变得特别激进经常在中局弃子然而它并没真正算清攻杀路线结果白送子力。后来调低权重、加强深度棋风才稳下来。这充分说明“逻辑正确”有多不靠谱连程序制造者自己都在反复调整“正确的定义”。3.2 记忆胜过计算开局库与残局表库引擎为什么开局阶段从来不出昏招因为它根本不是自己在算而是在背谱。开局库收录了大量职业棋谱和公开理论变化引擎开局时直接查表走棋省下宝贵的计算时间留给中局。这相当于把人类几百年的开局理论压缩成一本超大字典程序翻字典就行。残局阶段同理靠的是残局表库。表库的原理是逆向归纳从所有可能的将死局面出发反向推演所有子力配置标注每种局面下的胜负和最短取胜步数。当前许多残局表库已经覆盖了7个子力以内的全部局面。在这个范围内引擎是真的“逻辑正确”的因为每个局面都被精确算到底不存在近似。有一个很有意思的细节残局表库的体积可以用压缩算法控制到很小的程度但生成它需要海量算力。这跟人类棋手背残局定式有异曲同工之妙与其临场推导不如先记住结论。区别在于机器记忆的覆盖范围远超任何人类。3.3 为什么说引擎的强是“工程强”而非“逻辑强”现代引擎强在深度搜索、并行计算、高效剪枝、海量开局和残局知识的组合拳。它们的着法质量在绝大多数局面下已经超过了人类理解极限甚至人类特级大师都解释不清某步棋的意图。但这一切只是近似寻优不是绝对正确。一个直观的实验让两台引擎互相对弈一个搜索深度设20层一个设25层。25层那台大概率会赢但偶尔也会有深度浅的赢下对局。这说明深一层搜索往往更强但那一步“更强”的着法依然不能保证完胜。如果真有“逻辑正确的程序”深层的搜索结果本来就应该完胜浅层因为双方的胜负应该是数学上确定的事情。可实际对局里依然存在波动、误算和运气成分这恰恰说明引擎没有也不可能穷尽一切变化。注意网上有些人把引擎的“分数”当作绝对判据说“引擎给这个局面0.5所以白方一定多半个兵的优势”。这是误解。引擎评分建立在评估函数的启发式权重上换个评估体系分数就会变。分数只在这个引擎的认知框架内有意义跨引擎、跨版本都没法直接比较。4. 常见误区与踩坑实录聊了这么多理论我盘一下大家在接触这个话题时最常踩的坑。有些是认知误区有些是动手做引擎时才会遇到的教训整理出来能少走不少弯路。4.1 误区一“算得快就是算得正确”很多人觉得引擎毫秒级出棋一定是把所有变化摸透了。真相是引擎只用有限深度搜索然后靠评估函数“猜”叶子节点的优劣。深度越深越准但它永远在猜。这就好比一个老棋手一眼扫过棋盘就能说“这局面白稍好”你问他算到多少步之后他其实只凭经验和棋感。引擎本质是“高性能棋感”只是它可以把棋感背后的计算拆解得很细。用数据说话虽然合法局面数约 (4.8\times 10^{44})但现代引擎在一盘棋中真正搜索过的节点数也就能到几亿到几十亿。这个数字在 (10^{44}) 面前连零头都算不上。引擎的棋力来自搜索深度和评估函数的不断优化而不是因为它触及了庞大局面空间的某个角落。4.2 误区二“所有局面最终都能被硬算出来”这个误区最常见的变体是“现在算力每年翻倍早晚有一天能算完全部局面。”很遗憾算力增长是指数级局面空间也是指数级但两个指数的基数差别太大了。更重要的是显式枚举一个局面需要存储和索引而 (10^{44}) 个局面的存储空间哪怕每个只用1比特也要约 (10^{31}) TB起步远超地球总存储量。更别提一旦进入残局表库状态索引还要包含“轮到谁走”“能不能易位”“有没有吃过路”这些额外信息状态空间只会再膨胀。我用一个具体的数来感受差距假设你每秒处理一亿个局面一天就是约 (8.64\times 10^{14}) 个一年约 (3.15\times 10^{17}) 个。要把 (4.8\times 10^{44}) 个局面全都过一遍需要 (1.5\times 10^{27}) 年。宇宙年龄才约 (1.38\times 10^{10}) 年。所以“硬算全部局面”不是技术问题是宇宙尺度上的绝望问题。4.3 给想动手做象棋AI的新手几条建议如果你看完这些还想自己写一个象棋引擎作为一个踩过不少坑的人我给你几条实在的建议。第一先做合法着法生成和棋盘表示不要一上来就谈搜索。国际象棋每步约30种合法着法着法生成模块错了后面全是空中楼阁。建议用10x12的虚拟棋盘或者位棋盘表示位棋盘配合位运算效率极高是引擎性能的基石。第二评估函数从简单到复杂迭代。先只算子力差效果很弱但能跑通。然后加位置表和机动性再逐步加王安全、兵结构等。每个权重改动都要用大量对局验证不要拍脑袋。我一开始给王安全权重设太高引擎变得过分保守有赢棋机会都不敢吃子后来反复调才平衡。第三边界情况是最容易出bug的地方。吃过路兵、王车易位条件、兵的升变、三次重复局面、五十步规则任何一个漏了都会让程序的棋力断崖式下跌。特别是易位牵扯到王与车是否动过、中间格子是否被攻击写起来比想象中烦琐得多。第四用现成引擎做对照。初学者写好基础框架后让程序和自己写的AI对弈拿引擎的着法分析程序的问题。这个过程比自己闷头调试高效得多。5. 从国际象棋看更多博弈游戏的复杂度把国际象棋的复杂度放在整个棋盘游戏家族里看能获得更宏观的认识。不同游戏的状态空间差异极大处于不同复杂度层级也因此对“程序强不强”的定义各不相同。井字棋的合法局面数只有几千完全穷举毫无压力所以井字棋程序可以做到百分之百“逻辑正确”——任何局面下它都能给出必胜、必败或必和的准确结论。国际跳棋有被完全解开的版本在某些规则下它已经被穷举出所有局面程序达到了实际意义上的“绝对正确”。国际象棋呢远未解决。而围棋更夸张合法局面数约 (2\times 10^{170})博弈树复杂度约 (10^{360})比国际象棋还要可怕得多这也是为什么围棋AI一度被认为“人类无法战胜”只会更晚来临但最终同样被深度学习和大规模搜索攻克。这里有一个哲学反转我们说“无法写出逻辑正确的程序”但不完美的近似程序在工程上已经超越了人类最强能力。这有点像人类发明飞机鸟类的飞行并非符合空气动力学的全部最优解但喷气式飞机照样飞得比鸟高、比鸟快。象棋引擎同理——它没有穷尽所有变化却在无数对局实践中证明有限深度的搜索加上优秀评估足以战胜任何人类棋手对“无限变化”的直觉。顺着这个话题再往前想一层你就会碰到“完美博弈”的深层含义。在国际象棋这种完美信息游戏中理论上的“最优策略”确实存在因为游戏有穷、无随机只是我们无法计算出来。而在扑克这种不完美信息游戏中连“最优策略”的定义都要换成纳什均衡——你要考虑对手的隐藏信息和心理博弈逻辑正确变得更加不可能。所以“逻辑正确”这个目标与其说是程序员的追求不如说是数学家手中一个永远够不到的天花板。它定义了我们能走多远却从不告诉我们怎么一步跨过去。6. 写在最后体会与建议我自己在实际接触这个领域时最大的体会是纠结“逻辑正确”很容易让人走火入魔。我也曾经试图给引擎写一个“完美”的评估函数改完一个参数试跑了上千盘对局最终发现完美是个泥潭你以为在接近它实际上只是换了一种方式理解它。后来我想明白了一件事象棋程序的魅力恰恰在于它用极其有限的资源在无边的可能性中找到了足够好的路径这本身就是一种艺术。如果你也对这个话题感兴趣我建议你换个角度不要问“为什么做不到逻辑正确”而是去观察和思考那些近似手段——搜索、评估、剪枝、记忆——它们是如何一步步逼近极限的。亲自动手写一个能下棋的简单程序下一百盘输赢都无所谓那个过程里你对“计算”“近似”“精确”的理解会彻底不一样。最后补一个实用小技巧如果你要快速感受局面搜索的威力可以下载一个开源引擎把搜索深度从5层调高到10层你马上就能看到着法质量的显著跃升。再把评估函数的某个权重比如“中央控制”的权重人为改大或改小对弈几盘你就能亲眼看到这个“逻辑不正确的程序”如何被工程参数牵着走。亲手做过一次你才算真正理解这篇文章想表达的问题。