自博弈AI攻克多米诺骨牌：MCTS与CFR的抽象化困境

引言：从棋类到不完美信息博弈

近年来，AI在博弈领域的突破从围棋（AlphaGo）延伸到德州扑克（Libratus/Pluribus），核心方法论也从纯搜索走向搜索与博弈论求解的融合。AlphaGo在2016年击败李世石标志着AI在完美信息博弈中的统治地位确立，其核心依赖深度神经网络与MCTS的结合。然而完美信息博弈只是现实决策的冰山一角——现实世界中绝大多数决策场景都存在信息不对称。2017年卡内基梅隆大学的Libratus在单挑无限注德州扑克中击败职业选手，2019年Pluribus将这一成果扩展到6人桌，标志着AI在多人不完美信息博弈中取得突破。这一技术演进的核心转变在于：从"给定完整局面计算最优走法"转向"在不确定性下构建鲁棒策略"。

一位开发者近期在Reddit上分享了一个颇具挑战性的项目：为巴西Pernambuco多米诺骨牌（一种流行于伯南布哥地区的4人组队骨牌变体）构建自博弈AI，技术栈结合了蒙特卡洛树搜索（MCTS）与反事实遗憾最小化（CFR）。项目当前卡在一个关键瓶颈上——搜索空间的抽象化（search abstraction）。

这个案例虽然出自一个小众游戏，但它折射出的正是当代不完美信息博弈AI的核心难题，值得深入剖析。

reddit原帖截图

为什么多米诺骨牌是个硬骨头

不完美信息的本质

与国际象棋、围棋这类完美信息博弈不同，多米诺骨牌属于不完美信息博弈——玩家无法看到对手手中的牌，也不知道剩余牌堆的具体分布。这种信息的不对称使得传统的极小化极大搜索（Minimax）失效，因为你无法为一个确定的棋局状态计算精确的价值。

从博弈论的形式化角度来看，不完美信息通过**信息集（Information Set）**来刻画。信息集指的是在某一决策点上，当前玩家无法区分的所有可能博弈状态的集合。例如在多米诺骨牌中，你知道自己的7张牌和已经打出的牌，但无法区分对手手牌的多种可能分布——所有这些可能性构成你当前的信息集。博弈论要求同一信息集内的策略必须相同（因为玩家无法区分这些状态），这导致虽然底层状态空间巨大，但有效的策略表示必须按信息集组织，而非按具体状态。

团队协作的复杂性

Pernambuco变体通常是2v2的组队对抗，这进一步增加了难度。AI不仅要推理对手的隐藏信息，还要与队友进行隐式协作——在无法直接沟通的情况下，通过出牌选择传递信号。这类似于桥牌中的做牌与信号系统，是博弈论中极难建模的部分。

桥牌与Pernambuco多米诺骨牌有诸多相似之处：4人2队对抗、不完美信息、隐式队友协作。但桥牌有形式化的叫牌约定系统，使得队友间的信号传递有明确的编码规范。多米诺骨牌缺乏这种形式化约定，队友间的信号传递更加隐晦——比如故意出某个花色暗示自己该花色丰富，或在有其他选择时选择过牌来传递信息。如何让AI学会这种隐式通信协议，是一个兼具理论深度和实践难度的问题。

状态空间的爆炸

即便是标准的双六骨牌（double-six），28张牌在4名玩家间的分布组合就极为庞大。当我们要为每一个信息集维护策略时，状态空间会迅速膨胀到不可穷举的规模。这正是抽象化技术要解决的问题。

具体来说，Pernambuco多米诺骨牌使用标准双六骨牌（28张牌，从0-0到6-6），四名玩家分为两队对坐，每人发7张牌，无剩余牌堆。玩家轮流出牌，需匹配桌面链条两端的点数，无法出牌时必须过牌（pass）。一局结束时，手中剩余牌面点数最少的一方得分，或某位玩家出完所有牌（domino）则该队直接获胜。过牌行为会暴露手牌信息——对手可据此推断你缺少哪些花色，这使得信息推理成为高水平对局的核心技能。28张牌分配给4人的初始组合数为C(28,7)×C(21,7)×C(14,7) ≈ 4.86×10^12，再考虑对局过程中的动态信息，状态空间之庞大可见一斑。

