ACM通信gydF4y2Ba

研究突出了gydF4y2Ba

人头限时扑克解决了gydF4y2Ba

作者:Michael Bowling, Neil Burch, Michael Johanson, Oskari TammelingydF4y2Ba
ACM通讯，2017年11月，第60卷第11期，第81-88页gydF4y2Ba
10.1145 / 3131284gydF4y2Ba
评论gydF4y2Ba

扑克是一种呈现不完全信息的游戏，玩家对过去的事件并不完全了解。虽然已经解决了许多完美信息博弈(例如，四连和西洋跳棋)，但人类进行的非微不足道的不完美信息博弈并没有被解决。在本文中，我们宣布，扑克游戏中的最小变体，抬头限制德州扑克，现在基本上是弱解。此外，这种计算形式上证明了一个常识，即庄家在游戏中拥有显著优势。这个结果是通过一个新的算法CFR实现的gydF4y2Ba^+gydF4y2Ba，它能够解决比以前大3个数量级的广泛形式的游戏。本文是2015年原始论文的扩展版gydF4y2Ba科学gydF4y2Ba文章中,gydF4y2Ba^9gydF4y2Ba附加的结果显示了“仙王座”在游戏中对电脑和人类对手的表现。gydF4y2Ba

回到顶部gydF4y2Ba

1.简介gydF4y2Ba

游戏与最早的计算、博弈论和人工智能(AI)发展密不可分。在计算的概念诞生之初，巴贝奇就制定了详细的计划，要制造一个能够玩井字游戏的“自动机器”，并梦想着他的分析引擎能下国际象棋。gydF4y2Ba^4gydF4y2Ba阿兰·图灵都gydF4y2Ba^46gydF4y2Ba克劳德·香农,gydF4y2Ba^40gydF4y2Ba分别在纸上和硬件上开发下棋程序，以验证早期计算和人工智能的想法。半个多世纪以来，游戏一直是新想法的试验台，由此产生的成功标志着人工智能进步的里程碑:例如，会下跳棋的计算机程序奇努克成为第一个战胜人类赢得世界锦标赛冠军的程序，gydF4y2Ba^38gydF4y2Ba深蓝在国际象棋中击败卡斯帕罗夫，gydF4y2Ba^14gydF4y2Ba华生打败了詹宁斯和拉特gydF4y2Ba冒险!gydF4y2Ba^17gydF4y2Ba然而，打败顶级人类玩家并不等同于“解决”游戏，即计算出游戏理论中不会在公平游戏中输给任何对手的最优解决方案。解决游戏也是人工智能发展的里程碑，例如Connect-FourgydF4y2Ba^2gydF4y2Ba和跳棋。gydF4y2Ba^39gydF4y2Ba

迄今为止，人类所玩的每一款具有竞争性的游戏都是一种gydF4y2Ba完美的游戏信息。gydF4y2Ba^{一个gydF4y2Ba}在完美信息博弈中，所有玩家在做出决定之前都知道游戏中发生的一切。国际象棋、西洋跳棋和西洋双陆棋都是完美信息博弈的例子。在gydF4y2Ba不完全信息的游戏gydF4y2Ba在美国，玩家并不总是完全了解过去发生的事情(例如，在桥牌和扑克游戏中给其他玩家的牌，或卖家在拍卖中知道一件物品的价值)。这些游戏更具挑战性，包含理论、计算算法和解决游戏滞后的实例，结果是完美的信息设置。gydF4y2Ba^bgydF4y2Ba虽然完美信息可能是室内游戏的共同属性，但在现实世界的决策设置中却不常见。在布朗科夫斯基讲述的一段对话中，现代博弈论的创始人约翰·冯·诺伊曼(John von Neumann)也有同样的观察，“现实生活不是这样的。真正的生活是由虚张声势、欺骗的小伎俩、自问别人会认为我打算做什么组成的。在我看来，这就是游戏的意义所在。”gydF4y2Ba^12gydF4y2Ba

