Summary
Solving complex games often involves looking at many possible moves, which is very slow and usually faster on normal computer processors (CPUs) than on graphics cards (GPUs). The authors found a way to prepare the game details ahead of time, turning the problem into a fixed sequence of simple steps that a GPU can run repeatedly without extra overhead. By compiling the game data and using a special GPU feature to replay the solution steps efficiently, their method runs up to 80 times faster on a GPU compared to previous attempts and much faster than CPU methods. This means difficult game problems can be solved much quicker using GPUs with their approach.
Counterfactual regret minimizationGPU computingCUDA Graph ReplayStatic dataflowGame treeKernel launch overheadCompiler optimizationParallel computingInformation setsReach buffer
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.