[KataGo 논문 Review] Accelerating Self-Play in Go

"Accelerating Self-Play in Go" 논문을 한국어로 정리한 포스트입니다.

Accelerating Self-Play Learning in Go (2020) a.k.a. KataGo

David J. Wu,  Jane Street Group.

[ 논문 ] [ code ] 

Abstract

  AlphaZero의 학습과정과 구조에 몇 가지 향상된 기법을 적용함으로써, Self-play learning을 통한 바둑 AI의 학습 속도를 향상 시켰다. 비교할만한 다른 방법들에 비해 50x 절감된 계산량을 달성하였다. AlphaZero와 그 복제 알고리즘인 ELF OpenGo와 Leela Zero처럼, KataGo는 오직 뉴럴 네트워크에 기반한 몬테 카를로 트리 탐색을 통한 자체 대결(neural-net-guided Monte Carlo tree search self-play)에 의해서만 학습하지만, KataGo는 30개 이하의 GPU를 통해 19일만을 학습하였다. 이러한 속도 향상을 위해 다른 문제들에도 적용가능한 non-domain-specific improvements가 사용되고, domain-specific 테크닉들을 통한 성능 향상은 AlphaZero와 같은 순수한 general한 방식과 best 방식 사이에 존재하는 efficiency gap을 보여준다. 본 논문은 바둑과 같이 거대한 state space에서 large-scale computation 자원 없이 학습하기 위한 한 걸음이다.

Introduction

  AlphaGoZero, AlphaZero, ELF Open Go 등과 같은 기존 연구는 인간의 지식이나 기존에 존재하는 데이터에 의존하지 않고 self-play 만으로도 사람을 뛰어넘는 성능을 보여주었지만, 최고 레벨의 성능을 보여주기 위해 지나치게 많은 컴퓨팅 자원과 시간이 소요되었다.

  본 논문에서 self-play learning의 학습 효율성을 향상시키기 위한 몇 가지 새로운 테크닉을 제시하며, AlphaZero 이전에 컴퓨터 바둑에서 제시되었던 몇 아이디어를 되살려 AlphaZero 과정에 적용한다.

  KataGo는 몇 가지 domain-specific feature들과 최적화를 사용하지만 random play로부터 학습하며, 그 외에 어떤 starategic knowlege(전술적 지식)이나 기존의 데이터를 사용하지 않는다. 또한 ELF OpenGo나 Leela Zero보다 더 효율적인 모습을 보여준다.

AlphaGo Lee까지 사용되었던 Domain-specific한 정보들.

Non-domain-specific vs domain-specific
  학습하고자 하는 Domain(여기서는 바둑)과 관계 없이 적용 가능한 테크닉들. 보통 모델이나 학습 과정에서 적용되곤 한다. AlphaGo Zero, 특히 Alpha Zero에서는 바둑에 국한되지 않는 general한 모델을 만들고자 했기 때문에, AlphaGo Lee에서 다수 사용되던 바둑에 국한된 정보들이 학습과정에서 배재되었다. 하지만 바둑만을 목적으로 할 경우 바둑에 국한된 정보들 (ex: AlphaGo Lee는 state를 표현하기 위해, 위 그림과 같은 정보를 사용하였다.)을 활용할 수 있다면 학습의 효율성을 크게 향상 시킬 수 있다.

 

본 논문이 기여하는 바는 다음과 같다.

  다른 reinforcement learning에 더 일반적으로 사용가능한 다양한 domain-independent한 방식들을 제시한다. 구체적으로는 다음과 같다.

• 다른 target에서의 데이터의 balance를 향상 시킬 수 있는 새로운 테크닉인 playout cap randomization.
• MCTS에서의 exploration과 분리하여 policy 학습성능을 향상시킬 수 있는 policy target pruning.
• 비전 분야에서 (SENet 에서 소개된) global한 context를 학습과정에 적용시키는 global-pooling 메커니즘의 적용.
• 바둑에서의 supervised learning에서 사용된 아이디어를 적용한 auxiliary policy target. 이 방식은 쉽게 다른 self-play 방식에 적용 가능하며 다른 분야에도 적용가능함을 보였다.

 

  본 논문은 AlphaZero의 방식과 self-paly로 가능한 것 사이에 존재하는 중대한 efficiency gap이 존재함을 보여주는 case study로서의 역할을 한다. General한 알고리즘으로 동작하기 위해 AlphaZero에서 배재되었던 몇 domain-specific 방식을 통해 적지 않은 성능 향상을 보여주었다. 이는 집(ownership) 예측과 score targets과 같은 방식을 포함하며, 더 일반적인 meta-learning heuristic을 제공한다.

