AI攻陷多人德扑再登Science,训练成本150美元,每小时赢1000刀

2019 年 7 月 12 日 机器之心

机器之心报道

机器之心编辑部

在无限制德州扑克六人对决的比赛中,德扑 AI Pluribus 成功战胜了五名专家级人类玩家。Pluribus 由 Facebook 与卡耐基梅隆大学(CMU)共同开发,实现了前辈 Libratus(冷扑大师)未能完成的任务,该研究已经登上了最新一期《科学》杂志。

六人无限制玩法是德州扑克最受欢迎的游戏方式,Facebook 与 CMU 的成果是第一个在拥有两个(或以上)人类玩家的比赛中击败人类专业选手的 AI。


2017 年 1 月,由 CMU 学者 Noam Brown、Tuomas Sandholm 开发的人工智能程序 Libratus 在宾夕法尼亚州匹兹堡的 Rivers 赌场持续 20 天的 1 对 1 无限制德扑比赛中成功战胜了 4 名全球顶级职业玩家。这也成为了继围棋之后,又一个高难度游戏被 AI 攻陷的里程碑事件。2017 年底,Libratus 的论文也被《科学》杂志收录


「冷扑大师」使用大量算力和博弈论等方法来攻克信息不完整的纸牌游戏。该研究的另一篇论文《Safe and Nested Subgame Solving for Imperfect-Information Games》也在当年成为了人工智能顶会 NIPS 2017 的最佳论文


卡耐基梅隆大学计算机科学教授 Tuomas Sandholm(左)与他的门生,现任 Facebook 科学家 Noam Brown。


从 1 对 1 到玩转 6 人对决,人工智能经历了怎样的进步?「虽然从二到六看起来是一个渐进的过程,但这实际上是一个巨大的挑战,」研究游戏与人工智能的纽约大学助理教授 Julian Togelius 表示。「多人游戏方面的研究,此前在所有游戏中都未有出现。」


在「冷扑大师」的基础之上,Noam Brown 与 Tuomas Sandholm 提出的新算法 Pluribus 需要的算力更小。在为期 12 天,超过 10000 手牌的比赛中,Pluribus 击败了 15 名人类顶级玩家。「很多 AI 研究者此前都认为实现这样的目标是不可能的,」Noam Brown 表示。


几十年来,扑克一直是人工智能领域一个困难而又重要的挑战。原因在于,扑克中含有隐藏信息,也就是说,你无法知道对方的牌。要想在扑克中获胜,你需要 bluff(吓唬)或者使用其他策略,这在棋类比赛中一般是不需要的。这一点使得在扑克中应用人工智能变得非常困难。


现在的人工智能已经学会了 bluff,而且还可以看穿人类选手的 bluff。不过在 Noam Brown 看来,这些技巧也是由数学过程决定的策略。


据介绍,Facebook 和卡内基梅隆大学设计的比赛分为两种模式:1 个 AI+5 个人类玩家和 5 个 AI+1 个人类玩家,Pluribus 在这两种模式中都取得了胜利。如果一个筹码值 1 美元,Pluribus 平均每局能赢 5 美元,与 5 个人类玩家对战一小时就能赢 1000 美元。职业扑克玩家认为这些结果是决定性的胜利优势。


这是 AI 首次在玩家人数(或队伍)大于 2 的大型基准游戏中击败顶级职业玩家。以下是关于 Pluribus 的细节。


论文:Superhuman AI for multiplayer poker


论文链接:https://science.sciencemag.org/content/early/2019/07/10/science.aay2400


Pluribus 以 Libratus 和其他一些算法、代码为基础进行了几项改进。Libratus 曾于 2017 年在双人无限注德扑中击败人类顶级选手(参见:《学界 | Science 论文揭秘:Libratus 如何在双人无限注德扑中击败人类顶级选手》)。这些算法和代码都是由 Tuomas Sandholm 带领的卡内基梅隆大学研究实验室开发的。


值得一提的是,Pluribus 整合了一种新的在线搜索算法,可以通过搜索前面的几步而不是只搜索到游戏结束来有效地评估其决策。此外,Pluribus 还利用了速度更快的新型 self-play 非完美信息游戏算法。综上所述,这些改进使得使用极少的处理能力和内存来训练 Pluribus 成为可能。训练所用的云计算资源总价值还不到 150 美元。这种高效与最近其他人工智能里程碑项目形成了鲜明对比,后者的训练往往要花费数百万美元的计算资源。


