PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Boning Li, Longbo Huang

arXiv:2609.11923v1cs.DCcs.AIcs.GTcs.MScs.PL

TL;DR

CFR has remained difficult to accelerate because each iteration traverses a game tree through small dependent operations, and GPU dispatch can dominate their runtime. GPU-CFR compiles a fixed game into static dataflow and replays iterations with CUDA graphs. Across its eight-game suite, it substantially outperforms prior GPU CFR and, on the four largest games, LiteEFG.

  • Problem

    CFR’s tree traversal involves many small, dependent gathers and scatters, while GPU launches and framework dispatch dominate runtime and prior GPU implementations have lagged optimized CPUs.

    Source: §1 · pp. 1–2

  • Method

    GPU-CFR compiles a fixed game into flat arrays and depth-level batched dataflow, then uses CUDA Graph Replay to execute the fixed iteration sequence.

    Source: §1 · p. 2

  • Results

    29.8–80.4× faster than the matched A100 baseline across eight games, GPU-CFR is also 14–258× faster than LiteEFG on the four largest games.

    Source: §1 · p. 3, §8 · p. 17

  • Takeaways & Limitations

    GPU-CFR beats every tested CPU and GPU baseline on the suite’s mid-to-large games without changing the update rule.

    Source: §1 · p. 3, §8 · p. 17

    External-baseline head-to-head evidence stops at endgame 4’s scale because larger endgame exports and loads would dominate timing.

    Source: §13 · p. 32

Abstract

from arXiv · show

Counterfactual regret minimization (CFR) is one of the few large numerical workloads that still runs faster on CPUs than on GPUs. Each iteration sweeps a game tree with up to billions of states in millions of small, interdependent gather and scatter steps issued through a generic tree interface. On a GPU every kernel finishes in microseconds, so kernel launches and framework dispatch dominate the run time, and prior GPU implementations have lost to optimized CPU code. We observe that for a fixed game, everything about a CFR iteration except the numerical values is known before the first iteration runs. We propose GPU-CFR, a compiler and runtime built on this observation. It compiles any game once into static dataflow: flat edge and information-set arrays, precomputed indices, and depth-level batched passes fix the entire operation sequence, and only solver state changes between iterations. Static chance folding, depth-level execution blocks, and a dual-lane reach buffer cut the number of framework operations by up to 18.1x. Because shapes, indices, and buffer addresses never change, CUDA Graph Replay records the iteration once and replays it with a single graph launch. On one A100, across an eight-game suite that spans card games, dice games, and board games, GPU-CFR runs 29.8--80.4x faster than the fastest prior GPU CFR on the same accelerator, and 14--258x faster than LiteEFG, one of the fastest open-source CPU implementations, on the four largest games. The compiled representation carries most of that margin: on eight CPU threads with no accelerator it is already 2.2--51.1x faster than the GPU baseline. On the CPU the optimized path reproduces the reference iterates bitwise, and tree construction and graph capture pay for themselves within the first solve. GPU-CFR beats every CPU and GPU baseline on the mid-to-large games of the suite without changing the update rule.

1. Introduction

Tabular CFR remains difficult to accelerate because iterations traverse large trees through many small, dependent operations, while GPU dispatch overhead dominates. GPU-CFR compiles a fixed game into static dataflow and combines it with graph replay, achieving large speedups over prior GPU and CPU baselines.

1. Introduction

  • CFR iterations traverse every game-tree node through millions of small, dependent gather and scatter steps that resist batching on wide processors.Deployed implementations therefore use node-wise traversal through a generic game interface.Source: §1 · p. 1
  • GPU kernel work is so short that launches and framework dispatch dominate prior GPU CFR runtimes, leaving iteration times above optimized CPU solvers.For time-bound game-playing agents, solver iteration cost bounds what can be done within a decision budget.Source: §1 · pp. 1–2
  • GPU-CFR compiles a fixed game into flat arrays and depth-level batched passes, using static chance folding and a dual-lane reach buffer.Only solver state changes between iterations.Source: §1 · pp. 2–3
  • Because the compiled sequence has fixed shapes, indices, and buffer addresses, CUDA Graph Replay records it once and replays each iteration with one graph launch.The representation reduces framework work, while graph replay reduces the cost of issuing that work.Source: §1 · p. 3
  • 29.8–80.4× faster than the matched A100 baseline across eight games, GPU-CFR also runs 14–258× faster than LiteEFG on the four largest games.On eight CPU threads, the compiled solver alone beats the A100 baseline by 2.2–51.1×.Source: §1 · p. 3

