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

원문 발행 2026. 05. 19. 23:49원문 언어 영어AI 한국어 번역arXiv cs.AI 원문 보기

요약

본 논문은 불완전 정보 게임을 해결하기 위한 CFR(Counterfactual Regret Minimization) 알고리즘을 실시간으로 실행할 수 있도록 설계된 최초의 병렬화 프레임워크인 Parallel CFR을 제안합니다. 정보 집합 및 트리 노드 단위의 병렬성과 GPU를 활용한 배치 신경망 추론을 결합하여, 단일 스레드 대비 최대 3.4배의 속도 향상을 달성했습니다. 이를 통해 일반적인 데스크톱급 장치에서도 실시간 게임 플레이에 필요한 충분한 반복 횟수를 확보할 수 있음을 입증했습니다.

핵심 포인트

정보 집합별(by information set) 및 트리 노드별(by tree node) 병렬성을 결합한 직교 병렬화 구조 제안
리프 노드 평가를 위한 배치 신경망 추론을 GPU로 오프로딩하여 CPU-GPU 이기종 파이프라인 구축
Heads-Up No-Limit Texas Hold'em 실험에서 단일 스레드 대비 3.3~3.4배의 속도 향상 달성
데이터 센터급 인프라 없이도 일반 데스크톱 장치에서 실시간 결정 예산 내 수백 번의 CFR 반복 가능

반사실적 후회 최소화 (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 반복을 가능하게 합니다.

AI 자동 생성 콘텐츠

원문 바로가기

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

요약

핵심 포인트

댓글