该视频显示了 Pluribus 与职业人类扑克玩家对战的过程(牌面朝上是为了更容易看到 Pluribus 的策略)。


这些创新的意义远不止在扑克游戏中,因为双玩家零和交互(一输一赢)在娱乐游戏中非常常见,但在实际生活中却非常罕见。现实世界的——对有害内容采取行动、应对网络安全挑战以及管理在线拍卖或导航流量——通常涉及多个参与者和/或隐藏信息。多玩家交互对过去的 AI 技术提出了严峻的理论和实践挑战。Facebook 的结果表明,一个精心构造的人工智能算法可以在两人以上的零和游戏中超越人类的表现


在 6 人扑克中获胜


相比于过去典型的游戏中,6 人扑克有两个主要挑战。


不只是简单的双人零和游戏


过去所有游戏中的突破限制于 2 人或者 2 队的零和竞赛(例如象棋、西洋棋、星际争霸 2 或者 Dota2)。在这些比赛中,AI 之所以成功,是因为它们试图评估使用 Nash 均衡策略。在双人和双队的零和游戏中,无论对手做什么,作出精确的纳什均衡就可能无法输掉比赛。(例如,石头剪刀布的纳什均衡策略是以相同的概率随机选择石头、布或剪刀。)


尽管在任何有限制游戏中都存在纳什均衡,但通常在具有三个或更多玩家的游戏中,难以有效地计算纳什均衡。(对于两人一般和游戏也是如此。)此外,在两个以上玩家的游戏中,即使作出精确的纳什均衡策略,也有可能输掉比赛。例如在游戏 Lemonade Stand game 中,每个玩家同时在一个圆环上选择一个点,并且想尽可能远离任何其他玩家。纳什均衡是所有参与者沿着环间隔相等的距离,但是有很多方法可以实现。如果每个玩家独立计算其中一个平衡点,则联合策略不太可能导致所有玩家沿着该环间隔开同等距离。如下图所示:



除了双人零和游戏,纳什均衡的缺点引发研究人员思考:这种游戏的正确目标应该是什么?


在六人扑克中,研究者认为其目标不应该是特定的游戏理论解决概念,而是创建一个长期都能凭经验击败人类对手的 AI,包括精英人类专业人士。(对于 AI 机器人来说,这通常被认为是「超人」的表现。)


研究者表示,他们用来构建 Pluribus 的算法并不能保证在双人零和游戏之外收敛到纳什均衡。尽管如此,它们观察到 Pluribus 在六人扑克中的策略始终能击败职业玩家,因此这些算法,能够在双人零和游戏之外的更广泛的场景中,产生超人类的策略。


更复杂环境中的隐藏信息


没有其他游戏像扑克一样有这么大隐藏信息的挑战,每个玩家都拥有其他玩家没有的信息(自己的牌面)。一个成功的扑克 AI 必须推理这个隐藏的信息,并慎重平衡自己策略(以保持不可预测),同时采取良好的行动。


例如,bluff 偶尔会有效,但总是 bluff 就容易被抓,从而导致损失大量资金。因此,有必要仔细平衡 bluff 概率和强牌下注的概率。换句话说,不完美信息游戏中动作的值取决于其被选择的概率以及选择其他动作的概率。


相反,在完美信息游戏中,玩家不必担心平衡动作的概率。国际象棋中的好动作,无论选择的概率如何都是好的。


像先前 Libratus 这样的扑克 AI,在两个玩家无限制德州扑克游戏这样的游戏中,通过基于 Counterfactual Regret Minimization(CFR)理论上合理的自我游戏算法与精心构造的搜索程序相结合,解决游戏中的隐藏信息问题。


然而,在扑克中添加额外的玩家会以指数方式增加游戏的复杂性。即使计算量高达 10,000 倍,那些以前的技术无法扩展到六人扑克。


Pluribus 使用的新技术可以比以前的任何东西都更好地应对这一挑战。


理解 Pluribus 的蓝图策略


