arXiv:2605.19928cs.GTcs.AI2026-05被引 5

让扑克博弈求解快3倍,单机跑出超大规模策略

Real-Time Parallel Counterfactual Regret Minimization

  • 分7阶段流水线并行,按信息集和节点双维度加速
  • 每轮迭代仅需47-54毫秒,支持超10亿历史树的实时求解
  • 单台桌面设备完成数百次迭代,无需数据中心

对抗性后悔最小化(CFR)是求解大规模不完美信息博弈的核心算法,支撑了无限制德州扑克中的Libratus和Pluribus等突破。在实时博弈系统中,求解器必须在数秒内完成近似均衡策略计算,而迭代次数直接决定策略强度。本文提出首个面向实时深度有限CFR求解的并行框架Parallel CFR,无缝集成剪枝、抽象与先进CFR变体。将每轮迭代分解为七阶段流水线,识别出两种正交并行维度:按信息集和按树节点。叶节点评估通过批量神经网络推理卸载至GPU,构建异构CPU-GPU流水线。在二人无限制德州扑克对局中,Parallel CFR在翻后街实现3.3–3.4倍于单线程基线的速度提升,每轮迭代耗时约47–54毫秒,处理深度有限博弈树中超过10亿种历史路径。所有实验均在单台桌面级设备(NVIDIA DGX Spark)上运行,可在典型实时决策预算内完成数百次迭代,无需数据中心规模基础设施。

原文摘要 · Abstract (English)

Counterfactual Regret Minimization (CFR) is the dominant algorithmic family for solving large imperfect-information games, underpinning breakthroughs such as Libratus and Pluribus in No-Limit Texas Hold'em poker. In real-time game-playing systems, the solver must compute a near-equilibrium strategy within a strict time budget of only a few seconds per decision, and the number of CFR iterations completed in this window directly determines play strength. We present \textbf{Parallel CFR}, the first parallelization framework for real-time depth-limited CFR solving that seamlessly integrates pruning, abstraction, and advanced CFR variants. We decompose each CFR iteration into a pipeline of seven stages and identify two orthogonal dimensions of parallelism: \emph{by information set} and \emph{by tree node}. Leaf node evaluation is offloaded to GPUs via batched neural network inference, creating a heterogeneous CPU--GPU pipeline. Experiments on Heads-Up No-Limit Texas Hold'em demonstrate that Parallel CFR achieves $3.3$--$3.4\times$ speedup over the single-threaded baseline on postflop streets, with per-iteration time of ${\sim}47$--$54$~ms on a depth-limited game tree with over $1$ billion histories. All experiments run on a single desktop-class device (NVIDIA DGX Spark), enabling hundreds of CFR iterations within a typical real-time decision budget without requiring datacenter-scale infrastructure.

博弈求解并行计算深度有限实时系统

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。