“달성하고자 하는 target의 subcomponent를 예측하는 것이 학습 성능을 비약적으로 향상 시킨다."

 

  또한 몇 game-specific input feature가 성능을 향상시키는 것을 통해, 비록 AlphaZero가 이러한 domain-specific feature 없이도 큰 성공을 거뒀지만, 이를 쓸모없다하기에는 이르다는 사실을 보여준다.

  DeepMind와 같은 회사들은 General한 방법론에 관심을 가지고 다양한 task에 적용가능한 방향으로 연구를 진행한다. ( AlphaGO → AlphaGo Zero → AlphaZero → MuZero 로 이어지는 연구 결과, 모든 Atrai Game에 적용 가능한 Agent57 등 ) 따라서 그 과정에서 특정 domain에 국한된 정보들을 계속해서 배재하는 방식으로 연구가 이루어졌다. 하지만 특정 task나 domain에서만 높은 성능을 얻고자 할 경우, 그 task나 domain에 국한된 정보들을 사용하는 것이 여전히 가장 쉽고 효율적인 방법이 될 수 있다.

 

AlphaGo Lee to AlphaZero

 

MCTS in AlphaGo Zero

 

Basic Architecture and Parameters.

  minor한 부분에서 차이가 있지만, KataGo의 전체적인 구조는 AlphaGoZero 와 AlphaZero의 구조를 따라간다. training data 생성을 위해 neural net에 기반한 MCTS를 통해 스스로를 상대한다. Search는 반복되는 playout을 통해 성장하는 game tree로 이루어진다. playout은 root부터 시작해 tree를 타고 내려가며, 각 node $n$에서 다음을 최대화 하는 child $c$를 선택한다.

PUCT = Predictor + Upper Confidence bounds applied to Trees

  PUCT : $V(c)$는 $c$의 subtree에 있는 모든 node에서 예측된 utility 값의 평균이며, $P(c)$는 neural net으로 부터 얻어진 $c$에서의 policy prior, $N(c)$는 visit count이다. tree에 끝에 도달하면, 하나의 child를 추가하고 playout이 종료된다.

 AlphaZero와 같이, policy prior에는 Dirchlet distribution으로 부터 얻어진 noise가 더해져 exploration을 돕는다.

  탐색을 이끄는 neural net은 preactivation 구조의 convolutional residual net이 사용되며 $b$개의 residual block과 $c$개의 channel $(b,c)$로 이루어져있다. Leela zero와 같이 KataGo도 작은 사이즈의 네트워크로부터 학습을 시작해 동일한 데이터를 사용하며 점진적으로 모델의 크기를 키워나가는데, 평균 loss가 더 작은 size의 모델보다 작아질때 모델을 바꾼다. 총 19일 학습하였으며 (6,96) → (10,128) → (15,192) → (20,256)으로 0.75, 1.75, 7.5일 학습 때 모델이 switching 되었다.

  neural net은 몇 개의 출력 head를 가진다. position을 self-play game으로 부터 sampling하여, policy head는 가능한 좋은 수를 예측하고, game outcome value head는 게임의 최종 승패를 예측한다. loss 함수는 다음과 같다.

  세부적인 학습 parameter는 다음과 같다. SGD(momentum decay 0.9), batch size 256, 고정된 per-sample learning rate 6e-5 ( 첫 5M sample에서는 2e-5의 lr로 불안정성을 줄인다). 17.5일 학습 후에 lr은 6e-6으로 감소되어 최종 성능을 높이고자 하였다. sample은 가장 최신 data부터 moving window내에서 균일하게 샘플링하였고, window 크기는 250,000 에서 시작해 22M 까지 커졌다.

  학습에는 또한 stochastic weight averaging을 사용했는데, 약 250,000 샘플마다 weight의 snapshot을 저장하고, 매 4번째 snapshot 마다 exponential moving average (decay=0.75)가 적용된 weight 값으로부터 새로운 neural net 후보가 생성된다. 후보 네트워크는 현재 네트워크와 200 game 중 최소 100 game을 이겨야 하는 gating test를 통과해야 새로운 net이 될 수 있다.

  종합적으로 KataGo는 19일 동안 최대 28개의 V100 GPU를 통해 학습되었으며, 약 241M개의 training sample과 4.2M game을 생성하였다.

 

Major General Improvements

