바닥부터 배우는 강화 학습 | 10. 알파고와 MCTS

'바닥부터 배우는 강화 학습' 10장에는 MCTS(Monte Carlo Tree Search)의 개념과 알파고에 대해서 설명하고 있습니다. 아래 내용은 공부하면서 핵심 내용을 정리한 것입니다.

 

참고자료

도서: 바닥부터 배우는 강화 학습 / 10장 알파고와 MCTS

 

10.1 알파고

• 알파고는 2016년 3월에 이세돌과 바둑을 뒀던 버전
• 학습(learning) 단계
  ◦ 이세돌을 만나기 전에 이루어지는 과정
  ◦ 이후 단계에서 사용될 재료들을 미리 만들어 두는 과정
• 플래닝(decision-time planning)
  ◦ 이세돌과의 대국 도중에 실시간으로 이루어지는 과정
  ◦ 알파고 차례가 되었을 때 어디에 바둑알을 놓을지 고민하는 과정
  ◦ 알파고는 실시간 플래닝 알고리즘으로 MCTS(Monte Carlo Tree Search) 사용

 

◈ 학습 단계

• 학습 단계는 실시간 플래닝, 즉 MCTS에 쓰일 재료를 만드는 과정
• MCTS에 필요한 4가지 (3개의 정책 네트워크, 1개의 밸류 네트워크)
  ◦ 사람의 기보를 이용해 지도 학습한 정책 $\pi_{sl}$
  ◦ 롤아웃 정책 $\pi_{roll}$
  ◦ 스스로 대국하며 강화 학습한 정책 $\pi_{rl}$
  ◦ 밸류 네트워크 $v_{rl}$

 

1. 지도 학습 정책 $\pi_{sl}$

• 알파고의 모든 과정은 바둑 기사의 기보 데이터를 활용해 $\pi_{sl}$이라는 뉴럴넷을 학습시키는 것으로부터 시작
• 바둑판의 상태 정보 $s$가 인풋으로 들어오면 총 19*19 = 361개의 바둑 칸들 중 현재 둘 수 있는 곳에 대해 실제로 돌을 내려놓을 확률을 리턴 (361개의 클래스가 있고 그중에 하나로 분류(classification) 해주는 네트워크)
• 위와 같은 방법으로 3천만 개의 기보 안에 있는 "평균 전략"을 학습
• 13개 층의 컨볼루션 레이어(convolutional layer)를 쌓아 올려서 구성
• 바둑판의 정보를 토대로 사람의 지식을 이용하여 만든 feature를 48겹을 쌓아서 인풋으로 제공 ($19 \times 19 \times 48$)
• 학습 결과 $\pi_{sl}$은 주어진 데이터에 대해 57%의 정답률을 기록 (아마 5단 정도의 실력)

 

2. 롤아웃 정책 $\pi_{roll}$

• 롤아웃 정책 $\pi_{roll}$은 $\pi_{sl}$의 가벼운 버전
• 사람의 지식을 이용하여 만든 수많은 feature에 대해 선형 결합 레이어가 1개
• 속도가 매우 빠름 ($\pi_{sl}: 3ms, \pi_{roll}: 2μs$), $\pi_{sl}$이 $\pi_{roll}$ 보다 1500배 시간이 필요
• $\pi_{roll}$의 정확도는 24%
• $\pi_{roll}$이 필요한 이유는 MCTS 단계에서 같은 시간 동안 더 많은 수를 시뮬레이션해 볼 수 있음.
  결국 MCTS의 성능을 올려 줌

 

3. 강화 학습 정책 $\pi_{rl}$

• $\pi_{rl}$은 $\pi_{sl}$과 완벽히 똑 같이 생긴 뉴럴 네트워크이고 $\pi_{rl}$의 파라미터들은 $\pi_{sl}$을 이용해 초기화
• $\pi_{rl}$은 self-play를 통해 계속해서 강화됨
• $\pi_{sl}$로 초기화된 정책끼리 대결은 훨씬 고품질의 경기를 생산. (위 그림처럼 높은 산을 오르는데 산의 중간부터 오르는 것)
• 자신의 과거 모델들을 이용해 풀을 만들고, 풀에서 랜덤 하게 하나를 뽑아와서 경기를 펼치는 방식

• 학습을 받고 있는 네트워크가 500번 업데이트될 때마다 해당 모델을 풀에 넣어줌
• 알파고의 보상함수는 경기를 이기면 1, 지면 -1, 그 외의 중간 보상은 전혀 없음
• policy gradient 방법론을 사용하였고 그중에서도 리턴만 있으면 학습할 수 있는 REINFORCE 알고리즘 사용

$$\nabla_{\theta}J(\theta) = \mathbb{E} \left[ \nabla_{\theta} \log \pi_{\theta} (s, a) * G_t \right]$$

• $\gamma$ 값은 1.0
  ◦ 이긴 경기에서 발생한 모든 액션의 확률은 동등하게 증가
  ◦ 진 경기에서 발생한 모든 액션의 확률은 동등하게 감소
