【前沿】Science封面重磅：CMU、Facebook联合打造“赌神”AI，六人德扑击败人类
前不久，一款名叫 “Pluribus” 的 AI 扑克牌机器人在六人无限注德州扑克这项复杂游戏中，碾压了人类职业选手！
这是 AI 首次在规模超过两人的复杂对局中击败顶级人类玩家。
“Pluribus” 是CMU 和 Facebook 联合打造的史上最强德州扑克 AI，重点解决了多人对局环境下的非零和博弈和隐藏信息推理问题，是该领域的一个重大突破。
“Pluribus”的论文更是以封面的形式登上Science杂志！
来自CMU和Facebook AI的Noam Brown和Tuomas Sandholm教授，在论文中详细解读了“Pluribus”的策略。
作者表示，扑克一直是一个具有挑战性的问题，过去AI在这类基准测试中取得的成功仅限于两人参与的游戏。然而，传统上玩扑克的人不止两个人。多人扑克是一个公认的AI里程碑。
“Pluribus”AI在六人无限制注德扑中展现了比顶级人类专业玩家更强大的技能。
接下来是这篇论文的解读，完整论文可点击文末链接查看。
基于MCCFR的“蓝图”策略
三人或三人以上的博弈对博弈论提出了挑战。对于两个玩家的零和博弈，存在这样一种策略，即没有玩家可以通过切换到不同的策略来提高他们的机会。这种所谓的纳什均衡被认为是博弈的一个解。
但对于多人游戏，期望奖励可能因纳什均衡的不同而有所不同。保证收敛到纳什均衡的快速算法，例如虚拟遗憾最小化算法(CFR)，在多人游戏中可能失效。尽管如此，CFR在一些多人游戏领域仍显示出良好的经验表现。
Pluribus首先通过自我游戏(self-play)来学习通用技巧，我们称之为“蓝图”(blueprint)策略。
然后，在实际游戏中，它根据游戏的当前状态计算一个实时策略来细化blueprint策略。Pluribus程序通过名为Monte Carlo CFR (MCCFR)的CFR变体学习blueprint策略，并进行一些改进。
Pluribus会反复模拟所有玩家使用相同策略的扑克手牌；在每一手牌之后，它会递归地检查每个决策，并与在相同情况下可能选择的其他操作相比，评估该决策的预期结果。
为了提高Pluribus中MCCFR算法的效率，作者在训练的早期阶段引入了linear weighted discounting，并在训练的后期对negative-regret行为进行策略剪枝。
系统中最复杂的部分是实时策略组件。为了处理不完美信息，Pluribus执行嵌套搜索，维护搜索树的根节点和每个玩家持有的牌的根节点的概率分布，前提是假设所有玩家使用相同的(已知的)策略。
为了有效评估叶节点，Pluribus考虑了blueprint 策略的四种不同变体。
在Abstraction机制中，Pluribus通过将类似的情况打包在一起，减少了关于是否跟注(call)、加注(raise)或弃牌(fold)的决策点的数量。使用蒙特卡罗虚拟遗憾最小化(MCCFR)，将扑克游戏中树搜索的复杂性从一个棘手的问题降低到一个可解决的问题。
真实游戏
Pluribus需要为每个场景提供一个动作(跟注、加注或弃牌)。
抽象游戏
类似的方案，比如高牌9和高牌10一起。
抽象策略
Pluribus使用MCCFR通过操作将每个bucket映射到一个分布。
真实策略
每个方案都根据其bucket的抽象策略映射到操作上的分布。
对于大型复杂的游戏，状态和动作的抽象可以用来抑制搜索树的增长。这对于完整的六人无限德州扑克游戏来说是必要的，因为德扑太过复杂而无法直接搜索。
相反，如上面的示意图所示，Pluribus模拟了一个更简单的游戏版本，将类似的决策点组合在一起，并消除了一些操作。
“赌神”AI训练只需144美元
最后，Pluribus的blueprint策略是在64核服务器上在8天内计算出来的，总共使用了12400个CPU核心小时，所需内存小于512 GB。按照当前的云计算费用，这花费了大约144美元。
这与最近其他所有的超级AI里程碑游戏形成了鲜明的对比，那些AI使用了大量的服务器和/或GPU集群。更多的内存和计算可以支持更细粒度的blueprint，这将带来更好的性能，但也会导致Pluribus使用更多内存或在实时搜索变慢。
研究人员将blueprint策略抽象的大小设置为允许Pluribus在一台内存不超过128GB的机器上实时运行，同时在内存中存储blueprint策略的压缩形式。
由于无限德州扑克的规模和复杂性，整个游戏的blueprint 策略必然是粗粒度的。Pluribus只在第一轮投注(四次投注)中根据这个blueprint策略进行操作，其中决策点的数量足够少，以至于blueprint策略可以不使用信息抽象，并且在操作抽象中进行了很多操作。
在第一轮之后(甚至在第一轮中，如果对手选择的赌注大小与blueprint action抽象中的大小完全不同)，Pluribus将进行实时搜索，以确定针对当前情况的更好、更细粒度的策略。
结论
self play 的形式与搜索的形式相结合，在完全信息的二人零和博弈中取得了许多引人注目的成功。然而，现实世界中的大多数战略交互都包含隐藏的信息和两个以上的参与者。这使得这个问题在理论和实践上都有很大的不同和困难。
为多人德扑开发一个超级AI是该领域的一个公认的里程碑。在本文中，我们描述了Pluribus，一个AI，能够在六人无限注德州扑克中击败人类专业玩家。
Pluribus的成功表明，尽管对多人博弈的性能缺乏已知的强有力的理论保证，但仍存在大规模、复杂的多人博弈不完全信息设置，在这种情况下，精心构造的self play搜索算法可以生成超越人类的策略。
论文地址：
https://science.sciencemag.org/content/365/6456/885
来源：新智元
【重要通知】关于开展2019年度中国自动化学会会士候选人提名工作的通知
【重要通知】关于2019年度CAA科学技术奖励推荐工作的通知
【重要通知】关于开展2019年度中国自动化与人工智能创新团队奖推荐工作的通知
【CAA】中国自动化学会选举产生第十一届理事会领导机构（内附名单）
热烈祝贺中国自动化学会常务理事、火箭军工程大学教授胡昌华荣获中共中央军委通令记功
地址：北京市海淀区中关村东路95号
邮编：100190
电话：010-82544542（综合）
010-62522472（会员）
010-62522248（学术活动）
010-62624980（财务）
传真：010-62522248
邮箱：caa@ia.ac.cn
官方微信公众号（英文）
名称：CAA OFFICIAL
微信号：caaofficial
会员微信公众号
名称：CAA会员服务
微信号：caa-member
相关内容
微信扫码咨询专知VIP会员