Science论文详解击败德扑职业玩家的DeepStack,Nature探讨其与Libratus的优劣

在顶级职业德州扑克比赛上,人类已经败北,这可算得上今年人工智能领域的第一个大事件,参看机器之心的报道《 德扑人机大战收官,Libratus 击败世界顶尖扑克选手》和《新论文提出玩扑克人工智能 DeepStack:已达职业玩家水平》。今天早些时候,关于 DeepStack 的正式论文终于在顶级刊物 Science 的网站上发布,同时也得到了 Nature、科学美国人和 IEEE Spectrum 等众多科学和科技平台的关注和传播。机器之心在此编译了 Nature 的相关介绍文章,并在文后附上了 Science 上最新版论文的摘要介绍。原论文可点击阅读原文查阅。


在无限制德州扑克上,人类顶级职业玩家已被人工智能 bot 击败。


德州扑克这种复杂的扑克游戏已经被人工智能(AI)掌握。而且这个游戏还不是被征服了一次——两个不同的研究团队所开发的 bot 都在一对一德州扑克比赛上完成了击败人类的壮举。真希望看到它们互相对战一场!


首先完成这一胜利的 Bot 是阿尔伯塔大学的计算机科学家开发的 DeepStack,该成果的成功背后还有来自捷克的查尔斯大学和布拉格捷克理工大学的帮助。一个月后,卡内基梅隆大学所开发的 Libratus 又再次在与人类的比赛中取得了胜利。


过去十年来,这些团队一直在互相激励打造更好的 Bot,现在 DeepStack 背后的团队将其人工智能的细节正式发表到了 Science 上。Nature 在这篇文章中对这两个人工智能的原理进行了介绍,并探讨了这对在线赌博的意义以及人工智能还有什么尚未征服的目标。


为什么人工智能研究者应该关心扑克?


人工智能已经掌握了好几种棋盘游戏,包括国际象棋以及战略极其复杂的围棋。不过,扑克不同于这类游戏的关键之处在于其增加了复杂性:玩家必须在信息不完全的前提下,算出对手的策略。他们必须考虑对手手中会有什么牌以及对手会如何根据之前下的注猜测自己。


这种「不完美信息(imperfect information)」类博弈能反应真实生活我们的问题解决场景,诸如拍卖以及金融谈判,扑克也成为这些场景的人工智能测试平台。


算法已经破解了更加简单的扑克形式:2015 年,该阿尔伯塔大学团队就已经解决了有限双人扑克难题。DeepStack 和 Libratus 玩的仍然是双人博弈,但却是无限制规则,对于人工智能来说,这个挑战会困难得多。


人类与人工智能交战情况如何?


去年 11 月初的四周里,DeepStack 击败了 11 位职业选手中的 10 位,统计上,赢的优势很大,与每位对手玩了 3000 手。


然后,今年 1 月份,Libratus 击败了四个更加优秀的职业选手(专家级扑克玩家),总体交收 12 万多手。计算机最后赢得约为 180 万美元的筹码。


算法背后的数学原理是什么?


博弈论(game theory)。不论对手选择哪个策略,这两个人工智能系统都旨在搜寻一个能保证不会产生损失的策略。因为一对一扑克是零和游戏,这也就意味着一个博弈方的损失就是其对手的获利,博弈论证明了这种最优决策是经常存在的。而人类玩家可能会利用弱对手的错误获得更大的收益,但使用这种策略对人工智能不会奏效,它仅仅只是为了胜利而博弈。这也就意味着它并不会被对手故意夸张的行为吓住。


以前的扑克游戏的算法一般都试图提前制定出策略,通过计算大规模的「博弈树」而找到游戏可能展开的不同方式及其所有解决方案。但是这种算法所寻找到的展开可能性数量是十分巨大的,而要将这 10^160 次方可能性进行映射是不可能的。所以研究者决定使用更少的可能性解决问题。在一个博弈中,算法会将现场的情况与先前的计算情况相比较。然后算法会找到最接近的一个并从表中「转换」相应的动作。


然而,现在 DeepStack 和 Libratus 都找到了实时计算解决方案的方法,就如同下象棋和围棋的电脑一般。


如何比较这两个人工智能?


DeepStack 会在游戏的每一个节点重新计算一小段可能性的树,而不是提前算出整个博弈树。


开发者利用深度学习创造了这一方法,这种技术利用了一种受到大脑启发的名叫神经网络的架构(正是在这种架构的帮助下,计算机才打败了一位世界上最顶尖的围棋棋手)。