Pluribus 的核心策略是通过自我博弈的方式学习。在这一过程中,AI 和自己进行对战,不使用任何人类游戏数据作为输入。AI 首先随机地选择玩法,接着,随着决定每一步的行动后,逐渐提升性能,并对这些行动拟合概率分布。最终,AI 的表现比之前的策略版本会更好。Pluribus 中的自我博弈策略是一种改进版本的蒙特卡洛 CFR(MCCFR)。


每一次迭代中,MCCFR 指定其中一方为「traverser」对象,在迭代中更新这一方的当前策略。在迭代开始时,基于所有玩家的当前策略(最开始是完全随机的),MCCFR 模拟出一幅扑克。当模拟完成时,算法回顾「traverser」对象的每个策略,并计算如果选择其他的行动,它的胜率多大程度上能够提升或下降。之后,AI 再评价根据这一决策实施之后,接下来的每个假设决策的优势,以此类推。


该图显示蒙特卡罗 Counterfactual Regret Minimization 算法如何通过评估真实和假设的动作来更新遍历器的策略。Pluribus 中的遍历器以深度优先的方式进行遍历,以达到优化的目的。


探究其他假设的结果是可能的,这是因为 AI 是自我对弈的。如果 AI 想要了解其他选择之后会发生什么,它只需要问自己如何去回应这些行为。


「traverser」对象实际做了什么选择和可能做什么选择的差异被加入到反事实后悔(counterfactural regret)行为中。在迭代结束的时候,「traverser」对象的策略得到更新。因此,有着更高反事实后悔概率的选择被选中。保持德州扑克这样没有限制的游戏中每一个行动中的策略需要的字节数超过了整个宇宙的原子数。为了减少游戏的复杂度,研究人员要求 AI 忽略一些行动,并使用一种抽象方法将类似的决策点聚合在一起。在抽象之后,聚合的决策点被认为是独一无二的。


Pluribus 的自我博弈结果被称为蓝图策略。在实际游戏中,Pluribus 使用搜索算法提升这一蓝图策略。但是 Pluribus 不会根据从对手身上观察到的倾向调整其策略。


这幅图显示了 Pluribus 的蓝图策略是如何在训练过程中逐渐改进的。其性能通过训练的最终快照来评估。研究者在这些比较中没有使用搜索,他们基于与人类专业玩家的讨论对普通人类玩家和顶级人类玩家的表现进行评估。该图还显示出了 Pluribus 何时停止 limping,这是高级人类玩家通常会去避免的一种打法。



研究人员训练蓝图策略用了 8 天,使用了一个 64 核的服务器,需要的内存数量小于 512G。他们没有使用 GPU。在典型的云计算中,这只需要 150 美元。和其他 AI 研究相比,包括其他自我对弈的 AI,这种消耗很小。由于算法上的提升,研究人员可以在低成本的计算环境实现极大的性能提升。


更高效的搜索策略


由于无限制德州扑克的规模与复杂性,蓝图策略必须是粗粒度的。在实际过程中,Pluribus 通过实时搜索改进蓝图策略,以针对特定情况确定更好、更细粒度的策略。


AI bot 经常在很多完美信息博弈中使用实时搜索,包括西洋双陆棋(two-ply search)、国际象棋(alpha-beta pruning search)、围棋(Monte Carlo tree search)。例如,当模型在决定下一步该走哪时,国际象棋 AI 通常会考虑以后的一些移动步骤,直到算法的前瞻到达叶节点或深度的上限。


然而,这些搜索方法并不适合不完美信息博弈,因为它们并不考虑对手转移到叶节点之外策略的能力。这个弱点令搜索算法产生了脆弱的、不平衡的策略,从而使对手快速发现这个错误。AI bot 在以前也就不能将博弈扩展到 6 个参与者。


相反,Pluribus 使用一种新方法,其中搜索器明确地考虑了不完美信息博弈的实际情况,即任何参与者都可以转移到子博弈外的叶节点策略上。具体而言,研究者并不假设所有参与者都需要根据叶节点之外的单个固定策略进行博弈,这会导致叶节点只有单个固定值。在搜索已经到叶节点时,研究者假设每一个参与者会从四个不同的策略中选择,进行剩余的博弈。


