GPU-accelerated Counterfactual Regret Minimization : Massively parallel computation for real-time decision making in imperfect information settings

Sammanfattning

Artificial Intelligence (AI) evaluation through gameplay has a rich history, from groundbreaking victories such as Deep Blue’s triumph over Kasparov in chess to AlphaGo’s win over Lee Sedol in the game of Go. Unlike perfect information games, which offer complete knowledge of past events, imperfect information games like poker present challenges due to their inherent uncertainty. Counterfactual Regret Minimization (CFR) stands as the state-ofthe- art algorithm for solving imperfect information games, offering powerful implications for decision-making in dynamic environments. However, the computational demands of CFR become prohibitive for large-scale games, requiring significant computational resources. Enhancing the performance and power efficiency of CFR not only expands its applicability to more complex games but also facilitates real-time decision-making scenarios. Leveraging the parallel processing capabilities of Graphics Processing Units (GPUs), this study aims to optimize CFR efficiency through GPU acceleration. Our GPU implementation is notably more efficient, achieving a 98.6% reduction in energy usage compared to previous research, and 77.7% reduction compared to our own CPU implementation. Furthermore, we introduce a novel hybrid recall abstraction which is evaluated using the accelerated algorithm. The evaluation resulted in finding a strategy for Heads-Up Limit Texas Hold’em with an exploitability of 282 milli-big-blinds per hand (mbb/h). By significantly reducing the hardware requirements, this advancement enables the solution of large-scale games using consumer-grade hardware. In summary, this work showcases the efficacy of GPU acceleration in enhancing CFR efficiency, thereby broadening its applicability and scalability in the realm of imperfect information game solving.