2. Related Work

Prior work improves CFR’s update rules, approximates or reduces the game, and builds game-solving systems, but accelerator implementations have not overcome the traversal’s execution costs. GPU-CFR instead changes the representation used to execute the tabular sweep.

The CFR family and exact equilibrium solving

  • CFR minimizes counterfactual regret at each information set, while CFR+ changes regret matching and averaging; GPU-CFR targets the execution layer shared by these variants.Its compiled slot representation also supports DCFR and predictive CFR+ under both update orders.Source: §2 · p. 3

Scaling CFR by approximation

  • Sampling, abstraction, pruning, and neural methods reduce the game or the work sampled, while a faster tabular sweep can compose with these methods on the remaining tree.The compiler addresses repeated execution when the full tree is available.Source: §2 · pp. 3–4

Systems and frameworks for game solving

  • LiteEFG compiles games for a single-threaded C++ backend, while other systems parallelize traversal or specialize poker representations and evaluation.GPU-CFR changes the traversal representation, so its CPU arm requires no CFR-specific threading.Source: §2 · p. 4

Accelerators and GPU CFR

  • Earlier GPU CFR systems still ran slower than optimized CPU solvers; GPU-CFR compiles the game into depth-stratified tensors and replays the iteration as one captured CUDA graph.Compilation makes stock PyTorch and CUDA graphs applicable to CFR.Source: §2 · p. 4

3. Preliminaries

The paper models CFR on a finite two-player zero-sum game tree with information sets and reach probabilities. Each iteration propagates reaches, computes values and regrets, then updates strategies and their average.

3. Preliminaries

  • A game is a finite tree of histories owned by either player or chance; terminal histories pay one player and the opposite amount to the other.Chance histories have fixed action distributions.Source: §3 · p. 4
  • An information set groups histories indistinguishable to a player, whose strategy assigns an action distribution to each owned set.The model assumes perfect recall and distinguishes each player’s reach contribution from the counterfactual reach that excludes that player.Source: §3 · p. 4
  • CFR propagates reaches forward, folds terminal payoffs into values backward, accumulates instantaneous regret, then uses regret matching and reach-weighted averaging to update strategy.CFR+ clamps accumulated regret at zero; the cited description says it converges faster in practice than CFR.Source: §3 · pp. 4–5
  • CFR supports simultaneous or alternating player updates; alternating updates expose the first player’s update to the second and require roughly twice the work per iteration.GPU-CFR supports both orders and uniform or linear strategy averaging.Source: §3 · p. 5

4. Compiling CFR onto Accelerators

GPU-CFR separates one-time game compilation from a fixed per-iteration dataflow, making the solver’s work suitable for batched tensor operations and CUDA graph replay. The design reduces dispatch overhead while preserving the reference iteration semantics.

4.1. Compiled game representation

  • The compiler walks the game once and emits flat node, edge, and information-set arrays, then runs a fixed sequence of dataflow operations over them each iteration.Solver state lives in preallocated tensors; the example pipeline flattens the tree into depth-segmented arrays and a values template.Source: §4 · p. 5, §4.1 · p. 5, Figure 2 · p. 6

4.2. One iteration as a fixed dataflow

  • Static chance folding puts each history’s chance-probability product into a build-time values template, removing chance multiplications from the dynamic forward pass.Depth-level blocks batch edges at each depth in one operation, yielding 4–15 blocks per pass across the suite instead of up to 100 stage-by-depth blocks.Source: §4.2 · p. 7
  • A dual-lane reach buffer advances both players’ reaches in one branchless gather, multiply, and scatter, using a sentinel slot for edges that do not belong to that player.The iteration combines this reach pass with backward values, regret accumulation, and the update rule.Source: §4.2 · pp. 6–7
  • 64–152 Aten operations per iteration across the suite, versus 110–1,742 for the reference implementation, result from the fixed schedule and its flat regret scatter.Only the forward and value recurrences add operations proportional to depth.Source: §4.2 · pp. 7–8, Table 1 · p. 8

