您的位置:首页 >国际 >

机器学习超越了理论 击败了人类扑克冠军

2019-07-12 15:01:01来源:

如何处理机器学习中理论支持的细分?卡内基梅隆和Facebook的研究人员通过发明智能搜索策略来应对大多数玩游戏AI的理论数学缺乏,从而赢得了许多人对抗世界顶级扑克玩家的手。在近年来机器学习的众多成就中,一些最引人注目的是机器在游戏中对抗人类玩家的胜利,例如谷歌的DeepMind集团在2016年征服Go。在这些里程碑中,研究人员通常以理论数学为指导这表明,鉴于良好的算法和足够的计算,可以找到最佳策略。

但是当理论崩溃时你会怎么做?卡内基梅隆大学和Facebook的两名研究人员回到了绘图板,解决了“单挑无限德州扑克”,这是世界上最受欢迎的多人扑克形式。

理论对于这种形式的纸牌游戏是不可计算的,因此他们为他们的计算机程序“Pluribus”设计了一些优雅的搜索策略,以击败10,000手扑克中最好的人类玩家。作者甚至设法用一个64核的基于英特尔的服务器,只有512千兆字节的RAM,他们指出远远少于越来越大的机器学习模型,如DeepMind的“AlphaZero”,使用大量的计算解决问题。

Pluribus计划不是在玩家之间计算最佳解决方案,而是搜索足够好的解决方案,结果令人惊讶地表现得非常好。这项作品“多人扑克的超人AI”描述了扑克界顶级世界玩家超过12天的比赛,今天发表在“科学”杂志上,由Noam Brown和Tuomas Sandholm撰写。布朗和桑德霍尔姆都与卡内基梅隆大学有联系;Brown还与Facebook AI Research合作,Sandholm与三家Pittsburgh公司,Strategic Machine,Inc.,Strategy Robot,Inc。和Optimized Markets,Inc。有合作关系。

科学杂志已成为机器学习类型的尖端扑克论文的温床,这是布朗和桑德霍尔姆在一年多的时间里第二次亮相。在去年1月,他们发布了一个名为“Libratus”的机器学习模型,可以在德州扑克的双人版本中实现“超人”能力通过Pluribus,作者呈现出多个对手带来的复杂程度;在这种情况下,五个人对抗Pluribus机器。在大多数通过机器学习进行的游戏中,包括Go和双人扑克,有​​一个理论框架,构成了寻找最佳游戏策略的基础。以着名美国数学家约翰·纳什命名的“纳什均衡”说,基于假设游戏中的每个对手都在同样发挥其最佳策略,可以为每个玩家找到最佳游戏策略。

在像岩石,纸张,剪刀这样的简单游戏中,每一轮都可以选择相同的选择,例如岩石,这可能是导致玩家之间达到平衡的最佳策略。

所以制作玩游戏的机器人在某种意义上可以归结为构建一个计算纳什均衡的机器。

问题是,随着游戏复杂性的增加,发现纳什均衡变得越来越强大。近似这种均衡是计算机在实际时限内可以做到的最好的。它适用于多种方法,特别是在双人对决扑克中,这是一种为布朗和桑德霍尔姆与Libratus很好地合作的方法,因为它在阿尔伯塔大学的另一个团队,Moravčik及其同事,他们在2017年为科学德州扑克发布了他们的“DeepStack”机器。

但在多人德州扑克中,纳什均衡在计算上变得棘手。正如作者所写的那样,“理论上甚至接近纳什均衡很难(特殊情况除外),而且在有两个以上玩家的游戏中,即使是最好的完整算法也只能用每个玩家的少数可能策略来解决游戏问题。”

因此,布朗和桑德霍尔姆必须满足机器学习的方法,“不能保证收敛到纳什均衡”。从某种意义上来说,这是对未知事物的一次冒险,但不过有一种胜利:“尽管这些技术在双人零和设置之外的表现上没有强大的理论保证,但他们仍然能够生产更广泛的战略环境中的超人策略。“

