[AlphaGo] Mastering the Game of GO with Deep Neural Networks and Tree Search (NATURE Article)

By | 2016-10-22

NATURE에 AlphaGo(출처)에 대한 논문이 있어서 읽어 보았다. 솔직히 무슨 말인지 거의 이해를 하지 못하였다. 그래서 우선 이해한 부분만 정리하고 이해하지 못한 부분은 다시 정리할 계획이다. 기본적으로 Go(바둑)는 가능한 수가 너무 많아 단순 프로그램으로는 사람을 이기기가 쉽지 않다고 알려져 있다고 한다. AlphaGo가 최초로 사람(프로 기사)을 이긴 Go(바둑) 프로그램이 된 것이다.

160128-NS-01

그림 1: 이세돌과 AlphaGo 관련 사진 (출처)
(논문의 AlphaGo가 이세돌과의 경기에서 사용된 것인지는 알 수 없음)

기존의 Go(바둑) 프로그램은 크게 2가지 알고리즘(방법(?))으로 작성이 된다고 한다. 하나는 position value (각 점의 priority)를 기준으로 search의 death를 줄이는 방법이다. 내가 이해한 바에 의하면 position value가 높은 점을 기준으로 search를 처리하는 방법인 듯하다. 또 다른 방법은 sampling action을 기준으로 breadth search를 줄이는 방법이다. 두 번째의 sampling action이라는 정의를 잘 이해하지 못하겠다. 결과적으로 2번째 방법을 사용하면 아마추어 레벨 정도의 Go 프로그램을 작성 가능하다고 한다.

AlphaGo의 경우 Monte Carlo rollouts와 neural network를 같이 사용하여 Go(바둑) 프로그램을 만들었다고 한다. Monte Carlo rollout 은 기존에도 Go(바둑) 프로그램에서 자주 사용되는 방법이라고 한다. Neural network는 image classification, face recognition 등에서 좋은 성능을 보여 많이 사용되는 방법이다. NATURE 논문에 따르면 AlphaGo는 총 13개의 층으로 구성된 neural network를 기반으로 설계되었다고 한다. 그리고 아래와 같은 3개의 순서로 learning (학습?)을 진행한다고 한다 (그림 2 참조).

AlphaLearning 순서

그림 2: Alpha 학습 순서 (출처)

AlphaGo 학습 순서
  • Step 1: Supervised Learning (SL) of policy networks
  • Step 2: Reinforcement Learning (RL) of policy networks
  • Step 3: Reinforcement Learning (RL) of value networks
1. Supervised Learning (SL) of policy networks: 프로기사들의 기보를 사용하여 network를 학습하는 과정이다. 대략 3천만 번의 포지션 데이터를 학습에 사용하였다고 한다. 이 과정을 거치면 프로기사의 움직임을 대략 57% 정도 예측할 수 있다고 한다.
2. Reinforcement Learning (RL) of policy networks(제일 이해가 안 가는 부분이다): 앞에서 SL을 사용한 network의 값을 조금 변경하여 self training을 하는 과정이다. 이 과정을 거치게 되면 기존 SL보다 더 최적화된 network가 생성되어 predictive accuracy가 향상된다고 한다.
3. Reinforcement Learning (RL) of value networks: 각 포지션(돌을 놓을 수 있는 위치?)의 value(?) 값을 정하는 부분이다. 이해한 바에 의하면 각 포지션당 승리할 가능성의 값을 정하는 단계인 것 같다. 높은 값을 가질수록 더 높은 승리 확률이 존재하는 것이다. 그림3에 보면 각 포지션에 특정한 값이 표시된다. 이렇게 하여서 tree search 과정에서 value가 높은 걸 기준으로 다음 position을 search 하므로 overhead를 줄일수 있다.
AlphaLearning Value
그림 3: AlphaGo의 Value Network (출처)
논문에 따르면 아래 2개의 실험환경에서 AlphaGo 성능을 측정하였다.
  1. 40 search threads, 48 CPUs, 8 GPUs
  2. 40 search threads, 1,202 CPUs, 176 GPUs
위의 실험 환경으로 AlphaGo는 기존의 바둑 프로그램과 유럽 바둑 프로기사를 이겼다고 서술하였다. (이세돌을 이긴 AlphaGo의 스펙은 아직 찾지 못하였다) 개인적으로 논문을 읽으면서 이해하지 못하는 부분이 너무 많았다. 그래서 관련 논문을 조금 더 찾아서 공부할 계획이다. 그 후 틀린 부분 또는 미흡한 부분을 수정할 계획이다.
논문을 읽으면서 이해하지 못한 부분을 아래에 정리하였다.
  1. Monte Carlo Tree Search (MCTS) – Monte Carlo rollouts
  2. Deep neural networks (DNN)
  3. Supervised Learning (SL) 방법
  4. Reinforcement Learning (RL) 방법

Leave a Reply

Your email address will not be published. Required fields are marked *