冯·诺伊曼的声明暗示了典型的不完全信息博弈:扑克博弈。扑克游戏中，每个玩家都会收到一张私人牌，玩家们轮流下注，赌自己手里的牌是否最强(可能是虚张声势)，让对手下注，或者放弃手中的牌。扑克在博弈论的早期发展中发挥了重要作用。波莱尔gydF4y2Ba^7gydF4y2Ba和冯·诺依曼的gydF4y2Ba^{47gydF4y2Ba，gydF4y2Ba48gydF4y2Ba}基础工作的动机是发展扑克中唬人的数学原理，小型合成扑克游戏在许多早期论文中很常见。gydF4y2Ba^{7gydF4y2Ba，gydF4y2Ba29gydF4y2Ba，gydF4y2Ba32gydF4y2Ba，gydF4y2Ba48gydF4y2Ba}扑克也可以说是世界上最受欢迎的纸牌游戏，全球有超过1.5亿玩家。gydF4y2Ba^1gydF4y2Ba如今最流行的扑克形式是德州扑克。如果只有两个人玩(抬头)，并且下注的大小和增加的次数都是固定的(涨停)，这种游戏就被称为“抬头涨停”。gydF4y2Ba^10gydF4y2BaHULHE因为书中记载的一系列高风险游戏而流行起来gydF4y2Ba《教授》、《银行家》和《自杀之王》gydF4y2Ba^16gydF4y2Ba这也是人类竞争扑克的最小变体。呼和浩特有3.16 × 10gydF4y2Ba^17gydF4y2Ba游戏可能达到的状态，使它比Connect 4大，比西洋跳棋小。然而，作为一种不完美的信息游戏，许多这些状态并不能被行为玩家所区分，因为它们包含了关于未见过的过去事件的信息(如给对手的私人纸牌)。因此，游戏的分辨率为3.19 × 10gydF4y2Ba^14gydF4y2Ba玩家需要做出决定的决策点。gydF4y2Ba

虽然HULHE比西洋跳棋小，但其不完全信息的特性使其成为计算机玩或解决更有挑战性的游戏。17年前，奇努克在与世界象棋冠军马里昂•廷斯利的跳棋比赛中首次获胜，17年后，计算机程序“北极星”在与职业扑克玩家的第一次有意义的比赛中获胜。gydF4y2Ba^34gydF4y2BaSchaeffer等人在2007年解决了跳棋，gydF4y2Ba^39gydF4y2Ba抬头限制德州扑克，直到现在，还没有解决。这种缓慢的进展并不是因为缺乏努力。扑克对于人工智能、运筹学和心理学来说都是一个具有挑战性的问题，其研究工作可以追溯到40多年前。gydF4y2Ba^6gydF4y2Ba17年前，科勒和菲佛gydF4y2Ba^28gydF4y2Ba宣称:“我们距离解决大型游戏(如全尺寸扑克游戏)还差得远，而且我们也不太可能做到。”把HULHE作为“全面扑克”的一个例子的关注始于十多年前，gydF4y2Ba^5gydF4y2Ba2006年之后，它成为年度电脑扑克比赛的第一项赛事，成为数十个研究小组和爱好者的焦点，gydF4y2Ba^53gydF4y2Ba与人工智能促进协会(AAAI)主会议同时举行。这篇论文是为了解决“全面”扑克游戏而进行的持续研究的成果。gydF4y2Ba^10gydF4y2Ba

阿莱gydF4y2Ba^3.gydF4y2Ba给出了解决游戏的三种不同定义。一种游戏被称为gydF4y2Ba处理解决gydF4y2Ba如果对于初始位置(s)，博弈论值已经确定;gydF4y2Ba弱了gydF4y2Ba如果对于初始位置，在合理的资源下，一个策略已经确定，对双方参与者至少获得博弈论价值;而且gydF4y2Ba强烈的解决gydF4y2Ba如果对于所有的法律头寸，在合理的资源条件下，双方都确定了一个策略以获得该头寸的博弈论价值。在不完全信息博弈中，超出初始位置的一个位置的博弈理论价值不是唯一的，艾利斯的“强解”概念是没有定义的。此外，由于参与者策略或博弈本身的随机性，不完全信息博弈通常具有真实价值而非离散价值的博弈理论值(如国际象棋和西洋跳棋中的“赢”、“输”和“平”)，并且只能在多次博弈中实现预期。因此，博弈论的值通常是近似的，因此在解决一个博弈论时，一个额外的考虑因素是解决方案的近似程度。游戏所处的自然近似水平gydF4y2Ba本质上解决弱gydF4y2Ba如果一个人的游戏寿命不足以用统计显著性来证明这个策略不是一个精确的解决方案。gydF4y2Ba

