9.2 求解工具与模拟

9.2 求解工具与模拟

本节摘要：确切算法够不着的地方，工程靠两样东西活着：逼近算法与仿真锦标赛。本节把工具按"收敛保证"分层排队——虚拟对弈、反事实遗憾最小化、多智能体强化学习，各自标注适用域与失效方式；重复囚徒困境锦标赛示范"策略稳健性"怎么测；Kuhn 扑克的最小化演算展示现代扑克 AI 的数学内核。读完本节，你可以为手头的博弈问题选出正确的工具档位。

一、工具栈分层：按收敛保证排队

把常用工具按承诺强度排成四层。第一层是精确层：线性规划解零和、支撑枚举解小矩阵，输出的是带证明的均衡。第二层是有保证的近似层：虚拟对弈在两人零和与部分结构上收敛（平均策略逼近均衡），实现简单，是默认起点；遗憾匹配及其升级版反事实遗憾最小化（CFR）在零和不完美信息博弈上有收敛保证，是扑克 AI 的引擎。第三层是启发式层：多智能体强化学习在自对弈中寻找近似均衡，没有一般收敛保证，但规模上限最高——围棋与星际级别的复杂度都由它攻下。第四层是实证层：给定策略的锦标赛评估，不找均衡，只回答"这套打法在对手池里成绩如何"。选层的规则与 9.1 的地形图对应：平原上住着第一层，峭壁前先试第二层，规模极限挑战交给第三层，落地评估永远要第四层。

图 9-2：求解工具栈的四层结构

二、锦标赛方法论：以牙还牙为什么是冠军

阿克塞尔罗德 1980 年代的重复囚徒困境锦标赛是模拟方法论的教科书。他公开征集策略程序，让它们在两两对决的循环赛里积分：双方全合作各得 3 分一局，互相背叛各得 1 分，背叛合作者得 5 分或 0 分。两届比赛的冠军都是"以牙还牙"——区区四行代码：第一步合作，之后照抄对方上一期的动作。胜出的原因可拆成四个性质：善良（从不先背叛）、可激怒（立即惩罚背叛）、宽容（对方回头即原谅）、清晰（规则简单到对手几次交互就能识别）。锦标赛同时给出反直觉的负结果：更"聪明"的复杂策略常因无法被对手识别而互相误伤——可读性是策略资产。

锦标赛方法的三条工程纪律值得照抄。对手池决定结论：以牙还牙在"全是善良策略"的池里冠军，混入故意利用善良者的策略后名次下滑——宣布结论时必须声明对手池构成。指标要区分"绝对分"与"相对差"：锦标赛奖励的是稳定吃 3 分的能力，不是偶尔爆冷的 5 分。噪音敏感性必测：给交互加上小概率的误动作，以牙还牙会陷入循环互咬（6.1 的老结论），宽容变体才扛得住——稳健性排名在无噪音与有噪音下可以整体翻转。

三、代码实践：遗憾匹配跑一个剪刀石头布

import random

# 遗憾匹配自对弈：两人零和的收敛示范
REGRET_ACTIONS = 3                     # 石 剪 布
payoff = [[0, -1, 1], [1, 0, -1], [-1, 1, 0]]   # 行动者视角

def regret_matching(regrets):
    positive = [max(r, 0) for r in regrets]
    s = sum(positive)
    return [p / s for p in positive] if s else [1 / REGRET_ACTIONS] * 3

def train(iters=20000):
    r1 = [0.0] * 3; r2 = [0.0] * 3
    sum1 = [0.0] * 3; sum2 = [0.0] * 3
    for _ in range(iters):
        s1 = regret_matching(r1); s2 = regret_matching(r2)
        a1 = random.choices(range(3), s1)[0]
        a2 = random.choices(range(3), s2)[0]
        for a in range(3):             # 反事实遗憾：当初出别的会怎样
            r1[a] += payoff[a][a2] - payoff[a1][a2]
            r2[a] += payoff[a][a1] - payoff[a2][a1]
        for a in range(3):             # 累计平均策略
            sum1[a] += s1[a]; sum2[a] += s2[a]
    return [round(x / iters, 3) for x in sum1], [round(x / iters, 3) for x in sum2]

print(train())   # 平均策略逼近 各三分之一
​

遗憾匹配的思想一句话：每期按"当初换一招能多赚多少"（遗憾）的比例加大那一招的概率——遗憾为零就不加码。它自对弈剪刀石头布时，平均策略收敛到各三分之一；换成更大的牌类博弈，把"遗憾"沿博弈树逐节点反事实展开，就是 CFR，超级计算机扑克 AI 的全部秘诀建立在这一点上。Kuhn 扑克是可手算的最小试验床：两张牌（大牌小牌）、下注跟注弃牌，把遗憾匹配的更新在十来个信息集上手工迭代几轮，就能看到策略逼近理论均衡——大牌下注为主、小牌偶尔诈唬，诈唬频率精确到可验证。

四、从工具到结论：校准你的口径

工具层的最后一步是给结论标口径。用精确层算出的均衡可以写成"均衡是 X"；用近似层得到的要写成"平均策略在误差 ε 内逼近 X"；用启发式层跑出的只能说"在本次自对弈设置下观察到 X"；锦标赛结果必须附对手池构成与噪音设置。口径标注不是学术洁癖，是决策安全阀——把自对弈的成绩当成均衡性质，是把"我练过的对手"误当成"全部对手"，实战翻车的事故报告里最常见的正是这一条。

五、Kuhn 扑克：在纸上跑一次 CFR

Kuhn 扑克是可手工演算的最小不完美信息博弈：三张牌 J、Q、K，各发一张，大牌赢；玩家轮流可选下注一筹码或过牌，简单到全树只有十二个决策点，却包含诈唬所需的一切零件。用遗憾匹配手迭代几轮，均衡的轮廓就会浮现：持 K（最大牌）下注，持 J（最小牌）以下注的方式偶尔诈唬，持 Q 时混合出牌让对方捉摸不透——诈唬频率的均衡值精确到可验算，约三分之一的 J 选择下注。这个最小演算的教益在结构：诈唬不是心理戏，是让对手在中等牌上无差异化的数学必需——不诈唬，对手见注就弃，你的价值牌也榨不出利润；多诈唬，对手见注就跟，频率被无差异条件精确锁定。CFR 在德扑级别博弈上的胜利，无非是把这条无差异逻辑沿上千亿个信息集并行执行。学习建议：把上面剪刀石头布代码的收益表换成 Kuhn 扑克的树展开，跑两万次迭代看策略收敛——一天之内你就能亲手复现扑克 AI 的内核原理。

本节要点回顾

• 要点一：工具按承诺分四层——精确、有保证近似、启发式、实证，选层跟着 9.1 的复杂度地形走。
• 要点二：以牙还牙的冠军条件是善良、可激怒、宽容、清晰；对手池与噪音设置决定一切排名的可信度。
• 要点三：遗憾匹配按反事实遗憾调概率，平均策略在零和场景有收敛保证，CFR 是它沿博弈树的展开。
• 要点四：结论必须标注口径——均衡、近似、观察、锦标赛成绩是四句不同强度的话。