MCTS + CFR：两种范式的结合

MCTS 的角色

蒙特卡洛树搜索通过随机模拟来评估动作价值，避免了对整棵博弈树的完全展开。在不完美信息场景下，通常采用信息集MCTS（IS-MCTS），即在每次模拟时对隐藏信息进行采样（determinization），将不完美信息问题临时转化为一系列完美信息子问题来求解。

Determinization方法（也称为Perfect Information Monte Carlo，PIMC）的核心思想是：每次模拟时从当前信息集中随机采样一种对手手牌的具体分布，然后将问题当作完美信息博弈求解。最终对多次采样的结果取平均来指导决策。这种方法简单有效，但存在一个被称为"策略融合"（strategy fusion）的根本缺陷——它假设未来决策可以利用当前不可见的信息。例如，某个动作在对手持有A时最优、持有B时也最优，但它们要求后续采取不同的跟进策略，而实际上玩家在未来可能仍然无法区分A和B。IS-MCTS通过在信息集层面而非具体状态层面维护统计量，部分缓解了这一问题。

CFR 的角色

反事实遗憾最小化则是求解不完美信息博弈纳什均衡的主流算法。它通过反复自博弈，累积每个信息集上各动作的"遗憾值"，并据此迭代优化策略，最终收敛到接近均衡的解。Libratus和Pluribus等顶级扑克AI的核心正是CFR的各类变体（如MCCFR、Deep CFR）。

CFR的核心思想可以用"后悔最小化"来直观理解：在每次迭代中，算法计算"如果在某个信息集改用另一个动作，期望收益能提高多少"——这就是该动作的正遗憾值（positive regret）。策略按累积正遗憾值的比例进行更新，即遗憾值越高的动作在未来获得越多的选择概率。Zinkevich等人在2007年证明，经过T次迭代后，CFR产生的平均策略与纳什均衡的距离以O(1/√T)的速率收敛。这一收敛保证是无条件的——无论对手如何行动，长期来看遗憾值的增长都是次线性的。MCCFR（Monte Carlo CFR）通过在每次迭代中只采样部分博弈路径来降低单次迭代成本，使CFR能够扩展到更大规模的博弈。

融合的动机

将两者结合的思路在于：用CFR保证策略的博弈论合理性（避免被对手剥削），用MCTS/搜索在对局实时阶段进行局部深化求解。这与Pluribus"蓝图策略 + 实时搜索"的架构一脉相承。

Pluriubs的架构分为两个阶段：离线阶段在高度抽象的博弈树上运行MCCFR生成"蓝图策略"——这是一个覆盖全局但精度有限的基础策略；在线阶段则在实际对局中，当轮到AI决策时，以蓝图策略为起点，在当前子博弈的更精细表示上进行深度优先搜索。这种搜索被称为"深度受限求解"（depth-limited solving），它只展开几步未来动作，用蓝图策略的价值作为叶节点估值。关键创新在于搜索时不仅优化自己的策略，还要考虑对手可能的最佳反应，这保证了搜索结果不会引入可被利用的弱点。这一"粗粒度全局 + 细粒度局部"的范式正是MCTS与CFR融合的典型体现。

核心瓶颈：搜索抽象化

什么是抽象化

开发者遇到的搜索抽象化瓶颈，是这类项目最典型也最棘手的挑战。所谓抽象化，是指将海量的原始博弈状态聚类归并为数量可控的抽象状态，从而让CFR/搜索能够在有限计算资源下收敛。

抽象化通常分为两类：

信息抽象（Information Abstraction）：将战略上相似的手牌/局面归为一类。例如扑克中把点数接近、胜率相当的牌型合并。
动作抽象（Action Abstraction）：减少可考虑的动作数量，例如在下注博弈中只保留几个典型的下注尺度。