4.3. CUDA-graph execution

  • Fixed operation sequences, tensor shapes, and buffer addresses let CUDA graphs replay the iteration with one graph launch instead of repeated framework dispatch.Graph replay reduces steady-state iteration time by 1.6–3.6×, with capture costing 0.037–0.301 seconds.Source: §4.3 · pp. 8–9

4.4. Layered verification

  • Compiled eager execution and graph replay agree bitwise within one process, and the compiled dataflow matches the pre-optimization CPU reference bitwise in float32 after 22 iterations on all eight games.Across independent GPU processes, scatter reductions can differ in order; on the HUNL river subgame, 4 of 20 runs reach a second exploitability cluster 0.6% away.Source: §4.4 · p. 9
  • Verification also compares an independent per-node solver, exact best-response oracles, analytic anchors, and operation-count regression gates.The paper reports a test inventory of 499 tests.Source: §4.4 · p. 9

5. The Compiled Iteration, Formally

GPU-CFR formalizes each compiled iteration as indexed operators with fixed, depth-ordered dataflow. The formal properties show how chance folding, branch-free lane updates, and depth scheduling preserve computation while reducing per-iteration work.

5. The Compiled Iteration, Formally

  • The compiled iteration composes three indexed operators and establishes exact chance folding, an exact branch-free dual-lane update, a shortest dependency-respecting depth schedule, and an averaging representability horizon.The forward pass runs in increasing depth, while the backward pass and regret update run in decreasing depth.Source: §5 · pp. 9–10
  • Chance folding removes chance edges from the dynamic pass while preserving values, applying each terminal’s chance product exactly once.At the root, the resulting value is the expected payoff under the strategy profile.Source: §5 · p. 10
  • The compiled slot map resolves the dual-lane case distinction at build time, leaving no per-edge predicate evaluation during execution.The update computes the case definition exactly for each lane, block, and edge.Source: §5 · p. 10
  • The depth schedule uses the minimum D dependency-respecting groups, with c1 + c2D operator invocations independent of node and edge counts.Across the suite, c1 ≈ 31 and c2 = 8; the measured schedule is nearly flat in tree size across four decades, while the reference uses up to 100 groups where this schedule uses 8.Source: §5 · pp. 10–11
  • The representability horizon for unrescaled linear averaging is an order-of-magnitude resolution scale, not an exact stalling point.The bound assumes normal-range sums and x_T ≥ c > 0; exact stalling depends on the rounded trajectory, and GPU-CFR stores the averaging accumulator in float64.Source: §5 · p. 11

6. Experimental Setup

The evaluation uses separate suites for main timing and regression, update-rule comparisons, and extended poker tests. It compares GPU, compiled CPU, and prior solver backends on shared game representations, with repeated timing measurements under a stated protocol.

6. Experimental Setup

  • The eight-game main suite spans 54 to 275,983 information sets and supports timing, operation-count, and reference-parity results.Separate suites add twelve games for update-rule comparisons and poker endgames and larger instances for extended head-to-head tests.Source: §6 · p. 11
  • The backend matrix runs GPU-CFR on one A100 in eager or CUDA Graph mode, its compiled tensor dataflow on eight CPU threads, and prior GPU, CPU, and OpenSpiel implementations.The GPU modes differ only in dispatch; the main comparison uses simultaneous vanilla CFR for LiteEFG and matched update order for Kim’s GPU backend.Source: §6 · pp. 11–12
  • Table 2 reports benchmark suite counts, sequential blocks per pass, per-iteration PyTorch/Aten operations, and maximum absolute regret difference after 22 float32 iterations.The operation counts are for the reference implementation and compiled dataflow.Source: Table 2 · p. 12
  • For poker subgames and endgames, the compiled representation is exported to LiteEFG’s format and loaded through the Kim adapter; conversions are checked for structural counts and small-game behavior.Section 13 reports a poker value-agreement certificate.Source: §6 · p. 12
  • Timing rows use 1,000 CFR+ iterations, with GPU steady-state measurements after 50 warmups; construction and graph capture are measured separately from training calls.Table cells report medians over repeated runs in independent low-load processes.Source: §6 · p. 12

7. Results

GPU-CFR's graph path outperforms prior GPU and CPU implementations, with the margin especially large on bigger games. The results also separate the gains from compiling a fixed dataflow from those of graph replay.

