独家首发 | NIPS 最佳论文视频解读！德州扑克背后的不完全信息博弈

美国时间， 2017 年 12 月 4 日 8:00。

全球机器学习顶级会议 NIPS 在美国长滩开幕了。

本年度 NIPS 将持续一周，你现在才想参加肯定来不及，因为票早就卖光了。

为了让你隔着太平洋都能跟上 NIPS 的节奏，雷锋网带你抢先看 NIPS 2017 的最佳论文。这篇 NIPS Talk 的时间是美国时间 12 月 5 日下午 2:50。

Safe and Nested Subgame Solving for Imperfect-Information Games

安全和嵌套子游戏解决不完全的信息博弈

不跨洋不翻墙

点击观看下方视频

轻松解读 NIPS 2017 最佳论文！

 ▼

那些关注过人机大战的朋友们，你们肯定知道这篇论文在讲什么。

不方便打开视频的朋友们，可以看看雷锋网(公众号：雷锋网)简版图文：

今年年初，4 位顶尖德州扑克选手，在为期 20 天赛程里，与卡耐基梅隆大学（CMU）研发的人工智能系统 Libratus 对决 12 万手，争夺 20 万美元奖金池。

最终，Libratus 击溃了这组职业选手。Libratus 人工智能系统所用到的策略技巧，就是这篇论文的重点内容。

论文将德州扑克之类的游戏所运用的技巧，定义为一种不完美的信息博弈互动策略。这种互动策略不仅可以应用于游戏中，还能应用在谈判、拍卖、网络安全以及人身安全上。

为什么不能将 Alphago 或者 DeepBlue2 的技术应用在德州扑克上呢？

这里有几个原因，其中最重要的一个原因是，所有的完美游戏（例如五子棋、国际象棋）都有一种特性，那就是，当你采取一些行动时，你的对手也采取了一些行动，当你发现自己身处一个特别的子博弈环境时，完全可以忽略其它不相关的情况，决策点与最佳策略直接相关，你唯一需要做的事情就是，确定当前的决策点。

但是德州扑克是一种不完美游戏，当你处在一个特定的子博弈中时，随即又会出现其他的子博弈，你不能从这个决策点出发，因为其他子博弈会影响你当前子博弈的最佳策略。换句话说，当在不完美的信息博弈中进行决策时，你必须考虑到这个博弈的全局策略，而并非子博弈的最佳策略。

过去，我们的策略都是预先计算出来的，2015 年有人就在小型的德州扑克程序库中简单预先计算了整个博弈的最佳策略。但情况不总是这么简单，一旦遇到计算量庞大的游戏就最佳策略失灵了。

研究者针对不限注德州扑克做了相关的研究，针对整个游戏的玩法做了近似计算，在真实的不限注德州扑克中，发现了针对性的子博弈策略，这个技术叫做“嵌套的子博弈”。

在博弈树下重复这个过程，会发现我们还处在另一个子博弈中，再次找到一个更好的针对性的子博弈策略。通过这个技术，能够和已经计算出的全局蓝图进行很好的拟合。

在博弈树下重复这个过程，会发现我们还处在另一个子博弈中，再次找到一个更好的针对性的子博弈策略。通过这个技术，能够和已经计算出的全局蓝图进行很好的拟合。

所以你看，相比于之前的方法，不完美信息博弈的子博弈求解技术，有着更强的理论保证和更好的实际表现。同时，作者还展示了安全与非安全的子博弈求解技术，以及为嵌套子博弈求解引入了新方法。

Poker AI Libratus幕后的研究者：

卡耐基梅隆大学(CMU)Tuomas Sandholm 教授和他的学生 Noam Brown 是本篇论文的作者。更多幕后故事可以看雷锋网报道 德州扑克算法幕后研发者CMU博士Brown专访：AI如何打败顶级人类牌手？

Tuomas Sandholm 教授（右 ）与 Noam Brown 博士（左）

Tuomas Sandholm 是 CMU 计算机科学系教授，他在人工智能和自动谈判领域，研究超过 28 年。最早的成绩要追溯到 1989 年前后，他做了一套自动为卡车司机谈判并分配任务的系统。

近年来，Sandholm 和他的团队成绩显赫，多次在国际机器学习会议（ICML）、人工智能会议（AAAI）获奖，现在 Sandholm 还拿到 NSF(美国国家科学基金会)一笔为期三年的新投资，用以资助他继续基于 AI Libratus 展开相关研究。

Noam Brown 是 Sandholm 的博士生，他的研究将强化学习和博弈论结合起来，在大量不完美信息多智能体交互中，做出能够进行战略推理的 AI。

Brown 把他的研究应用导 AI Libratus 身上，AI Libratus 在不限注的扑克中击败顶级人类选手。他还曾创建了 Libratus 的前身 Claudico 以及 Baby Tartanian8、Tartanian7，都在近两年的计算机扑克大赛中获胜。

11 月 29 日，Noam Brown 在自己的 Twitter 上炫耀了一波，说拿了最佳论文，NIPS Talk 的时间是 12 月 5 日下午 2:50，邀请大家来跟 Poker AI Libratus 一决高下。

学霸们想了解更多，可以打开更新版的论文原文：

https://www.cs.cmu.edu/~sandholm/safeAndNested.aaa17WS.pdf

翻译 / 余杭

整理 / 吴璇

。