2020/09/27 12:54

杜伟机器之心报道

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

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

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

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

Noam Brown 与其导师 Tuomas Sandholm 教授（右）。

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

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

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

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

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

博士论文简介

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

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

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

CFR 方法。

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

CFR 中的剪枝流程。

将 CFR 扩展至大型博弈

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

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

以往方法的局限性。

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

利用 Deep CFR 扩展至大型博弈中。

不断改进的搜索技术

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

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

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

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

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

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

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

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

2017 年，Noam Brown 与其导师 Tuomas Sandholm 开发的 AI 系统 Libratus 在宾夕法尼亚州匹兹堡 Rivers 赌场持续 20 天 1 对 1 无限制德扑比赛中成功战胜了 4 名全球顶级职业玩家。该研究登上了《科学》杂志，与研究相关的另一篇论文《Safe and Nested Subgame Solving for Imperfect-Information Games》也获得了 NIPS 2017 最佳论文奖。

此外，Noam 团队还因此获得了 IJCAI 颁发的第二枚马文 · 明斯基奖章（Marvin Minsky Medal）。

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

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

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

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

此外，Noam 还曾获得 2017 年度 Allen Newell「卓越研究奖」，也曾被 MIT 科技评论评选为 2019 年度「35 岁以下科技精英」（MIT TR35）。2019 年，Noam Brown 与其导师 Tuomas Sandholm 合著的论文《Solving Imperfect-Information Games via Discounted Regret Minimization》获得了 AAAI 杰出论文荣誉提名奖。

参考链接：

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

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

理论大型对抗性不完美信息博弈中均衡计算Noam Brown博士论文

相关数据

纳什均衡技术

纳什平衡，又称为非合作赛局博弈，是在非合作博弈状况下的一个概念解，在博弈论中有重要地位，以约翰·纳什命名。如果某情况下无一参与者可以通过独自行动而增加收益，则此策略组合被称为纳什均衡点。

来源：维基百科

机器学习技术

机器学习是人工智能的一个分支，是一门多领域交叉学科，涉及概率论、统计学、逼近论、凸分析、计算复杂性理论等多门学科。机器学习理论主要是设计和分析一些让计算机可以自动“学习”的算法。因为学习算法中涉及了大量的统计学理论，机器学习与推断统计学联系尤为密切，也被称为统计学习理论。算法设计方面，机器学习理论关注可以实现的，行之有效的学习算法。

来源：Mitchell, T. (1997). Machine Learning. McGraw Hill.

零和博弈技术

零和博弈，又称零和游戏或零和赛局，与非零和博弈相对，是博弈论的一个概念，属非合作博弈。零和博弈表示所有博弈方的利益之和为零或一个常数，即一方有所得，其他方必有所失。在零和博弈中，博弈各方是不合作的。非零和博弈表示在不同策略组合下各博弈方的得益之和是不确定的变量，故又称之为变和博弈。

来源：维基百科

人工智能技术

在学术研究领域，人工智能通常指能够感知周围环境并采取行动以实现最优的可能结果的智能体（intelligent agent）

来源：Russell, S., & Norvig, P. (2003). Artificial Intelligence: A Modern Approach.

基准技术

一种简单的模型或启发法，用作比较模型效果时的参考点。基准有助于模型开发者针对特定问题量化最低预期效果。

来源：Google ML Glossary

剪枝技术

剪枝顾名思义，就是删去一些不重要的节点，来减小计算或搜索的复杂度。剪枝在很多算法中都有很好的应用，如：决策树，神经网络，搜索算法,数据库的设计等。在决策树和神经网络中，剪枝可以有效缓解过拟合问题并减小计算复杂度；在搜索算法中，可以减小搜索范围，提高搜索效率。

来源：Wikipedia

收敛技术

在数学，计算机科学和逻辑学中，收敛指的是不同的变换序列在有限的时间内达到一个结论（变换终止），并且得出的结论是独立于达到它的路径（他们是融合的）。通俗来说，收敛通常是指在训练期间达到的一种状态，即经过一定次数的迭代之后，训练损失和验证损失在每次迭代中的变化都非常小或根本没有变化。也就是说，如果采用当前数据进行额外的训练将无法改进模型，模型即达到收敛状态。在深度学习中，损失值有时会在最终下降之前的多次迭代中保持不变或几乎保持不变，暂时形成收敛的假象。

来源：Wikipedia Google ML glossary

神经网络技术

（人工）神经网络是一种起源于 20 世纪 50 年代的监督式机器学习模型，那时候研究者构想了「感知器（perceptron）」的想法。这一领域的研究者通常被称为「联结主义者（Connectionist）」，因为这种模型模拟了人脑的功能。神经网络模型通常是通过反向传播算法应用梯度下降训练的。目前神经网络有两大主要类型，它们都是前馈神经网络：卷积神经网络（CNN）和循环神经网络（RNN），其中 RNN 又包含长短期记忆（LSTM）、门控循环单元（GRU）等等。深度学习是一种主要应用于神经网络帮助其取得更好结果的技术。尽管神经网络主要用于监督学习，但也有一些为无监督学习设计的变体，比如自动编码器和生成对抗网络（GAN）。

来源：机器之心

深度受限搜索技术

DFS中出现的无界树问题可以通过对DFS可达到的深度加以限制来加以固定，这个极限我们称为深度极限L，这就解决了无限路径问题。当问题存在先验知识时，可以使用DLS，但现实常常并非如此。通常情况下，除非我们以前解决过这个问题，否则我们不会知道问题最浅的深度。

来源：Muhamad Hesham's T-Blog

博弈论技术

博弈论，又译为对策论，或者赛局理论，应用数学的一个分支，1944年冯·诺伊曼与奥斯卡·摩根斯特恩合著《博弈论与经济行为》，标志着现代系统博弈理论的的初步形成，因此他被称为“博弈论之父”。博弈论被认为是20世纪经济学最伟大的成果之一

来源：维基百科

完美信息博弈技术

在经济学中，完全的信息是完美竞争的特征。随着市场信息的完善，所有消费者和生产者都被假定在对自由市场体系进行理论化和财务政策效应时，对产品的价格，效用，质量和生产方法有完整的认识。

来源：Wikipedia

强化学习技术

强化学习是一种试错方法，其目标是让软件智能体在特定环境中能够采取回报最大化的行为。强化学习在马尔可夫决策过程环境中主要使用的技术是动态规划（Dynamic Programming）。流行的强化学习方法包括自适应动态规划（ADP）、时间差分（TD）学习、状态-动作-回报-状态-动作（SARSA）算法、Q 学习、深度强化学习（DQN）；其应用包括下棋类游戏、机器人控制和工作调度等。

来源：机器之心

机器之心机构

机器之心，成立于2014年，是国内最具影响力、最专业、唯一用于国际品牌的人工智能信息服务与产业服务平台。目前机器之心已经建立起涵盖媒体、数据、活动、研究及咨询、线下物理空间于一体的业务体系，为各类人工智能从业者提供综合信息服务和产业服务。

https://www.jiqizhixin.com/