幸运彩票:德扑AI之父解答Libratus的13个疑问:没有用到任何深度

德扑AI之父解答Libratus的13个疑问:没有用到任何深度学习,DL远非AI的全部

AI 科技评论按:昨天晚上,卡耐基梅隆大学计算机系在读博士生 Noam Brown 和计算机系教授 Tuomas Sandholm 来到 reddit 的机器学习分版,和网友们一起来了一场「你问我答」(ask me anything)。这两个名字大家现在也比较眼熟了,他们就是今年早些时候在人机大赛中首次打败职业扑克选手的 AI「冷扑大师」(Libratus)的创造者。

具体来说,在持续了 20 天、4 位人类职业选手分别上阵的十二万手一对一无限注德州扑克中,四位职业选手一共输给「冷扑大师」1766250 分,单独来看每个人类选手也都负于 AI。(如下图)

Noam Brown 和 Tuomas Sandholm 两位撰写的介绍这个 AI 中核心技术的论文《Safe and Nested Subgame Solving for Imperfect-Information Games》(在不完全信息博弈中安全、嵌套地求解子博弈)已经被评选为 NIPS 2017的最佳论文,雷锋字幕组也翻译了作者们的论文介绍视频。而且就在这两天,两位作者的新论文已经发表在《Science》,其中介绍了关于整个 AI 的更多细节。

借着 NIPS 2017 论文被关注,以及 AI 的更多细节发表在《Science》的机会,Noam Brown 和 Tuomas Sandholm 教授两位作者就来到 reddit 与网友们进行这次「你问我答」,回答网友们提出的关于「冷扑大师」、这次比赛、人工智能领域、不完全信息博弈、卡耐基梅隆大学、在读博士生或者教授的学术生活等等各种问题。

以下 AI 科技评论精选了一些热门问答呈现给大家

这次的比赛是一对一的,你们打算做一个能玩 6 人局比赛的 AI 吗?

Noam Brown  简单来说,目前看来我们提出的技术在 6 人局里也有很好的实战效果(表现超过人类)。我觉得多于 3 个玩家参与的游戏是确实有一定技术挑战的,但扑克这个领域里体现得不明显。别的一些游戏更适合做多玩家参与的 AI 的研究。

下面仔细解释下:多于两个玩家参与的游戏对现有技术提出了很多有趣的理论和实践方面的挑战。对于博弈论的初学者来说,如果要估计一个纳什均衡,从计算角度讲已经变得很低效了。即便找到了一个,这也不一定是你想要执行的玩法。在两个玩家参与的零和博弈中,不管你的对手怎么做,纳什均衡都可以保证你的期望是「不会输」。然而在三个玩家及以上的博弈中就不会发生这样的事情了,即便你达成了纳什均衡,你还是可能会输。所以我们需要新的技术才能处理三个玩家及以上的博弈,而且需要考虑如何在这样的博弈中评价 AI 的表现。

话虽这样说,但目前我们在一对一 AI 中所用的技巧,看起来在三个玩家及以上的扑克中也有很好的实战表现。这件事有两个主要原因:

1,在玩扑克的时候,人类很快就会弃牌,所以实际比赛中,大多数手牌很快就变成了一对一比赛。

2,玩扑克的时候,玩家之间基本上没有什么机会合作,你没办法和一个玩家组队攻击另一个玩家。真的尝试这样做的话(玩家间串通),就会违反游戏规则。

由于这两个原因,我认识的开发训练用途的 AI(以及训练 AI 的工具)的人告诉我这些技巧在 6 人局的德扑比赛里也有很好的表现,而且基本上每种能在网上玩的扑克类型,现在都是有超过人类水平的 AI 的。说到底,达成有意义的 6 人局比赛可行性很低,因为很难避免人类玩家之间串通起来对抗 AI(即便他们是无意识的)。

有没有什么办法,尽量小地修改扑克的玩法,同时把它变成 AI 玩不了的游戏?