Cross-framework timing

  • 29.8–80.4× faster than Kim across the eight-game suite; the compiled solver is also 2.2–51.1× faster than the A100 baseline on eight CPU threads.The graph path has a 44.1× median speedup over Kim.Source: §7 · p. 12, Table 3 · p. 13
  • 14–258× faster than LiteEFG on the four largest games, with graph replay extending the compiled solver’s eight-thread CPU advantage.The eight-thread arm alone is 4.4–25.8× faster on those games.Source: §7 · p. 13

Where the speed comes from

  • 18× fewer Aten operations and 19× lower time from compilation; graph replay then cuts time a further 1.6×, for a 29× end-to-end ladder.The eager path issues 87 kernel launches per iteration; graph replay issues one graph launch and keeps the GPU busy 94% of the time.Source: §7 · pp. 13–14, Figure 4 · p. 13

Graph replay

  • 3.6× on Kuhn to 1.6× on the HUNL turn subgame is the graph-over-eager speedup, shrinking as kernel work grows with tree size.The reported per-iteration times are steady-state CFR+ times.Source: §7 · p. 14, Figure 7 · p. 14

Scaling

  • 37.9× more nodes increased iteration time only 2.95× as HUNL turn trees grew from 4 to 24 hands per player.The operation sequence stays fixed while batch widths grow; achieved bandwidth reaches 5.5% of A100 peak in the bytes-moved model.Source: Figure 5 · p. 13, §7 · p. 14

Quality against wall-clock

  • 3.8–44× sooner to the tested exploitability thresholds than Kim’s A100 arm, with disjoint bootstrap intervals.The thresholds are 10, 3, and 1.5 times Kim’s 30-second exploitability; the comparison uses matched CFR+ semantics.Source: §7 · p. 15, Figure 8 · p. 15, Table 5 · p. 16

Repeated solves of one tree

  • Setup is repaid within the first solve: GPU-CFR takes 4.936 s from specification to solution, versus 11.893 s for Kim and 102.160 s for LiteEFG for 1,000 iterations.The comparison is for the HUNL turn tree; building and compiling dominate setup, while graph capture is an order of magnitude cheaper.Source: Table 4 · p. 13, §7 · p. 16

Libratus endgame

  • 870× faster than LiteEFG on full-range Libratus endgame 4, where the three backends agree on value to 2.5 chips.The tree has 96,159 Infosets and 36 million states, and is almost entirely terminal.Source: §7 · p. 16, Table 7 · p. 17

8. Conclusion

GPU-CFR beats the prior GPU CFR solver and CPU LiteEFG on large games while converting a fixed game into a replayable sequence of tensor operations. The conclusion frames this approach as applicable to tabular-CFR-based solvers without changing their update algorithm.

8. Conclusion

  • 0.397 ms per CFR+ iteration on the 83k-Infoset HUNL turn subgame; GPU-CFR is 29.8–80.4× faster than prior GPU CFR and 14–258× faster than LiteEFG on the four largest games.The prior GPU comparison uses identical A100 hardware; the CPU comparison is against LiteEFG.Source: §8 · p. 17
  • A fixed game compiles into 64 to 152 tensor operations that CUDA Graph Replay executes with one launch, replacing pointer-chasing traversal.The conclusion describes flat arrays, folded chance, depth scheduling, and branchless edges as parts of the compiled representation.Source: §8 · p. 17
  • The pipeline applies to two-player zero-sum games and any regret-minimization rule, and its iterates agree bitwise with the reference implementation.The paper states that solvers built on tabular CFR inherit the speedup without changing their algorithm.Source: §8 · p. 17

9. HUNL Subgame Construction

The HUNL benchmarks use native river and turn subgames designed to reflect repeated re-solving workloads. The river game is independently reconstructed for external comparisons, while the turn game is not because its all-in handling cannot be matched across streets.

