[RL] AlphaGO

키워드

1. 딥러닝과 몬테카를로 트리 탐색을 결합한 AlphaGo 알고리즘을 통해 바둑에서 인간 챔피언을 이긴 최초의 인공지능 시스템. 강화학습의 실용적 성과를 보여줌.

2. "Mastering the game of Go with deep neural networks and tree search"

3. AlphaGo, MCTS

Monte Carlo tree search

  완벽한 정보가 존재하는 게임에는 optimal value function v*(s)를 재귀적으로 구할 수 있다. 하지만 b = 게임의 폭(가능한 수), d = 깊이(게임 길이)로 정의 할 때, 체스는 b ≒ 35, d ≒ 80,  Go는 b ≒ 250, d ≒ 150 수준으로 매우 큰 크기를 보인다. 이러한 게임에서 철저한(exhaustive) search를 통해 optimal 값을 구하는 것은 불가능하다.

  이에 효과적으로 검색하기 위한 두 가지 방법이 있다. 먼저, position evaluation을 통해 검색 깊이를 줄일 수 있다. 이는 state s의 tree를 value function의 근사값 v(s)로 교체한 후 state의 결과를 예측하는 것이다. 이러한 접근 방식은 체스, 오델로 등의 게임에서 뛰어난 성능을 보였으나 바둑에서는 게임의 복잡성으로 인해 한계를 보였다. 다음은 검색 범위(breadth)를  policy p를 통한 샘플링으로 줄일 수 있다. 예를 들어, Monte Carlo rollout은 두 플레이어 모두에 대한 policy p 기반 긴 action 시퀀스를 샘플링하여 전혀 분기하지 않고 최대 깊이까지 검색할 수 있다. 이 rollout들은 averaging 함으로써 효과적인 position evaluation이 가능하다.

  Monte Carlo tree search(MCTS)는 Monte-Carlo rollout을 사용하여 search tree의 각 state의 value를 추정하는 것이다. 더 많은 시뮬레이션이 실행될수록 search tree가 커지고 value가 더 정확해지며, 점진적으로 policy는 최적의 플레이로 수렴하고 evaluation은 최적의 value function으로 수렴한다. 많은 바둑 프로그램은 human expert의 수를 예측하도록 훈련된 policy로 강화된 MCTS를 기반으로 동작한다. 이는 policy가 확률이 높은 beam으로 검색 범위를 좁히고, rollout 중에 action을 샘플링하는 데 사용된다.

AlphaGo

  바둑(Go)은 오랫동안 고전 게임 중 가장 어려운 게임 중 하나이다. AlphaGo는 컴퓨터를 통한 Go의 새로운 접근 방식을 구현하였다. Value 네트워크를 통해 board의 위치에 대해 ​​평가하고, policy 네트워크를 통해 수를 선택한다. 이러한 Deep NN은 human expert 게임의 지도 학습과 self-play 게임의 강화 학습을 결합하여 훈련하였으며, Monte Carlo simulation을 활용한 새로운 search 알고리즘으로 프로그램 수준에서 바둑을 플레이할 수 있다.

  Alpha Go는 검색 트리의 유효 깊이와 폭을 줄이기 위해 CNN을 사용한다. 19x19 크기로 board 이미지를 통과시켜 position의 representation을 구성한다. 이는 여러 단계로 구성된 파이프라인을 통해 훈련되는데, 먼저 supervised learning(SL) policy 네트워크 pσ를 훈련한다. 이는 human expert의 feedback을 통한 고품질 그라디언트를 통해 빠르고 효율적으로 학습한다. 또한 rollout 중 신속하게 action을 샘플링하기 위한 fast policy pπ도 훈련한다.

  그 다음 reinforcement learning(RL) policy 네트워크 pρ를 훈련한다. SL policy 네트워크와 달리 최적화 self-play 게임의 결과로 학습하며, 예측 정확도를 최대화하기보다는 승리라는 올바른 목표를 향해 policy을 조정하게된다. 마지막으로 value 네트워크 vθ를 훈련한다. 이 네트워크는 RL policy 네트워크의 self-play 게임의 승자를 예측한다. 최종적으로 AlphaGo는 policy 네트워크와 value 네트워크를 MCTS와 효율적으로 결합하여 게임을 진행한다.

Architecture

Supervised Learning of Policy Networks

  첫 번째 단계에서는 지도 학습을 사용하여 전문가의 움직임을 예측을 학습한다. 최종 softmax 레이어는 가능한 수 a에 대한 확률 분포를 출력한다. 여기서 입력 s 는 board state가 사용된다. Policy 네트워크는 무작위로 샘플링된 state-action 쌍에 대해 SGD를 사용하여 전문가의 수에 대한 가능성을 최대화하도록 학습된다.

  SL policy 네트워크는 13개 레이어로 구성되어 있다. 이 네트워크는 테스트 세트에서 57.0%의 정확도를 보였다. 아래 그래프를 통해 약간의 정확도 향상은 큰 승률로 이어지는 결과도 확인 할 수 있다. 또한 더 빠르지만 정확도가 떨어지는 rollout policy도 학습했다. SL policy 네트워크는 3ms가 소요되는 대신, rollout policy는 단 2μs를 사용하여 수를 선택함으로써 24.2%의 정확도를 달성한다.