在本文中，我们宣布了抬头限制德州扑克本质上是弱解。进一步，我们对博弈的博弈理论值进行了定界，证明了博弈是庄家的赢局博弈。gydF4y2Ba

回到顶部gydF4y2Ba

2.解决不完全信息博弈gydF4y2Ba

不完全信息设置的经典表示是gydF4y2Ba粗放型的游戏。gydF4y2Ba这里的“游戏”一词指的是自利代理之间的正式互动模型，既适用于娱乐游戏，也适用于严肃的努力，如拍卖、谈判和安全。看到gydF4y2Ba图1gydF4y2Ba用于以广泛形式对简单扑克游戏的一部分进行图形描述。广泛形式游戏的核心是gydF4y2Ba博弈树gydF4y2Ba指定可能事件的分支，即玩家行动或机会结果。这棵树的树枝在夜里劈开了gydF4y2Ba游戏状态gydF4y2Ba每个事件都与决定事件结果的玩家(或机会)有关。树的叶子表示游戏的结束，每个玩家都有一个相关的实用程序。与玩家相关的状态被划分为gydF4y2Ba信息集gydF4y2Ba，这是行动玩家无法区分的状态集(例如，对应于对手获得不同私人纸牌的状态)。信息集合中的状态分支是玩家可用的gydF4y2Ba行动。gydF4y2Ba一个gydF4y2Ba策略gydF4y2Ba为玩家指定每个信息，设置可用操作的概率分布。如果博弈恰好有两个参与人，并且每个叶和的效用都为零，那么博弈就会被调用gydF4y2Ba零和。gydF4y2Ba

图1。三卡库恩扑克的广泛形式游戏表现的一部分gydF4y2Ba^29gydF4y2Ba玩家1得到皇后(Q)，对手得到杰克(J)或国王(K)。游戏状态是由玩家在每个状态下的行为标记的圆圈(“c”代表随机选择初始交易)。箭头显示了玩家可以选择的事件，并标有其游戏含义。叶子是正方形的顶点，标记着参与人1的相关效用(参与人2的效用是参与人1的否定)。用粗灰线连接起来的状态属于同一信息集的一部分，也就是说，玩家1无法区分每对中的状态，因为它们代表着发给对手的不同的未观察到的纸牌。参与人2的状态也在信息集中，包含了图中没有显示的其他状态。gydF4y2Ba

经典的游戏解决方案概念是gydF4y2Ba纳什均衡gydF4y2Ba，即每个参与人都不能通过单方面选择不同的策略来增加他们的预期效用。所有有限广义对策至少有一个纳什均衡。在零和博弈中，所有博弈的参与者都有相同的期望效用，这个值叫做gydF4y2Ba博弈理论的价值。gydF4y2Baε-gydF4y2Ba纳什均衡gydF4y2Ba对于每个参与人来说都是一种策略没有人能通过选择不同的策略来增加大于ε的效用。根据艾利斯的分类，计算零和博弈的博弈论值是超弱解，计算纳什均衡策略是弱解。如果ε-纳什均衡计算的ε足够小，在人类玩游戏的一生中统计上与零没有区别，我们就称这个游戏本质上是弱解的。对于完美信息博弈，通常需要对博弈树进行(部分)遍历。然而，同样的技术不能应用于不完美的信息设置。我们简要回顾了在解决不完全信息博弈方面的进展，并根据算法在解决越来越大的合成扑克游戏方面的进展对其进行基准测试gydF4y2Ba图2gydF4y2Ba．gydF4y2Ba

图2。随着时间的推移，不完美信息博弈的规模越来越大。阴影区域指的是在正文中引用的实现结果的技术。CFR+是本工作中使用的算法，虚线表示本文建立的结果。gydF4y2Ba

