CMU冷扑大师团队推出新德扑AI，笔记本竟打败超算

近日，有在读博士 Noam Brown，来自 CMU 冷扑大师团队，还有 Tuomas Sandholm 教授，以及研究助理 Brandon Amos，他们提交了一个新研究，这个新研究是关于名为德州扑克人工智能 Modicum 的研究。该人工智能仅凭借一台笔记本电脑的算力，就打败了业内顶尖的 Baby Tartanian8，它是 2016 计算机扑克冠军，还打败了 Slumbot，它是 2018 年计算机扑克冠军 。在此之前，名为《Safe and Nested Subgame Solving for Imperfect-Information Games》的冷扑大师论文，是NIPS 2017的最佳论文，介绍了不完美信息博弈对智能体和隐藏信息间战略互动的建模，此类博弈主要基准是扑克，特别是一对一无限注德州扑克，2017年人工智能Libratus打败德州扑克人类顶级玩家 。句号。带来这般超人性能的关键突破之处在于嵌套求解，也就是 nested solving，随着于博弈树里的位置持续下移，智能体实时重复进行计算，去更为精细地调准策略，而此策略只是完整博弈的一部分 。

但，实时子博弈求解于前半场对 Libratus 来讲成本过高，因 Libratus 实时求解的这一部分博弈树，也就是子博弈，通常会延伸至游戏结束 。所以，前半场 Libratus 预先算出一个精密策略用作查找表。倘若该策略成功，那它就需要可用于计算的数百万核心时间以及数 TB 内存。另外，在更深的序贯博弈里，该方法的计算开销更为昂贵，因为要求解更长的子博弈以及更大型的预计算策略。一种更为通用的办法是，处在博弈的前期时段，针对深度受限的子博弈展开求解 。

DeepStack这种操作是通过使用一项类似于嵌套求解的技术得以实现的，这是扑克AI的一种 。然而，DeepStack虽说战胜了一组HUNL非顶尖人类专业选手，可它却并未胜过之前顶尖的AI 。尽管DeepStack在训练智能体时使用了超过一百万核心时间，可这表明它所采用的方法在扑克这类领域或许不够实际或者有效 。本论文在第7部分对该问题展开了详细探讨 。本论文讲述了一种别样的深度有限求解办法，此办法击败了先前顶尖的人工智能，并且计算开销达成了数量级的降低。

在完美信息博弈里头，深度有限子博弈的叶节点处的值，被替换做了所有选手在均衡状态时的状态估计值，举例来说，该方法在西洋双陆棋、国际象棋以及围棋上，达到了超越人类的水平德信竞技，同样的方法还广泛应用于单智能体设置当中，像启发式搜索。

29, 24, 30, 15

确实，于单智能体以及完美信息多智能体的设定情形下，知晓所有选手处于均衡状态之际的状态值这样的情况，是足以去重建均衡的。然而，此方法在存在不完美信息的博弈这个场景里并不发挥效力。

博弈中面临的挑战，是深度有限求解于不完美信息环节所遭遇的，在不完美信息博弈里，也就是部分可观测的游戏范畴内，子博弈里边的最优策略，不能经由知晓所有选手处于均衡状态之际的状态值，就是博弈树的节点，来加以确定。图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出石头、布以及剪刀的概率是这样的情况，那么P_1将会选出任意的一种策略，其结果是期望值为0。可是呢，如果假定P_2总是执行固有的策略，那么P_1有可能没办法找到对于P_2变化有着鲁棒性的策略。实际上，P_2的最优策略是依靠着P_1选择石头、布和剪刀的概率的。通常来讲，处于不完美信息博弈里，玩家于某决策点的最优策略靠的是玩家在状态方面的信度分布，还有其他智能体在该决策点的策略。

在本文里头，研究者引进了一种深度有限求解办法，进而保证玩家策略针对对手的变化拥有鲁棒性。研究者准许对手于深度有限（depth limit）的地方开展最后一回动作挑选（这里面每个动作对应着对手会于博弈剩余部分施行的策略），并非在深度极限的地方单纯地替换单个状态值。策略的挑选确定了状态值。对手并非依照特定于状态的方式来挑选（也就是挑选最大状态值）。相反地，自然而然地，对手必须于所有状态开展相同的（对他来说）无法辨别的挑选。有种情况在深度有限处，研究者证实了，要是对手被给到足够数量的策略，那么处在深度有限处的任何子博弈求解，都是完整博弈的纳什均衡策略里的一部分。他们还借助实验表明了，当只为提高计算速度而仅提供少量策略时，该方法的性能抵达了极端的高度 。

进行实验的研究者，在一对一无限注德州扑克也就是 HUNL 上构建了实验，同时还在一对一无限注 flop 扑克即 NLFH 上构建了实验，附录 B 当中有这些游戏的规则，HUNL 是不完美信息博弈 AI 的主要大规模基准，NLFH 和 HUNL 相似，只是博弈会在第二个回合之后马上就结束，借着这个使得其规模足够小，进而能够精确地计算最佳反应和纳什均衡，性能是依据 mbb/g 来测量的，这是文献里的标准胜率度量。mbb/g也就是milli – big blinds per game，它表示玩家于每一手牌里，平均能够赢取的大盲注（玩家在起始时必须承诺下的赌注）的一千分之一 。

图2，回应对手的off – tree动作的深度有限解决方案的利用度，此利用度作为状态值数量的函数，研究者作了对比，对比的是动作转换的方法，以及在动作提取中包含off – tree动作的方法，在动作提取中包含off – tree动作的方法指在CFR +的1000次迭代的达成利用度是下限值的那种方法 。

我们针对6.2在一对一无限注德州扑克（HUNL）上，与顶尖AI展开对抗的实验之中，主要采用了深度有限求解这种方法，而且只是借助普通笔记本电脑内存有的计算资源，从而生成了具备大师级水平的HUNL扑克AI，即Modicum啊。我们对Modicum、Baby Tartanian8以及Slumbot进行了测试，Baby Tartanian8是2016年度计算机扑克竞赛的获胜者，Slumbot是2018年度计算机扑克竞赛的获胜者，Baby Tartanian8不使用实时计算，其 策略是在预计算的查找表中搜索得到的，Slumbot也不使用实时计算，它的策略同样是在预计算的查找表中搜索得到的。Baby Tartanian8 计算策略时，使用了大约 250000 个核心计算小时，以及 2TB RAM。相反，Modicum 计算策略仅用 700 个核心计算小时和 16GB 的 RAM，并且它在使用 4 核 CPU 的情形下还能够以人类专家的速度实时进行博弈，平均一手扑克需要 20 秒 。

有这样一种情况，7 与先前研究工作相比，先前研究工作存在通过为状态分配多个值的做法，而在这种情况下，本论文介绍了一种克服这一挑战的方法。有一种不同的方法呢，是把「状态」的定义修改为所有博弈者对状态的信念概率分布，也就是 belief probability distribution，我们把这种情况称之为联合信念状态，并且这种技术以前也被用来开发扑克 AI DeepStack 。还有实验表明，在我们进行测试的领域当中，使用多值状态，也就是 multi-valued states，能够产生更好的性能。比如说，咱们的途径在少于一千个核心计算小时的状况下，能够战胜两种先前顶级的德州扑克 AI。与之相较，尽管 DeepStack 战胜了在 HUNL 里没那么专业的人类行家，不过它即便动用了一百万 个核心计算小时，也无法打败先前顶尖的 AI。然而，这两种办法都各有优劣之处，我们得依据领域正确地挑选，未来的研究或许会提升它们的性能与优势。