自己玩了 1100 万种游戏场景,并且在每一个场景中进行学习,DeepStack 在游戏中已经获得了一种在某个给定点获胜可能性的「直觉」。这让它可以在相对较短的时间内(大约 5 秒)进行更少的可能性计算,并作出实时决策。


Libratus 的团队目前还没有公布它们的方法,所以这一程序是如何运作的还尚不清楚。但我们早知道的是,它使用了预先计算可能性和「转化」的方法,虽然它在游戏出现更多信息的时候会改进策略。但另一方面,随着可能的结果范围变得越来越窄,算法也可以实时计算出解决方法。


Libratus 也有一个学习元素。其开发者为其加入了一个自我提升的模块,其可以自动分析该 Bot 的玩牌策略,从而可以了解一个对手会如何利用它的缺点。然后它们使用这些信息来永久性地修补这些漏洞。


这两种方法需要明显不同的计算能力:DeepStack 的训练使用了 175 个 core years——相当于运行一个处理单元 150 年或运行几百台计算机几个月。而在比赛过程中,它可以在单一一台笔记本上工作。而 Libratus 则相反,在比赛之前和比赛过程中都使用了一台超级计算机,相当于大约 2900 个 core years。


它们会 bluff 吗?


会。人们时常以为唬牌是人类技能,但是,对一台计算机来说,读不读懂对手没啥关系,它们要做的就是处理博弈背后的数学原理。bluff 主要是 一种策略,确保玩家的下注模式不会让对手发现他们手里的牌。

  

好吧,哪个结果更亮眼?


主要看你问谁了。专家可能会在方法的错综复杂之处含糊其辞,但是,总体上这两个人工智能系统都已经玩了足够多的牌,取得了统计学上显著的胜利——而且对手都是职业玩家。


Libratus 玩了更多手,但是,DeepStack 没这个必要,因为它的团队使用了成熟的统计方法,这个方法能够从较少的博弈中证实比赛结果。较之 DeepStack,Libratus 击败了优秀得多的职业选手,不过 平均说来,DeepStack 赢得的优势更大。


两个人工智能系统会一较高下吗?


或许吧。比较棘手的一点就是计算能力存在较大差别,因此会影响游戏速度。我们很难找到双方都赞同的游戏规则。


阿尔伯塔大学计算机科学家 Michael Bowling、DeepStack 的研发者之一说他的团队打算与 Libratus 比赛。不过,Libratus 的研发、 CMU 的 Tuomas Sandholm 说,他们想先看看 DeepStack 击败 Baby Tartanian 8——他们团队较早的人工智能系统,能力也弱一些。

Bowling 强调,需要注意的是:胜者或许并不意味着它是更好的机器人程序。虽然大家都在尽力让比赛完美,但是,最接近完美的策略并不总是会在正面交锋中出现。一方可能会偶然击中对方的策略漏洞,但是,这并不意味着整体策略上也有更多或更大的漏洞。除非一个团队以明显优势胜,Bowling 说,「我的感觉是它不会像人类期望的那样博闻强识。」


在线扑克是不是没得玩儿了?


不会。虽然顶级玩家已经开始训练对抗机器,但是,许多在线扑克赌场仍然禁止玩家在比赛中使用机器人。


既然计算机又实现了一个征服人类的里程碑,接下来又该征服啥了?


还有几座高山等着我们呢。还有许多没被征服的游戏,比如桥牌,它的规则复杂多了,因此目标也不那么明确了。


接下来,两个团队自然是要征服多人扑克。这意味着大家几乎要从头开始,因为零和博弈理论并不适用它们:在三人扑克游戏中,对手的一个烂招会间接阻碍另一个玩家,并非总是对对方有利。


但是,深度学习的直觉或许能帮助我们找到解决方法,即使在博弈理论并不适用的场景中,Bowling 说。他的团队率先试着将类似的办法应用到三人版的有限德扑中,他介绍说,结果发现,效果好得让人惊讶。


另一个挑战是训练人工智能玩游戏,但并不告诉它们游戏规则,而是随着游戏的进行,让系统自己发现规则。这一场景更加真实反映出真实世界的问题解决情况。


终极测试会是研究出不完全信息算法,使其能利用不完全信息来帮助解决杂乱无章的真实问题难题,比如金融和网络安全。


以下为发表在Science上的论文的摘要介绍