标准形式的线性规划。gydF4y2Ba解决广义游戏的最早方法是将其转化为gydF4y2Ba标准的游戏gydF4y2Ba，表示为原广义形式博弈中每一对可能的确定性策略的值矩阵，然后用线性规划(LP)求解。不幸的是，可能的确定性策略的数量与博弈的信息集数量呈指数关系。所以，虽然LPs可以处理包含数千种策略的常规游戏，但即使只有几十个决策点，也会使这种方法不切实际。库恩扑克，一种扑克游戏，有三张牌，一个回合，和一个赌注，最多有12个信息集(见gydF4y2Ba图1gydF4y2Ba)，可以用这种方法解决。但即使是勒杜克，gydF4y2Ba^42gydF4y2Ba六张牌，两轮投注，两个赌注最多总共只有288个信息集，超过10个是棘手的gydF4y2Ba^86gydF4y2Ba可能确定的策略。gydF4y2Ba

线性编程排序表。gydF4y2BaRomanovskiigydF4y2Ba^35gydF4y2Ba以及后来的科勒等人。gydF4y2Ba^{26gydF4y2Ba，gydF4y2Ba27gydF4y2Ba}建立了解决不完全信息博弈的现代时代，引入了策略的序列形式表示。通过这一简单的变量变化，他们表明，广泛形式的博弈可以直接作为LP解决，而不需要指数转换到常态形式。序列形式线性规划(Sequence-Form Linear Program, SFLP)是第一个求解不完全信息广泛形式博弈的算法，其计算时间增长为博弈表示大小的多项式。2003年，比林斯等人。gydF4y2Ba^5gydF4y2Ba将此技术应用于扑克，求解了一套简化的HULHE，构建了第一个竞技扑克游戏程序。2005年，Gilpin和SandholmgydF4y2Ba^19gydF4y2Ba使用这种方法和一种寻找游戏对称性的自动技术来解决罗德岛Hold'em，gydF4y2Ba^41gydF4y2Ba一个3.94 × 10的合成扑克游戏gydF4y2Ba^6gydF4y2Ba去除对称性后的信息集。gydF4y2Ba

反事实的遗憾最小化。gydF4y2Ba2006年，一年一度的电脑扑克比赛开始了。gydF4y2Ba^53gydF4y2Ba这场比赛推动了解决越来越大的游戏的重大进步，在随后的几年里提出了多种技术和改进。gydF4y2Ba^{36gydF4y2Ba，gydF4y2Ba37gydF4y2Ba}其中出现的技术之一，目前在竞争中最广泛采用的是反事实后悔最小化(CFR)。gydF4y2Ba^dgydF4y2BaCFR是一种通过两种后悔最小化算法之间的反复自演过程来逼近广义博弈的纳什均衡的迭代方法。gydF4y2Ba^{10gydF4y2Ba，gydF4y2Ba52gydF4y2Ba}后悔gydF4y2Ba算法在效用上的损失是由于没有选择唯一的最佳确定性策略，这只能在事后才知道。一个gydF4y2Baregret-minimizinggydF4y2Ba算法是一种保证它的遗憾随时间呈次线性增长的方法，因此最终实现与最佳确定性策略相同的效用。CFR的关键见解是，与存储和最小化指数级的确定性策略的遗憾不同，CFR存储和最小化每个信息集和后续行动的修改的遗憾，可以用来形成任何确定性策略的遗憾的上界。通过在所有迭代中平均每个参与者的策略，可以获得近似的纳什均衡，并且随着迭代次数的增加，近似值也会提高。该算法所需的内存在信息集数量上是线性的，而不是二次的，这是高效LP方法的情况。gydF4y2Ba^25gydF4y2Ba由于解决大型游戏通常是受内存限制的，所以CFR导致解决游戏的规模急剧增加，正如Koller等人所提出的那样。自2007年推出以来，CFR已被用于解决日益复杂的HULHE简化，达到3.8 × 10gydF4y2Ba^10gydF4y2Ba2012年的信息集。gydF4y2Ba^20.gydF4y2Ba

回到顶部gydF4y2Ba

3.解决人头极限Hold住他们gydF4y2Ba

完整的HULHE游戏有3.19 × 10gydF4y2Ba^14gydF4y2Ba信息集。即使在移除游戏对称性后，它也只有1.38 × 10gydF4y2Ba^13gydF4y2Ba也就是说，比之前解决的游戏大3个数量级。要处理这种规模的游戏，现有的CFR变体面临两个挑战:内存和计算。在计算过程中，CFR必须存储每个信息集的结果解和累积的后悔值。即使使用单精度(4字节)浮点数，这也需要262TB的存储空间。此外，过去的经验表明，信息集的数量增加三个数量级，需要至少增加三个数量级的计算。为了解决这两个挑战，我们采用了这篇论文的合著者Tammelin最近提出的两个想法。gydF4y2Ba^44gydF4y2Ba