Noam Brown  这个问题非常好!根据我和这个领域其它的人工智能开发者一起的研究和讨论,我们认为目前所有的扑克玩法都可以找到超越人类水平的 AI。即便是奥马哈扑克、9 个人玩的奥马哈扑克也不能阻止 AI 胜过人类。

如果要让 AI 搞不定某个游戏,有一个很有可能会起到很大作用的要素,就是在游戏中引进某些半合作机制,比如《Settlers of Catan》中的买卖和《Diplomacy》中的谈判。所以可能在游戏规则里加一条可以和其它玩家换牌?当然了,真要是这么改了,这还算不算是扑克都不好说了。

目前来讲还没有找到什么成功的理论方法可以解决半合作游戏。我觉得这将是未来研究的重要方向之一,而我们真正看到这类游戏中的良好表现也至少还需要好几年的时间。

参加比赛的职业选手们如何评价「冷扑大师」的牌技?有没有什么很有趣或者很惊人的特点?

Noam Brown  简单说几条:

  1.  AI 可以使用各种不同的下注大小,而且可以高效地在它们之间做出取舍。人类玩家通常只用一到两种下注大小。

  2. AI 会使用一个混合策略(对于不同的可能性采取不同的行动),而人类玩家倾向于单独使用某一种策略。所以局面复杂的时候人类玩家会觉得非常难以估计 AI 所处的状况,因为 AI 各种行为都做得出来。

  3.  AI 用了很多不常见的下注大小。具体来说,下很大的注会给人类选手带来很大的压力。我从好几个职业牌手那里听说,在这场比赛之后顶级选手之间也开始更多地出现这种做法,很大程度上和「冷扑大师」用很大的下注大小取得了不小的成功有关系。

AlphaZero 和「冷扑大师」的泛化性谁高谁低?

Tuomas 幸运彩票 Sandholm 教授  AlphaZero 是为完全信息博弈设计的(比如围棋、国际象棋),而冷扑大师是为不完全信息博弈设计的。这是非常大的一个区别。在不完全信息博弈中,有一部分信息是没有对所有玩家公开的,比如,谈判时谈判者的个人偏好、扑克中玩家的手牌、拍卖时参与者心中的价值函数、网络安全攻防中某一方被泄露出的零日漏洞,等等。多数真实世界中人和人之间的互动过程都是不完全信息博弈。

对于给定的博弈大小,不完全信息博弈解决起来要难得多,因为玩家需要在不同的子博弈间寻找平衡。比如在扑克中,玩家不应该总是看到好牌就加注、看到差牌就弃牌。相比之下,在完全信息博弈中,要解决一个子博弈,只需要那个子博弈中的信息就够了,而且不需要与其它的子博弈之间作取舍。

现在,在我们的 NIPS 论文和《Science》论文中,我们已经阐述了理论上非常有力的不完全信息博弈中的子博弈解决方法。这些方法中借助对整个博弈的策略蓝本得出不同子博弈的值,然后也就是依靠这些值在不同的子博弈之间取得平衡。

「冷扑大师」没有使用深度学习啊。这是你们有意识地选的吗?还是说到了最后发现反正没用上?你们有没有试过,效果不好吗?以及,现在我们都知道了另一个用了神经网络的扑克 AI DeepStack 表现如何。如果回过头重新考虑一下,你们有可能用神经网络吗?

Noam Brown  对,「冷扑大师」没有用到任何深度学习。我们希望这能告诉人们深度学习远远不是人工智能的全部。只靠深度学习自己,还不足以玩好扑克这样的游戏。

不过,我们开发出的这些技术也是和深度学习兼容的。我觉得它们更像是蒙特卡洛树搜索的一个替代选择。对于解决扑克这样的游戏,深度学习的必要性不是很高。但是我觉得在其它一些游戏中,某种形式的价值函数幸运彩票选号近似会有很大的帮助。

