실시간 병렬 반사실적 후회 최소화 (Real-Time Parallel Counterfactual Regret Minimization)

반사실적 후회 최소화 (Counterfactual Regret Minimization, CFR)는 대규모 불완전 정보 게임 (imperfect-information games)을 해결하기 위한 지배적인 알고리즘 계열이며, No-Limit Texas Hold'em 포커에서의 Libratus 및 Pluribus와 같은 돌파구의 기반이 되었습니다. 실시간 게임 플레이 시스템에서 솔버 (solver)는 결정당 단 몇 초라는 엄격한 시간 예산 내에 근사 평형 전략 (near-equilibrium strategy)을 계산해야 하며, 이 시간 내에 완료되는 CFR 반복 (iterations) 횟수가 플레이 강도를 직접적으로 결정합니다. 본 논문에서는 가지치기 (pruning), 추상화 (abstraction), 그리고 고급 CFR 변형 모델들을 원활하게 통합하는 실시간 깊이 제한 (depth-limited) CFR 해결을 위한 최초의 병렬화 프레임워크인 \textbf{Parallel CFR}을 제시합니다. 우리는 각 CFR 반복을 7단계의 파이프라인으로 분해하고, 두 가지 직교하는 병렬성 차원인 \emph{정보 집합별 (by information set)} 및 \emph{트리 노드별 (by tree node)} 병렬성을 식별합니다. 리프 노드 (Leaf node) 평가는 배치 신경망 추론 (batched neural network inference)을 통해 GPU로 오프로딩되어, 이기종 CPU-GPU 파이프라인을 생성합니다. Heads-Up No-Limit Texas Hold'em에 대한 실험 결과, Parallel CFR은 포스트플랍 (postflop) 스트리트에서 단일 스레드 베이스라인 대비 $3.3$--$3.4 imes$의 속도 향상을 달성하였으며, 10억 개 이상의 히스토리를 가진 깊이 제한 게임 트리에서 반복당 시간은 ${\sim}47$--$54$~ms를 기록했습니다. 모든 실험은 단일 데스크톱급 장치 (NVIDIA DGX Spark)에서 실행되었으며, 데이터 센터 규모의 인프라 없이도 일반적인 실시간 결정 예산 내에서 수백 번의 CFR 반복을 가능하게 합니다.