2-1.jpg

摘要


近些年来,人工智能领域出现了很多突破,其中游戏往往被用作重要的里程碑。过去实现那些成功的游戏的一个常见的特征是它们都具有完美信息(perfect information)的性质。扑克是一个典型的不完美信息(imperfect information)游戏,而且其一直以来都是人工智能领域内的一个难题。在这篇论文中,我们介绍了 DeepStack,这是一种用于扑克这样的不完美信息环境的新算法。它结合了回归推理(recursive reasoning)来处理信息不对称性,还结合了分解(decomposition)来将计算集中到相关的决策上,以及一种形式的直觉(intuition)——该直觉可以使用深度学习进行自我玩牌而自动学习到。在一项涉及到 44000 手扑克的研究中,DeepStack 在一对一无限制德州扑克(heads-up no-limit Texas hold'em)上击败了职业扑克玩家。这种方法在理论上是可靠的,并且在实践中也能得出比之前的方法更难以被利用的策略。


论文提纲:


DeepStack 


1、持续解决(Continual re-solving)

2、通过直觉实现有限深度的前瞻(Limited depth lookahead via intuition)

3、合理推理(Sound reasoning)

4、解析前瞻树(Sparse lookahead trees)

5、与完美信息游戏中启发式搜索的关系(Relationship to heuristic search in perfect information games)

6、与基于抽象的方法的关系(Relationship to abstraction-based approaches)


深度反事实价值网络(Deep counterfactual value networks)


1、架构(Architecture)

2、训练(trainning)


评估 DeepStack


1、开发度(Exploitability)


讨论


DeepStack 是一种可用于一个很大类别的序列不完美信息博弈(sequential imperfect information games)的通用算法。为了明晰这个算法,我们将会在 HUNL 游戏中描述其运算。一个扑克游戏的状态可以被分成玩家的私有信息(两张牌面朝下的手牌)和公共状态(包括牌面朝上的牌和玩家采取的下注动作序列)。游戏中的公开状态的可能序列构成一个公开树(public tree),其中每一个公开状态都有一个相关的公开子树(public subtree)。


2-2.jpg

图 1:HUNL 中公开树的一部分。红色和天蓝色的边表示玩家动作。绿色边表示公开的公共牌。带有筹码的叶节点表示游戏结束,其中,如果一个玩家根据之前的动作和玩家手牌的联合分布而弃牌或做出决定,那么收益就可能是固定的。


2-3.jpg

图 2:DeepStack 架构概览。(A)DeepStack 在公共树(public tree)中的推理,该树总是会为一个公开状态(public state)中其持有的所有牌得出动作概率(action probabilities)。它在玩牌时维持着两个向量:它自己的范围和其对手的反事实价值(counterfactual values)。随着该游戏的进行,它自己的范围会在其采取了一个动作之后使用其所计算出的动作概率来通过贝叶斯规则进行更新。对手反事实价值会如在「Continual re-solving」中所讨论的那样被更新。为了在其必须采取动作时计算出动作概率,它会使用其范围和对手反事实价值来执行一个 re-solve。为了使该 re-solve 可以实现,它限制了玩家的可用动作,且前瞻预测也被限制到了这一轮的结束。在 re-solve 期间,其会使用 DeepStack 所学习到的评估函数来近似用于其前瞻之外的公开状态的反事实价值。(B)该评估函数被表示成了一个神经网络,该网络以当前迭代的公开状态和范围作为输入,然后输出两个玩家的反事实价值。(C)在比赛之前,该神经网络通过生成随机扑克情景(底池大小、台面上的牌和范围)来进行训练,然后解决它们以生成训练样本。完整的伪代码见算法 S1。


2-4.jpg

算法 S1:Depth-limited continual re-solving


2-5.jpg

图 3:深度反事实价值网络(Deep counterfactual value networks)。该网络的输入包括底池大小、公共牌、手牌范围(player ranges),这些首先会被处理成 hand clusters。来自这 7 层全连接隐藏层的输出还要经过后处理(post-processed),从而保证该值(values)满足零和约束(zero-sum constraint),然后这些值又会回过来被映射为 hand counterfactual values。


2-6.jpg

图 4:职业扑克玩家与 DeepStack 对战的表现。以 95% 的置信区间用 AIVAT 估计的表现。下面的柱状图给出了参与者完成的比赛的数量。


入门机器人理论论文人机大战DeepStack
返回顶部