【组合博弈】01|胜负的底层逻辑:P/N 态、倒推法与对称模仿

【组合博弈】01|胜负的底层逻辑:P/N 态、倒推法与对称模仿

💡 原文中文,约12600字,阅读约需30分钟。
📝

内容提要

本文介绍组合博弈论中有限、公平、正常规则博弈的P/N态倒推法:从终局逆向标记,P态为后手必胜,N态为先手必胜。据此可推出巴什博弈的必败态为(k+1)的倍数,减法博弈则呈周期规律。文章还讲解对称模仿与策略盗取两大技巧,并用Python求解器验证。

🔎

延伸解读

P/N 态倒推:从终局逆向标记的底层逻辑

文章强调,面对有限、公平、正常规则的组合博弈,不要从开局正向推演分支,而应从终局逆向标记 P/N 态。终局为 P 态;若某状态存在一步走向 P 态,则为 N 态;若所有走法都走向 N 态,则为 P 态。这套三公理把博弈树转化为有向无环图上的染色问题,使胜负判断从“算尽所有路径”变为“盯住 P 态锚点”。

巴什博弈与减法博弈:周期规律与抽屉原理

巴什博弈中,每次取 1 到 k 颗时,P 态恰为 (k+1) 的倍数,先手只需将局面压回该倍数并配对回应。若取法集合受限,模 k+1 失效,但 P/N 序列仍会因有限窗口的重复而进入周期。文章以 S={1,3,4} 为例,展示周期为 7 且 P 态为 n mod 7 ∈ {0,2},说明倒推加抽屉原理可处理陌生规则。

对称模仿与策略盗取:不计算数字的必胜武器

对称模仿依赖棋盘可划分为互不干扰的镜像区域,后手通过镜像回应保持对称,从而迫使对手先无路可走。策略盗取则用反证法证明先手必胜,如 Chomp 中先手可“偷走”后手的必胜回应。但文章指出,策略盗取是非构造性证明,只保证存在必胜步,不直接给出具体走法;且依赖“多走一步不会有害”的单调性前提,遇到 Zugzwang 类局面会失效。

Python 求解器与练习:从理论到可验证的实践

文章提供约 40 行的记忆化 P/N 倒推求解器,只需传入状态转移函数,即可输出小规模游戏的 P 态表与必胜走法。文中用该求解器验证了巴什博弈、减法博弈和 4×5 Chomp,并给出多道练习,涵盖变体巴什、受限取法、2×n Chomp 显式策略及反常规则。这提示读者:遇到规则古怪的小游戏,可先用倒推求解器暴力验证,再尝试寻找规律或对称策略。

❓

Q&A

组合博弈论中的P态和N态分别代表什么?怎么记才不会搞混?

P态(Previous-player winning position)表示后手必胜/必败态:轮到当前玩家走时,只要对手不犯错,当前玩家必输,而上一步把局面推到这里的人必胜。N态(Next-player winning position)表示先手必胜/必胜态:轮到当前玩家走时,只要走对一步就能稳赢。记忆技巧:P = Previous wins(上家赢),N = Next wins(下家也就是现在的我赢)。

巴什博弈(每次取1到k颗,取最后一颗者胜)的必败态有什么规律?

对于单堆共n颗石子、每次可取1到k颗、取走最后一颗者胜的巴什博弈,局面n是P态(必败态)当且仅当 n ≡ 0 (mod k+1)。也就是说,必败态是所有(k+1)的倍数。例如k=3时,P态为0, 4, 8, 12, ...。

如果每次只能拿特定数量的石子(比如只能拿1、3、4颗),怎么判断胜负?

这种游戏称为减法博弈(Subtraction Game),模k+1的公式不再适用。需要从终局开始倒推,给每个剩余石子数标P/N标签。由于每次最多拿4颗,第n项的标签只取决于前4项,而长度为4的布尔窗口最多16种组合,由抽屉原理,P/N序列最终必然进入循环。例如取法集合{1,3,4}时,周期为7,P态为 n mod 7 ∈ {0, 2}。

对称模仿策略(Tweedledum-Tweedledee)怎么用?能举两个例子吗?

对称模仿的核心是:把棋盘划分成两块完全对称、互不干扰的区域,让对方先动,之后对方在一边走什么,你就在另一边走完全对称的一步,这样你永远不会先无路可走。例如圆桌放硬币:先手把第一枚放在圆心,之后对方在(x,y)放,你就在(-x,-y)放;两堆相同的石子(n,n):后手应对,对方从一堆拿t颗,你就从另一堆拿t颗。注意此策略依赖正常规则(最后一步者胜),若改为反常规则(最后一步者输)则可能失效。

策略盗取(Strategy Stealing)如何证明Chomp游戏先手必胜?它有什么局限?

策略盗取用反证法证明:假设先手先咬掉最右上角一格X。如果剩下局面已是P态,先手直接赢;如果不是P态,后手存在必胜回应M,但咬M会顺带清除X,所以先手可以直接第一步咬M,得到与“先手咬X、后手咬M”相同的结果,从而偷走后手的必胜策略。因此只要棋盘大于1×1,Chomp永远先手必胜。局限在于它是非构造性证明,只告诉你先手必胜,却不告诉你具体第一步该咬哪一格;对于一般矩形Chomp,至今没有闭合的必胜步公式。

有没有通用的方法或代码来求解任意小规模组合博弈的P/N态?

可以写一个记忆化的P/N倒推求解器,核心是一个递归函数:传入当前状态和“状态→后继状态列表”的函数,若存在一步走向P态则当前为N态,否则为P态。文章给出了约10行的Python实现(solve_pn函数),能快速输出小规模游戏的P态表和必胜走法,例如验证巴什博弈、减法博弈和4×5 Chomp。

🏷️

标签

➡️

继续阅读