Boning Li (ボーニング・リー) とLongbo Huang (ロンボー・ファン) は2026年9月10日(現地時間)、arXiv cs.DCにて「GPU-CFR」と題する論文を発表した。本研究は、GPU上でCPUよりも高速に動作する数少ない大規模数値計算である仮想後悔最小化 (Counterfactual regret minimization: CFR) の処理速度を大幅に向上させる新手法を提示している。GPU-CFRは、既存のGPU実装と比較して最大80.4倍、最速のオープンソースCPU実装であるLiteEFGと比較して最大258倍の高速化を達成した。
Counterfactual regret minimization (CFR) は、各反復が数億の状態を持つゲームツリーを、数百万の小さな相互依存するギャザーおよびスキャッターステップで走査する数値計算手法である。GPU環境では、各カーネルがマイクロ秒単位で完了するため、カーネル起動とフレームワークのディスパッチが実行時間を支配し、これまでのGPU実装は最適化されたCPUコードに劣る結果となっていた。
Li氏とHuang氏は、固定されたゲームの場合、数値以外のCFR反復に関するすべての要素が最初の反復実行前に既知であるという観察に基づき、GPU-CFRを提案した。GPU-CFRは、任意のゲームを一度、静的データフローにコンパイルするコンパイラとランタイムである。このコンパイルにより、フラットなエッジ配列と情報セット配列、事前計算されたインデックス、深度レベルでのバッチ処理されたパスが操作シーケンス全体を固定し、反復間でソルバーステートのみが変化する。
GPU-CFRでは、静的チャンスフォールディング、深度レベル実行ブロック、デュアルレーンリーチバッファといった最適化手法を採用し、フレームワーク操作の数を最大18.1倍削減した。さらに、形状、インデックス、バッファアドレスが変化しないため、CUDA Graph Replayを利用して反復を一度記録し、単一のグラフ起動でリプレイすることを可能にしている。
NVIDIA A100 GPUを用いた性能評価では、カードゲーム、サイコロゲーム、ボードゲームを含む8つのゲームスイートにおいて、GPU-CFRは同アクセラレータ上の最速の既存GPU CFR実装と比較して29.8倍から80.4倍高速に動作した。また、最速のオープンソースCPU実装の一つであるLiteEFGと比較して、最も大きな4つのゲームでは14倍から258倍の高速化を実現している。アクセラレータを使用せず8つのCPUスレッドで実行した場合でも、コンパイルされた表現はGPUベースラインより2.2倍から51.1倍高速であり、GPU-CFRが更新ルールを変更することなく、スイートの中規模から大規模なゲームにおいてすべてのCPUおよびGPUベースラインを上回ることを示している。
参考: arXiv cs.DC (アーカイブ) — 2026年9月11日 02:58 (JST)
原文ハイライト"GPU-CFR runs 29.8--80.4x faster than the fastest prior GPU CFR"