1. Playout Cap Randomization

  KataGo 학습 과정에서 AlphaZero와의 주요 차이점은 랜덤하게 변하는 playout의 수이다. 이는 policy 학습과 value 학습 사이에 major tension을 완화시키는 역할을 한다.’

  AlphaZero에서, 게임 승패 value target은 data-limited하며, 각 게임에서 하나의 noisy binary 결과만이 존재한다. value 학습을 위해서는 적은 수의 playout만 하는 것(비록 이렇게 생성된 게임이 상대적으로 quality가 떨어진다 하더라도)이 더 많은 게임을 만들 수 있다는 장점이 있다. AlphaGo의 첫번째 버전에서는 각 턴에 오직 한번의 playout만으로도 value net을 학습할만한 충분한 품질을 보여주었다.

결국 하나의 게임에서 승/패는 하나의 고정된 값이기 때문에, value target을 잘 학습하기 위해서는 playout을 줄여 그 만큼 더 많은 게임을 생성하는 것이 낫다는 뜻인 듯.

 

  하지만 Forsten (2019)의 기존 연구는, policy 학습을 위한 이상적인 playout 수는 훨씬 더 크며, 이는 AlphaZero의 800번/수와 비슷한 수치이다. 비록 policy가 각 게임에서 많은 sample을 얻는다 하더라도, playout의 수가 value training을 위한 이상적인 수치보다 크지 않다면, search는 policy 와 크게 달라지지 않을 것이고, 궁극적으로 policy는 향상되지 않는다.

Alpha- 시리즈에서 policy network가 있음에도 MCTS를 사용하는 이유는 단순히 policy network로 부터 다음 수를 결정하는 것보다 MCTS에 policy network를 적용하여 수를 선택하는 것이 더 좋은 성능을 보이기 때문이다. playout의 수가 일정 수준 이상이 되지 않는다면, MCTS로 얻는 이점이 policy network 만을 사용하는 것보다 크게 나아지지 않는다는 의미 같다.

 

  이러한 긴장관계를 완화시키기 위해 playout cap randomization을 소개한다. 작은 확률인 $p$로 full search를 실시하며, $N$ node를 방문하기 전까지 tree를 탐색한다. 그 외의 경우는 훨씬 더 작은 cap인 $n < N$으로 탐색을 시행한다. Full search를 시행한 턴만 학습을 위해 기록되며, fast search 시에는 Dirichlet noise와 다른 exploration setting을 사용하지 않도록하였다. $p$는 0.25를 사용하였으며, $(N, n)$은 (600, 100) 에서 (1000, 200)으로 이틀에 걸쳐 값을 키워주었다.

 

2. Forced Playouts and Policy Target Pruning

  AlphaZero, ELF, Leela Zero와 같이 KataGo는 학습시 policy target학습을 위해 최종 root playout distribution을 사용하였다. 하지만 KataGo는 raw distribution을 사용하지 않았다. 대신 forced playout을 통해 향상된 exploration을 가능하게 하는 새로운 방식, policy target pruning을 소개한다.

  Dirichlet Noise를 기반으로 한 수는 좋았지만 initial evaluation은 negative가 될 수 있으며, 추가적인 search를 막음으로써 발견되지 않은 수를 남겨둘수 있었다. 따라서 playout을 전달받은 root의 각 child $c$에 대하여, 최소한의 수의 forced playout을 받도록 하였다. 이는 playout의 총 수와 noised policy를 기반으로 한다.

  이러한 방식은 root의 child가 위 만큼의 playout을 받지 못했을 경우 MCTS 선택의 urgency $PUCT(c)$를 무한대로 설정하는 방식으로 이루어진다. exponent 1/2는 forced playout을 확장하면서도 점진적으로 나쁜 수에 대해서는 0으로 decay 되도록하며, $k$는 2 정도로도 충분히 작은 비율의 playout을 강제하기에 충분했다.

  하지만 대부분의 경우에, noise move는 나쁜 수이고, policy target은 playout distribution이기 때문에 policy가 추가적인 bad playout을 학습하게 할 위험이 있다. 따라서, policy target pruning step을 거친다. 정확히는 가장 많은 playout을 한 child $c$에 대해, $PUCT(c) ≥ PUCT(c^*)$을 발생하기 전까지 강제된 $n$ playout을 삭제한다. 이러한 삭제는 그 수가 충분히 좋지 않을 경우에 일반적인 PUCT가 스스로 선택하지 않을 추가적인 playout을 제거하는 효과를 가진다.

