CH10. 알파고와 MCTS

* [바닥부터 배우는 강화학습] 도서를 읽고 정리한 글입니다

 

10.1 알파고

여기서는 2016년 이세돌과 겨루었던 버전에 대한 논문 내용을 쉽게 재구성하여 다룬다.

알파고는 학습단계와 실시간 플래닝 2단계로 나누어 볼 수 있다.

학습단계는 실제 대국을 치르기 전에 다양한 데이터들을 활용해 학습함으로 대국에서 사용할 여러가지 케이스들을 학습하게 되는 단계이다.

실시간 플래닝은 대국 과정에서 학습했던 데이터를 활용하여 실시간으로 다양한 수를 시뮬레이션 해서 다음 수를 결정하는 과정이다.

실시간 플레닝 알고리즘으로  MCTS (Monte Carlo Tree Search)를 사용한다.

 

이 2단계를 차례로 살펴본다.

(1) 학습단계

학습단계는 MCTS에서 쓰일 재료를 만드는 과정이다.

MCTS 는 4가지 준비물이 필요하다.

- 사람의 기보를 이용해 지도 학습한 정책 \( \pi_{sl}\)

- 롤 아웃 정책 \( \pi_{roll}\)

- 스스로 대국하며 강화 학습한 정책 \( \pi_{rl}\)

- 밸류 네트워크 \( \nu_{rl}\)

1) 지도 학습 정책 \( \pi_{sl}\)

학습은 6단 이상의 바둑 기사 기보 데이터를 활용해 \( \pi_{sl}\) 신경망을 학습시키는 것으로 시작한다.

기보 데이터는 바둑판의 상태와 해당 상태에서 실제 바둑알을 둔 곳의 위치의 쌍으로 이루어지며 3천만 개의 데이터를 사용했다.

 

 \( \pi_{sl}\) 신경망은 바둑판 상태 정보 s가 인풋으로 들어오면 19*19=361 칸 중에 현재 상태에서 둘 수 있는 칸 들에 대해 돌을 놓을 수 있는 확률을 리턴한다.

예컨대 바둑판 특정상태 s에서 바둑기사가 (16, 14) 위치에 돌을 두었다면 이를 정답으로 보고, 정답과 신경망 예측값 사이의 차이를 손실함수로 정의하여 이를 줄이는 방향으로  \( \pi_{sl}\) 신경망의 파라미터를 업데이트 한다.

이렇게 학습을 한다면 3천만 개의 데이터 안에 있는 평균 전략을 학습할 수 있다.

 

\( \pi_{sl}\) 신경망은 정답률이 57%를 기록했다.

전문가들의 기보를 이용한 학습의 성능은 그리 좋은 것은 아니다.

이 정책을 잘 보관하여 추후 MCTS에서 활용하게 된다.

 

2) 롤아웃정책 \( \pi_{roll}\)

\( \pi_{sl}\) 신경망과 유사하게 바둑판의 상태 S를 인풋으로 받아 어디에 둘지 각 액션의 확률 분포를 리턴하며, 기보 데이터를 이용한 지도 학습을 하게 된다.

대신 사용된 신경망은 훨씬 작고 가벼운 네트워크이다.

\( \pi_{roll}\)은 사람 지식을 이용해 만든 수 많은 feature에 대해 선형 결합 레이어가 하나만 존재한다.

따라서 계산속도는 매우 빠르다. 다만 정확도 성능은 24.2%에 불과하다.

 

3) 강화 학습 정책 \(\pi_{rl}\)

강화학습을 통해 강화되는 정책을 \(\pi_{rl}\)라고 하겠다.

\(\pi_{rl}\)은 \(\pi_{sl}\)과 완벽히 똑같이 생긴 신경망이고 \(\pi_{rl}\) 파라미터들은 \(\pi_{sl}\) 파라미터를 이용해 초기화한다. 따라서 초기에는 \(\pi_{rl}\)는 \(\pi_{sl}\)과 완전히 같은 네트워크이다.

하지만 \(\pi_{rl}\)는 self-play를 통해 계속 강화된다.

 

self-play는 자신의 과거 모델들을 이용해 풀을 만들고, 풀에서 랜덤하게 하나를 뽑아와서 경기를 펼치는 방식이다.

알파고는 학습을 받고 있는 네트워크가 500번 업데이트 될 때 마다 해당 모델을 풀에 넣어주었다고 한다.

self-play에서 보상함수는 경기를 이기면 1, 지면 -1로 하였고 중간 보상은 없었다.

또한 강화학습시 방법론은 리턴만 있으면 학습할 수 있는 REINFORCE 알고리즘을 사용하였다.