研究者在 Pluribus 中使用的四个延续策略分别是预计算的蓝图策略;在蓝图策略的基础上进行修改,以令策略偏置到弃牌;修改蓝图策略以令其偏置到叫牌;修改蓝图策略以令其偏置到加注。


这种技术可以令搜索器找都一种更均衡的策略,从而在整体性能表现得更好。因为选择不平衡的策略会使对手转向其它延续策略,从而产生惩罚。例如玩石头剪刀布,我只出石头,那么对手肯定能学习到只出布的策略。


正如研究者所指出的,搜索不完全信息博弈的另一个挑战是,参与者针对特定情况的最佳策略取决于对手对其玩法的看法。例如打德州扑克,如果一个参与者永远不会 bluff,那么它的对手总会知道应该在加大注的情况下弃牌。


为了应对这种情况,Pluribus 根据自身策略,在每一手时追踪当前状况的出现概率。不管它实际上在哪一手,Pluribus 首先都会预测每一手时将要采取的行动——从而小心翼翼地在所有手时平衡自身策略,令人类玩家无法预测其下一步行动。一旦计算这一涵盖所有手的平衡策略,Pluribus 随后就会为它实际所在的手执行一个操作。


比赛时,Pluribus 在两个 CPU 上运行。相比而言,在 2016 年和李世石的围棋比赛中,AlphaGo 使用了 1920 块 CPU 和 280 块 GPU。同时,Pluribus 使用了不多于 128GB 的内存。在对每一个子分支进行搜索的时候,根据现场的情况,它所用的时间介于 1 秒和 33 秒之间。Pluribus 的游戏时间比人类专业玩家快两倍:在六人游戏场景,和自身对弈的时候,它平均每手只需要 20 秒。


Pluribus 与人类玩家的对抗效果如何?


研究者令 Pluribus 与一组人类顶级扑克玩家对抗,从而评估它的实战效果。这些玩家包括「耶稣」Chris Ferguson(2000 年世界扑克系列赛主赛事冠军)、Greg Merson(2012 年世界扑克系列赛主赛事冠军)和 Darren Elias(四届世界扑克巡回赛冠军)。人类玩家的完整名单如下:Jimmy Chou、Seth Davies、Michael Gagliano、Anthony Gregg、Dong Kim、Jason Les、Linus Loeliger、Daniel McAulay、Nick Petrangelo、Sean Ruane、Trevor Savage 和 Jake Toole。


当 AI 系统在其他基准游戏中与人类对战时,机器有时在刚开始的时候表现非常好,但随着人类玩家发现它们的弱点,最终就会击败它们。如果 AI 想要彻底掌控一场游戏,它必须展示出这样一种能力,即使人类玩家能够逐渐适应它们的节奏,但它们也能取得胜利。过去几天,职业扑克玩家与 Pluribus 进行了数千场比赛,因而有足够的时间来找出它的弱点,并逐渐适应它。


Elias 说道:「Pluribus 是在与世界上最好的扑克玩家进行对抗啊。」


以下是实验中 Pluribus 与人类玩家对抗时的界面:



实验分为两种模式:其一,5 名人类玩家与 1 个 AI 进行对抗;其二,1 名人类玩家与 5 个 AI 副本进行对抗。因此,在每一种对抗模式下,共有 6 名玩家参与其中,并且每局开始的时候有 10000 筹码。小盲(small blind)50 筹码,大盲(big blind)100 筹码。


尽管扑克是一款技巧游戏,但其中也会有非常大的运气成分。如果运气不佳的话,顶级职业玩家也会在 10000 手的扑克比赛中输钱。为了弱化运气成分在扑克比赛中的作用,研究者使用了一种 AIVAT 方差缩减算法,该算法对各种状况的值进行基线估计,从而在保持样本无偏的同时缩减方差。举例而言,如果 Pluribus 得到一副强手牌,AIVAT 将从它赢得中减去基准值,从而对抗好运气。


5 名人类玩家+1 个 AI


