카운터팩추얼 후회 최소화 알고리즘의 병렬화

Parallelizing Counterfactual Regret Minimization

병렬화는 인공지능(AI) 분야에서 중요한 역할을 수행하며, 대규모 AI 모델의 학습 및 평가 시간을 획기적으로 단축시킵니다. 그러나 AI 전반에 미치는 영향과 달리, 계산 게임 해결에 병렬화를 적용하는 것은 상대적으로 탐구가 덜 이루어진 분야이며, 잠재력이 매우 큽니다. 본 논문에서는 대규모 불완전 정보 게임 해결에 중요한 기여를 한 카운터팩추얼 후회 최소화(CFR) 알고리즘 패밀리를 병렬화합니다. 우리는 CFR을 일련의 선형 대수 연산으로 재구성하는 일반화된 병렬화 프레임워크를 제시합니다. 이를 통해 선형 대수 연산 병렬화에 사용되는 기존 기술을 적용하여 CFR의 속도를 향상시킬 수 있습니다. 또한, 우리의 기술이 CFR 패밀리의 다른 알고리즘, 즉 최첨단 기술인 CFR+, 할인된 CFR 및 예측 기반 CFR 변형에도 적용될 수 있음을 설명합니다. 실험 결과, GPU에서 구현된 우리의 CFR 구현 방식이 Google DeepMind OpenSpiel의 CPU 기반 CFR 구현 방식보다 최대 4배 빠른 속도를 보였습니다.

Parallelization has played an instrumental role in the field of artificial intelligence (AI), drastically reducing the time taken to train and evaluate large AI models. In contrast to its impact in the broader field of AI, applying parallelization to computational game solving is relatively unexplored, despite its great potential. In this paper, we parallelize the family of counterfactual regret minimization (CFR) algorithms, which were central to important breakthroughs for solving large imperfect-information games. We present a generalized parallelization framework, reframing CFR as a series of linear algebra operations. Then, existing techniques for parallelizing linear algebra operations can be applied to accelerate CFR. We also describe how our technique can be applied to other tabular members of the CFR family of algorithms, including the state-of-the-art, such as CFR+, discounted CFR, and predictive variants of CFR. Experimentally, we show that our CFR implementation on a GPU is up to four orders of magnitude faster than Google DeepMind OpenSpiel's CFR implementations on a CPU.