登顶Science封面、拿下NIPS最佳论文！这位CMU大神要毕业了

作者 | 陈大鑫

我已经答辩完成了我的博士学位论文！在我攻读博士学位的过程中，看到击败扑克界的顶尖人物的想法从科幻小说演变成现实，真是太神奇了。

昨日，Noam Brown在推特上宣布答辩完成了卡耐基梅隆大学（CMU）的 230页 超硬核博士论文：

《Equilibrium Finding for Large Adversarial Imperfect-Information Games》

这也差不多宣告他要毕业了，毕竟博士答辩结束就行了~

其实不用想也知道他能百分百通过答辩。

相信我，看完全文，没人敢把这位大神挂掉。

 

1

拿奖到手软

Noam Brown，卡耐基梅隆大学（CMU）博士，Facebook 人工智能实验室研究科学家、AI德州扑克作者，致力于使AI在大型不完全信息多智能体交互中进行战略推理。

Noam Brown已经将自己的研究成果应用到了第一款在无限注德州扑克中击败顶级人类的 AI 上。

他和他的CMU导师一起创建了AI系统Libratus和Pluribus，并在人机对抗比赛中果断击败了顶尖的人类扑克职业玩家：

2017 年一月在宾夕法尼亚州匹兹堡的 Rivers 赌场，一场奖金20 万美元的比赛正在进行，在这为期 20 天的赛程里面 4 名人类职业玩家和 Libratus共对战12 万手。最终，Libratus 人工智能系统成功击败了人类顶级职业玩家。

AI扑克Pluribus也因此曾登顶了 Science封面 ：

不可不提的是，同样在2017年 ，Noam Brown及其导师获得了 NIPS 2017最佳论文奖 ，获奖论文：

2019年，同样是和导师合作，他们二人又拿下 AAAI 2019杰出论文奖 ，获奖论文：

随后Noam Brown之后的一系列成果也成为 《Science》2019年年度突破的亚军 ：

除此之外，Noam Brown及其团队也因在AI方面的杰出成就获得了 马文·明斯基奖 （Marvin Minsky，人工智能先驱）。

最后，Noam Brown本人也被《MIT科技评论》评为35岁以下35位创新者之一。

而获得过这个奖项的大佬都有谁呢？

 

2

研究背景

近年来，以AlphaGo为代表的人工智能进步有目共睹，人工智能也再一次火遍全球。

而人工智能的成功似乎总是和人类对抗游戏的表现做对比体现出来。

对抗游戏的核心就在于博弈一词，博弈论起源于 纳什均衡：

大家有看过电影《美丽心灵》的都会知道一二。

而纳什均衡的代表就是囚徒困境：

囚徒困境的故事讲的是，两个嫌疑犯作案后被警察抓住，分别关在不同的屋子里接受审讯。警察知道两人有罪，但缺乏足够的证据。

警察告诉每个人：如果两人都抵赖，各判刑1年；如果两人都坦白，各判两年；如果两人中一个坦白而另一个抵赖，坦白的放出去，抵赖的判5年。于是，每个囚徒都面临两种选择：坦白或抵赖。

然而，管同伙选择什么，每个囚徒的最优选择是坦白：如果同伙抵赖、自己坦白的话放出去，抵赖的话判5年，坦白比不坦白好；如果同伙坦白、自己坦白的话判两年，比起抵赖的判5年，坦白还是比抵赖的好。结果，两个嫌疑犯都选择坦白，各判刑两年。

现在我们谈游戏，以游戏为代表的信息博弈大致可以分为完全（完美)信息博弈和不完全(完美)信息博弈。

跳棋、国际象棋、五子棋、围棋等都属于完美信息博弈，即双方都知道博弈中每一时刻的确切状态，以及未来可能发生的所有状态（如果算力允许）。

相反，扑克牌是不完美信息博弈：博弈状态的一些信息是隐藏的，即博弈中存在包含多个决策点的信息集或博弈者无法预测对手的一些行动。