在实验中,人类玩家和 AI 之间展开的 10000 手扑克比赛持续了 12 天,每天挑选 5 名人类玩家与 AI 进行比赛。这些玩家将根据自身表现瓜分 50000 美元的奖励,以激励他们发挥最佳水平。在采用 AIVAT 后,Pluribus 的胜率预计约为每 100 手 5 个大盲注(标准误差为 5 bb/100),这对顶级人类扑克玩家而言是巨大胜利(盈利 P 值为 0.021)。所以,如果每个筹码价值 1 美元,Pluribus 每手平均能赢 5 美元,每小时能赢 1000 美元。这一结果超过了纯职业玩家在与职业和业余混合玩家对抗时的胜率。


Ferguson 在比赛实验结束后说道:「Pluribus 真是太难对付了!我们很难在任何一手中盯死它。它不仅非常擅长进行薄的价值下注,而且擅长从好手牌中赢得最大价值。」


但值得注意的是,Pluribus 本意是成为 AI 研究的工具,研究者仅将扑克比赛作为一种方式,以衡量 AI 在不完全信息多智能体交互(与人类顶级能力相关)中的进展。


5 个 AI+1 个人类玩家


参与实验的有 Ferguson、Elias 和 Linus Loeliger。Loeliger 是很多人公认的六人无限德扑顶级玩家。每个人与五个 Pluribus AI 玩 5000 手扑克。Pluribus 并没有根据对手的情况调整策略,因此机器人之间的故意勾结不是问题。总的来说,人类每 100 手损失 2.3 bb。Elias 每 100 手损失 4.0 bb(标准误差为 2.2 bb/100),Ferguson 每 100 手损失 2.5bb(标准误差为 2.2 bb/100),Loeliger 每 100 手损失 0.5 bb(标准误差为 1.0 bb/100)。


这张图显示了 Pluribus 在 10000 手实验中对职业扑克玩家的平均胜率。直线表示实际结果,虚线表示一个标准差。


「这个 AI 最大的优势就是它使用混合策略的能力,」Elias 表示。「人类也想这么做。对人来说,这是一个执行的问题——以一种完全随机的方式持续去做。多数人类做不到这一点。」


由于 Pluribus 的策略完全是在没有任何人类数据的情况下通过 self-play 自己学到的,因此它也提供了一个外部视角,即在多人无限制德州扑克游戏中最好的玩法应该是什么样子。


Pluribus 证实了人类传统的聪明玩法——limping(叫大盲而不是加注或弃牌)对于任何除小盲之外的任何玩家来说都不是最佳策略,因为根据规则,小盲已经下了大盲的一半,因此小盲跟注只需再下一半。


尽管 Pluribus 最初在通过 self-play 离线计算蓝图策略时尝试 limping,但随着 self-play 的继续,它逐渐放弃了这一策略。


此外,Pluribus 并不认同 donk 是一种错误的观念(在前一轮投注结束时,开始新一轮加注);与专业人士相比,Pluribus 更喜欢这么做。


「和扑克 AI 比赛,看到它选的一些策略,真的非常过瘾,」Gagliano 表示。「有几场人类根本就没有发挥什么作用,尤其是它下注比较狠的那几场。」


这张图显示了在与顶尖玩家对战时 Pluribus 的筹码数量变化。直线表示实际结果,虚线表示一个标准差。


从扑克到其它不完美信息博弈的挑战


AI 以前曾经在完美信息零和博弈(两个参与者)中取得了多次引人注目的成功。但大多数真实世界策略交互都涉及隐信息,且并非两个参与者的零和博弈。Pluribus 的成功表明,目前还有更大规模的、极其复杂的多参与者场景,仔细构建的自我博弈和搜索算法能够在这些场景下获得很好的效果,尽管当前并没有很强的理论支持来保证这个效果。


Pluribus 也非同一般,因为与其它近期的 AI 系统相比,在基准博弈中,它的训练和推断成本都要低得多。尽管该领域的一些研究者担心未来的 AI 研究会被拥有大量计算资源的大型团队主导。但研究者相信 Pluribus 是一个强有力的证据,说明新方法只需要适当的计算资源,就能驱动顶尖的 AI 研究。


尽管 Pluribus 是为了玩扑克开发的,但其使用的技术并不是扑克所独有的,它也不需要任何专家领域的知识进行开发。该研究给我们提供了一个更好的基本理解,即如何构建一般的 AI 以应对多智能体环境,这种环境既包括其它 AI 智能体,也包括人类。同时,搭建一般的多智能体 AI,也能使研究人员将研究过程中取得的 AI 基准成绩与人类能力的尖峰做对比。


