GPU-CFR: 80x Faster Counterfactual Regret Minimization by Compiling the Game to Static Dataflow and CUDA Graph Replay
Source: https://arxiv.org/abs/2609.11923
Authors: Boning Li, Longbo Huang
Published: 2026-09-10
Categories: cs.DC, cs.AI, cs.GT, cs.MS, cs.PL
PDF: https://arxiv.org/pdf/2609.11923
Abstract
Counterfactual regret minimization (CFR) is one of the few large numerical workloads that still runs faster on CPUs than on GPUs. Each iteration sweeps a game tree with up to billions of states in millions of small, interdependent gather and scatter steps issued through a generic tree interface. On a GPU every kernel finishes in microseconds, so kernel launches and framework dispatch dominate the run time, and prior GPU implementations have lost to optimized CPU code. We observe that for a fixed game, everything about a CFR iteration except the numerical values is known before the first iteration runs. We propose GPU-CFR, a compiler and runtime built on this observation. It compiles any game once into static dataflow: flat edge and information-set arrays, precomputed indices, and depth-level batched passes fix the entire operation sequence, and only solver state changes between iterations. Static chance folding, depth-level execution blocks, and a dual-lane reach buffer cut the number of framework operations by up to 18.1x. Because shapes, indices, and buffer addresses never change, CUDA Graph Replay records the iteration once and replays it with a single graph launch. On one A100, across an eight-game suite that spans card games, dice games, and board games, GPU-CFR runs 29.8--80.4x faster than the fastest prior GPU CFR on the same accelerator, and 14--258x faster than LiteEFG, one of the fastest open-source CPU implementations, on the four largest games. The compiled representation carries most of that margin: on eight CPU threads with no accelerator it is already 2.2--51.1x faster than the GPU baseline. On the CPU the optimized path reproduces the reference iterates bitwise, and tree construction and graph capture pay for themselves within the first solve. GPU-CFR beats every CPU and GPU baseline on the mid-to-large games of the suite without changing the update rule.
中文概要
反事实遗憾最小化(CFR)是少数仍跑得比 CPU 还慢的大规模数值负载——每轮迭代要遍历包含数十亿状态的博弈树,通过通用树接口发起数百万次小而相互依赖的 gather/scatter。GPU 上每个 kernel 微秒内结束,内核启动与框架调度占满运行时间,先前的 GPU 实现都跑不过优化过的 CPU 代码。
作者观察到:对固定博弈,CFR 迭代除了数值本身之外的所有信息,在第一轮迭代前就已经确定。
GPU-CFR 是一套编译器 + 运行时,把任意博弈一次性编译成静态数据流:
- 扁平化边与信息集数组、预计算索引、按层级批处理——把整个操作序列固化下来,迭代之间只更新求解器状态。
- 静态机会折叠、按层级执行块、双 lane reach buffer 把框架操作数削减到 18.1× 之内。
- 因为 shape、索引、buffer 地址都不变,CUDA Graph Replay 一次性记录整轮迭代,之后用单次 graph launch 即可重放。
在单卡 A100 上的 8 个博弈套件(覆盖扑克、骰子、棋类):
- 比同加速器上最快的旧 GPU CFR 快 29.8–80.4×。
- 比 LiteEFG(最快的开源 CPU 实现之一)在最大 4 个博弈上快 14–258×。
- 仅编译后的表示本身,在 8 个 CPU 线程、无加速器时,就已比 GPU baseline 快 2.2–51.1×。
- CPU 上优化路径按位复现参考迭代,树构造与 graph capture 在首次求解中即可回本。
意义:CFR 不再是 GPU 难啃的硬骨头——把"游戏"与"求解"在编译期分离后,游戏级数据流可以在 GPU 上高效重放,不动更新规则即可拿下中大型博弈。