携Science封面，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

（编辑：应用网_阳江站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!