目录

• 引言
• 多人博弈理论与实际的挑战
• Pluribus的描述
• 大型不完备信息博弈的抽象化
• • 动作抽象
  • 信息抽象
• 通过改进型蒙特卡洛CFR来进行自学习训练
• 不完备信息博弈的深度限制搜索
• 实验评价
• 总结
• 文章链接

引言

为什么poker能成为AI和博弈论领域要挑战的问题？因为人们可以优雅且高效的从poker中捕捉隐藏信息。并且针对多人牌局的AI被认为是下一阶段的重点。

多人博弈理论与实际的挑战

目前AI在游戏领域取得成绩均是基于双人零和博弈(整体的利益不会改变，要么你赢我输，要么我赢你输)，AlphaGo就是基于双人零和博弈。在双人零和博弈中，应用那是均衡策略至少可以保证不输，基于双人零和博弈的AI 算法就是去寻找纳什平衡。找到一个基于三人或者更多人零和博弈的纳什平衡是非常困难的（理论上接近纳什平衡也是很困难的）。如果每个玩家单独计算找到纳什平衡，玩家联合起来的策略可能就不是一个纳什平衡。例如下面的Lemonade Stand Game：

在游戏中，每个玩家都要在这个环上找到一点离其他成员尽可能地远。左图表示了四个玩家，每个颜色代表了他们的一个纳什平衡，处于纳什平衡的玩家均匀的分布在环上。右图表示如果他们独立寻找纳什平衡，那么玩家的联合策略可能就不是一个纳什平衡。
所以作者提出，我们的目标不是寻找一个具体的博弈论解决方案，而是创造出一个AI，通过经验不断地击败人类对手包括顶级的专业选手。

Pluribus的描述

Pluribus 策略核心是持续不断地进行自学习自博弈，通过这样的策略训练，AI 系统和自己的镜像进行对抗，而不获取任何人类游戏数据或先前的 AI 游戏数据。Pluribus 利用自学习制定的离线策略为“蓝图策略”，随着真实游戏的进行，Pluribus 通过在比赛中根据自己的实际情况实时搜索更好的策略来改进蓝图策略。

大型不完备信息博弈的抽象化

为了降低游戏的复杂性，作者忽略了一些考虑因素并且将类似的决策点放在一起，这个过程称之为抽象。在抽象之后，划分的决策点被认为是相同决策点。作者在 Pluribus 中使用了动作抽象和信息抽象。

动作抽象

动作抽象主要是减少AI所要考虑的动作即将一些产生影响相似的动作归为一类。例如：在德州扑克中，下注200美元和下注201美元两种动作又很小的差异，他们可以归结为同一个动作。为了减少形成策略的复杂度，Pluribus在任何给定的决策点仅仅考虑 一些不同的下注情况。如果Pluribus只接受过100美元和200美元的投注训练，而对手投注150美元，会产生什么的结果？Pluribus 会通过实时搜索算法对这种“离树”行为产生相应动作。

信息抽象

对于透漏信息相似（比如说，在poker中，玩家的牌和显示的底牌）的决策点进行合并，例如，10-high straight （6到10的顺子）和 9-high straight（5到9的顺子） 在牌型上差距明显，但是针对他们的策略是相同的。Pluribus 可以将这些相似牌型放在一起进行相同的处理，从而减少了确定策略所需的不同情况的数量。信息抽象降低了游戏的复杂性，但它可能会消除一些对于超人表现来说非常重要的细微的不同。因此，在与人类进行实际比赛时，Pluribus仅用信息抽象来推断未来下注轮次的情况，而不会用它来实际进行下注。

通过改进型蒙特卡洛CFR来进行自学习训练

Pluribus 的蓝图策略使用了 CFR（counterfactual regret minimization）。
作者使用一种蒙特卡洛CFR（Monte Carlo CFR） 方法对博弈树上的行动进行采样而不是在每次迭代时遍历博弈树。

在图中，玩家P1正在遍历博弈树。左图模拟游戏直到结束。中间图是对于左侧面板中遇到的每个P1决策点，在P1决策点中探索P1可能采取的其他操作，并在游戏结束时进行模拟。然后P1更新其策略，选择回报率更高、概率更高的行动。右图P1探索P1在中间面板中遇到的每个新决策点可能采取的行动，P1在这些假设决策点更新其策略。这个过程会重复，直到没有遇到新的P1决策点。（图中的百分比仅供说明，可能与算法计算的实际百分比不符。）
遍历者选择的动作和实际的动作的差值将在迭代中被添加到这个动作的遗憾值中。
由于反事实值和期望值的差值是被添加到遗憾值中的而不是取代，所以，玩家第一次的动作会仍对后续的遗憾值产生影响。因此这种策略是为了将来的迭代。
在一般的CFR中，第一次动作的影响以1/T的速率衰减，其中T的迭代次数。为了快速减少早期的“坏”的策略的影响，Pluribus 在早期迭代中采取线性 CFR 方法（后期迭代不会使用这种方法，乘法的时间成本太高）。第一次动作的影响会以下面的速率衰减：