为了解决记忆问题，我们使用压缩存储近似解策略和累积遗憾。对于解决方案和遗憾，我们使用不动点算法，首先将所有值乘以一个比例因子，然后将它们截断为整数。然后对得到的整数进行排序，使压缩效率最大化，压缩比约为13比1。总的来说，在计算过程中，我们需要低于11TB的存储，这些存储分布在一个计算节点集群中。这个量无法存储在主存中，因此我们将压缩的策略和后悔值存储在每个节点的本地磁盘上。每个节点负责一组gydF4y2Ba现在进行gydF4y2Ba也就是说，游戏树的各个部分是基于公开观察到的行动和纸牌进行划分的，这样每个信息集都与一个子游戏相关联。子游戏的遗憾和策略从磁盘加载，更新，并保存回磁盘，使用流压缩技术解压和重新压缩子游戏的部分需要。通过将子游戏做得足够大，更新时间将占据处理子游戏的总时间。使用磁盘预缓存，磁盘存储引起的低效率大约占总时间的5%。gydF4y2Ba

为了解决计算问题，我们使用CFR的变体CFR+。gydF4y2Ba^{10gydF4y2Ba，gydF4y2Ba44gydF4y2Ba}CFR的实现通常只采样游戏树的部分内容，以便在每次迭代中更新。他们还在每个信息集上使用后悔匹配，该匹配为每个行为保留后悔，并在积极后悔的行为中选择与后悔成比例的概率。相反地，CFR+在整个游戏树中进行穷举迭代，并使用遗憾匹配gydF4y2Ba^+gydF4y2Ba，后悔匹配的一种变体，其中后悔被限制为非消极的。那些看起来很糟糕的行为(游戏邦注:因为没有玩游戏而后悔的次数少于零)将在证明是有用的之后立即再次被选择(而不是等待多次迭代让后悔变成积极的)。最后，与CFR相比，我们从经验上观察到，在计算过程中，参与人策略的可利用性有规律地收敛于零。因此，我们跳过了计算和存储平均策略的步骤，而是使用玩家当前的策略作为CFR+解决方案。我们根据经验观察到CFR+比最先进的采样CFR需要的计算量要少得多，gydF4y2Ba^22gydF4y2Ba同时也非常适合大规模并行化。gydF4y2Ba

定理1。gydF4y2Ba^egydF4y2Ba给定一组动作a，和任意序列的T值函数vgydF4y2Ba^tgydF4y2Ba:一个ℜ，其边界L使|vgydF4y2Ba^tgydF4y2Ba(一)−vgydF4y2Ba^tgydF4y2Ba(b)对于所有t和a, b∈a，根据后悔匹配行为的代理，|≤LgydF4y2Ba^+gydF4y2Ba算法最多会有遗憾的gydF4y2Ba．gydF4y2Ba

与CFR一样，CFR+是一种迭代算法，用于计算纳什均衡解的逐次逼近。近似的质量可以用它来衡量gydF4y2Ba可利用性:gydF4y2Ba比预期中最坏情况下对手策略所获得的博弈价值少的数量。gydF4y2Ba^10gydF4y2Ba计算策略的可利用性包括计算最坏情况值，传统上需要遍历整个游戏树。对于像HULHE这样规模的游戏来说，这一直是一个棘手的问题。最近的研究表明，利用博弈的不完全信息结构和效用的规律性，可以大大加快这种计算速度。gydF4y2Ba^23gydF4y2Ba这是我们用来确认我们的策略的近似质量的技术。该技术和实现已经在小型游戏和独立计算中验证了HULHE中简单策略的可利用性。gydF4y2Ba

