近年来，人工智能领域取得了许多令人惊讶的进展。其中最引人注目的成就是AI在各种游戏中击败人类。随着OpenAI在Dota2比赛中大放异彩以及DeepMind在Atari游戏中展现出色表现，最引人注目的是AlphaGo击败了韩国围棋大师李世石。这是机器首次在围棋中表现出超越人类的能力，标志着AI领域的一个历史性时刻。
与此同时，一组来自美国、加拿大、捷克共和国和芬兰的研究人员已经开始致力于解决另一种游戏：无限注德州扑克。自2005年以来，来自阿尔伯塔大学（现与Google Deepmind合作）和卡耐基梅隆大学的研究人员在博弈论方面取得了许多进展，最终目标是解决扑克问题。
Cepheus：极限德州扑克AI
第一个重大成功是在2015年，当时Oskari Tammelin、Neil Burch、Michael Johanson和Michael Bowling创建了一个名为Cepheus的计算机程序，这个AI可以在无限注德州扑克中与人类对抗。他们在论文中声称“解决了无限注德州扑克”，实际上是通过近似一个策略组合达到纳什均衡。对于两人零和游戏，使用纳什均衡策略是最佳选择，即便对手的策略未知。
极限德州扑克的主要特点在于其分支因子的不同。在极限德州扑克中，下注数量和大小有限，这使得在给定情况下的动作数量有限。而在无限注德州扑克中，没有这样的限制。因此，极限德州扑克的游戏规模大约为$10^{14}$，而无限注德州扑克的规模则达到$10^{160}$。这使得解决无限注德州扑克变得更加困难。
Cepheus通过离线计算所有可能的游戏情况的响应，并将这些概率分布存储为向量。尽管这种方法听起来不如AlphaGo的深度神经网络那么吸引人，但其核心算法——反事实遗憾最小化（Counterfactual Regret Minimization, CFR）——与AlphaGo/AlphaZero的算法在某种程度上是相似的。两者的共同点在于通过与自己对战来学习。
DeepStack：基于神经网络的无限注德州扑克AI
在Cepheus之后大约两年，另一个成功的扑克机器人出现了，这次它可以在无限注德州扑克中击败人类。这个AI名为DeepStack，它使用神经网络辅助的持续再解法（continual re-solving）作为核心技术。
再解法是子游戏解法技术之一。子游戏是当前决策点的游戏树根节点。从高层次来看，子游戏解法意味着在从父节点分离的情况下解决子游戏。在DeepStack中，深度神经网络被用来克服持续再解法中的计算复杂性。这种复杂性源于在游戏中的任何决策点重新计算反事实值向量。
为了评估DeepStack对人类的表现，研究人员选择了33名来自17个国家的职业玩家，每人玩3000手牌。DeepStack在所有玩家中平均赢得了492 mbb/g（每100手牌赢得49个大盲注）。除了一个统计上不显著的对手外，DeepStack击败了所有玩家。
Libratus：DeepStack的主要竞争对手
在2017年1月，卡耐基梅隆大学的Tuomas W. Sandholm和他的同事们开发的Libratus在无限注德州扑克中击败了4名职业玩家。比赛在匹兹堡的一家赌场举行，持续了20天，共进行了大约120,000手牌。Libratus平均每百手牌赢得147 mbb/g。
Libratus使用了三种主要方法的结合：
- 使用蒙特卡洛遗憾反事实最小化（Monte Carlo Counterfactual Regret Minimization, MCCFR）计算的蓝图策略。
- 嵌套子游戏解法。
- 在比赛期间进行自我改进。
在比赛期间，Libratus记录对手的下注行为，并在每晚更新蓝图策略，以应对可能的利用行为。
博弈论基础
为了理解反事实遗憾最小化，我们需要了解一些博弈论的基础知识。博弈论是数学的一个分支，为模拟和推理交互情况提供了有用的工具。这些交互情况被称为游戏，可能因许多因素而性质各异，如玩家数量、收益结构或动作顺序等。
什么是头对头无限注德州扑克？
无限注德州扑克是一个两人零和有限信息不完全且带有机会动作的游戏。
- 这是一个两人游戏，因为只有两个玩家参与。
- 游戏是有限的，因为可能的动作历史是有限的。
- 游戏是零和的，因为所有支付的总和为零。
- 游戏是不完全信息的，因为玩家不了解游戏的确切状态。
- 游戏带有机会动作，因为存在一些随机元素，如发牌。
策略在无限注德州扑克中的意义
策略描述了在每个可能情况下如何行动。对于扑克这样的游戏，策略不能完全是确定性的，必须包含随机化成分，否则玩家的下注模式会迅速被学习和利用。
行为策略是一组在决策点上的概率分布，描述了在所有游戏情况下如何行动。策略组合则是所有玩家的策略集合。在头对头无限注德州扑克中，策略组合包含两个策略（每个玩家一个）。
为什么选择纳什均衡？
我们的主要算法CFR生成的是纳什均衡的近似。纳什均衡是一个策略组合，其中没有单个玩家有改变策略的动机。这代表了玩家之间的平衡点，即没有玩家通过改变策略能获得额外的收益。
对于两人零和有限游戏，纳什均衡是必然存在的。Minimax定理证明了对于两人零和有限游戏，存在一个最佳的单一可能收益，即游戏的价值。在扑克中，所有纳什均衡的预期收益是相同的。
反事实遗憾最小化（CFR）
反事实遗憾最小化是一种基于无遗憾学习的算法，用于计算博弈中的纳什均衡。无遗憾学习是一种框架，其中一个简单的例子是结合专家建议（combining expert advice）。
在CFR中，算法通过不断调整策略以最小化在不同决策点上的遗憾值。遗憾值表示在特定情况下未选择最佳动作所带来的损失。通过反复迭代，算法逐渐收敛到一个纳什均衡策略。
CFR的基本过程
- 初始化策略和遗憾值。
- 在每次迭代中，模拟游戏并更新遗憾值。
- 根据遗憾值调整策略。
- 重复迭代，直到策略收敛。
CFR的核心在于通过模拟游戏中的所有可能情况，计算每个决策点上的最佳动作，并根据遗憾值调整策略。最终，算法生成的策略将接近于纳什均衡。
总结
反事实遗憾最小化是打败职业扑克玩家的核心技术。通过不断调整策略以最小化遗憾值，CFR能够生成接近纳什均衡的策略，使AI在无限注德州扑克中表现出超越人类的能力。随着技术的不断进步，AI在游戏中的表现将越来越接近完美。
参考文献
- Counterfactual Regret Minimization – the core of Poker AI beating professional players
- Oskari Tammelin, Neil Burch, Michael Johanson, Michael Bowling. "Solving Heads-Up Limit Texas Hold’em."
- Tuomas W. Sandholm, Noam Brown. "Libratus: The Superhuman AI for Heads-Up No-Limit Poker."