AI内参_13_012_精读2017年NIPS最佳研究论文之三如何解决非完美信息博弈问题

你好，我是洪亮杰。

今天我和你分享的主题是精读NIPS二零一七最佳研究论文之三，如何解决非完美信息博弈问题？今天我们来分享一下NIPS二零一七的最后一篇最佳论文，安全和嵌套此博弈，解决非完美信息博弈问题。

这篇文章讲的到底是什么内容呢？讲的是如何解决非完美信息的博弈问题。

和前两篇分享的文章类似，这篇文章也是理论性很强，并不适合初学者。

我们在这里仅仅对文章的主要思想进行一个高度概括。

如果你对文章内容感兴趣，还是建议要阅读原文。

另外一个值得注意的现象是，即便在深度学习如日中天的全部，我们本周分享的三篇NIPS最佳论文，均和深度学习无关，这方面展现了深度学习，并不是人工智能的全部。

另一方面，也让我们看到机器学习和人工智能领域的宽广。

我先来简要介绍一下作者群的信息。

本文一共两位作者，第一作者叫诺阿布朗。

布朗是卡内基梅隆大学计算机系的博士生，目前的主要研究方向是利用强化学习和博弈论的思想，来解决大规模的多机器人交互的问题。

这篇文章提到的非完美信息博弈，也是这里面的一个分支论题。

第朗已经在这个方向发表了多篇论文，包括三篇AAAI论文、其篇NIPS论文、一篇ICML论文以及一篇IJCAI论文和本文非常相关的一个研究内容。

在二零一七年发表于科学杂志上，讲述了如何利用博弈论来解决hass up无限制扑克的问题。

并且在现实比赛中已经超过了人类的表现，这个工作也得到了不少媒体的报道。

布朗二零一七年在伦敦的谷歌deep mat实习，在博士阶段之前，他曾经在金融领域工作。

第二，作者是诺阿的导师，托马斯桑德霍姆。

桑德霍姆是卡内基梅隆大学计算机系的教授，其在机制、设计以及拍卖理论等领域有长期的研究发表了四百五十多篇学术论文，并且有超过两万多的影魔术。

除了他在学术上的造诣以外，桑德霍姆还有一些意识，比如他还有非常广泛的兴趣爱好。

在他的主页就列举了他冲浪、喜好、魔术以及对飞行的热爱。

我们首先来看一下这篇文章的主要贡献，弄明白这篇文章主要解决了什么场景下的问题。

对于一篇理论性很强的文章来说，我们通常需要不断的提问这篇文章的核心主旨到底是什么？这样才能够帮助我们了解到文章的主干。

首先文章讲到的是一个非完美信息的博弈问题，这是什么意思呢？要理解非完美信息博弈，我们就必须要说一下完美信息博弈。

简单来说，完美信息博弈指的是博弈，双方对目前的整个博弈状况都完全了解，对于博弈之前以及整个博弈时候的初始状态也完全了解。

在这种定义下，很多大家熟悉的游戏都是完美信息博弈，比如围棋、象棋等等。

那么deep mat开发的阿尔法go,以及后来的阿尔法go, zara都是典型的针对完美信息博弈的人工智能算法。

非完美信息博弈，并不是说我们不知道对方的任优信息，而只是说信息不充分，什么意思呢？比如，我们可能并不知道对手在这一轮里的动作，但我不知道对手是谁，有可能有怎样的策略，或者他们的策略的收益等。

除了在定义上表面的区别以外，在这个问题的机构上也有不同完美信息。

博弈有这样的特征，那就是在某一个时刻的最优策略，往往仅需要在问题决策书当前节点的信息，以及下面此数对应的所有信息，而并不需要当前节点之前的信息，以及其他的旁边节点的信息。

什么意思呢？比如我们看阿尔法go本质上，在这样完美信息博弈的场景中，理论上我们可以列出所有的棋盘和棋手博弈的可能性，然后用一个决策方案数来表达当前的决策状态。

在这样的情况下，尽管某一个决策状态之后，往往我们仅仅需要分析后面的状态，尽管这样的情况数目会非常巨大，但是从方法论的角度来说，并不需要引用其他的信息来做最优决策。

非完美信息博弈的最大特点就正好和这个相反。

也就是说，每一个子问题或者叫子博弈的最佳决策，都需要引用其他信息。

而实际上，本篇论文讲述了一个事实，那就是非完美。

信息博弈。

在任何一个决策点上的决策，往往取决于那些根本还没有达到的子博弈问题。

在这一点上，论文其实引用了一个制硬币的游戏来说明这个问题。

限于篇幅，我们就不重复这个比较复杂的问题设置了，有兴趣的话可以深读论文。

但是从大体上来说，这个制硬币的游戏其核心就是想展展示两个人玩之硬币在回报不同。

并且两个人的玩法在游戏规则上有一些关联的情况下，其中某一个玩家总可以根据情况完全改变策略。

而如果后手的玩家仅仅依赖观测到先手玩家的回馈来，决策，则有可能完全意识不到这种策略的改变，这个选择了并非优化的办法。

这里的重点在于先后手的玩家之间因为规则的牵制，导致后手玩家无法观测到整个游戏状态，得到的信息并不能完全反映先手玩家的策略，从而引起误判。

为解决这样博弈问题，这篇文章提出的一个核心算法，就是根据当前的情况，为整个现在的情况进行一个抽象。

这个抽象是一个小版本的博弈。

抽象既希望这个抽象能够携带足够的信息。

然后我们根据这个抽象来求解。

当在求解真正的全局信息的时候，我们利用这个抽象的解来辅助我们的决策。

有时候，这个抽象又叫做蓝图策略，这篇文章的核心在于如何构造的蓝图，以及如何利用蓝图来进行求解。

文章提出的方法有效果吗？文章在hass up无限制扑克的数据集上做了实验，并且还比较了之前在科学杂志上发表的叫做利布拉图斯的算法版本，人工智能算法都大幅度领先人类的玩家。

有一种算法叫非安全子博弈算法，也就是说并不考虑非完美信息的博弈状态。

把这个情况当做完美信息来做的一种算法，在很多盘游戏中均有不错的表现。

但是有些时候会有非常差的结果，也就是说不能有健壮的结果。

这里也从实验上证明了为什么需要本文提出的一系列方法。

今天我为你讲了NIPS二零一七的第三篇最佳研究论文文章的一个核心观点，就是希望能够通过构建蓝图来引导我们解决非完美信息博弈的问题。

特别是现在在扑克上面的应题一起来回顾一下要点。

第一，我们简要介绍了这篇文章的作者群信息。

第二，我们详细介绍了这篇文章要解决的问题以及贡献。

第三，我们简要的介绍到了文章的实验结果，最后给你留一个思考题。

为什么非完美博弈的整个问题求解？现在并没有依靠深度加强学习呢？大家在这个问题上有什么直观上的体会呢？欢迎你给我留言，和我一起讨论。