一种策略可以在预期中被利用，但由于游戏中的机会元素和策略的随机性，其最坏情况下的对手仍然不能保证在任何有限的牌数后获胜。我们将游戏定义为gydF4y2Ba基本上解决了gydF4y2Ba如果一辈子玩游戏都无法从统计学上区分它和95%的置信度被解决。想象一下，一个人一小时玩200手扑克，每天12小时，连续70年没有一天不玩。进一步想象他们采用最坏的情况，最大限度地利用对手的策略，并且从不犯错。他们的总奖金，作为数百万独立结果的总和，将是正态分布的。因此，观察到在扑克游戏的整个生命周期中，20次中至少有1次比预期值(即策略的可利用性)低1.64个标准差或更多。使用单手HULHE的标准偏差，据报道约为5bb/g(每场游戏大盲，其中大盲是HULHE的赌注单位)，gydF4y2Ba^11gydF4y2Ba我们到达了一个门槛gydF4y2Ba所以，一个可利用性低于1mbb/g的近似解决方案(每场游戏的毫米波大小)无法从一个精确解决方案中得到高可信度的区分，而且确实有1 / 20的机会击败最坏情况下的对手，即使在人类一生的游戏之后。因此，1mbb/g是宣告HULHE的临界值，基本上解决了。gydF4y2Ba

回到顶部gydF4y2Ba

4.解决方案gydF4y2Ba

我们的CFR+实现是在一个包含200个计算节点的集群上执行的，每个节点具有24个2.1GHz的AMD内核、32GB的随机访问内存(RAM)和1TB的本地磁盘。我们将游戏划分为110,565个子游戏(基于翻牌前投注、翻牌纸牌和翻牌投注)。这些子游戏被分配给199个工作节点，其中一个父节点负责游戏树的初始部分。工作节点并行执行它们的更新，将值传递回父节点，以便父节点执行更新，平均花费61分钟完成一次迭代。然后，计算运行了1,579次迭代，用时68.5天，总共使用了900个核心年的计算gydF4y2Ba^fgydF4y2Ba以及10.9TB的磁盘空间，包括大量文件带来的文件系统开销。gydF4y2Ba

图3gydF4y2Ba通过增加计算量，说明了该计算策略的可利用性。该策略的可利用性达到0.986mbb/g，使得HULHE基本上是弱解。使用每个位置(作为庄家和非庄家)的单独可利用性值，我们得到了博弈理论值的精确边界:庄家在87.7mbb/g和89.7mbb/g之间，证明了庄家在HULHE中拥有显著优势的普遍智慧。gydF4y2Ba

图3。增加计算量的近似解的可利用性。gydF4y2Ba

最后的策略，接近于纳什均衡，也可以回答一些基本的和长期争论的问题，在HULHE博弈理论最优发挥。gydF4y2Ba图4gydF4y2Ba在游戏的两个早期决策中，我们可以看到最终的策略。人类玩家对于“跛行”是否可取持不同意见，也就是说，用某些手在第一个动作时就叫，而不是举起来。传统观点认为，一瘸一拐会放弃激怒对手的机会，因此更倾向于抬起头。我们的解决方案强调同意(见中没有蓝色gydF4y2Ba图4一gydF4y2Ba)．这个策略只有0.06%的情况下会失败，而没有手的情况下会失败的概率超过0.5%。在其他情况下，该策略给出了超越传统智慧的见解，指出了人类可能改进的领域。这种策略很少“设限”，也就是说，作为庄家，在第一轮就做出最终允许的加注，而一些强大的人类玩家会用大范围的下注来设限。即使是手握最强的牌，一对a，这种策略的赌注上限也低于0.01%，最有可能下上限的牌是一对2，概率为0.06%。也许更重要的是，该策略选择玩，即不叠牌，作为非发牌者比大多数人类玩家的手牌范围更广gydF4y2Ba图4 bgydF4y2Ba)．当持有较低级别的对(如3或4)时，它也更有可能重新提高。gydF4y2Ba^ggydF4y2Ba

图4。两个早期决策的求解策略中的行动概率。每个格子代表169张牌中的一张(即两张私有牌)，上面的对角线由相同花色的牌组成，而下面的对角线由不同花色的牌组成。细胞的颜色表示所采取的行动:红色表示折叠，蓝色表示呼叫，绿色表示提高，混合颜色表示随机决定。gydF4y2Ba

虽然这些观察结果只是博弈理论最优博弈的一个例子(不同的纳什均衡可能会有不同的玩法)，但它们既证实了也反驳了目前人类对均衡博弈的信念，并说明人类可以从这种大规模的博弈理论推理中学习到相当多的东西。gydF4y2Ba

回到顶部gydF4y2Ba

