图5：DeepStack 在第五张牌开始前特定公共状态下的攻击性和分解迭代数量之间的方程。
算法DeepStack ：让机器拥有“直觉”
DeepStack 是一大类的序列不完美信息博弈的通用算法。我们将解释 DeepStack 在 HUNL（heads-up no-limit，一对一无限注）德州扑克中的作用。扑克游戏的状态可以分为玩家的私人信息，即两张牌面朝下的手牌，以及公共状态，包括牌面朝上的公共牌和玩家的下注顺序。游戏中公共状态的可能序列形成公共树，每个公共状态有一个相关联的子公共树。见下图6：
图6：HUNL公共树的一部分。红色和湖蓝色代表玩家的动作。绿色代表被翻开的公共牌。
DeepStack 算法试图计算玩游戏的低利用率策略，即，求解一个近似的纳什均衡（Nash equilibrium）。DeepStack在玩牌期间计算这个策略，公共树的状态如图7所示。这种本地的计算使得 DeepStack 在对现有算法来说规模太大的游戏中可推理，因为需要抽象出的游戏的10的160次方决策点下降到10的14次方，这让算法变得易处理。
图7：DeepStack 概览图。（a）DeepStack 对在每个公共状态的动作进行 re-solves，使用 depth-limited lookahead，其中子树值的计算用训练好的深度神经网络（b）通过随机生成的扑克状态在玩牌前进行训练（c）最终状态如图3.
DeepStack 算法由三个部分组成：针对当前公共状态的本地策略计算（local strategy computation），使用任意扑克状态的学习价值函数的 depth-limited lookahead，以及预测动作的受限集合。
连续 Re-Solving
Own Action：将对手的反事实值替换为在为我们自己选择动作的解决策略中计算的值。使用计算策略和贝叶斯规则更新我们自己的动作范围。
Chance Action：用从最后一次分解为这个动作计算出的反事实值替换对手反事实值。通过清除在任何新公共牌不可能的手牌范围，更新我们自己的范围。
Opponent Action：不用做什么。
Limited Lookahead 和 Sparse Trees
连续re-solving在理论上是可行的，但实际使用上不现实。它没有维持一个完整的策略，除非游戏接近结束，re-solving本身就很棘手。例如，对于第一次动作的re-solving需要为整个游戏临时计算近似解决方案。
Deep Counterfactual Value Networks
深度神经网络（DNN）已被证明在图像和语音识别、自动生成音乐以及玩游戏等任务上是强有力的模型。DeepStack 使用DNN和定制的架构作为它的 depth-limited lookahead其的价值函数。如图8。训练两个独立的网络：一个在第一次三张公共牌被处理（flop网络）后估计反事实值，另一个在处理第四张公共牌（turn网络）后估计反事实值。一个辅助网络用于在发任意公共牌之前加速对前面的动作的re-solving。
图8：Deep Counterfactual Value Networks。网络的输入是pot的大小，公共牌和玩家范围，玩家范围先被处理为bucket ranges。输出来自七个完全连接的隐藏层，被后处理以保证值满足零和限制（zero-sum constraint）。
CMU 又被截胡
近日，新智元在报道中提到，被称为“人脑 vs 人工智能：跟不跟 ” 的赛事将于1月11日在匹兹堡的 Rivers 赌场启幕。比赛期间，职业扑克手 Jason Les， Dong Kim， Daniel McAulay 和 Jimmy Chou 将在20天的时间和 CMU 计算机程序玩120000手一对一不限注的德州扑克。
CMU的人工智能系统名叫 Libratus ，相比去年失败的 Claudico，其终于策略发生了改变。 Libratus 会用 Bridges 计算机实时计算新的终局解决方法和算法，而不是像 Claudico 那么依赖终局。
另外，Claudico 常用的策略是 limping，这是一个扑克术语，指跟注混进去看看，而不是加注或者放弃。而 Libratus 偶尔也会这样。