9. HUNL Subgame Construction

  • The native river game has 3,000 Infosets, while the turn game has 83,040 Infosets and adds a 44-card river chance layer between betting streets.The river uses one betting street; the turn uses two and has all-in handling.Source: §9 · p. 23
  • The two fixed-board, fixed-range subgames reproduce the repeated re-solving structure of HUNL-style workloads.The paper connects this structure to online subgame solving under second-scale time budgets.Source: §9 · p. 23
  • The river nuts anchor yields +10.000033 under the game’s chance discretization, and the quads anchor forces root value +10.The solver and brute-force best-response enumeration reproduce the river anchor to 10−10; the quads case reaches exploitability below 10−3 after 1,000 iterations.Source: §9 · p. 23
  • The external river reconstruction matches GPU-CFR on 137,416 nodes, 9,161 deals, and every terminal payoff after mapping hands and actions by name.The reconstruction uses OpenSpiel universal_poker; hand-slot and opening-action orders differ from GPU-CFR’s.Source: §9 · pp. 23–24
  • After three alternating CFR+ iterations, the reference and GPU-CFR river exploitabilities are 1.6107099050007263 and 1.6107099050007272, respectively.The reference solver is separately pinned against OpenSpiel on Kuhn poker; the generic best-response oracle is validated against brute-force enumeration on reduced instances.Source: §9 · pp. 23–24
  • The turn subgame is not reconstructed in universal_poker because no single chips-behind parameter makes all-in deduplication match on both streets.The turn subgame is therefore reported against the authors’ own arms rather than that external reconstruction.Source: §9 · p. 24

10. Benchmark Protocol and Environment

The benchmark protocol reports GPU steady-state iteration times separately from fresh-solver training calls, using a specified A100 and software stack. Solve settings, timing controls, and archived artifacts support comparisons and reproduction.

10. Benchmark Protocol and Environment

  • Measurements used one NVIDIA A100 80GB PCIe with PyTorch 1.13.1+cu117 and CUDA 11.7; CPU rows used eight pinned physical cores.The host had dual Intel Xeon Gold 6348 processors and 256 GB of memory; the paper also remeasured stages under PyTorch 2.5.1+cu121.Source: §10 · p. 24
  • GPU steady-state time covers iterations 51–1050 after 50 state-changing warmups, whereas training-call time includes three eager warmups and graph capture.Training calls exclude game specification, compilation, solver construction, and exploitability evaluation; GPU times use CUDA events and CPU rows use wall-clock time.Source: §10 · p. 24
  • Timing medians use 20 repetitions for GPU-CFR and its CPU arm, versus 10 for vanilla-CFR and baselines; results come from a serial gated campaign.The campaign covered 2,293 measurement cells over 24.2 hours, with load recorded for archived results.Source: §10 · pp. 24–25
  • Aten operation counts are intercepted reproducibly, and peak GPU memory is reported from PyTorch’s allocated and reserved memory counters.Operation counts are collected with TorchDispatchMode; memory values are reported in binary megabytes.Source: §10 · p. 25
  • The solve protocol uses CFR+ with linear averaging, simultaneous updates, float32, seed 0, and exploitability measured as NashConv/2.The update-rule study instead sweeps four rules under both update orders on CPU at T=1,000.Source: §10 · p. 25, Table 8 · p. 25
  • Backend conversions are checked by structural counts and behavioral values, and the artifact includes archived JSONL results, generators, scripts, and tests.The Dark Hex 2×2 conversion reproduces its known first-player-win value of +1 with exploitability approaching zero.Source: §10 · p. 25

11. Correctness Test Inventory

The test inventory checks parity with reference solvers, graph behavior, structural invariants, and game-value correctness. It also audits seed effects and reduction-order variability, which motivate using CPU results for close update-rule comparisons.

11. Correctness Test Inventory

  • The optimized path matches the reference loop bitwise in float32 after 22 iterations on all eight full-size games, and independent HUNL solvers agree to 10−9.Parity tests also cover Kuhn, a chance-heavy synthetic game, reduced HUNL instances, and float64 CPU comparisons; the suite contains 499 tests.Source: §11 · p. 26
  • Graph replay and eager execution are checked across variants, while tests assert buffer coverage, batching equality, fallback behavior, and safe handling of degenerate games.Graph-versus-eager parity is tested over 30 iterations; replacing a persistent tensor after capture must trigger an error before replay.Source: §11 · p. 26
  • All eight games pass the seed-invariance permutation test at α=0.05, with minimum p=0.15.CPU runs are pairwise identical; GPU runs are compared as distributions because reduction order is unordered.Source: §11 · p. 26
  • At T=1,000 in float32, reduction-order spread ranges from 0.004% to 65%, with a 3.5% median across sixteen cells.At T=8,000 in float64 on Leduc, median spread is 31%; regret matching+ can amplify last-bit regret differences into changed strategy supports.Source: §11 · pp. 26–27
  • The update-rule study runs on CPU because fixed reduction order yields repeatable results, while GPU within-cell spread can exceed differences between close medians.The paper reports per-iteration timing is unaffected, moving by less than 2% across the logged load range.Source: §11 · p. 27
  • The generic best-response evaluator is checked against an exact recursive oracle, analytic poker anchors, and known game values.The oracle is itself validated by brute-force pure-strategy enumeration on reduced games.Source: §11 · p. 27