5.游戏结果gydF4y2Ba

在原始论文的扩展版中，gydF4y2Ba^9gydF4y2Ba我们提供了测量仙王在游戏中与计算机代理和人类对手的表现的额外结果。十多年来，HULHE一直是人工智能研究的通用测试平台，研究人员为该领域开发了一系列计算机代理。这一努力在很大程度上是由2006年与HULHE开始的年度计算机扑克比赛(ACPC)协调的。虽然每年的顶级代理在竞争中都比老代理表现得更好，因此似乎趋同于最优发挥，但他们的实际最坏情况的可利用性是未知的。2011年，一种高效的最佳反应技术被开发出来，使衡量计算机代理的可利用性变得可行，gydF4y2Ba^23gydF4y2Ba这是研究人员第一次能够精确测量他们在解决游戏问题方面的进展。这篇论文的一个关键结果是，顶级ACPC代理只以微小的优势击败对方，但却拥有广泛的可利用性。使用仙王座，我们现在还可以通过匹配最优策略来评估这些历史因素。gydF4y2Ba

图5gydF4y2Ba呈现了我们历史代理人的可利用性以及他们在对阵仙王时的平均损失。为了减少运气的影响，我们使用了一种重复的扑克格式，即每次游戏都使用相同的纸牌，但玩家处于相反的位置。PsOpti4是为HULHE产生的第一个博弈论策略，也是阿尔伯塔大学进入2006年ACPC。gydF4y2Ba^{5gydF4y2Ba，gydF4y2BahgydF4y2Ba}阿尔伯塔大学的ACPC条目被命名为Hyperborean，从2007年开始，所有条目都使用CFR的变体创建。gydF4y2Ba^我gydF4y2Ba2007年和2008年的北极星代理是由阿尔伯塔大学为它的两个人vs创建的。-机器扑克锦标赛，北极星在2007年以微弱劣势输掉，在2008年以微弱优势获胜;对这些匹配的分析载于gydF4y2Ba^24gydF4y2Ba(第八章)。最后，CFR-BR剂是我们在这项工作之前最接近的平衡近似。gydF4y2Ba^21gydF4y2Ba它使用了与《Hyperborean 2011》相同的抽象游戏，但使用了一种以最低的真实游戏可利用性解决抽象策略的算法。gydF4y2Ba

图5。早期计算机策略对Cepheus的可利用性和性能。结果以mbb/g为单位，表示策略对手的预期赢局(最佳对策或仙王座)。Cepheus的比赛包含了100万次重复的扑克游戏(共200万次)，除了PsOpti4，它进行了2万次重复的游戏(共4万次)。gydF4y2Ba

这些结果表明，除了Hyperborean 2009之外，每一代新策略在可利用性和损失方面都优于本质上最优的策略。然而，尽管这些策略中的许多都是高度可利用的，但它们输给仙王座的概率相当低。这种损失很难用统计置信来衡量:一个10万场比赛(非重复)的95%置信区间为31mbb/g，比Cepheus和除PsOpti4之外的所有代理之间的性能差异都要大。此外，《Hyperborean 2009》在对抗《仙王座》时的游戏表现确实比之前的游戏有所改善，并且因为使用了“策略嫁接”而在可开发性上有所退让，这是一种不完善的解决技术，它将抽象问题解决为一系列碎片。gydF4y2Ba^50gydF4y2Ba这一技术允许更大且更细粒度的抽象，从而提高游戏内的性能，但却不能从理论上保证可开发性。综上所述，这些结果说明了仅通过其竞争表现而不是计算其可利用性来评估战略的难度。gydF4y2Ba

我们还可以衡量仙王座与人类对手的表现。在这篇文章于2015年1月首次发表后，我们的网站允许访客与仙王座对战并查看其策略。gydF4y2Ba^8gydF4y2Ba每个访问者选择一个用户名，并与仙王进行任意数量的简短的100场比赛。在过去的两年里，39564个独立用户参加了98040场比赛，总共参加了3564094场比赛。gydF4y2Ba^jgydF4y2Ba在这组游戏中，仙王以169.9±5.2mbb/g的95%可信率获胜。然而，大多数玩家并没有完成一场100场的比赛(只有7878名玩家完成了比赛，总共完成了20374场比赛)，所以这个胜率可能不能反映Cepheus在面对强大对手时的表现。gydF4y2Ba