当然,在 Pluribus 中采取的方法可能并不会在所有多智能体设定上取得成功。在扑克中,参与方很难有机会与其它智能体沟通,这有可能构建非常简单的调和博弈(coordination game),因此 self-play 算法找不到一个好策略。


然而对于很多现实世界的交互,包括反欺诈、网络安全和内容审核等潜在都能通过 Pluribus 的方法建模。即建模为涉及隐藏信息的场景,并(或)通过多个智能体的有限交流来构建不同参与方间的联系。这项打德州扑克的技术甚至允许 Pluribus 帮助 AI 社区在不同领域中构建更高效的策略。


最后,在过去的 16 年中,Tuomas Sandholm 和 CMU 团队都在研究策略推理技术。Pluribus 构建并融合了策略推理的大部分技术与代码,但它同样也包含了扑克的专门代码,这些代码 CMU 和 Facebook 合作完成,且并不会用于国防应用。



参考内容:

https://ai.facebook.com/blog/pluribus-first-ai-to-beat-pros-in-6-player-poker

https://www.nature.com/articles/d41586-019-02156-9

https://science.sciencemag.org/content/early/2019/07/10/science.aay2400



市北·GMIS 2019全球数据智能峰会7月19日-20日在上海市静安区举行。本次峰会数据智能为主题,聚焦最前沿研究方向,同时更加关注数据智能经济及其产业生态的发展情况,为技术从研究走向落地提供借鉴。

本次峰会设置主旨演讲、主题演讲、AI画展、「AI00」数据智能榜单发布、闭门晚宴等环节,已确认出席嘉宾如下:

我们为广大学生用户准备了最高优惠的学生票,点击阅读原文即刻报名。

登录查看更多
2

相关内容

Noam Brown是Facebook人工智能研究科学家,研究兴趣是人工智能,博弈论算法,多智能体系统,机器学习。
非凸优化与统计学,89页ppt,普林斯顿Yuxin Chen博士
专知会员服务
102+阅读 · 2020年6月28日
阿里巴巴达摩院发布「2020十大科技趋势」
专知会员服务
106+阅读 · 2020年1月2日
兴军亮Science评述:多人德州扑克博弈新突破
中国科学院自动化研究所
19+阅读 · 2019年7月15日
【学界】继图像识别后,图像标注系统也被对抗样本攻陷!
GAN生成式对抗网络
6+阅读 · 2017年12月11日
盘点2017年度AI领域大事件
大数据文摘
5+阅读 · 2017年12月9日
NIPS 2017最佳论文出炉:CMU「冷扑大师」不完美信息博弈研究获奖
最可怕的不是被机器淘汰,而是……
全球创新论坛
18+阅读 · 2017年10月28日
已删除
将门创投
5+阅读 · 2017年10月20日
Arxiv
14+阅读 · 2020年1月27日
Arxiv
3+阅读 · 2018年11月13日
Mobile big data analysis with machine learning
Arxiv
6+阅读 · 2018年8月2日
Arxiv
3+阅读 · 2018年4月3日
VIP会员
相关VIP内容
非凸优化与统计学,89页ppt,普林斯顿Yuxin Chen博士
专知会员服务
102+阅读 · 2020年6月28日
阿里巴巴达摩院发布「2020十大科技趋势」
专知会员服务
106+阅读 · 2020年1月2日
相关资讯
兴军亮Science评述:多人德州扑克博弈新突破
中国科学院自动化研究所
19+阅读 · 2019年7月15日
【学界】继图像识别后,图像标注系统也被对抗样本攻陷!
GAN生成式对抗网络
6+阅读 · 2017年12月11日
盘点2017年度AI领域大事件
大数据文摘
5+阅读 · 2017年12月9日
NIPS 2017最佳论文出炉:CMU「冷扑大师」不完美信息博弈研究获奖
最可怕的不是被机器淘汰,而是……
全球创新论坛
18+阅读 · 2017年10月28日
已删除
将门创投
5+阅读 · 2017年10月20日
Top
微信扫码咨询专知VIP会员