기술 요약: 반사적 후회 최소화 (CFR) 의 병렬화

문제 제기

병렬화는 인공지능의 초석으로 자리 잡아 대규모 모델의 학습 시간을 획기적으로 단축해 왔으나, 계산적 게임 해결에 적용되는 것은 상대적으로 미개척 영역으로 남아 있습니다. Cepheus, Libratus, Pluribus와 같은 대규모 불완전 정보 게임 해결의 기념비적 성공 사례들이 일종의 병렬화에 의존해 왔음에도 불구하고, 반사적 후회 최소화 (CFR) 알고리즘을 병렬화하는 구체적인 메커니즘은 일반화되지 않았습니다. Reis 와 Rudolf 의 시도와 같은 기존 시도들은 재현성 문제, 스레드당 복잡한 제어 흐름 요구, 또는 비최적의 2 차 작업 복잡도 (quadratic work complexity) 로 인해 어려움을 겪곤 했습니다. 또한 Cepheus 와 같은 이전의 도메인 특화 접근법은 일반성이 부족했습니다. 저자들은 알고리즘의 효과성을 결정하는 특성을 희생하지 않으면서 CFR 및 그 표식 (tabular) 변형들을 가속화할 수 있는 일반화되고 도메인 독립적인 프레임워크의 필요성을 확인했습니다.

방법론

저자들은 CFR 의 시퀀스 형태 (sequence-form) 버전을 일련의 선형 대수 연산으로 재해석하는 일반화된 병렬화 프레임워크를 제안합니다. 이 변환은 게임 해결에 선형 대수를 병렬화하기 위한 표준적이고 고도로 최적화된 기법 (특히 GPU 에서) 을 적용할 수 있게 합니다.

핵심 기술적 접근

1. CFR 을 선형 대수로 재해석:
   이 논문은 CFR 고유의 트리 탐색 단계 (전략 업데이트를 위한 상향식, 효용 관찰을 위한 하향식) 를 행렬 - 벡터 연산으로 변환합니다. 이는 서로 다른 데이터 표현을 조정하기 위해 논리 행렬 (entries 가 $\{0, 1\}$인 행렬) 을 사용하여 달성됩니다:

   • 시퀀스 대 노드 표현: 논리 행렬 $A \in \mathbb{R}^{P \times \Sigma}$는 노드별 벡터 ($\mathbb{R}^P$) 와 시퀀스별 벡터 ($\mathbb{R}^\Sigma$) 간 변환을 수행합니다.
   • 행동 표현: 논리 행렬 $B$는 빈 시퀀스를 제외한 행동 표현 ($\mathbb{R}^{\Sigma^+}$) 으로의 변환을 처리합니다.
   • 행동 집계: 논리 행렬 $C$는 결정 지점에서의 사용 가능한 행동에 걸쳐 값을 집계하여 행렬 곱셈을 통한 L1-정규화 및 기대값 계산을 가능하게 합니다.

2. 병렬화된 트리 탐색:
   재귀적 트리 탐색 대신, 이 알고리즘은 트리 형태 순차 결정 과정 (TFSDP) 을 레벨 구조로 분해합니다. 인접 행렬 $L^{(d)}$는 각 깊이 $d$에서의 간선을 나타냅니다.

   • 상향식 탐색(전략 전파용) 은 $L^{(1)}, L^{(2)}, \dots, L^{(k)}$를 순차적으로 적용하여 수행됩니다.
   • 하향식 탐색(효용 누적용) 은 이러한 행렬을 역순으로 적용하여 수행됩니다.
   • 이러한 연산들은 병렬 하드웨어에서 매우 효율적인 압축 희소 행렬 (Compressed Sparse Row, CSR) 희소 행렬 - 벡터 곱셈을 사용하여 구현됩니다.

3. 알고리즘적 적응:
   이 프레임워크는 모듈식으로 설계되었습니다. 핵심 병렬 연산 (NEXTSTRATEGY 및 OBSERVEUTILITY) 이 정의되고, 특정 CFR 변형들은 이러한 핵심 함수에 간단한 연산을 추가하여 구현됩니다:

   • CFR+: 후회에 플로어링 (flooring) 연산을 추가합니다.
   • 할인 CFR (DCFR): 양의 후회와 음의 후회에 시간 의존적 스케일링 인자를 적용합니다.
   • 예측 CFR (PCFR): 순간 후회를 위한 예측 벡터를 통합합니다.

주요 기여