决定这些玩家中的哪一个是强大的并非易事，因为他们的匹配存在差异，每个玩家玩的游戏数量也不相同。虽然运气和技能都有助于玩家的表现，但得分最高的玩家更有可能是最幸运的，而不是最强的。此外，如果玩家继续玩游戏，但如果他们输了就退出游戏，就会产生偏见。为了限制偏差的影响，并评估Cepheus对不同等级人类的表现，我们使用了以下方法。首先，我们剔除了数据不足、玩了少于500场游戏的用户名，留下821个用户名玩了33,752场比赛、1,765,656场游戏。接下来，我们将每个用户的游戏分成两组，即Rank和Test。gydF4y2Ba^kgydF4y2Ba我们会评估每个用户的Rank游戏，并根据游戏表现对玩家进行排序。这种排序既反映了他们的技巧，也反映了他们的运气。然后玩家被平均分成5个等级:用户名中排名靠后的20%，21-40%等等。在每个层级中，测试游戏结果的平均值产生了层级的胜率，这与影响Rank游戏的运气无关。gydF4y2Ba

这些结果显示在gydF4y2Ba图6gydF4y2Ba．仙王的胜率在225到87mbb/g之间变化，随着人类玩家水平的提高而降低。即使在这个实验中对前20%的玩家，仙王87mbb/g的胜率也比我们对任何历史代理都要高。它甚至超过了50mbb/g，这是一个经常被引用的基准，用来衡量职业扑克玩家试图从较弱的对手那里赢下什么。gydF4y2Ba

图6。人类和造父座玩的游戏。人类被平均分为5个技能组，列和误差条表示该组对仙王的平均损失(mbb/g)。gydF4y2Ba

回到顶部gydF4y2Ba

6.结论gydF4y2Ba

在本文中，我们宣布了抬头限制德州扑克本质上是弱解。这是人类参与的第一个非平凡的不完全信息博弈。即便如此，读者可能会问，破解扑克游戏的终极意义是什么?这一结果背后的突破是一般性算法的进步，使任何大规模模型中的博弈论推理变得更容易处理。虽然博弈论看起来很有趣，但它一直被认为具有严重的影响，例如，它对冷战政治的早期影响。gydF4y2Ba^31gydF4y2Ba最近，博弈论在安全方面的应用激增，包括部署在机场检查站、空中指挥官调度和海岸警卫队巡逻的系统。gydF4y2Ba^43gydF4y2Ba基于本文所述的CFR算法，已用于在没有明显对手的情况下进行稳健决策，有可能应用于医疗决策支持。gydF4y2Ba^15gydF4y2Ba现实生活中的决策设置几乎总是涉及不确定性和信息缺失，因此需要在算法上取得进步，比如解决扑克游戏的算法，以推动未来的应用。然而，我们也赞同阿兰·图灵为自己的游戏工作辩护的说法，“如果我们掩盖推动这项工作的主要动机是纯粹的乐趣这一事实，那就太虚伪了。”gydF4y2Ba^30.gydF4y2Ba

回到顶部gydF4y2Ba

致谢gydF4y2Ba

作者顺序按字母顺序排列，反映了作者的同等贡献。CFR+和压缩遗憾的想法和策略起源于Oskari Tammelin。gydF4y2Ba^44gydF4y2Ba这项研究由自然科学和工程研究委员会(NSERC)支持，阿尔伯塔创新技术未来(AITF)通过阿尔伯塔创新机器学习中心(AICML)，并只有可能由于计算加拿大和计算Québec提供的计算资源。作者想要感谢阿尔伯塔大学计算机扑克研究小组(CPRG)的所有当前和过去的成员，在那里解决heads-up限制德州扑克的想法是第一次讨论;Jonathan Schaeffer, Robert Holte, Duane Szafron和Alex Brown对本文初稿的评论;和布莱斯·帕拉迪丝对人类顶级扑克玩家的传统智慧的见解。gydF4y2Ba

回到顶部gydF4y2Ba

回到顶部gydF4y2Ba

回到顶部gydF4y2Ba

数字图书馆是由计算机协会出版的。版权所有©2017 ACM股份有限公司gydF4y2Ba

---

没有发现记录gydF4y2Ba