리턴 계산에 사용되는 \(\gamma\)값은 1.0으로 정했다.

즉 한 경기 안의 모든 시점에 대해 같은 값의 리턴을 갖게 된다.

이긴 경기에서 발생한 모든 액션의 확률을 동등하게 증가시키고, 진 경기에서 발생한 모든 액션의 확률은 동등하게 감소시킨다.

128 경기의 데이터를 이용해 1개의 미니 배치를 구성하였다.

미니 배치가 매우 크기 때문에 안정적인 그라디언트 계산이 가능하다.(?)

학습이 끝난 \(\pi_{rl}\)을 \(\pi_{sl}\)과 경기를 붙이면 80% 승률로 \(\pi_{rl}\)이 이겼다.

 

4) 밸류 네트워크 \(\nu_{rl}\)

\(\nu_{rl}\)의 신경망 구조는 \(\pi_{rl}\), \(\pi_{sl}\) 과 동일하지만 아웃풋이 1개인 스칼라 값이다.

즉, 각 상태 (s)의 가치 밸류를 리턴하는 신경망이다.

\(\nu_{rl}(s)\)는 주어진 상태 s부터 시작해서 \(\pi_{rl}\)을 이용해서 플레이 했을 때 이길지 여부를 예측하는 함수이다.

\(\nu_{rl}\) 학습 시 손실함수는 해당 경기에서의 승패 여부와 승패 여부 예측값인 신경망 아웃풋 사이 MSE로 정의했다.

해당 신경망이 학습된 후 임의의 상태를 인풋으로 넣으면 해당 경기의 승자가 누가 될지 그 결과를 가늠할 수 있게 된다.

이 함수는 MCTS 에서 매우 중요한 역할을 수행한다.

 

이제까지 4가지 준비물을 살펴보았다.

본격적으로 MCTS를 살펴본다.

 

(2) MCTS

MCTS 기본개념을 간단히 보면,

"주어진 상황에서 결과를 예측하기 위해 수 많은 시뮬레이션을 머릿속으로 실행해보고 그 중에 결과가 가장 좋았던 액션을 선택하는 방법"이다.

 

MCTS 방법을 적용하기 위해서는 전제조건이 있다.

첫번째, MDP 모델을 알아야 한다. 즉 상태 전이 확률과 보상함수를 알아야 한다.

바둑의 경우는 규칙을 알고 있으므로 결국 상태전이확률과 보상함수를 알고 있다고 할 수 있다.

그래서 시뮬레이션이 가능한 것이다. 

이처럼 시뮬레이션을 통해 더 나은 정책을 만드는 과정을 플래닝 이라고 한다.

두번째, 게임 중간마다 시간적 틈이 있어야 한다. 플래닝을 진행하기 위해서는 일정 시간이 필요하다.

바둑은 차례가 도래하면 생각할 시간이 주어지는데 이 규칙이 있기 때문에 MCTS를 사용할 수 있는 것이다.

1) 선택

루트 노드에서 출발하여 리프노드 (자식이 없는 노드)까지 가는 과정이며 각 노드에서 다음 노드를 선택할 때 기준은 다음 식을 활용한다.

시뮬레이션이 진행하며 경험이 쌓일 수록 Q의 영향력이 커지고, u의 영향력은 줄어든다.

Q(s,a)는  상태s에서 액션a를 선택한 이후 도달한 리프 노드들의 리턴의 평균을 의미한다.

예를 들어 상태 \(s_{78}\)에서 액션 \(a_{33}\)을 선택하는 경험을 총 100번 했다고 가정하고 , 

각 경험 별로 도달한 리프노드를 \( s_L^1, ..., s_L^{100}\) 이라 한다면 ,

이때 \(Q(s_{78}, a_{33})\)는 다음과 같다.

 

여기서 밸류V 계산방법은 뒤에서 다시 언급한다.

 

다음은 u(s,a) 공식을 살펴본다.

P(s,a)는 사전확률(prior probability) 로 시뮬레이션 해보기 전에 각 액션에 대한 확률을 부여한다.

이 경우는 사람 기보를 이용해 학습해두었던 \(\pi_{sl}(a \vert s)\)를 사용하여 정의한다.

 

$$ P(s,a) = \pi_{sl}(s,a) $$

즉, 사람이라면 두었을 법한 수에 높은 확률을 부여하는 것이다.

N(s,a)는 시뮬레이션 도중 엣지(s,a)를 지나간 횟수이다. N(s,a) = 0에서 시작하여 한 번 지나갈 때 1씩 더해진다.