在德州扑克AI的发展史中，信息抽象技术经历了多代演进。早期的Tartanian系列使用基于期望手牌强度（Expected Hand Strength，EHS）的k-means聚类，将翻牌后数百万种可能手牌组合压缩到几千个抽象桶中。后来的方法引入了"潜力感知"聚类——不仅考虑当前手牌强度，还考虑在未来公共牌揭示后手牌强度的分布（即听牌潜力）。更先进的方法如ACPC竞赛中的获胜者Baby Tartanian8使用了"蓝图到精细"的渐进式抽象方案，在早期行动中使用粗糙抽象，而在关键决策点动态切换到更细致的抽象。这些经验对多米诺骨牌的抽象设计具有直接参考价值。

抽象化的两难

瓶颈的本质在于一个根本性权衡：

抽象过粗，AI会丢失关键的战略区分能力，导致策略质量下降；抽象过细，则状态空间无法压缩，CFR无法在合理时间内收敛。

对于多米诺骨牌而言，如何设计一个既能捕捉"哪些骨牌已出、哪些花色被封锁、队友可能持有什么"等关键特征，又能大幅压缩状态数的抽象方案，是决定项目成败的关键。

可能的破局方向

领域知识驱动的特征抽象

一个务实的方向是引入领域专家知识，手工设计紧凑的状态特征：如各花色的剩余数量、每位玩家已"过牌"（pass）暴露的花色缺失信息、当前得分等。基于这些特征进行聚类，往往比纯数据驱动的抽象更高效。

从手工抽象转向学习式抽象

业界趋势是用神经网络替代人工抽象，即Deep CFR路线——用函数逼近器直接学习信息集到策略/遗憾值的映射，让网络自己"隐式"完成抽象。这能规避手工聚类的信息损失，但需要更多训练数据和调参经验。

Deep CFR由Brown等人在2019年提出，用两个神经网络分别逼近累积遗憾值函数和平均策略函数，从而绕过了显式枚举所有信息集的需要。训练过程中，CFR的遍历轨迹被存储为经验样本，网络通过监督学习拟合这些样本。其核心优势在于泛化能力——面对未见过的信息集，网络可以基于相似特征给出合理估计，这相当于隐式完成了抽象化。然而实践中Deep CFR面临显著挑战：样本效率低（需要大量遍历才能生成足够训练数据）、函数逼近误差可能破坏收敛保证、以及超参数敏感性高。对于计算资源有限的个人开发者，可能需要结合领域知识设计网络输入特征，以降低学习难度。

借鉴信号博弈建模

针对团队协作难题，可参考桥牌AI（如WBridge5、NooK）在建模队友信号上的方法，将出牌序列作为通信信道显式建模，让AI学会"用出牌说话"。

传统强桥牌AI如WBridge5主要依赖Determinization + Double Dummy Solver的组合，即采样对手手牌后用完美信息求解器计算最优打法。2022年NukkAI的NooK则引入了深度学习，用神经网络预测最佳出牌，并在对队友意图的推理上展现出超越传统方法的能力。对于多米诺骨牌AI，一个可行的方案是在信息集表示中显式编码"队友的出牌历史所传递的信号"，例如"队友在第3轮有其他选择但仍选择出了6点花色"这类观察，使AI能够学习利用这些隐式通信来更精确地推断队友手牌分布。

结语：小众项目的普适价值

这个多米诺骨牌AI项目虽小，却完整浓缩了不完美信息博弈AI的核心命题：如何在信息不对称、状态爆炸、隐式协作的三重压力下，构建既稳健又可计算的策略。开发者遇到的抽象化瓶颈，恰恰是从Libratus到Pluribus这些里程碑工作都必须直面的难关。

对于社区中的算法爱好者而言，这类实践项目提供了绝佳的学习样本——它提醒我们，博弈AI的进步不仅在于算力堆砌，更在于对问题结构本身的深刻理解与巧妙抽象。从更广阔的视角看，不完美信息博弈的求解技术正在向更多现实场景渗透：网络安全中的攻防博弈、自动驾驶中的多车交互、商业谈判中的策略优化——这些领域都共享"在不确定性下做出鲁棒决策"这一核心挑战，而多米诺骨牌这样的"玩具问题"恰恰是磨练方法论的理想试验场。