很显然，在扑克牌中如果大家都互相知道对手的牌面，那四个3也就没法当成4个2唬住对方了，这会使游戏顿时变得索然无味~

隐藏信息在现实世界策略互动中无处不在，如交通信息、战争等，这使得研究不完美信息博弈的技术尤其重要。

而反观 Noam Brown这一路拿奖到手软的历程，其实可以看出他的研究关注点一直都在不完全信息博弈上面 ,这一次他在推特上介绍的也是刚刚完成的博士论文: 研究大型对抗性不完全信息博弈的均衡发现 ，这也是他博士几年的研究积累成果汇总。

接下来就来介绍一下这篇博士论文。

 

3

博士论文

论文名称：

《Equilibrium Finding for Large Adversarial Imperfect-Information Games》

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

Noam Brown在博士论文前言有提到,除了第5.3节的ReBeL外，本文中的所有研究都是 他和他的导师Tuomas Sandholm合作完成 的，而在致谢中Noam Brown又说到：

首先我要感谢我的导师  Tuomas Sandholm 。Tuomas耐心地指导我完成了整个研究过程，包括几次深夜披萨助力（ late-night pizza-fueled）的论文写作。没有这个指导，我的博士学位肯定不会成功。

说到这里，我们不得不停下来问一句，Noam Brown还都干了啥？

——带你“打德州扑克”、带你上Science封面、带你拿NIPS最佳论文！带你拿马文.明斯基奖.......

请问这么好的导师上哪去找？请给我来一打！

跟着这样的导师简直要起飞了！别问，问就是： 带你梭哈！

论文摘要

不完全信息博弈模型是指多个主体与私人信息之间的相互作用。在这种情况下，一个典型的目标是接近一个均衡，在这个平衡中，所有的智能体策略都是最优的。本文描述了大型对抗性不完全信息博弈均衡计算的若干进展。这些新技术使人工智能智能体首次有可能在无限注扑克牌中击败顶尖的人类专业玩家，几十年来，这一直是人工智能和博弈论领域的重大挑战问题。

我们首先介绍了对反事实后悔最小化（CFR）的改进，

这是一种在两人零和博弈中收敛到纳什均衡的迭代算法。我们描述了CFR的新变体，它使用折扣原则（discounting）来显著加快收敛速度。

这些新的CFR变体现在是大型对抗性不完全信息博弈的SOTA均衡发现(equilibrium-finding)算法。 我们还介绍了第一个热启动（ wa rm starting）CFR的通用技术。

随后，我们介绍了理论上合理的剪枝技术，可以在大型博弈中数量级地加速收敛。

接下来，我们将描述通过自动抽象和函数近似将CFR扩展到大型游戏的新方法。

特别地，我们介绍了第一个在不完全信息博弈中离散连续动作空间的算法。我们将其扩展到求解具有连续动作空间博弈的算法中。

之后，我们介绍了Deep CFR，一种使用神经网络函数近似而不是基于bucketing的抽象形式。Deep CFR是第一个可扩展到大型游戏的non-tabular形式的CFR，它使CFR能够在几乎没有领域知识的情况下成功部署。

最后，我们 提出了一种新的不完全信息博弈搜索技术，以确保智能体的搜索策略不会被对手利用。

这些新的搜索形式在理论上和实践上都优于过去的方法。接下来，我们将介绍一种深度受限搜索的方法，它在计算上比以前的方法要代价要少得多。

最最后，我们提出了一种在训练和测试时结合强化学习和搜索的算法ReBeL:

它朝着弥合完全信息游戏和不完全信息游戏研究之间的差距迈出了重要的一步。

论文目录：

在致谢的最后，Noam Brown表达了对家人的感谢：

最后，我要特别感谢我的父母 Michael 和 Nurit，还有我的全家，感谢你们一直支持我，鼓励我追求我的激情。

点击阅读原文，直达“CCF-NLP走进高校之郑州大学”直播页面！