Pruning을 사용할시 위와 같이 edge 주변의 많은 나쁜 수로 인한 policy mass를 줄일 수 있었다.

  이러한 pruning의 가장 주요한 특징중 하나는 이것이 AlphaZero의 policy target을 MCTS의 dynamics나 exploration noise의 사용으로부터 분리시킨다는 점이다(decoupling the policy target in AlphaZero from the dynamics of MCTS or the use of exploration noise). MCTS의 최적의 레벨의 playout 분산이 policy target과 neural net의 장기적인 수렴에도 최적일 것이라고 생각할 이유가 없다. forced playout을 통한 policy target pruning은 이러한 방법의 단순한 적용일 뿐이다.

  일반적인 AlphaZero에서 사용되는 exploration method (MCTS dynamics, explorataion noise)와 별개로 적용되는 exploration 기법이라는 의미 같다. 이를 통해 policy 학습 시에 MCTS의 내부적인 구조에 지나치게 의존하는 경향을 줄일 수 있는 방법인 점을 강조하는 듯.

 

3. Global Pooling

  또 다른 개선점은 neural net의 다양한 지점에 global pooling 레이어를 추가한 것이다. 이는 Convolution layer로 하여금 제한된 인식 범위를 가진 convolution만으로는 불가능한 global한 context를 고려하도록 해준다.

  global pooling layer는 각 채널 $c$에서 1) 채널의 평균과 2) board 크기로 선형적으로 확대된 채널의 평균, 3) 채널의 최댓값을 계산해 총 $3c$의 결과 값을 만든다. 이는 fully connected layer를 통해 $c_X$의 크기로 변해 다시 $X$와 곱해진다.

  이는 학습의 후반부에서 성능을 크게 향상시키며, 바둑이 가지는 nonlocal한 전술적 측면을 생각할 때 크게 놀랍지 않다. 하지만 global context는 바깥으로 드러난 nonlocal 상호작용이 없을때도 도움이 되는데 예를 들어, 다양한 전략 게임에서, 강한 player는 이기고 있을때 단순한 수를 선호하도록 그들의 지역적인 수의 선호도를 변경하지만, 지고 있을 때는 복잡한 수를 추구한다. global pooling은 내부적으로 이러한 global context에서 이러한 조건을 충족할 수 있도록 한다.

  global context를 고려하는 것은 완전히 새로운 방식은 아닌데. SENet의 "Squeeze-and-Excitation" 구조를 통해 image classfication시에 이러한 아이디어를 처음 소개하였다. 구현은 다르다 할지라도, 근본적인 컨셉은 동일하다. 또한 이러한 SE 구조는 몇 온라인 AlphaZero관련 프로젝트에 적용되고 있다.

 

4. Auxiliary Policy Targets

  마지막 general한 개선점은 다음 턴 상대방의 반응을 예측하는 auxiliary policy target을 추가하여 regularization을 향상시킨 것이다. 단순하게 policy head에 이러한 target을 예측하는 새로운 채널과 이에 대한 loss term을 추가해 주었다.

  이러한 아이디어는 넓은 범위의 강화학습 task에 적용가능하다. single-agent 상황에서조차 스스로의 future action이나 environment를 예측할 수 있다. 이 AlphaZero나 다른 학습 알고리즘을 regularize하기 위한 단순하고 cost도 거의 없는 방식은 더 주목할만한 가치가 있는 것으로 판단된다.

 

Major Domain-Specific Improvements

1. Auxiliary Ownership and Score Targets

  KataGo의 학습 과정에서 AlphaZero로부터의 주요 개선점중 하나는 부가적으로(auxiliary) ownership과 score 예측 타겟을 추가한 것이다. 비슷한 타겟이 supervised 학습 기반 기존 연구(CGI)에서 탐구되었고, 저자는 결과 예측시 향상된 mse error 및 전반적인 성능 향상을 발견할 수있었다.

  KataGo는 이러한 아이디어를 self-play 기반 바둑 강화학습에 최초로 적용한 사례일 것이다. 타겟 자체는 game-specific하지만 또한 이전의 transfer learning이나 multi-task learning에서 주목받지 못했던 더 일반적인 휴리스틱을 강조한다.

  AlphaZero에서 학습은 데이터와 게임 결과 예측시의 noise에 국한된다. 하지만 아무리 게임 결과가 noisy하고 binary한다 할지라도, 그것은 최종 점수(집)차이나 바둑판 위 각 위치의 소유권(ownership)과 같은 세밀한 변수들의 직접적인 함수(direct function)이다.

  AlphaZero에서 학습에 사용되는 것은 게임의 결과(승 혹은 패) 뿐이고, 이를 기반으로만 게임 과정에 대한 평가 및 학습이 이루어지게 된다. 게임 결과가 세밀한 변수들의 직접적인 함수라는 말은 게임의 과정과 세부적인 사항들이 그러한 게임의 결과에 직접적인 영향을 주는 요소라는 의미이다.

 

  게임 결과를 이러한 세밀한 변수로 분해하고 예측하는 것은 regularization을 향상시킬수 있어야 한다. 따라서 다음 세가지 output과 loss 함수를 추가하였다.

