GPU-CFR: 80x Faster Counterfactual Regret Minimization by Compiling the Game to Static Dataflow and CUDA Graph Replay

GPU-CFR: Compiling Game Trees for Static Dataflow and CUDA Graph Replay§

Counterfactual regret minimization (CFR) is a dominant algorithm for solving imperfect-information games, but its iterative tree traversal with millions of tiny gather/scatter operations makes it notoriously inefficient on GPUs. Despite massive parallelism, prior GPU implementations lose to optimized CPU code because kernel launch overhead and framework dispatch dominate runtime. GPU-CFR addresses this by exploiting a key observation: for a fixed game, the entire operation sequence (shapes, indices, buffer addresses) is known before the first iteration. Only the numerical values change. The authors compile the game once into a static dataflow representation and then replay it with a single CUDA graph launch.

Core Methodology: Static Dataflow Compilation§

The CFR iteration updates regrets and strategies by traversing the game tree. Mathematically, for each information set $I$ and action $a$, the counterfactual regret is updated as:

$$R^T(I, a) = \sum_{t=1}^T r^t(I, a)$$

where $r^t(I,a)$ is the instantaneous counterfactual regret at iteration $t$. The strategy is then derived via regret matching:

$$\sigma^{T+1}(I, a) = \frac{\max(R^T(I,a), 0)}{\sum_{a'} \max(R^T(I,a'), 0)}$$

The key bottleneck is the traversal: each iteration performs millions of small gather and scatter operations across the tree. GPU-CFR compiles the tree into flat arrays:

• Edge and information-set arrays: flattened representations of the tree structure.
• Precomputed indices: all gather/scatter indices are computed once and stored.
• Depth-level batched passes: operations are grouped by tree depth, enabling batched execution that eliminates per-node overhead.
• Static chance folding: chance nodes are folded into the dataflow, removing dynamic branching.
• Dual-lane reach buffer: reduces the number of framework operations by up to 18.1x.

Because shapes, indices, and buffer addresses never change across iterations, the entire CFR update can be recorded once as a CUDA Graph and replayed with a single launch. This eliminates kernel launch overhead and framework dispatch, which previously dominated runtime.

Implementation Details§

GPU-CFR is implemented as a compiler and runtime. The compiler takes a game description (e.g., in a generic tree format) and produces a static dataflow graph. The runtime executes this graph on GPU using CUDA Graph Replay or on CPU with optimized batched passes. On CPU, the optimized path reproduces reference iterates bitwise, ensuring correctness. Tree construction and graph capture costs are amortized within the first solve. The system is evaluated on an eight-game suite spanning card, dice, and board games. On a single A100, it achieves 29.8–80.4x speedup over the fastest prior GPU CFR, and 14–258x over LiteEFG (a fast CPU implementation) on the four largest games. Notably, the compiled representation alone (without GPU) runs 2.2–51.1x faster than the GPU baseline on eight CPU threads, demonstrating the power of the compilation approach.

Code Snippet: Compiling a CFR Iteration to Static Dataflow§

import torch
import numpy as np

class StaticCFRCompiler:
    def __init__(self, game_tree):
        self.tree = game_tree
        self.edges = []
        self.infosets = []
        self.depth_levels = []
    
    def compile(self):
        # Flatten tree into edge and infoset arrays
        self._flatten_tree(self.tree)
        # Precompute gather/scatter indices for each depth level
        self._precompute_indices()
        # Batch operations by depth
        self._batch_by_depth()
        return StaticDataflow(self.edges, self.infosets, self.depth_levels)
    
    def _flatten_tree(self, node, depth=0):
        if node.is_terminal:
            return
        if node.is_chance:
            # Static chance folding: distribute probabilities into edges
            pass
        else:
            self.infosets.append(node.infoset_id)
        for action, child in node.children.items():
            self.edges.append((node.id, child.id, action))
            self._flatten_tree(child, depth+1)
        self.depth_levels.append((node.id, depth))
    
    def _precompute_indices(self):
        # Build index tensors for gather/scatter
        pass
    
    def _batch_by_depth(self):
        # Group operations by depth for batched execution
        pass

# Runtime: replay CUDA graph
class CFRRunner:
    def __init__(self, dataflow, device='cuda'):
        self.dataflow = dataflow
        self.device = device
        self.graph = None
    
    def capture(self, state):
        # Record the CFR iteration as a CUDA graph
        torch.cuda.synchronize()
        g = torch.cuda.CUDAGraph()
        with torch.cuda.graph(g):
            self._cfr_iteration(state)
        self.graph = g
    
    def _cfr_iteration(self, state):
        # Batched depth-level passes
        for depth_ops in self.dataflow.depth_levels:
            # e.g., gather regrets, compute counterfactual values, scatter updates
            pass
    
    def step(self, state):
        # Replay the captured graph
        self.graph.replay()
        return state

Results and Impact§

GPU-CFR demonstrates that algorithmic and compiler-level optimizations can overcome hardware limitations for irregular, fine-grained workloads. By eliminating dynamic dispatch and exploiting static structure, it makes GPU CFR practical and significantly outperforms both prior GPU and CPU baselines on mid-to-large games without changing the update rule. This work has implications for accelerating other iterative, tree-structured algorithms in AI and operations research.