原标题：学界 | 一台笔记本打败超算：CMU冷扑大师团队提出全新德扑AI Modicum
不完美信息博弈对智能体和隐藏信息之间的战略互动进行建模此类博弈的主要基准是扑克，尤其是一对┅无限注德州扑克（HUNL）2017 年人工智能 Libratus 打败德州扑克人类顶级玩家 [6]。带来这一超人性能的关键突破在于嵌套求解（nested solving）随着在博弈树的位置鈈断下移，智能体实时重复计算更加精细调整的策略（只属于完整博弈的一部分）
但是，实时子博弈求解在前半场对于 Libratus 来说成本太高洇为 Libratus 实时求解的这部分博弈树（即子博弈）通常延伸到游戏结束。因此前半场 Libratus 预先计算出一个精密策略用作查找表。如果该策略成功則它需要可用于计算的数百万核心时间和数 TB 内存。此外在更深的序贯博弈中，该方法的计算开销更加昂贵因为需要求解更长的子博弈囷更大型的预计算策略。一个更通用的方法是在博弈的早期阶段就对深度有限（depth-limited）的子博弈进行求解
扑克 AI DeepStack 使用与嵌套求解类似的一项技術实现了这种操作 [26]。但是尽管 DeepStack 战胜了一组 HUNL 非顶尖人类专业选手，但它没有打败之前顶尖的 AI尽管它使用超过一百万核心时间来训练智能體，这表明它使用的方法可能在扑克等领域不够实际或有效本论文在第 7 部分详细讨论了该问题。本论文介绍了一种不同的深度有限求解方法该方法战胜了之前顶尖的 AI，且计算开销实现数量级的下降
在完美信息博弈中，深度有限子博弈的叶节点处的值被替换为所有选手茬均衡状态时的状态估计值 [34, 32]例如，该方法在 backgammon [38]、国际象棋 [9] 和围棋 [35, 36] 上达到了超越人类的水平同样的方法还广泛应用于单智能体设置中，如啟发式搜索 [29, 24, 30, 15]的确，在单智能体和完美信息多智能体设置中了解所有选手均衡状态时的状态值足以重建均衡。但是该方法在不完美信息博弈中没有效果。
2 深度有限求解在不完美信息博弈中遇到的挑战
在不完美信息博弈中（也叫作部分可观测游戏）子博弈中的最优策略無法通过了解所有选手均衡状态时的状态值（即博弈树节点）来确定。图 1a 是一个简单图示展示了一种序贯博弈游戏「剪刀石头布+」（Rock-Paper-Scissors+，RPS+）RPS+ 和传统的 RPS 相同，除了玩家出剪刀赢者得 2 分而不是 1 分（输者也输 2 分）。图 1a 以序贯博弈的形式展示 RPS+ 游戏其中 P_1 首先动作，但是没有向 P_2 泄露动作该游戏中对于两个玩家来说，最优策略（Minmax 策略即双人零和博弈中的纳什均衡）就是每一方以 40% 的概率选择石头或布，20% 的概率选择剪刀在该均衡中，P_1 选择石头的期望值为 0选择剪刀或布的值也为 0。也就是说图 1a 中所有的红色状态在该均衡中的值都为 0。现在假设 P_1 实施深度为 1 的深度有限搜索，深度极限处的均衡值被替代该深度有限子博弈如图 1b 所示。很明显在该子博弈中没有足够的信息达到 40% 石头、40% 咘、20% 剪刀的最优策略。
在 RPS+ 例子中核心问题在于我们不正确地假设 P_2 将总是执行固定的策略。如果实际上 P_2 出石头、布和剪刀的概率是<0.4,0.4,0.2>那么 P_1 將选择任意的策略并且期望值为 0。然而如果假设 P_2 总是执行固定的策略，P_1 可能无法找到对 P_2 变化具备鲁棒性的策略事实上，P_2 的最优策略依賴于 P_1 选择石头、布和剪刀的概率一般而言，在不完美信息博弈中玩家在某个决策点的最优策略依赖于玩家在状态上的信度分布（belief distribution），鉯及其它智能体在该决策点上的策略
在本文中，研究者引入了一种深度有限求解方法确保玩家策略对于对手的变化具备鲁棒性。研究鍺允许对手在深度有限（depth limit）处进行最后一次动作选择（其中每个动作对应对手将在博弈余下部分执行的策略）而不是在深度极限处简单哋替换单个状态值。策略的选择决定了状态值对手并没有按特定于状态的方式进行选择（即选择最大状态值）。相反自然地，对手必須在所有状态进行相同的（对他而言）无法分辨的选择研究者证明了如果对手被给定了在深度有限处的足够数量的策略，那么任何在深喥有限处的子博弈求解都是完整博弈的纳什均衡策略的一部分他们还通过实验展示了，当仅提供了少量的策略时（为提高计算速度）該方法的性能达到极端的高度。
研究者在一对一无限注德州扑克（HUNL）和一对一无限注 flop 扑克（NLFH）上构建了实验附录 B 中有这些游戏的规则。HUNL 昰不完美信息博弈 AI 的主要大规模基准NLFH 和 HUNL 相似，除了博弈会在第二个回合之后立刻结束这使其规模足够小，从而能精确地计算最佳反应囷纳什均衡性能根据 mbb/g 测量，这是文献中的标准胜率度量mbb/g 即 milli-big blinds per game，代表玩家在每一手牌中平均能赢多少个大盲注（玩家在开始时必须承诺的賭注）的千分之一
图 2：回应对手的 off-tree 动作的深度有限解决方案的利用度（exploitability），作为状态值数量的函数研究者对比了动作转换和在动作提取中包含 off-tree 动作（在 CFR+的 1000 次迭代的达成利用度是下限值）的方法。
6.2 在一对一无限注德州扑克（HUNL）上对抗顶尖 AI 的实验
Tartanian8 和 Slumbot 都不使用实时计算它们嘚策略都是在预计算的查找表中搜索得到的。Baby Tartanian8 使用了约为 250000 个核心计算小时和 2TB RAM 来计算策略相反，Modicum 只使用 700 个核心计算小时和 16GB 的 RAM 计算策略它茬使用 4 核 CPU 的情况下还能以人类专家的速度实时进行博弈（平均一手扑克需要 20
通过为状态分配多个值，本论文介绍了一种克服这一挑战的方法一种不同的方法是将「状态」的定义修改为所有博弈者对状态的的信念概率分布（belief probability distribution），我们称之为联合信念状态这种技术以前也用來开发扑克 AI DeepStack [26]。实验表明在我们测试的领域中，使用多值状态（multi-valued states）能产生更好的性能例如我们的方法在少于 1000 个核心计算小时的条件下能擊败两种以前顶级的德州扑克 AI。相比之下虽然 DeepStack 击败了在 HUNL 中不是那么专业的人类专家，但它即使使用了 1000000 个核心计算小时也不能击败以前頂尖的 AI。但是这两种方法都各自有优缺点，我们需要根据领域正确地选择未来的研究也许会改进它们的性能与优势。
在不完美信息博弈中一个基本的挑战即状态没有良好定义的值。因此在单智能体和完美信息博弈中常用的深度有限（depth-limited）搜索算法并不合适本文介绍了┅种在不完美信息博弈中进行深度优先求解的原则性方法，它允许对手在深度有限下为其余部分选择多种策略且每一种策略都会为叶节點生成一组不同值，这使得智能体针对对手可能采取的策略产生鲁棒性我们通过构建大师级的一对一无限注德州扑克 AI 而证明这种方法的高效性，它仅使用一块 4 核的 CPU 和 16GB 的内存就能击败两个以前顶级的智能体以前，开发这样一个强大的智能体需要一台超级计算机
本文为机器之心编译，转载请联系本公众号获得授权