DeepStack 用的是深度学习,但是目前还不清楚它的效率高到什么程度。比如它并没有连续击败之前的顶级扑克 AI。我觉得 DeepStack 的实际表现还不错的原因是它也用了嵌套子博弈求解,他们团队和我们团队各自同时开发了相关的技术。这件事不需要深度学习。「冷扑大师」的嵌套子策略求解方法比他们的更高级一点,再加上其它方面的一些优势,最终让我们达成了很强力的表现。

DeepStack 2017 年 5 月就在《Science》发表了论文,你们发表论文的 NIPS 2017 则是在 12 月了,那么是谁先做出来的?可以做一下对比吗?你们和其它的研究团队有合作吗?

Tuomas Sandholm 教授  DeepStack 的方法确实有自己的有意思的地方,不过我赞同网友 LetterRip 对它的评价(「冷扑大师肯定可以碾压 DeepStack,两个 AI 面对的选手的质量简直天上地下。DeepStack 比赛中遇到的职业扑克选手多数都很弱,虽然也有几个非常厉害的,但没有一个是算得上顶级选手的。另外,比赛设定里只有人类选手的第一名有奖金,这其实是在鼓励不常见的玩法」)。

下面我来谈谈两个 AI 之间的异同点。同时我推荐大家读读我们刚刚发表在《Science》上的论文,其中详细介绍「冷扑大师」同时也和 DeepStack 做了对比。

DeepStack 中的算法和「冷扑大师」的嵌套子策略求解很相似,他们称之为连续重新求解。在冷扑大师中它的工作方式是,剩余的子博弈在抽象提取、求解时,也会加上对手的确切下注数目。我们的论文 2016 年 10 月就在网上发布了,2017 年 2 月也参加了 AAAI2017 的一个 workshop;DeepStack 的论文是 2017 年 1 月上传到 arXiv 的(投稿给《Science》的时间是 2017 年春末)。考虑到开发这些技术需要很长的时间,我觉得我们两个幸运彩票团队都在此之前就花了好几个月做研究,说「这些方法是两个团队分别开发但时间上同步」是没什么问题的。并且,两个团队的方法也有很大的区别。「冷扑大师」的子策略求解方法至少在下面几个方面都更先进,在我们的《Science》论文中也有详细的解释:

  • 「冷扑大师」中改进了手牌的处理方法,降低了只有当对手犯过错误之后持有的手牌的看重程度;DeepStack 中就没有这一项。

  • DeepStack 中对于不同手的牌,子博弈行为的抽象不会发生改变

  • 我们有许多不依赖算法的均衡搜索方法可以保证安全性,我们的子策略求解也是接近安全的,这在我们的《Science》论文和 NIPS2017 论文中都有讲到

另外还有一个区别是两个 AI 是如何处理前两轮下注的。DeepStack 会在前两轮下注中求解一个有限深度的子博弈,而这个深度值的估计是通过神经网络做出的。这就让它总是可以实时计算如何应对对手做出的预测树之外的行为。而「冷扑大师」只在前两轮中做短暂的计算,然后根据提前算好的策略蓝本向下执行(如果赌注很高了就会用自己的子博弈求解器)。由于「冷扑大师」是根据前两轮下注时提前计算好的策略蓝本执行的,它会把对手做出的策略树之外的下注大小约等到某个相近的、已经经过抽象的行为上去。这几轮中的行为蓝本抽象就有很高的密度,就是为了改善这个问题。另外,「冷扑大师」有一个独特的自我学习模块,可以随着时间逐渐增强策略蓝本的计算水平,对于部分博弈树中对手有可能在它的策略中发现潜在的漏洞的时候,它可以计算出更接近纳什均衡的近似解。

在表现评估方面,除了刚才 LetterRip 写的与人类选手对局中体现的之外,DeepStack 也从未表示过自己可以在正面交锋中打败在此之前就已公开的各个顶级扑克 AI,而「冷扑大师」以很大优势击败了此前最好的 HUNL 扑克 AI Baby Tartanian8(它是 2016 年计算机扑克大赛的冠军)。

