CMU团队提出全新德扑AI Modicum，笔记本竟能打败超算

选自arXiv

机器之心编译

参与：路、晓坤

近日，CMU冷扑大师团队在读博士Noam Brown提交了一个新研究，Tuomas Sandholm教授、研究助理Brandon Amos，德州扑克人工智能Modicum，它仅用一台笔记本电脑的算力，就打败了业内顶尖的2016计算机扑克冠军Baby Tartanian8，还打败了2018年计算机扑克冠军Slumbot 。在此之前，名为《Safe and Nested Subgame Solving for Imperfect-Information Games》的冷扑大师的论文，是NIPS 2017的最佳论文。

1 引言

对智能体与隐藏信息之间战略互动予以建模的是不完美信息博弈，此类博弈的主要基准是扑克，特别是一对一无限注德州扑克，也就是 HUNL，在 2017 年人工智能 Libratus 将德州扑克人类顶级玩家打败，带来这一超人性能的关键突破是嵌套求解，随着在博弈树位置持续下移，智能体实时重复计算更为精细调整的策略，而该策略仅属于完整博弈的一部分 。

然而，实时子博弈求解于前半场而言，对 Libratus 来讲成本过高，缘由在于 Libratus 实时求解的那部分博弈树，也就是子博弈，一般会延伸至游戏结束。所以，前半场 Libratus 预先算出一个精密策略用作查找表。要是该策略成功，那么它需要可供计算的数百万核心时间以及数 TB 内存。另外，在更深的序贯博弈里，此方法的计算开销更为昂贵，这是由于要求解更长的子博弈以及更大型的预计算策略。相比于其他方法，有一种方法更为通用，这种方法是，在博弈的早期阶段，针对深度受到限制的子博弈，去进行求解操作。

使用与嵌套求解类似的一项技术，扑克AI DeepStack实现了这种操作 ，但是，一组HUNL非顶尖人类专业选手之中，DeepStack没有打败之前顶尖的AI，虽然它使用超过一百万核心时间来训练智能体 ，尽管如此但DeepStack战胜其中一部分，这表明它使用的方法可能在扑克等领域不够实际或有效 ，本论文在第7部分详细讨论了该问题 。本论文讲述了一种别样的深度有限之求解方式，这种方式击败了此前位于顶尖水平的AI，并且致使计算开销达成了数量级的降低。

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

29, 24, 30, 15

确实，于单智能体以及完美信息多智能体的设置之中，知晓所有选手处于均衡状态之际的状态值，便足够用以重建均衡，然而，此种方法在不完美信息所涉及的博弈里面并无效果。

2 深度有限求解在不完美信息博弈中遇到的挑战

在被称作部分可观测游戏的不完美信息博弈里，子博弈中的最优策略不能够经由知晓所有选手均衡状态那般的状态值也就是博弈树节点来加以确定。有一个简单示意图是图1a，它呈现出一种名叫剪刀石头布+的序贯博弈游戏。剪刀石头布+跟传统的剪刀石头布一样，只是玩家出剪刀赢者可获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选择石头、布和剪刀的概率的。通常来讲，于不完美信息博弈里边，玩家在某一决策点的最优策略，是依靠玩家在状态方面的信度分布，以及其他智能体在该决策点处的策略的。

在本文当中，研究者引入了一种深度有限求解的方法，以此来确保玩家策略针对对手的变化能够具备鲁棒性。研究者允许对手在深度有限之处开展最后一次动作选择，这里面每个动作对应着对手会在博弈余下部分执行的策略，并非在深度极限那里简单地替换单个状态值。策略的选择决定了状态值，对手没有按照特定于状态的方式去进行选择，也就是没有选择最大状态值。相反，自然而然地，对手必须在所有状态进行相同的，对他而言无法分辨的选择。对于研究者而言，他们证明了这样一种情况，即要是对手被给定了深度有限处的足够数量的策略，那么在深度有限处的任何子博弈求解，都是完整博弈的纳什均衡策略要涉猎的部分。他们还借助实验表明，当仅仅提供了少量的策略时（目的是提高计算速度），该方法的性能抵达了极端的高度。

6 实验

有研究者，针对一对一无限注德州扑克（HUNL），以及一对一无限注flop扑克（NLFH），构建了实验。附录B中，存在这些游戏的规则。HUNL，是不完美信息博弈AI的主要大规模基准。NLFH，和HUNL相似，只是博弈会在第二个回合之后，立刻结束，这使得其规模充分得小，进而能够精确地计算最佳反应以及纳什均衡。性能，根据mbb/g测量，这是文献里的标准胜率度量。将“mbb/g”，也就是表达为“milli – big blinds per game”，其所代表的含义是，玩家在每一手牌当中，平均能够赢取的大盲注数量（这里的大盲注是玩家在开始的时候必须要承诺加以投入的赌注）的千分之一 。

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

6.2开展的，在一对一无限注德州扑克上的，对抗顶尖AI的，实验。

我们主要的实验运用了深度有限求解这一方法生成大师级HUNL扑克AI：Modicum，只用了普通笔记本电脑上的计算资源。我们对Modicum与Baby Tartanian8以及Slumbot进行了测试，Baby Tartanian8可是2016年度计算机扑克竞赛的获胜者，Slumbot则是2018年度计算机扑克竞赛的获胜者。婴儿塔塔尼亚8号，和睡眠机器人，都并非运用的实时计算机制，它们所采用的策略，皆是于预先计算生成的查找表里面，通过搜索行为而获取到的数据。其中，婴儿塔塔尼亚8号，为了计算该策略，动用了大约达250,000个核心计算小时这一数量数值，以及2TB的计算机随机存取存储器的存储空间容量。与之相反，Modicum采用的计算策略是仅使用700 个核心计算小时以及16GB的RAM ，在运用4核CPU的情形下，它能够以人类专家的速度实时开展博弈，平均每一手扑克所需时间为20秒 。

7 对比先前研究工作

本论文介绍了一种克服这一挑战的方法，此方法是通过为状态分配多个值。一种不同的方法是把「状态」的定义修改为所有博弈者对状态的信念概率分布，也就是我们所说的联合信念状态，这种技术以前被用于开发扑克 AI DeepStack 。实验显示，在我们进行测试的领域里，运用多值状态能产生更出色的性能。像是我们所采用的方法，在核心计算小时数少于1000个的状况下，能够战胜两种先前处于顶级水平的德州扑克AI 。相比较而言，尽管DeepStack击败了在HUNL中并非那么专业的人类专家，然而即便它使用了1000000个核心计算小时，却也无法击败先前顶尖的AI 。不过，这两种方法都分别存在着优点与缺点，我们需要依据领域正确地去进行选择，未来的研究或许会对它们的性能与优势加以改进。