GPU-CFR speeds game-tree solving up to 80x

GPU-CFR beat the fastest prior GPU implementation of counterfactual regret minimization by 29.8 to 80.4 times across eight games on a single A100, according to a paper posted September 12. Counterfactual regret minimization is the standard algorithm behind poker solvers and other imperfect-information game research. It has stayed CPU-bound even as GPUs took over most of machine learning.

Each iteration issues millions of tiny gather and scatter steps across a game tree, and kernel-launch overhead usually erases whatever a GPU offers. GPU-CFR gets around that by treating the game as fixed ahead of time. It compiles the game once into flat arrays of edges and information sets with the indices already computed, grouped into batched passes by depth.

It then records one iteration with CUDA Graph Replay and relaunches that recorded graph on every following round instead of issuing new kernel calls.

That compiled structure alone helps without a GPU. Run on eight CPU threads, it's still 2.2 to 51.1 times faster than the baseline the paper compares against. The paper also reports 14 to 258 times the throughput of LiteEFG on the four largest of the eight games tested.