至于合作,我们两个研究团队一直都在发表自己的工作、也一直学习借鉴对方的技巧,这已经有 13 年的时间了。另外,加拿大扑克社团的负责人 Michael Bowling 就是在 CMU 拿到他的博士学位的,我就是他的学位评审委员会成员之一。不过,我们目前还没有过任何直接的合作。

如果有人在超级计算机上跑一个超大规模的 PIO 求解器,这种做法和你们的软件区别在哪里?

Noam Brown 「冷扑大师」中的做法比 PIO 求解器不知道高明到哪里去了。下面我列举几个原因说明为什么在这种比赛中 PIO 求解器一点都不好使:

  1. PIO 求解器需要有一个人类输入双方的信念分布。「冷扑大师」完全是靠自己判断这些信息的。

  2. PIO 求解器是可以欺骗的,可以故意做一些均衡中出现概率为 0 的行为。比如如果你下注了 10%,并且 PIO 求解器认为这种情况不可能发生的话,那么它对你手牌的信念分布就是未经定义的,然后就会给出不合理的答案。我觉得 PIO 是一个很明显的反面例子,提醒我们当对手做了「奇怪」的事情的时候不要完全相信他。同样明显的是,如果你和顶级人类选手对局,而他们想要发现你的 AI 的弱点,这就肯定会出现严重的问题。「冷扑大师」就不会有这些问题。即便对手做出了在均衡中理应出现概率为 0 的行为,它也能做出鲁棒的、正确的回应。

可以说说模型中为什么没有加入强化学习吗?强化学习挺配这个问题的。

Noam Brown  我们在「冷扑大师」中使用了反事实遗憾最小化(CFR)的一种变体。具体来说,我们用了蒙特卡洛 CFR 计算策略蓝本,然后用 CFR+ 处理实时的子博弈求解。

CFR 就是一种自我对弈的算法,和强化学习有点类似,但是 CFR 会更多地考虑自我对局中没有选择的那些选择,假设选了以后会有怎么样的投入产出。完全像强化学习一样的 CFR 变体也是有的,不过实际应用中总是要花更长时间才能找到好的策略。

我听说上一次「Claudico」人工智能对阵人类输的一败涂地,那么从「Claudico」到「冷扑大师」,都做出了哪些改进或者调整?「Claudico」被打败的事情是不是对「冷扑大师」的成功有很大的启发?

Tuomas Sandholm 教授  2015年的时候,Claudico 对阵人类输了每一百手 9 盲注,而「冷扑大师」以每一百手 15 盲注胜出了人类。「冷扑大师」在以下三个方面都编写了新的算法:

  1.  新的、更好的平衡搜索算法,用来在比赛开始前计算策略蓝本

  2.  新的子博弈求解方法,这次的方法是安全的、嵌套的。Claudico 中的残局求解器既不安全,也不嵌套。

  3.  一个自我学习模块,可以随着时间逐渐增强策略蓝本的计算水平,对于部分博弈树中对手有可能在它的策略中发现潜在的漏洞的时候,它可以计算出更接近纳什均衡的近似解。

「冷扑大师」已经很厉害了,可以打败人类职业选手。但是根据我的理解,它还不是「不可战胜」的,也许过几年还会出现可以打败「冷扑大师」的 AI。那么「冷扑大师」距离能玩出完美的扑克的 AI 还有多远?

Noam Brown  我觉得各种主流的无限制德州扑克玩法里,要说达到一个完美的、理论上不可能被打败的策略,是做不到的一件事。游戏的可能性就是太多了。有没有激励研发更好的德扑 AI 也难说,现在 AI 已经在这些游戏里超越人类了,我觉得整个研究领域更可能转向其它还没有解决的游戏中。

你们接下来计划研究哪些任务/游戏?