Reinforcement Learning of Policy Networks

  두 번째 단계는 policy gradient reinforcement learning(RL)을 통해 RL policy 네트워크를 학습하는 것이다. 이는 SL policy 네트워크와 구조가 동일하며 가중치도 동일하다. 다만 학습 방식에 차이가 있으며 RL policy 네트워크와 이전 iteration 중 무작위로 선택된 policy 사이에 self-play 게임을 통해 학습한다. 무작위로 상대방을 선택함하면 overfit을 방지하여 안정적으로 훈련할 수 있다. 게임이 끝날 때 승리 시 1, 패배 시 -1의 최종 보상을 받는다. 각 time step t 마다 가중치가 업데이트하며, 예상 결과를 최대화하는 방향으로 SGD을 통해 학습된다.

  게임 플레이에서 각 수를 샘플링하여 RL policy 네트워크의 성능을 평가하였다. 우선 RL policy 네트워크는 SL policy 네트워크를 상대로 80% 이상의 게임에서 승리했다. 하지만 CNN 지도 학습에 기반한 다른 강력한 Go 프로그램인 Pachi 와의 대결에서 RL policy 네트워크는 11%의 승률을 보였다.

728x90

Reinforcement Learning of Value Networks

  마지막 단계는 position evaluation을 위한 학습으로, value function vp(s)는 position s로부터 두 선수 모두 policy를 사용할 때의 결과를 예측한다.

  이상적으로 완벽한 플레이 optimal value function v*(s)을 를 알고 싶지만, 실제로는 성능이 뛰어난 RL policy 네트워크를 기반으로 value function를 근사해야한다. Value 네트워크는 policy 네트워크와 유사한 구조를 가지고 있지만 확률 분포 대신 단일 예측을 출력한다. 그리고 state-action 쌍에 대해 MSE로 예측된 value가 대응되는 목표에 대해 regression 되도록 학습된다.

  여기서 전체 게임으로 구성된 데이터로 결과를 예측하는 naive한 접근 방식은 overfit을 초래한다. 그 이유는 연속된 position은 돌 하나만 다를 정도로 강한 상관관계가 있지만, regression target은 게임 전체에서 공유되기 때문이다. 이 문제를 완화하기 위해 별도의 게임에서 샘플링된 3천만 개의 서로 다른 position으로 새로운 self-play 데이터셋을 생성했다. 각 게임은 게임이 종료될 때까지 동일한 RL policy 네트워크가 진행한다. 이 데이터셋에서 train 및 test 세트에서 MSE가 0.226 및 0.234로 나타났으며, 과적합이 최소화되었음을 알 수 있다.

  위 그림은 빠른 rollout policy를 사용한 Monte-Carlo 롤아웃과 비교하여 value 네트워크의 position evaluation 정확도를 나타낸다. value function가 꾸준히 더 정확한 것을 알 수 있다.

Searching Algorithm

  AlphaGo는MCTS 알고리즘과 policy 네트워크, value 네트워크를 결합하여 수를 선택한다. 우선 search tree의 각 Edge(s, a)에는 action-value Q(s, a), 방문 횟수 N(s, a), prior probability P(s, a)가 존재한다.

  먼저 root state부터 시작하여 시뮬레이션을 통해 tree를 순회한다. 시뮬레이션 별 각 time step t에서 state st에 따라 action a가 선택된다. 여기서 bonus 항 u(st, a) 가 추가되는데 이는 exploration을 장려하기 위해 반복 방문하면 감소하는 효과를 유도한다.

  L step에서 leaf node sl에 도달할 때, leaf node는 확장된다. SL policy 네트워크에 의해 한 번만 처리되며, 모든 가능한 action의 output probability가 prior probability P로 저장된다. Leaf node는 value 네트워크 vθ(sL)과 pπ를 통한 terminal step까지 rollout 후 얻은 최종 결과 zl 로 평가된다. 이에 대한 식은 아래와 같으며, 가중치 매개변수 λ를 사용하여 결합한다.

  시뮬레이션이 끝나면, 통과된 모든 edge의 action-value과 방문 횟수가 업데이트된다. 각 edge는 해당 edge를 통과한 모든 시뮬레이션의 방문 횟수와 평균 평가를 누적한다.검색이 완료되면 알고리즘은 root position로 부터 가장 많이 방문한 수를 선택합니다. 

  MCTS와 Deep NN을 효율적으로 결합하기 위해, AlphaGo는 CPU에서 시뮬레이션을 실행하고 GPU에서 policy 네트워크와 value 네트워크를 병렬로 계산하는 synchronous multi-thread search를 사용했다. 최종 버전에서 알파고 40개의 search thread, 48개의 CPU 및 8개의 GPU를 사용했으며, distributed 버전에서는 40개의 search thread, 1202개의 CPU 및 176개의 GPU를 활용했다.

결과

  (A) 위는 AlphaGo와 다른 바둑 프로그램간 대국 결과다. Elo scale에서 230 포인트 차이가 79%의 승률 차이를 의미한다. AlphaGo는 495경기 중 494승(99.8%)을 거두며 강력한 순위를 차지했다. 또한 더 큰 도전을 위해 4개의 핸디캡을 사용하여 게임을 했고, Crazy Stone, Zen, Pachi를 상대로 77%, 86%, 99%의 승률을 보였다. (C) 또한 distributed AlphaGo는 단일 버전을 상대로 77% 승률을 보이며 훨씬 더 강력한 성능을 보였다.

  (B) λ를 조절하여 AlphaGo value 네트워크만을 통한 position evaluation을 평가했다. Rollout이 없더라도 다른 모든 Go 프로그램의 성능을 능가하여 value 네트워크가 Monte-Carlo evaluation에 대한 적절한 대안을 제공한다는 것을 입증했다. 하지만 λ = 0.5에서 최고의 성과를 보이며, 두 메커니즘이 상호보완적임을 시사하기도 했다.

  위 그림은 실제 게임에서 알파고의 position evaluation을 시각화 한 것이다. Distributed AlphaGo가 활용되었으며 핸디캡 없이 최초로 인간 프로 선수를 이겼다.

Reference

논문 링크 : https://www.nature.com/articles/nature16961