Safe and Nested Subgame Solving for Imperfect Information Games 论文总结

摘要

和完美信息博弈不同，在不完美信息博弈中，子博弈的最优策略往往取决于其他未到达的子博弈。因此一个子博弈无法被单独求解，必须考虑将整个博弈的策略看作一个整体。然而，我们可以先估计出整个博弈的一个策略，然后再通过解决单个子博弈的方式提升这个策略。这被称作是子博弈求解。我们在这篇论文中介绍了一种在理论和实践中都超过了先前方法的子博弈求解方法。我们还阐述了如何将这种方法（以及先前的子博弈求解方法）应用到如何响应对手“不在动作抽象”中的动作，这种方法显著的超过了现有的“动作翻译”的方法。最后，我们证明了子博弈求解可以随着博弈树的深入被重复使用，可以得到更低的可利用度。这些技术是Libratus的关键组成部分，Libratus是第一个在德州单挑无限注中打败顶尖人类的AI。

抛硬币游戏

想象有这么一个抛硬币的游戏：玩家抛一枚硬币，只有能看到硬币的结果，在看到结果之后，有两种选择：卖掉硬币或者让猜硬币落在了哪面，如果在硬币落在正面时选择卖掉硬币，他会得到+0.5的期望收益（中间双方是如何博弈的并不重要），如果在硬币落在反面时选择卖掉硬币，他会得到-0.5的期望收益，如果选择让猜硬币的结果，当猜对时，会获得-1的收益，当猜错时，的收益为+1，也可以选择弃权（虽然弃权是不应该被选择的），这时的收益为+1，的收益永远与的相反（零和博弈）

P2视角下的博弈树，其中S里的两个状态对P2来说是无法区分的

我们期望计算出在选择play之后的最优策略

显而易见的，的最优策略应该为：以25%的概率猜正面，75%的概率猜反面，这会让在硬币落在正面时无论选择sell还是play的期望收益都是+0.5，而在硬币落在反面时的期望收益都是-0.5，从而的总期望收益为0，即达到纳什均衡。

但是，如果我们改变和在选择sell之后的博弈策略，使得在硬币落在正面时选择sell的期望收益为-0.5，落在反面时选择sell的期望收益为+0.5，这时在选择play之后的最优策略就会变为以75%的概率猜正面，25%的概率猜反面。这说明了玩家在一个子博弈中的最优策略往往会取决于在其他没有到达的子博弈中的收益，因此，我们不能只关心当前子博弈的状态。这是非完全信息博弈和完全信息博弈区别最大的地方。

先前求解子博弈的方法

对于一些大型博弈，解决思路是对其进行一系列的抽象（简化）然后求解，求解得出的策略称为“蓝图策略”，子博弈求解的目的就是在蓝图策略的基础上改进子博弈中的策略。虽然蓝图策略在很多时候就是整个博弈的纳什均衡解，但我们不这么认为，事实上蓝图策略可以是任意一种策略

一种蓝图策略

现在假设我们已经求出了一个蓝图策略：当硬币为正面时，以25%的概率选择sell，75%的概率选择play，当硬币为反面时，以50%的概率选择sell，50%的概率选择play；以50%的概率猜正面，25%的概率猜反面，25%的概率弃权。我们会试图提升在选择play之后的策略。

不安全的子博弈求解

不安全子博弈求解

不安全子博弈求解的思路极为求解上图所示的博弈树，其中从根节点到两个节点的概率为蓝图策略中到达两个节点的概率归一化。求解出的结果是以100%的概率选择heads，但这种策略的可利用度太高（因为可以在硬币落到heads的时候选择sell，在硬币落到tails的时候选择play）

安全的子博弈求解

安全子博弈求解

在安全子博弈求解的博弈树中，我们给添加了一个“选择退出”的选项，该选项为带来的收益为在对上的蓝图策略时所能获得的最高收益

显然，不会比总是选择做的更差，但是也不会比总是选择做的更好，因为可以在中使用蓝图策略，这会导致和的收益相同（如果在中使用最优策略的话）。在这种情况下，在中的策略就被限制为不比蓝图策略差。例如，如果总是选择heads，那么则会在硬币为heads的时候选择，在硬币为tails时选择

不会比总是选择做的更差的意思是：哪怕在新策略中能使的期望收益变小（也就是变小），依然可以选择来无视这种情况，因此对于来说最坏的情况就是的新策略无论是在硬币为heads还是tails的时候都会使的期望收益降低，此时依然可以选择来逃避这一情况，可以说，是的一个保底选项。

不会比总是选择做的更好的意思是：如果我们想让在中的新策略比蓝图策略更好的话，我们只需要保证成立就可以了

这种求解方式保证了的新策略的可利用度不会大于蓝图策略的可利用度，但是这种求解方式可能会错过更新的机会。使用这种求解方式的目的是把原策略的期望收益保存在根节点上。

Maxmargin子博弈求解

略

安全子博弈求解

图1：蓝图策略的博弈树

图2：安全子博弈求解的博弈树

安全子博弈求解的博弈树中的实际上就是蓝图策略中选择play之后的期望收益。由图1可以发现，当硬币落在正面时，比起选择play（收益为0），有更好的选择sell（收益为+0.5）。因此，作为玩家，当在计算中的新策略时，我们可以允许让硬币落在heads时的收益提高到至多+0.5，与此同时，降低硬币落在tails时的收益。也就是说，修改图2所示的子博弈树，将硬币为heads时的由0改到+0.5，重新计算该子博弈树的策略。

图3：一个更进一步的例子

考虑上图所示的一个更进一步的例子，其玩法和抛硬币游戏类似，在选择play之后，会有一个额外的节点，其结果可以被和观测到，需要确定在中的策略和在中的策略。如果我们固定在中的策略不变，则可以允许当硬币为heads时在中的期望收益提高到至多+1。然而，如果我们要同时改变在和中的策略，我们就必须保证两个期望收益之和不超过+1，也保证了当硬币为heads时选择play的总期望收益不超过+0.5。

嵌套子博弈求解

如果在进行决策时选择了一个不在动作抽象中的动作（如上文抛硬币游戏中没有选择sell或者play而选择了其他的动作），则我们在构建子博弈树的时候应当让等于所有抽象动作中所能获得的最高期望收益。