|
近些年来，人工智能领域出现了很多突破，其中游戏往往被用作重要的里程碑。过去实现那些成功的游戏的一个常见的特征是它们都具有完美信息（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）。
图 1：HUNL 中公开树的一部分。红色和天蓝色的边表示玩家动作。绿色边表示公开的公共牌。带有筹码的叶节点表示游戏结束，其中，如果一个玩家根据之前的动作和玩家手牌的联合分布而弃牌或做出决定，那么收益就可能是固定的。
图 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。
算法 S1：Depth-limited continual re-solving
图 3:深度反事实价值网络（Deep counterfactual value networks）。该网络的输入包括底池大小、公共牌、手牌范围（player ranges），这些首先会被处理成 hand clusters。来自这 7 层全连接隐藏层的输出还要经过后处理（post-processed），从而保证该值（values）满足零和约束（zero-sum constraint），然后这些值又会回过来被映射为 hand counterfactual values。
|
