如何为“多轮剪刀石头布”设计一个 AI？


对于一个程序员来说，最直观的思路莫过于搜索。我们可以构建一个简单的搜索树： 


  1. 如果我出“石头”，对手出“布”，我输。

  2. 如果我出“剪刀”，对手出“石头”，我输。

  3. 如果我出“布”，对手出“剪刀”，我输。


搜索算法的结论是：无论我出什么，都会输。这个结论显然是错的——它假设我的策略是透明的，对手能完美预知我的选择。


这正是不完美信息博弈（Imperfect Information Games）给传统 AI 算法设下的第一个陷阱。在这类博弈中，信息本身就是武器，胜利的关键不仅仅是做出最优决策，更是要管理信息的获取。换句话说，AI 必须学会策略性地“说谎”与“伪装”。


在扑克牌桌、商业谈判桌乃至国际外交舞台上，隐藏自己的真实意图，同时试探对方的虚实，才是博弈的核心。那么算法如何才能掌握这种在不完美信息中进行决策的艺术？


在揭晓答案之前，我们先要理解：为什么那些在象棋和围棋中叱咤风云的强大算法，到了这里会集体失灵？


传统巨头的失灵：当“大力”不再出奇迹

1. Minimax 搜索的“确定性”盲区

Minimax 算法是传统棋类 AI 的基石，它的核心是对抗性搜索。它通过递归地向前推演，寻找能让自己在“对手最完美的应对下”获得最好结果的那个行动。这个“确定性”逻辑在象棋里无懈可击，但在扑克里却行不通。


Minimax 的每次推演都假设自己的意图已被看穿。因此，它永远无法理解“诈唬”（bluffing）的价值——用弱牌下大注，恰恰是利用了对手不知道你底牌这一点。


2. 蒙特卡洛树搜索（MCTS）的“估值”难题

AlphaGo 的核心算法 MCTS 依赖于对任何“中间局面”进行快速的胜率评估，但这在扑克中是不可能的。一个扑克局面的价值，严重依赖于对手头脑中关于你手牌的信念，而这个信念是由之前的整个历史路径决定的。


同一个物理局面，仅仅因为你之前打得凶悍或保守，导致对手的信念不同，其价值就会天差地别。MCTS 无法在一个节点上编码这无穷的“信念”可能性，因此它赖以生存的局面评估就失效了。


CFR 的核心：在自我博弈中进行“平行宇宙”的复盘

面对传统算法的困境，CFR（Counterfactual Regret Minimization，反事实遗憾最小化）的提出者们另辟蹊径，引入了一个源自哲学和逻辑学，却在计算机科学中大放异彩的概念——反事实思考（Counterfactual Thinking）。


什么是反事实思考？它就是我们人类每天都在做的“如果当初……就好了”。


这是一种对未曾发生的、与事实相反的可能性进行推演的思维能力。我们通过想象这些“平行宇宙”的结局，来总结经验，修正未来的行为。


传统算法（如 MCTS）在信息不完整的游戏中，其本质是“猜”：它们必须先猜测对手的底牌，把游戏“确定”下来，然后再去寻找当前这一步的最佳走法。这是一种有根本缺陷的妥协。


CFR 的本质是“学”，它通过海量的自我博弈，去学习一个跨越时间的、统计意义上的真理。它的核心逻辑是：不要在“这一局”里寻找最佳答案，而是去计算，在所有和当前长得一模一样的局面下，哪个选择会让你在千百万局之后“后悔”最少。


这个“后悔值”（Regret），就是 CFR 唯一的学习信号。它放弃了在单局游戏中寻找“最优解”的尝试，转而去寻找一个“无悔”的均衡策略。


理论之美与现实之力

CFR 之所以在 AI 领域备受推崇，不仅因为它解决了实际问题，更在于其深刻的理论意义和强大的扩展性。


1. 理论意义：通往纳什均衡的优雅路径