不完备信息博弈的深度限制搜索

由于无限制德州扑克的规模和复杂性，整个游戏的蓝图策略一定是粗粒度的。Pluribus只在第一轮下注时，根据蓝图策略进行游戏，因为第一轮的决策点的数量足够少，蓝图策略可以承担不使用信息抽象，并且在动作抽象使用大量的动作。在第一轮之后（即使对手赌注大小与蓝图策略中动作抽象的大小完全不同），Pluribus会进行实时搜索，来确定针对当前情况的更好、更细粒度的策略。对于对手在第一次偏离树的下注，Pluribus通过the pseudoharmonic mapping将赌注映射到on tree附近的赌注上，然后继续按照蓝图策略进行，就好像对手使用了on tree 上的赌注。
在许多完备信息博弈中，实时搜索时实现超人性能的必要条件。

在剪刀石头布的游戏中，如果玩家P1首先行动，但是P1的动作不展示给玩家P2。然后，玩家P2行动。从玩家P1进行搜索，只前进行了一步，他的每一个动作都会产生一个零值的叶节点。如果玩家P2选择纳什均衡策略，玩家P2会以1/3的概率随机选择一个动作。那么选择石头的玩家P1的值为0，选择剪刀的玩家P1的值也为0。那么玩家P1总选择石头也是一个最佳策略。但是实际上，玩家P2可以根据玩家P1的动作调整策略，调整为总是出布。在这种情况下，玩家P1总是出石头的值是-1。在不完美信息子博弈中，叶子节点是没有固定值的，他们的值取决于搜索者在子博弈中选择的策略（搜索者在子博弈中分配给其动作的概率）。原则上，可以通过子博弈的叶子节点的值作为子博弈中搜索者策略的函数来解决，但是在大型游戏中是不是实际的。

Pluribus使用了一种改进的方法，搜索者明确认为任何或者所有的玩家都可以转移到子博弈叶子节点之外的不同策略中。 作者假设当到达叶子节点时，每个玩家不是只有固定的策略而是可以在 k 个不同的策略之间进行选择以进行接下来的博弈。这种技术会使搜索者找到一个更平衡的策略，选择一个不平衡的策略，例如总是出石头会被对手转换到总是出布的策略惩罚。

在不完备信息博弈中搜索的另一个主要的挑战是，玩家的在特定环境的最优策略依赖于对手如何看待玩家在每种情况下的策略是什么。比如说，玩家拿着一副特别好的牌，下注可能是一个很好的策略。但是如果玩家只在有好牌的情况下下注，那么对手就会知晓你的策略。为了解决这一问题，Pluribus根据它的策略追踪每副可能的手牌达到当前状态的概率。无论实际上持有哪副手牌，它都会先计算出每一手牌的动作,一旦计算出所有人的平衡策略，Pluribus 就会为它实际持有的手牌执行一个动作。

为了简单起见，子博弈只显示两个玩家。节点之间的虚线表示要操作的玩家不知道她在两个节点中的哪一个。左图表示原始的博弈子树，假设对手只是用一种固定的策略；右图表示对手使用k（k=2）种不同策略的博弈子树。

Pluribus使用两种不同形式的CFR来计算子博弈中的策略，这取决于子博弈的大小和博弈的位置。如果子博弈相对较大或者在博弈的早期，则使用线性蒙特卡洛CFR。否则，Pluribus使用一种优化的基于向量的线性CFR形式，只对机会事件进行采样（例如对公共牌进行采样）。
实际测试时，Pluribus 仅仅使用了两台 Intel Haswell E5-2695 v3 CPU，仅占用小于 128G 的内存。AlphaGo 对阵李世石时使用了 1920 块 CPU 和 280 块 GPU。在对每一个子博弈进行搜索时，根据现场情况，Pluribus 仅需要 1-33 秒。在其与自己镜像对抗的 6 人牌局中平均出牌时间为 20s，这远比顶尖人类选手快了近乎 2 倍。

实验评价

作者采用了两种形式评估 Pluribus 对阵精英选手。1、5 个顶尖人类选手 +1 个 AI (5H1 AI )；2、1 个人类顶尖选手 +5 个 AI (1H5AI )。作者通过使用 AI 领域中的标准度量mbb /game来衡量 AI 表现。作者利用 AIVAT 技术来减少游戏中的运气成分。

在 5H1AI 实验中，在应用了 AIVAT 之后，Pluribus 平均每手赢 48 个 mbb（48 mbb/game）。在 1H5AI 中，Pluribus 平均以 32mbb/game 的速率将人类击败。

总结

Pluribus的成功表明，尽管在多人博弈的性能上缺乏已知的强有力的理论保证，但在存在大规模、复杂的多人不完善信息这种情况下，一个精心构建的自我博弈加实时搜索算法可以产生超人的策略。

文章链接

《Superhuman AI for multiplayer poker》

总结

以上是生活随笔为你收集整理的解读《Superhuman AI for multiplayer poker》的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。