Parallelizing Counterfactual Regret Minimization
This work addresses the computational bottleneck of solving large imperfect-information games, offering a dramatic speedup for a key class of algorithms in game theory and AI.
The paper introduces a parallelization framework for counterfactual regret minimization (CFR) algorithms, reframing them as linear algebra operations to leverage GPU acceleration. Their GPU implementation achieves up to four orders of magnitude speedup over CPU-based CFR implementations in OpenSpiel.
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.