携Science封面、NIPS最佳论文，CMU大神Noam博士毕业，论文已公开

发布时间：2020-09-27 14:21:03来源：机器之心

机器之心报道

作者：杜伟

还记得在双人无限扑克和多人无限扑克中战胜人类顶级玩家的游戏AI系统和吗？近日，这两个AI系统的开发者之一、CMU大神宣布其完成博士论文，并即将从CMU毕业。

当地时间9月21日，FAIR研究科学家NoamBrown在推特宣布其顺利完成了CMU博士论文答辩，并公开了长达230页的超硬核博士论文《EquilibriumFindingforLargeAdversarialImperfect-InformationGames》以及101页的slides。

Noam在论文前言中表示，除了章节5.3中描述的ReBel算法，论文中所有其他研究都是与其导师TuomasSandholm合作完成的。在整个研究过程中，Tuomas给了Noam耐心指导。Noam表示，如果没有导师的悉心指导，他肯定不会顺利地完成博士学位。

NoamBrown与其导师TuomasSandholm教授（右）。

NoamBrown的博士论文题目为《大型对抗性不完美信息博弈的均衡发现》。不完美信息博弈模拟了多个智能体与私人信息之间的交互。在这一设置下，一个典型的目标是近似一个均衡，其中所有智能体的策略都能达到最优。

完美信息博弈（Perfect-informationGames）和不完美信息博弈（Imperfect-informationGames）是游戏中信息博弈的两种主要形式。在游戏中，完美信息博弈的前提是所有玩家都知道关于游戏的信息，如规则等；而不完美信息博弈中的玩家对正在玩的游戏没有共同知识，如其他玩家是谁、哪些策略或行动是可行的、结果如何取决于行动等。就难度而言，信息的不完美增加了玩家决策选择的难度，因而博弈分析的难度也更大。

围棋、国际象棋、跳棋等棋类游戏属于完美信息博弈。扑克牌则属于典型的不完美信息博弈，这也是NoamBrown一直以来的研究重心。从2017年的AI系统Libratus到2019年的新算法Pluribus，它们都属于不完美信息博弈的范畴。

在论文中，NoamBrown对博士期间的一系列研究成果进行了汇总。机器之心对该论文的核心内容进行了简要介绍，感兴趣的读者可以阅读原论文。

论文地址：http://www.cs.cmu.edu/~noamb/thesis.pdf

Slides地址：http://www.cs.cmu.edu/~noamb/thesis_slides.pdf

博士论文简介

这篇博士论文详述了大型对抗性不完美信息博弈中均衡计算的一系列进展。这些新技术使得AI智能体首次有可能在无限注扑克游戏中击败顶级职业玩家，而这正是几十年来AI和博弈论领域一直存在的重大挑战性难题。

反事实遗憾最小化（CFR）的改进

作者首先介绍了对反事实遗憾最小化（counterfactualregretminimization,CFR）做出的改进，这是一种在双人零和博弈中收敛至纳什均衡的迭代算法。此外还描述了CFR的新变体，它们利用折扣原则（discounting）来显著加快收敛速度。

CFR方法。

然后，作者介绍了理论上合理的剪枝（pruning）技术，这些技术可以在大型博弈中呈数量级地加快收敛速度。

CFR中的剪枝流程。

将CFR扩展至大型博弈

作者描述了通过自动抽象和函数近似算法将CFR扩展至大型博弈的新方法。

具体而言，作者介绍了首个在不完美信息博弈中离散化连续动作空间的算法，该算法被证明局部最优。但是，这种算法需要大量的领域知识，并且难以扩展至其他博弈中。

以往方法的局限性。

所以，作者提出了CFR的一种变体DeepCFR，它使用了神经网络函数近似，而没有使用基于bucketing的抽象。DeepCFR是首个可以扩展至大型博弈的non-tabular形式的CFR，并且使得CFR在几乎没有领域知识的设置下实现部署。

利用DeepCFR扩展至大型博弈中。

不断改进的搜索技术

作者提出了一种新的不完美信息博弈搜索技术，该技术确保智能体的搜索策略不被对手利用。这些新的搜索形式在理论和实践两方面均优于以往方法。

此外，作者介绍了一种深度受限（depth-limited）搜索方法，它的计算成本显著低于以往方法。

Pluribus算法中的深度受限搜索。

最后，作者提出了一种新型ReBel算法，它在训练和测试时结合强化学习和搜索，并为缩小完美信息博弈和不完美信息博弈研究的差距迈出了关键一步。

在双人无限注德州扑克中的结果对比。

以下是博士论文的章节目录：

致力于德扑游戏AI研究的CMU大神NoamBrown

NoamBrown，Facebook人工智能实验室的研究科学家，他致力于结合计算博弈论和机器学习来开发能够在不完美信息多智能体环境中进行策略推理的AI系统，其研究成果应用到了首个分别在在双人无限扑克和多人无限扑克中战胜人类顶级玩家的Libratus和Pluribus。这两个游戏AI系统为NoamBrown带来了巨大的荣誉。

2017年，NoamBrown与其导师TuomasSandholm开发的AI系统Libratus在宾夕法尼亚州匹兹堡Rivers赌场持续20天1对1无限制德扑比赛中成功战胜了4名全球顶级职业玩家。该研究登上了《科学》杂志，与研究相关的另一篇论文《SafeandNestedSubgameSolvingforImperfect-InformationGames》也获得了。

此外，Noam团队还因此获得了IJCAI颁发的（MarvinMinskyMedal）。

Noam在IJCAI2019大会上领取马文·明斯基奖章证书。

2019年，NoamBrown与其导师TuomasSandholm在Libratus的基础上，开发出了所需算力更少的新算法Pluribus。在为期12天、超过10000手牌的比赛中，Pluribus击败了15名人类顶级玩家。

这是AI首次在玩家人数（或队伍）大于2的大型基准游戏中击败顶级职业玩家。Pluribus不仅登上了《科学》杂志的封面，还被该杂志列为2019年度十大突破科研成就之一。

Pluribus登上了《科学杂志》封面。

此外，Noam还曾获得2017年度AllenNewell「卓越研究奖」，也曾被MIT科技评论评选为2019年度「35岁以下科技精英」（MITTR35）。2019年，NoamBrown与其导师TuomasSandholm合著的论文《SolvingImperfect-InformationGamesviaDiscountedRegretMinimization》获得了。

参考链接：

https://mp.weixin.qq.com/s/IoaSWYvBn_M2Io5EGcDWOA

https://www.cs.cmu.edu/~noamb/

AIWIN世界人工智能创新大赛——2021赛季「抗新冠助科研AI大赛」全球招募啦！

开放新冠开放研究数据集（Corvid-19OpenResearchDataset，简称CORD-19）包含近20万篇有关冠状病毒学术论文的数据集。

如果你是个人，这里有高额的奖金、世界500强合作企业的实习和就业机会、个人技术的世界级展示和交流平台；

如果你是企业，这里有AI+医疗全生态对接资源、有面向全球的线上线下展示机会、有真实的AI场景需求对接通道。

识别图片二维码或者点击阅读原文，立刻报名参赛吧！

©THEEND

转载请联系本公众号获得授权

投稿或寻求报道：content@jiqizhixin.com