GPU-parallelized CFR runs 10,000x faster than DeepMind's OpenSpiel

Parallelization has revolutionized training for large AI models, but its application to computational game solving has lagged. In a new paper, Juho Kim and Tuomas Sandholm address this by parallelizing the family of Counterfactual Regret Minimization (CFR) algorithms—the engine behind breakthroughs in solving large imperfect-information games like poker. They present a generalized framework that reframes CFR iterations as a series of linear algebra operations, allowing existing GPU-optimized linear algebra libraries (e.g., cuBLAS) to accelerate computation. Experimentally, their GPU implementation achieves up to four orders of magnitude (10,000x) speedup over the CPU-based CFR implementations in Google DeepMind's OpenSpiel library.

The technique extends to other tabular CFR variants, including CFR+, discounted CFR, and predictive CFR, covering the current state-of-the-art. By mapping iterative regret updates to matrix operations, the method not only accelerates training but also opens the door to larger game state spaces and more complex multi-agent scenarios. This work could dramatically reduce the time required to develop AI for strategic decision-making in domains ranging from cybersecurity negotiation to autonomous driving planning, where imperfect information and multiple agents are the norm.