将博弈求解算法CFR转化为线性运算，实现超高速并行计算。
Parallelizing Counterfactual Regret Minimization
- 把CFR算法重构成线性代数操作，便于并行处理。
- 在GPU上比传统CPU实现快达10000倍。
- 适用于CFR+等主流博弈算法，适合大规模游戏求解者。
并行化在人工智能领域中发挥了关键作用，显著缩短了大型AI模型的训练与评估时间。然而，在计算博弈求解领域，尽管潜力巨大，并行化应用仍相对有限。本文对核心的反事实后悔最小化（Counterfactual Regret Minimization, CFR）算法家族进行了并行化改造，将其重构为一系列线性代数操作，从而可直接利用现有线性代数并行技术加速求解过程。该框架可推广至CFR家族中的其他表格型算法，包括当前最先进的CFR+、折扣版CFR及预测型CFR变体。实验表明，基于GPU的本方法实现相较谷歌DeepMind OpenSpiel在CPU上的实现，速度提升高达四个数量级。
原文摘要 · Abstract (English)
Parallelization has played an instrumental role in the field of artificial intelligence (AI), drastically reducing the time taken to train and evaluate large AI models. In contrast to its impact in the broader field of AI, applying parallelization to computational game solving is relatively unexplored, despite its great potential. In this paper, we parallelize the family of counterfactual regret minimization (CFR) algorithms, which were central to important breakthroughs for solving large imperfect-information games. We present a generalized parallelization framework, reframing CFR as a series of linear algebra operations. Then, existing techniques for parallelizing linear algebra operations can be applied to accelerate CFR. We also describe how our technique can be applied to other tabular members of the CFR family of algorithms, including the state-of-the-art, such as CFR+, discounted CFR, and predictive variants of CFR. Experimentally, we show that our CFR implementation on a GPU is up to four orders of magnitude faster than Google DeepMind OpenSpiel's CFR implementations on a CPU.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。