1) Ownership loss : 바둑판의 각 지점의 소유권이 누구한테 있는지를 예측하고 계산 2) Score belief loss ("pdf") : 게임의 최종 점수(집) 차의 정확한 값을 예측 3) Score belief loss ("cdf") : 최종 점수 차의 실제값과 예측값의 차이를 loss로 사용.

 

  Ablation을 통해 위와 같은 부가적인 타겟이 놀라울 만큼 학습 효율을 향상시킨다는 점을 확인햇다. 이는 또한 neural net이 진작에 바둑판에 대한 복잡한 판단을 개발했을 때를 넘어 학습의 끝까지 유지된다. 이처럼 초기 스테이지를 넘어 이러한 타겟들이 지속적으로 도움이 된다는 점은 놀라운 사실이다. 이에 대한 저자는 다음과 같은 직관을 제시한다

  바둑판 위 특정 지역에 대한 잘못된 판단으로 인해 지게 되는 게임을 학습하는 경우를 고려해보자. 게임의 승패만이 나타나 있는 최종 binary 결과 만으로는, neural net은 그저 바둑판 위 어떤 지점이 패배를 야기했는지 ‘추측’할 수 있을 뿐이다. 반면에, ownership 타겟을 통해, neural net은 큰 error와 gradient를 통해 바둑판 내 잘못 예측된 지역에 대한 직접적인 피드백을 받을 수 있다. 이로인해 neural net은 더 적은 샘플만으로도 정확한 업데이트를 할 수 있게 된다.

neural net에 의해 학습된 집(ownership) 예측 결과

  이러한 결과는 transfer나 multi-task learning에서 타겟이나 task를 추가함으로써 성능을 향상 시키는 결과들과 일치한다. 하지만 언제 추가적인 타겟이 도움을 주는지에 대한 연구는 많지 않다. 이번 연구는 다음과 같은 휴리스틱을 제안한다.

요구되는 목표(여기서는 바둑의 승리)가 분리된 subevent(집의 소유권, 최종 점수 차이)들의 조합으로 표현될수 있거나, 그러한 subevent들과 깊이 연관되어 있을 때, subevent를 예측하는 것이 도움이 될 확률이 높다. 전체 결과를 예측할 때보다 잘못 예측된 subevent가 더 정밀하고 지역적인 피드백을 gradient를 통해 전달할 수 있고, subevent와 연관된 main target을 달성하는데 도움을 주기 때문이다.

 

  물론 이러한 휴리스틱을 처음 발견한 것은 아니고 항상 적용가능한 것은 아니지만, 추후 연구나 실용적인 사용 측면에서 강조할만한 점이라고 생각했고, 적용이 가능한 상황에서 더 general한 문제에서 mult-task-learning의 신뢰성을 연구하고 향상시킬수 있는 잠재적인 방법이라 생각된다.

 

2. Game-specific Features

  단지 바둑판 내 돌의 위치나 history, 규칙, komi를 나타내는 raw feature 외에 추가로, KataGo는 몇가지 game-specific한 high-level feauture를 neural net에 인풋으로 사용하였다. 또한 2개의 마이너한 specific optimization을 사용하였다.

1. 특정 횟수 이상의 연속적인 pass후에 pass-alive 공간에 수를 놓는 것을 금지한다.
2. passing과 게임을 지속하는 것이 동일한 점수를 얻을 때, passing을 선호하도록 tiny bias를 추가하였다.

두가지 최적화 기법을 통해 각 게임이 끝나는 속도를 미세하게 향상 시켰다.

 

Results

  생략

 

Conclusions And Future Work

  외부 데이터 없이 랜덤한 self-play로부터 시작해, KataGo는 몇 AlphaZero 기반 모델에 필적하는 성능을 보여주면서도 놀라울 만한 효율성을 가졌다. 본 논문에서 self-play learning을 향상시키기 위한 다양한 테크닉을 제시하였고 이중에서 대다수가 쉽게 다른 게임이나 문제상황에 더 일반적으로 적용이 가능하다. 또한 domain-specific한 개선점은 기본 AlphaZero-like 학습(specific 한 정보를 활용하지 않는, general한 모델)과 더 가능한 것들 사이에 존재하는 격차를 보여주는 동시에 일반적인 방법론의 향상을 위한 원칙과 가능한 방법들을 제시한다. 본 연구가 강화학습의 데이터 효율성에서의 더 나은 발전을 위한 기초가 되기를 바란다.