• 일반화된 프레임워크: 이 논문은 CFR 을 선형 대수로 취급하는 도메인 독립적 프레임워크를 제시하여, 모든 표식 CFR 변형 (CFR, CFR+, DCFR, PCFR, PCFR+) 에 적용 가능하게 합니다.
• 이론적 분석: 작업 - 깊이 (work-depth) 모델을 사용하여 저자들은 병렬화된 알고리즘이 순차식 시퀀스 형태 CFR 과 동일한 총 작업 복잡도 ($W = \Theta(|P|)$) 를 유지함을 증명하여, 병렬화가 부재할 경우 효율성 손실이 없음을 보장합니다. 깊이는 $D = \Theta(k \log B)$임이 입증되었으며, 여기서 $k$는 트리 높이이고 $B$는 분기 인자입니다.
• 오픈소스 구현: 이전의 GPU 시도들과 달리, 이 작업은 OpenSpiel 라이브러리와 호환되는 오픈소스 구현을 제공하여 재현성과 통합을 용이하게 합니다.
• 확장성: 이 접근법은 서브게임 경계뿐만 아니라 모든 깊이에서 게임을 효과적으로 분할하여 Cepheus 와 같은 이전 아키텍처보다 더 높은 병렬성을 얻을 수 있습니다.

실험 결과

저자들은 다양한 크기 (58 개의 노드를 가진 Kuhn 포커에서 $5.2 \times 10^7$개의 노드를 가진 Large Battleship 까지) 의 7 개 벤치마크 게임에서 CPU 로 실행된 Google DeepMind 의 OpenSpiel 구현체 (Python 및 C++) 에 대해 GPU 가속 구현을 평가했습니다.

• 소규모 게임: Kuhn 포커, Leduc 포커와 같은 소규모 게임의 경우, GPU 오버헤드로 인해 CPU 구현체에 비해 속도가 느려집니다.
• 대규모 게임: 게임 크기가 증가함에 따라 병렬화된 구현은 CPU 베이스라인을 크게 능가합니다.
  • Small Battleship의 경우, 속도가 OpenSpiel 의 C++ 구현체보다 약 $2.1 \times 10^2$배 빠릅니다.
  • Medium Battleship의 경우, 속도는 $1.2 \times 10^3$배에 달합니다.
  • Large Battleship의 경우, 속도는 $4.1 \times 10^3$배입니다.
  • 전반적으로, GPU 구현은 OpenSpiel 의 Python 구현체보다 최대 18,889 배 빠르고, C++ 구현체보다 3,413 배 빠릅니다.
• 수렴: 실험은 병렬화된 구현이 벽시계 시간 (wall-clock time) 에 걸쳐 동일한 취약성 감소를 달성하지만, 그 시간이 훨씬 짧음을 보여주며, 게임 크기가 커질수록 속도 향상 효과가 더욱 두드러집니다.

중요성 및 주장

이 논문은 이러한 병렬화 기법이 해결 가능한 게임의 크기(메모리 용량 측면) 를 반드시 증가시키는 것은 아니지만, 최적 해를 찾는 데 필요한 시간을 획기적으로 단축한다고 주장합니다.

• 연구 가속화: 주요 가치 제안은 연구자들이 가설, 새로운 CFR 변형, 그리고 하이퍼파라미터 체제를 훨씬 빠른 turnaround 시간으로 테스트할 수 있게 하는 것입니다.
• 반복적 설정: 이 프레임워크는 개별 게임 트리가 유사한 다양한 스택 크기의 포커와 같이 반복적으로 플레이되는 설정의 게임에 특히 유용하여 신속한 재해결을 가능하게 합니다.
• 호환성: 저자들은 그들의 방법이 OpenSpiel 과의 완전한 호환성을 유지하며, 게임 정의의 재작성 없이 기존 게임 이론 연구에 바로 적용 가능한 가속기로 사용할 수 있음을 강조합니다.
• 겸손함: 저자들은 그들의 기여가 Cepheus 의 서브게임 분할과 같은 이전 아키텍처와 상호 배타적이지 않다고 명시적으로 밝힙니다. 오히려 그들의 기법은 추가적인 병렬화를 위해 그러한 아키텍처와 함께 보완될 수 있습니다. 또한 그들은 GPU 와 CPU 를 비교하지만, 결과가 일반적인 사용 사례에서도 병렬화의 잠재력을 강조한다고 인정하면서도, 이전에는 메모리 제약으로 인해 해결 불가능했던 게임을 해결한다고 주장하지는 않습니다.