• GPU 50대를 이용해 1일간 학습, 128경기의 데이터를 이용해 1개의 미니 배치를 구성
• 학습이 끝난 $\pi_{rl}$은 80%의 승률로 $\pi_{sl}$을 이김
• MTCS 과정에서 $\pi_{rl}$이 직접적으로 사용되지 않음. $\pi_{rl}$은 다음 재료인 $v_{rl}$을 구하는데 핵심 역할을 할 뿐

 

4. 밸류 네트워크 $v_{rl}$

• $v_{rl}$의 신경만 구조는 $\pi_{sl}$, $\pi_{rl}$과 동일하지만 아웃풋이 $19 \times 19$가 아니라 1개의 값

$$v_{\pi_{rl}}(s) = \mathbb{E} \left [ G_t | s_t = s \right ]$$

• $\gamma=1.0$이고 중간 보상이 없기 때문에 결국 $s$에서 시작하여 1을 받을지, -1을 받을지 예측하는 함수, 즉 승자를 예측하는 함수 임
• $v_{rl}$의 손실함수는 MSE(mean squared error)로 정의
• 총 3천만 개의 각기 다른 게임에서 나온 상태를 가지고 데이터 셋을 만드고 50개의 GPU로 1주일간 학습
• $v_{rl}$은 임의의 상태를 인풋으로 넣었을 때 해당 경기의 승가가 누가 될지 그 결과를 가늠할 수 있음

◈ Monte Carlo Tree Search(MCTS)

• MCTS는 주어진 상황에서 시작하여 "그냥 많이 둬 보는" 방법론
• MCTS는 주어진 상황에 특화된 해를 찾는데 쓰이는 플래닝(planning) 알고리즘