Pluribus使用熟悉的Libratus和DeepStack方法来训练机器,称为“反事实后悔最小化”或CFR。在扑克游戏的背景下,行动包括召唤,加注或弃牌,CFR计算每个行动时刻本来可以更好地发挥作用,让计算机对抗自己并分析它的进展有多好或者糟糕的结果是。在任何当前的游戏状态下,训练机器相当于构建一个移动的“蓝图”是高价值的。机器在游戏结束后通过分支轮次移动继续完善这个蓝图。

但是,在动作发生的地方,理论崩溃的地方,就是与人类的现场比赛。因为扑克不像国际象棋或者去,是一个“不完全信息”的游戏 - 对手的牌是隐藏的 - 计算纳什均衡是行不通的,因为对手可以在每次移动时采用不同的策略,所以机器没办法在国际象棋中展望未来。正如作者用技术术语所说,“在不完全信息子游戏(正在进行搜索的游戏部分)中,叶子节点没有固定值。”

为了解决这个问题,Brown和Sandholm提出了他们认为Pluribus在游戏中计算的优秀搜索策略。假设四种可能性,机器搜索对手的多种可能的策略变化:对手坚持到目前为止的策略,或者他们追求三种可能的策略中的一种,这些策略偏向于呼叫,加注或折叠。

他们还让机器根据到那个时间点的游戏动作来计算其他玩家可能认为Pluribus手中的东西。这是让Pluribus改变战略以使对手失去平衡的一种方式。正如作者所写的那样,“无论Pluribus持有哪只手,它都将首先计算出它将如何与每一只可能的牌一起动作,小心平衡其所有牌局的策略以保持对手无法预测。”

机器学习,任务自动化和机器人技术已经广泛应用于商业领域。这些和其他人工智能技术即将繁衍,我们将研究组织如何最好地利用它们。

在这方面的搜索方法不同于其他服装与纳什均衡难度的竞争方式。例如,DeepMind在制作战略视频游戏“星际争霸”的人类玩家的“AlphaStar”机器时,不能依赖于DeepMind的AlphaZero使用的相同技术。在国际象棋和国际象棋中,人们可以近似纳什均衡,因为人们可以假设两个对手,他们各自优化各自的策略,同时考虑到对方的优化。但星际争霸是所谓的非传递性游戏,意味着没有一致的对手可以优化。DeepMind解决这个问题的方法是扩展搜索“空间”,如果你愿意,可以寻找最佳动作,即所谓的“多面体”。

以这种方式扩展搜索空间最终会带来更多的计算需求,而Brown和Sandholm很自豪他们的工作可以最大限度地减少实际的计算需求。虽然Pluribus的培训是在64核服务器上进行的,但是针对人类的实时游戏玩法是在具有“两个Intel Haswell E5-2695 v3 CPU且使用少于128 GB内存的计算机”上进行的。

正如他们在博客文章中指出的那样,在云计算设施中培训的成本约为150美元。他们写道:“这与其他最近的人工智能突破形成了鲜明的对比,其中包括那些涉及游戏自我游戏的突破,通常需要花费数百万美元进行训练。”

事实证明,这样的智能搜索技术在实践中做得很好,即使没有融入纳什均衡。作者没有透露Pluribus在10,000手牌中赢了多少人。但在与ZDNet的后续电子邮件中,诺姆·布朗解释说重要的是机器的平均奖金。

Pluribus“长期以来令人信服地赢得了胜利”,这是布朗所描述的。

“考虑机器人的表现的另一种方式是,如果它与这些人类专业人士玩钱,那将会赢得什么,”布朗继续说道。“与一些世界上最优秀的人类专业人士一起玩数千手牌 - 每个人都赢得了至少100万美元的扑克玩家 - 机器人领先,每小时收入相当于1000美元。”