Parallelizing Counterfactual Regret Minimization

About

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.

Juho Kim, Tuomas Sandholm · 2026

Related benchmarks

Task	Dataset	Result
Solving Zero-Sum Partially Observable Stochastic Games (zs-POSGs)	Kuhn Poker	Time—	6
CFR solver performance	Kuhn Poker	Average Iteration Time14.3	4
CFR solver performance	Tiny battleship	Average Iteration Time24.2	4
CFR solver performance	battleship Medium	Average Iteration Time19.4	4
CFR solver performance	Large battleship	Average Iteration Time22	4
Counterfactual Regret Minimization	Leduc Poker	Average Iteration Time (ms)25.2	4
CFR solver performance	Liar's Dice	Average Iteration Time (s)38.6	4
CFR solver performance	Battleship Small	Average Iteration Time25.7	4
Counterfactual Regret Minimization	Tiny battleship	Speedup6.9	1
Counterfactual Regret Minimization	Liar's Dice	Speedup1.5	1