CFR 最有趣的理论特性在于其优美的收敛性保证。在开创性论文[1]中证明：在二人零和博弈中，只要持续运行 CFR 算法，其平均策略就必然会收敛到一个纳什均衡。这一结论将抽象的博弈论理论与机器学习实践完美地连接了起来。


2. 应用价值：与 AI 并行的进化之路

CFR 一方面在应用领域攻城略地，另一方面在技术内核上与最前沿的 AI 技术深度融合：


在应用中，CFR 思想先被用来“解决”双人有限注德州扑克[2]，再推广至双人无限注[3,4]和多人局[5]，后来又成为了《Diplomacy》游戏 AI 的战略核心[9]。


在技术上，CFR 通过与蒙特卡洛采样（MCCFR）结合解决了计算效率问题[6]，与深度学习（Deep CFR）结合使得 CFR 的应用不再需要大量人类知识和设计[7]，也可以与强化学习思想融合[8]，展现了其作为基础理论的强大生命力与扩展性。


正是这种理论、技术、应用的螺旋上升，让 CFR 从一个优美的构想，成长为驱动现代 AI 进行复杂决策的强大引擎。


参考文献：

[1] Zinkevich, Martin; Johanson, Michael; Bowling, Michael; Piccione, Carmelo (2007). "Regret Minimization in Games with Incomplete Information". Advances in Neural Information Processing Systems 20 (NIPS 2007).

[2] Bowling, Michael; Burch, Neil; Johanson, Michael; Tammelin, Oskari (January 9, 2015). "Heads-up limit hold'em poker is solved". Science 347 (6218): 145-149.

[3] Moravčík, Matej; Schmid, Martin; Burch, Neil; Lisý, Viliam; Morrill, Dustin; Bard, Nolan; Davis, Trevor; Waugh, Kevin; Johanson, Michael; Bowling, Michael (May 12, 2017). "DeepStack: Expert-level artificial intelligence in heads-up no-limit poker". Science 356 (6337): 508-513.

[4] Brown, Noam; Sandholm, Tuomas (December 15, 2017). "Superhuman AI for heads-up no-limit poker: Libratus beats top professionals". Science 359 (6374): 418-424.

[5] Brown, Noam; Sandholm, Tuomas (July 11, 2019). "Superhuman AI for multiplayer poker". Science 365 (6456): 885-890.

[6] Lanctot, Marc; Waugh, Kevin; Zinkevich, Martin; Bowling, Michael (2009). "Monte Carlo Sampling for Regret Minimization in Extensive Games". Advances in Neural Information Processing Systems 22 (NIPS 2009).

[7] Brown, Noam; Lerer, Adam; Gross, Sam; Sandholm, Tuomas (2019). "Deep Counterfactual Regret Minimization". Proceedings of the 36th International Conference on Machine Learning (ICML), PMLR 97:793-802.

[8] Steinberger, Erik (2020). "Combining Deep Reinforcement Learning and Search for Imperfect-Information Games". Advances in Neural Information Processing Systems 33 (NeurIPS 2020).

[9] Bakhtin, Anton; Brown, Noam; Dinan, Emily; Farina, Gabriele; Flaherty, Colin; Fried, Daniel; Goff, Andrew; Gray, Jonathan; Hu, Hengyuan; Jacob, Athul Paul; Komeili, Mojtaba; Koncel, Karthik; Lewis, Mike; Miller, Timothy; Shih, Shrimai; Turpin, Jack; Wu, Jiawei (November 22, 2022). "Human-level play in the game of Diplomacy by combining language models with strategic reasoning". Science 378 (6624): 1067-1074.


文 | 吴天意

图 | 朱成轩


—   版权声明  —

本微信公众号所有内容，由北京大学前沿计算研究中心微信自身创作、收集的文字、图片和音视频资料，版权属北京大学前沿计算研究中心微信所有；从公开渠道收集、整理及授权转载的文字、图片和音视频资料，版权属原作者。本公众号内容原作者如不愿意在本号刊登内容，请及时通知本号，予以删除。

内容中包含的图片若涉及版权问题，请及时与我们联系删除