12. Additional Results

Additional results examine timing variability, precision, GPU comparisons, memory use, solver reuse, and whether update-rule rankings transfer across implementations. The cross-implementation check finds matching rankings in all 10 comparisons with a unique winner on both sides, while two tied comparisons are excluded.

12. Additional Results

  • Table 9 measures one-time setup and per-call phases alongside wall-clock for 1, 2, 10, and 100 reused-solver solves, compared with rebuilding for each solve.Across 100 reused solves, per-solve time varied by at most 0.3% on the HUNL turn subgame and 0.0% on endgame 4.Source: §12 · p. 27, Table 9 · p. 28
  • Table 10 reports peak allocated and reserved GPU memory per game for the 1,000-iteration float32 CFR+ solve.Reserved memory includes the private CUDA-graph capture pool.Source: §12 · p. 27, Table 10 · p. 28
  • Within 2% on the four largest games, the graph path has low timing dispersion; spread is concentrated on the smallest trees and eager execution.The eager path remains sensitive to host scheduling at every size.Source: §12 · p. 27
  • 0.999× and 0.991× float64-to-float32 time on Leduc and Liars Dice, respectively, with exploitability changing by at most 6.3%.The reported exploitability pairs are 6.636e−3 vs. 6.240e−3 and 3.441e−3 vs. 3.445e−3.Source: §12 · p. 27
  • 11–176× faster than OpenSpiel on the four larger shared games, Kim’s GPU backend sees fixed launch overhead dominate on Kuhn and Dark Hex.Source: §12 · p. 27

12.1. Cross-implementation check of the update-rule study

  • 10 of 10 cross-implementation comparisons with a unique winner agree on the update-rule ranking; two further comparisons are excluded because at least one side ties.Rankings are compared within each backend, game, and update order, not by absolute values across backends.Source: §12.1 · p. 27, Table 12 · p. 30
  • 185× and 213× are the reported GPU-CFR speedups over LiteEFG’s simultaneous vanilla CFR on Liar’s Dice and Battleship, respectively.LiteEFG’s alternating CFR+ preset is 1.28–1.47× more costly per iteration; its matched-iteration convergence advantage mixes update variant and order.Source: §12.1 · pp. 28–29

13. Poker Head-to-Heads and the Value-Agreement Certificate

The section exports poker trees for external solvers and checks agreement using structural, value-based, and matched-variant comparisons. On Libratus endgame 4, GPU-CFR completes 200 iterations 870× faster than LiteEFG, while the external head-to-head evidence does not extend to endgame 3.