• 주어진 상황을 $s$라 하면 $s$부터 시작하여 주어진 시간 안에 초대한 많은 게임을 시뮬레이션해 보는 것
• $s$에서 할 수 있는 액션 $a_1, a_2, ..., a_{180}$까지 할 수 있는 액션을 최대한 다양하게 해 봄
• 다양한 액션을 해 보고 결과가 가장 좋았던 액션을 실제로 선택하는 방법이 MCTS
• $\pi_{rl}$이 바로 결정을 내리는 것보다 좋음
• MCTS를 사용하기 위한 몇 가지 까다로운 조건
  ◦ MDP의 모델을 알아야 함 $(P_{ss'}^a, R_s^a)$
  ◦ 게임 중간마다 MCTS를 실행할 시간적 틈이 있어야 함
• MCTS는 선택, 확장, 시뮬레이션, 백 프로파게이션 4 단계로 구성
• 4단계가 한 바퀴 돌면 새로운 노드가 생성됨, 노드(node)는 바둑판의 상태에 해당, 엣지(edge)는 액션에 해당
• 노드를 평가하고 그 노드에 오기까지 거쳐온 모든 경로의 모든 엣지(액션)의 가치를 업데이트
• 이 평가를 바탕으로 좋았던 액션을 선택

 

1. 선택

• 루트 노두에서 출발하여 리프 노드(leaf node, 자식이 없는 노드)까지 과는 과정
  리프 노드에 도착하면 다음 단계인 확장 단계로 넘어감
• 기존에 평가해 놓은 각 액션의 벨류를 높은 액션을 선택

$$a_t = \underset{a}{\mathrm{argmax}} \left ( Q(s_t, a) + u(s_t, a) \right )$$

• $Q(s_t, a)$: 시뮬레이션 실행 후 얼마나 좋은 지
• $u(s_t, a)$: 시뮬레이션 실행 전 얼마나 좋을 것이라 추측하는지(prior)
• 시뮬레이션을 진행하면 경험이 쌓일수록 $Q(s_t, a)$의 영향력이 커지고 $u(s_t, a)$의 영향력은 줄어듦
• 시뮬레이션 도중 어떤 상태 $s_{78}$에서 액션 $a_{33}$을 선택하는 경험을 총 100번 했다고 가정한 경우

$$Q(s_{78}, a_{33}) = {1 \over 100} \sum_{i=1}^{100} V(s_L^i)$$

• 다시 말해 $(s_{78}, a_{33})$을 지나서 도달한 리프 노드의 평균 밸류

$$u(s_t, a) \propto {P(s, a) \over 1 + N(s, a)}$$

• $P(s, a)$는 사전 확률(prior probability)로 시뮬레이션해 보기 전에 각 액션에 확률을 부여함
  $P(s, a) = \pi_{sl}(s, a)$
• $N(s, a)$는 시뮬레이션 도중 엣지 (s, a)를 지나간 횟수
  $N(s, a)=0$에서 시작하여 한 번 지나갈 때마다 1씩 더해 짐
  시뮬레이션이 진행되면 분모가 커지면서 사전 확률의 영향이 줄어듦
• $\pi_{rl}$ 보다 $\pi_{sl}$이 더 다양한 액션을 시도하는 정책이었기 때문에 $\pi_{sl}$로 사전확률을 초기화

 

2. 확장(Expansion)

• 방금 도달한 리프 노드를 실제로 트리에 매달아 주는 과정
• 또한 이 노드에서 뻗어나가는 엣지들의 다양한 정보를 초기화

$$\begin{equation} \begin{split} P(s, a) &\gets \pi_{sl}(s, a) \\ N(s, a) &\gets 0 \\ Q(s, a) &\gets 0 \\ \end{split} \end{equation}$$

 

3. 시뮬레이션(Simulation)

• 리프 노두가 트리의 정식 노드가 되었기 때문에 노드의 가치를 평가, $V(s_L)$를 계산
• MCTS에서 노드의 벨류를 계산하는 두 가지 방법
  ◦ 리프 노드 $s_L$부터 시작하여 게임이 끝날 때까지 빠르게 시뮬레이션해 봄 ($\pi_{roll}$을 이용해 $z_L$ 계산)
  ◦ 벨류 네트워크 $v_{rl}(s)$를 활용
• 알파고는 위 두 가지 방법을 섞어서 계산

$$V(s_L) = {1 \over 2} v_{rl}(s_L) + {1 \over 2} z_L$$

 

4. 백 프로파게이션(Back propagation)

• 백 프로파게이션은 에지를 지나서 도달한 리프 노드 밸류의 평균값인 $Q(s, a)$를 계산해 주는 과정
• 이미 계산된 평균값에 새롭게 도달한 리프 노드의 밸류를 평균에 반영하기 위해 평균값 Q(s, a)를 업데이트해 주는 과정

$$\begin{equation} \begin{split} N(s, a) &\gets N(s, a) + 1 \\ Q(s, a) &\gets Q(s, a) + {1 \over N(s, a)} \left ( V(s_L) - Q(s, a) \right ) \\ \end{split} \end{equation}$$

• 값이 리프 노드로부터 루트 노드로 전파된 것이니 "역전파"라고 부름
• 48개의 CPU와 8개의 GPU를 이용한 병렬 연산을 이용해 빠른 속도로 MCTS를 수행

• MCTS에서 계산했던 액션 벨류인 $Q(s, a)$가 가장 높은 액션이 제일 액션이라 할 수 있음
• 하지만 알파고는 $Q(s, a)$ 대신 방문 횟수, 즉 $N(s, a)$가 가장 큰 액션을 선택, 위 그림에서는 $a_1$을 선택
• 아래 식과 같이 MCTS을 결정론적(deterministic)이 아닌 확률적(stochastic)으로도 움직일 수 있음

$$\pi_{mcts}(s, a_i) = {N(s, a_i) \over N(s, a_1) + N(s, a_2) + N(s, a_3)} \;\;\;\; i= 1, 2, 3$$

• 위 그림과 같이 확률분포로 부터 샘플링하여 액션을 뽑는 방법도 가능

 

10.2 알파고 제로

• Mastering the Game of Go without Human Knowledge
• 사람의 지식을 배제하고도 바둑을 정복함

 

◈ 인간을 대신할 새로운 선생님, MCTS

• 알파고와 달리 알파고 제로는 학습 때도 MCTS를 사용
• MCTS를 현재 상태 $s$를 인풋으로 그에 특화된 정책 $\pi(s)$를 내놓는 모듈로 생각할 수 있음
• MCTS는 현재 정책을 이용해 여러 번 시뮬레이션해 보고 얻은 결과 이기 때문에 현재 정책보다 좋은 정책
  이를 정답으로 보고 학습함
• MCTS의 분포와 현재 정책 네트워크의 아웃 풋 사이 차이를 줄이는 방향으로 네트워크를 업데이트

• 각 상태 $s_i$에서 MCTS 실행 후 액션 $a_i$ 샘플링, 이 과정을 게임이 끝날 때까지 반복
• 위와 같은 방법으로 수백만 경기의 데이터를 얻음
• 각 데이터는 $(s_t, \pi_t, z_t)$ 형식, $z_t$는 게임의 결과 (이겼으면 +1, 졌으면 -1)
• 이 데이터를 이용해 뉴럴넷 $f_{\theta}(s) = (p, v)$를 학습

• 상태 $s_t$를 $f_{\theta}$에 인풋으로 넣어서 정책 네트워크의 아웃풋 $p_t$와 벨류 네트워크 아웃풋 $v_t$를 계산
• $p_t$는 MCTS가 알려주는 확률 분포인 $\pi_t$와의 차이를 줄이는 방향으로 업데이트 (크로스 엔트로피)
• $v_c$는 경기 결괏값인 $z_t$와의 차이를 줄이는 방향으로 업데이트 (MSE)

$$L(\theta) = (z_t - v_t)^2 - \pi_t \log p_t$$

• 결국은 MCTS가 선생님 역할을 수행

 

◈ 알파고 제로에서의 MCTS

• MCTS 진행은 $f_{\theta}(s) = (p, v)$만을 이용해 진행

• 학습이 진행됨에 따라 $p$가 조금씩 발전할 것이기 때문에 MCTS 성능도 점점 좋아질 것으로 기대할 수 있음
• $s_L$의 벨류를 평가할 때는 $f_{\theta}$의 아웃풋인 $v$를 이용