(실제 N(s,a)값의 업데이트는 백 프로파게이션 단계에서 이루어진다)

시뮬레이션 횟수를 증가시켜 방문횟수가 증가할 수록 N(s,a)값이 증가하므로 분모가 증가하면서 결국 u값은 작아지게 되어 선택에 영향력이 줄어들게 된다.

 

사전확률에 \(\pi_{rl}\) 대신 \(\pi_{sl}\)를 선택한 이유는 \(\pi_{rl}\)보다 다양한 액션을 시도하는 정책이었기 때문에 \(\pi_{sl}\)로 초기화하면 시뮬레이션 도중 다양한 수를 시도하여 다양한 경험을 쌓을 수 있기 때문이다.

 

2) 확장

선택단계에서 도달한 리프노드를 실제로 트리에 매달아 주는 과정이다. 또한 이 노드에서 가지치는 엣지들의 다양한 정보를 아래와 같이 초기화 해 준다.

위 3가지 값이 정의 되었기 때문에 새로 추가된 노드에서 실행 가능한 각 액션에 대해서도 Q+u 값을 계산할 수 있으며 이 노드에서 액션을 선택할 수 있게 된다. 따라서 리프 노드가 트리의 정식 노드로 확장한 것이다.

 

3) 시뮬레이션

확장을 통해 리프노드가 트리의 정식노드가 되었으므로 해당 노드의 가치를 평가해야 한다.

노드의 가치밸류 계산 방법은 2가지가 있다.

첫째 방법은 리프 노드 \( s_L \)부터 시작하여 게임이 끝날 때까지 롤아웃 정책\(\pi_{roll}\)를 이용하여 빠르게 시뮬레이션 해보는것이다.

롤아웃 정책을 이용하여 번갈아 두어 가면서 게임 종료시 이겼으면 +1, 지면-1이 된다. 이 시뮬레이션 결과값을 \(z_L\)로 표기한다.

시뮬레이션은 한번만 진행되며 결과값 \(z_L\)을 해당 노드 \(s_L\)의 밸류로 사용한다.

 