13. Poker Head-to-Heads and the Value-Agreement Certificate

  • The exporter streams the tree to LiteEFG’s generic extensive-form format, and structural checks reproduce Kuhn exploitability bitwise and match sequence counts on larger poker trees.For example, the endgame 4 sequence counts match at 19,741 and 27,497.Source: §13 · pp. 30–31
  • Using globally unique child-node names instead of action labels silently split each infoset’s action sets; on Kuhn, this raised sequence counts from 13 to 25 per player.Labeling actions by child position fixes the issue, with the exporter validating action order across infoset members.Source: §13 · p. 31
  • Eq. (16) bounds value disagreement between backends using each profile’s NashConv; it needs only two scalars per backend and applies even when structural comparison is impractical.The paper reports this identity as the check that caught the adapter’s action-labeling bug.Source: §13 · p. 31
  • 1.27 × 10−5 vs. 1.25 × 10−5 exploitability at 8,000 iterations, GPU-CFR and LiteEFG agree within 1.6% when CFR+, alternating updates, linear averaging, and float64 are matched.Their game values agree to 3 × 10−8; the matched configuration isolates algorithm agreement from update-order differences.Source: §13 · p. 31
  • At most 24% of the certificate bound is used in every river-subgame backend pair; an eightfold iteration increase shrinks the three-way value spread 12-fold, from 1.02 × 10−3 to 8.58 × 10−5.Table 13 compares the three backends on the same exported 137,415-state river subgame, each using its native CFR+ preset.Source: §13 · p. 31, Table 13 · p. 32
  • 870× faster than LiteEFG for 200 CFR+ iterations on Libratus endgame 4, GPU-CFR’s values agree within 2.5 chips across three backends against gaps reaching 77 chips.The value discrepancy uses 1.4% of the bound in Eq. (16); the two GPU backends agree within 0.39 chips at 1,000 iterations.Source: §13 · pp. 31–32
  • External-baseline comparisons stop at endgame 4: endgame 3’s export would exceed 6 GB, while LiteEFG loading already peaks at 24.4 GiB on the 2.6× smaller endgame 4.Source: §13 · p. 32

14. Kernel-Level Profile and Alternative Execution Models

The appendix profiles graph replay and alternative execution models, then details how GPU-CFR compiles a game into a fixed schedule and establishes correctness and scope properties of that schedule. The proofs cover folded chance, dual-lane reach updates, depth scheduling, and finite-precision averaging.

14. Kernel-Level Profile and Alternative Execution Models

  • Graph replay reduces host submissions from 87 eager launches to one graph launch per iteration and raises GPU residency above 90%.Across 1, 10, and 100 iterations per graph, per-iteration time is unchanged within measurement noise; gather kernels account for 58% of GPU time, and the device is latency-bound on small grids.Source: §14 · p. 33
  • Inductor is 11% faster than CUDA graph replay on the turn subgame, but 1.4× slower on Leduc; reduce-overhead mode is no faster in either case.Inductor does not fuse the gather and scatter kernels, takes 4.025–4.747 s to compile on the turn subgame, and reorders reductions so its floats differ from eager iterates. The fused Triton path issues 2D + 5 launches and agrees with the generic path to 10^-9 in float64.Source: §14 · pp. 33–34

15. Compiler Passes and Memory Plan

  • Compilation validates a tabular game, emits flat node, edge, and information-set arrays, sorts edges into depth blocks, and folds chance work into values.Rule-specific hooks bind into the shared iteration schedule. The memory-fit estimate is a planning indicator, and the solver builds regardless.Source: §15 · p. 36

16.1. Proposition 1: folded chance is exact

  • Folded chance preserves expected-payoff values because chance probabilities enter the template, while chance-edge multipliers remain 1 to avoid applying a probability twice.The proof also identifies dynamic multipliers other than 1 on chance edges as a violation of that invariant.Source: §16.1 · p. 38

16.2. Proposition 2: the dual-lane update is exact

  • The dual-lane update matches the reach recurrence exactly: own decision edges use strategy probabilities, while opponent and chance edges use the sentinel value 1.Compile-time indices eliminate predicates; one gather over the doubled index range advances both lanes without duplicate writes.Source: §16.2 · p. 38

16.3. Proposition 3: the depth schedule is shortest

  • The depth schedule is shortest: a dependency chain spanning D occupied depths requires at least D groups, and the generated schedule uses c1 + c2D operations.On the measured suite, c1 ≈ 31 and c2 ≈ 8 Aten operations; the regression gate requires fewer than 40 + 10D operations.Source: §16.3 · pp. 38–39

16.4. Proposition 4: the averaging horizon

  • For normal-range floating-point accumulators, increments below half the upward spacing do not change the current sum, but one absorbed increment does not prove permanent stagnation.Uniform averaging can lose resolution; GPU-CFR uses float64 strategy accumulation for all update rules without changing increment precision or the device-side counter.Source: §16.4 · p. 39

17. Future Work

  • The compiler is aimed at repeated structurally identical solves; extending it beyond two players and to sampled CFR variants remains an open design question.The paper identifies real-time subgame re-solving, abstraction pipelines, and tournament continuations as examples of repeated solves that fit the compile-once design.Source: §17 · p. 39

Related papers

Loading 2609.11923v1…