Noam Brown  有意思的方向有很多!我们目前还没决定下来。

有一种非常有意思的研究路线是「半合作博弈」,比如谈判。在这里,玩家们有激励一同合作,但同时每个人也都想达到自己的个人效用最大化。现有的技术在这类博弈中根本无效,所以还有很多有意思的研究等待大家去做。带有这种特性的休闲游戏有很多,比如《Settlers of Catan》(买卖)和《Diplomacy》(谈判)。

Dota2 和星际争霸这样的 RTS 游戏也是非常有意思的研究领域,它们也是不完全信息博弈,那么如果想要研究一个难以捉摸、但总是可以击败顶尖人类选手的 AI 的话,我们在扑克方面做的研究全都可以起到帮助。

我觉得还有一个问题很有意思,就是如何缩小游戏 AI 之间的差距,比如 AlphaZero 和「冷扑大师」之间的差距。现在,想要解决围棋和国际象棋,我们有一组很棒的方法;要解决扑克这样的游戏,我们有另一组很棒的办法;但最好的情况当然是我们用一个算法就可以解决所有这些游戏。现有的不同游戏的解决方案之间有巨大的差别,如何缩小差距目前也没有明确的答案。

对于目前的算术方法博弈论,你们觉得有哪些有意思的研究方向?

Tuomas Sandholm 教授  有趣的问题有很多,整个领域也非常活跃。以我个人来讲,我最喜欢有这些特点的研究工作:1. 针对实际问题,而不是高度简化的抽象模型,这类问题也就通常需要真实世界的数据;2,研究那些如果理论研究部分得到了成果,就能对真实世界有许多正面影响的问题。

我自己特别喜欢的所以动手在研究的方向有这么几个:

  • 不完全信息博弈中的博弈理论求解以及利用对手。在我的 CMU 实验室和创业公司 Strategic Machine 中,我都在做这方面的研究。

  • 自动规则设计 (比如通过数据对多物品、多买家的拍卖场景做定制化的拍卖设计)

  • 肾移植(我的 CMU 实验室中的 AI 负责 UNOS 的国家肾交换中心;这个交换中心下属有 159 个移植中心)

  • 多种市场问题的组合优化。我在我的 CMU 实验室和一个我创立的广告宣传公司 Optimized Markets 中做这方面的研究。

你们觉得这种方法拿到产业界来的话,最相符的应用是什么?比如说你们觉得你们的方法可以用来为贸易协商建模吗?另外,目前来看「冷扑大师」还是需要运行在超计算机上的,有没有可能把它改进得更高效一点,一般的电脑或者服务器就可以运行?

Noam Brown  对于「让 AI 进入真实世界」这个目标,我觉得我们的研究至关重要,因为多数真实世界中的策略互动问题都多多少少有一些信息是隐藏的。我们在这项研究中想要解决的根本问题也就是这个。贸易协商肯定可以是未来的应用方式之一,其它还可以有拍卖、金融市场、信息安全互动以及军事行动相关。

话虽这样说,但是想要从扑克这样的所有行为、成本、收益都定义好的游戏拓展到定义得不那么明确的真实世界互动中的话,我们还面临着相当大的挑战。不过只要有人能够提出一个贸易协商的模型,我们这次的研究成果肯定可以用在里面。这也会是未来研究中的一个有意思的方向。

是的我们觉得做一个能运行在一般电脑和服务器上、然后稍微弱一点的版本是做得到的。我也觉得随着算法的不断升级改进,达到同样的表现所需要的硬件性能也会越来越低。我觉得可能 5 年以后就能在智能手机上见到这个水平的人工智能了。


这次关于德扑 AI AMA 的内容就介绍到这里。我们也期待更多更接近现实生活的问题被人工智能逐一解决。via Machine Learning@Reddit,(公众号:) AI 科技评论编译。

版权文章,未经授权禁止转载。详情见转载须知。