두번째 방법은 학습과정에서 준비해둔 밸류 네트워크(\(\nu_{rl}(s)\)를 활용하는 것이다.

(\(\nu_{rl}(s)\)는 상태 s부터 정책 \(\pi_{rl}\)로 플레이할 때 누가 이길지 예측해주는 함수이다.

노드 \(s_L\)을 인풋으로 넣으면 시뮬레이션 필요없이 \(\nu_{rl}(s_L)\)값이 계산되며 해당 값이 \(s_L\)노드의 밸류가 된다.

 

알파고는 위 2가지 방법을 모두 사용하여 평균을 낸 값을 해당 노드의 밸류로 택했다.

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

백 프로파게이션은 주어진 상태s에서 액션a 선택시 새롭게 도달한 리프 노드 밸류 값을 이미 계산되어 있는 평균값 Q(s,a)에 업데이트 하는 과정이다.

지나온 모든 엣지에 대해 Q(s,a)값과 N(s,a)값을 아래와 같은 수식으로 업데이트 해 준다.

리프노드의 밸류값이 리프노드로부터 루트 노드로 전파된 것이니 역전파(백 프로파게이션)라고 부른다.

업데이트를 반복 진행하다 보면 Q는 액션의 실제 밸류로 수렴한다.

 

결국, 선택=>확장=>시뮬레이션=>백프로파게이션 과정을 한 번 진행하면 하나의 노드가 새롭게 추가된다.

수십개의 CPU, GPU를 사용하여 무수히 반복하여 MCTS를 돌렸다고 한다.

MCTS를 종료하고 나서 생성된 트리를 이용하여 루트노드 s 에서 액션을 선택하는 기준은 무엇일까?

위 그림에서 상태 s에서는 액션 a1, a2, a3 3개 중 하나를 선택할 때 알파고에서는 방문횟수 N(s,a)가 가장 큰 액션을 선택했다.

결국, a1 아래로 노드가 가장 많이 매달려 있으므로 a1을 선택하게 된다.

방문횟수가 많다는 것은 MCTS 도중 해당 엣지의 밸류(Q)가 좋았다는 것을 의미한다. Q가 크다는 것은 그 엣지를 지나서 도달했던 리프 노드의 가치가 높았다는 뜻이므로 합리적인 선택이다.

또한 신뢰도가 높다는 것을 의미한다. ( 예를 들면 음식점 평점이 높은 것과 함께 리슈개수가 많아야 신뢰가 간다)

 

10.2 알파고 제로

알파고 제로는 기보 데이터 없이 강화학습을 가능하게 방법을 고안했다.

 

(1) 인간을 대신한 MCTS

알파고 제로는 학습때도 MCTS를 사용한다.

학습시에 MCTS를 사용하려면 MCTS 내부를 변경해야 한다.

내부 변경사항은 뒤에 다시 설명하고,

일단 MCTS를 블랙박스로 보고 인풋으로 현재상태 s를 받으면 그에 특화된 정답 정책을 내놓는 아래 그림과 같은 모듈을 생각해본다.

해당 모듈을 이용해 self-play를 진행함으로 기보 데이터를 대채하는 데이터를 얻는다.

위 그림의 s1상태에서 MCTS를 돌리면 각 액션에 대한 확률분포 \(\pi_1(s_1)\)을 얻는다.

얻어진 확률분포를 근거로 샘플링하여 a1 액션을 선택한다.

a1을 실행하여 상태s2를 얻는다.

다시 MCTS를 돌리고 정책을 얻고 그 정책확률을 근거로 샘플링해서 a2를 선택한다.

이 과정을 게임 종료시 까지 반복하면 한 경기의 데이터가 생기며 같은 방식으로 반복하면서 수백만 경기의 데이터를 얻게 된다. 그리고 이 데이터를 이용해 정책 신경망 학습을 하게 된다.

여기서 게임 진행과정에 얻게 되는 데이터는 (\(s_t, \pi_t, z_t\)) 형식이다.

\(s_t\)는 t시점에 상태이며, \(\pi_t\)는 상태 \(s_t\)에서 진행한 MCTS가 알려주는 정답 정책이고, \(z_t\)는 게임결과값이다.

이렇게 쌓인 데이터를 이용해 신경망 \(f_{\theta}\)를 학습한다.

신경망 \(f_\{theta}\)는 정책네트워크와 밸류 네트워크를 한 번에 계산해준다.

CH09의 TD 액터-크리틱에서 사용했던 신경망과 유사하게 아랫단 레이어는 공유하며 윗단에서 갈라져 액션의 확률분포p와 밸류v를 리턴한다.

 

상태 \(s_t\)를 \(f_{\theta}\)에 인풋으로 넣어서 정책 네트워크 아웃풋 \(p_t\)와 밸류 네트워크 아웃풋 \(\nu_t\)를 계산한다.

정책 네트워크 아웃풋 \(p_t\)는 MCTS가 알려주는 확률분포 \(\pi_t\)와의 차이를 줄이는 방향으로 업데이트한다.

밸류 네트워크 아웃풋 \(\nu_t\)는 경기 결과값인 \(z_t\)와의 차이를 줄이는 방향으로 업데이트한다.

이를 근거로 손실함수를 구성하면 아래와 같다.

\(z_t\)와 \(\nu_t\) 사이는 MSE를 사용하여 손실함수를 구성하며, \(\pi_t\)와 \(p_t\) 사이는 크로스 엔트로피를 사용하여 손실함수를 구성한다.

위 식의 의미는 다음과 같이 풀어볼 수 있다.

MCTS가 알려준 액션 분포 \(\pi_t\)를 따라가도록 정책네트워크를 업데이트하고, MCTS를 이용해 진행한 게임결과(\(z_t\))를 예측하도록 밸류 네트워크를 업데이트 하는 것이다.

 

(2) 알파고 제로에서의 MCTS

알파고의 MCTS에서는 사전 준비물이 필요했다.

기보 데이터를 이용해 학습한 \(\pi_{sl}\)과 \(\pi_{roll}\), 그리고 강화 학습을 통해 얻은 \(\nu_{rl}\)이 더 이상 존재하지 않는다.

대신 아직 학습하지 않은 신경망 \(f_{\theta}(s) = (p,\nu)\) 가 있다.

이를 이용해 \(\pi_{sl}\) 대신 p를 사용하고 \(\nu_{rl}\) 대신 \(\nu\)를 사용한다.

\(\pi_{roll}\)는 사용하지 않는다.

확장단계와 시뮬레이션단계가 하나로 합쳐졌다.

확장단계에서 리프노드에서 뻗어나가는 액션의 사전확률은 \(\pi_{sl}\) 대신 \(f_{\theta}\)의 아웃풋인 p를 이용하여 초기화한다.

알파고의 MCTS에서는 시뮬레이션 단계에서 \(\pi_{roll}\)을 이용하여 얻은 시뮬레이션 결과와 밸류 함수 아웃풋 \(\nu\)의 평균을 사용했지만 , 알파고 제로에서는 리프노드 \(s_L\)의 밸류 평가시 \(f_{\theta}\)의 아웃풋인 \(\nu\)를 이용한다.