GPU-Accelerated Counterfactual Regret Minimization

Counterfactual regret minimization is a family of algorithms of no-regret learning dynamics capable of solving large-scale imperfect information games. We propose implementing this algorithm as a series of dense and sparse matrix and vector operations, thereby making it highly parallelizable for a graphical processing unit, at a cost of higher memory usages. Our experiments show that our implementation performs up to about 352.5 times faster than OpenSpiel's Python implementation and up to about 22.2 times faster than OpenSpiel's C++ implementation and the speedup becomes more pronounced as the size of the game being solved grows. Counterfactual regret minimization (CFR) (Zinkevich et al., 2007) is a family of algorithms of noregret learning dynamics capable of solving large-scale imperfect information games. Its variants dominated the development of AI agents for large imperfect information games like Poker (Tammelin et al., 2015; Moravčík et al., 2017; Brown & Sandholm, 2018; 2019b) and The Resistance: Avalon (Serrino et al., 2019) and were components of ReBeL (Brown et al., 2020) and student of games (Schmid et al., 2023).