[논문리뷰] DeepMind의 AlphaGO 논문 톺아보기

Nature 논문으로 살펴보는 AlphaGo 알고리즘

이 글은 최성준 박사님의 <Nature 논문으로 살펴보는 AlphaGo 알고리즘> 강의와 여러 자료들을 기반으로 AlphaGo 논문(다운로드)을 정리한 글입니다. 혹시 잘못된 내용이 있으면 말씀해 주세요!

Silver, D., Schrittwieser, J., Simonyan, K., Antonoglou, I., Huang, A., Guez, A., ... & Chen, Y. (2017). Mastering the game of Go without human knowledge. Nature, 550(7676), 354.

---

딥마인드와 알파고

2011년에 설립한 딥마인드 테크놀로지(DeepMind Technologies)는 기계학습과 신경과학을 통해서 인공지능을 구현하고 개발하는 영국의 스타트업이다. 2014년 구글이 4~5억 달러(약 4억 330억~5천 412억 원)에 인수한 뒤, 지금의 이름 딥마인드(DeepMind)가 되었다.

Complexity of Go

체스와 바둑

체스의 경우의 수는 10의 123승이다. 

1997년 카스파로프를 이겼던 IBM의 딥 블루(비공식 별명: Deeper Blue)는 12수를 예측할 수 있었다. 반면, 인간 플레이어는 10수를 내다 볼 수 있었다고 한다. 이제 체스는 사람이 인공지능을 이길 수 없는 영역이 되었다.

반면, 바둑의 경우의 수는 250의 150승(10의 360승)이다. 

바둑은 19 x 19 영역에 자신의 돌이 타인의 돌 안에 있으면 안되며, 자신의 집 안에 얼마나 공간이 있는지로 점수를 측정한다.

이는 우주의 원자 수인 10의 80승 보다 많으며, 현존하는 기술로는 모든 경우의 수를 고려할 수 없다고 한다. 따라서 아직도 사람이 인공지능을 이길 여지가 있는 영역이라고 볼 수 있다. 따라서 바둑을 인공지능이 정복하기 위해서는 탐색 범위를 줄이는 게 필요하다.

* b (breath) : 게임의 폭, 가능한 착수 위치 / d (depth) : 게임의 깊이, game length

체스는 b≈ 35, d ≈ 80인 것에 반해, 바둑은 (b ≈250, d ≈150)이기 때문에 탐색 트리로 b^d 경우를 모두 탐색하는 것은 불가능하다.

이 문제를 해결하기 위한 두 가지 방법

1. b를 통해서 탐색해야하는 깊이를 줄인다.
   > 바둑은 너무 복잡하기 때문에 이 방법을 다루기 어렵다.

2. 어떤 상태 s에서 착수가 가능한 모든 경우 a의 확률 분포 P(a|s)로부터 액션을 샘플링하면 탐색의 폭을 줄일 수 있다.

Monte-Carlo Tree Search

이 연구에서 활용된 몬테카를로 트리 서치(이하, MCTS)는 나와 상대방이 번갈아가면서 수를 두며, 트리처럼 뻗어나간다. 

주어진 시간 내에 모든 수를 둘 수 없다. 따라서 MCTS는 가장 효과적으로 탐색하기 위해 상대방이 둘 것 같은 수를 두어 가장 효과적으로 탐색하는 방식이다. 

[그림] MCTS를 적용한 AlphaGo

현재 단계(selection)에서 한 단계(expansion)를 예측한 뒤 시뮬레이션(simulation)을 한 최종 결과를 트리 상태에 업데이트(backpropagation) 하는 과정을 반복함으로써 바둑의 경우의 수를 효과적으로 탐색할 수 있다. 네 가지 단계를 반복하며, 각각의 단계에는 딥러닝 기법이 적용되어 있다.

1. Selection: 현재 바둑판(t) 상태에서 특정 시점(L)까지 착수 선택.. 리프 노드가 될 때까지 계속 선택함.
2. Expansion: 탐색 경로의 마지막 노드(L)를 확장시킴. (넓이 탐색 범위 줄이기)
3. Simulation: 게임이 끝날 때까지 시뮬레이션을 함 (깊이 범위 탐색 줄이기)
4. Backpropagation: 그 결과가 얼마나 좋은 수였는지를 파악하는 역할

Training Networks

MCTS in AlphaGo

[그림] AlphaGod의 핵심 알고리즘

Human Expert Positions

사람의 기보를 토대로 학습하여 분류 문제를 푸는 네트워크로, 번갈아 두면서 학습한 것이기 때문에 expansion 단계에 활용한다.

• Rollout policy: 사람의 기보만으로 학습되며, 빠르게 의사결정을 해야하는 경우 사용됨
  > 정확도는 24.2%이지만, Policy network가 의사결정하는 데 3ms(천 만분의 3초)가 걸리는 데 반해 2μs(백 만분의 2초)밖에 소요되지 않음
• SL policy network: 한 수 한 수 착수할 때 사용하는 네트워크

Self-play Positions

사람이 둔 바둑과 알파고끼리  두었을 때의 수를 가지고 학습하는 네트워크 (self-play positions)

• RL Policy network: 판이 돌아오면 어디에 다음 바둑을 둬야할지 찾는 네트워크
  
• Value Network: 알파고가 생각하는 현재의 판세를 평가하는 네트워크
  > 바둑의 최종 결과를 파악하기 어려우니, 가상의 수를 두는 시뮬레이션을 하다가 너무 아니라고 생각하는 수를 판단하는 단계
  > 일정 값으로 떨어지면 끝
  > 마지막 activation은 tanh(탄젠트 하이퍼볼릭)을 이용하여 -1에서 1의 값이 나옴

[그림] Input Features

ConvNet에서 학습할 기보 이미지에는 한 지점당 돌의 색상, 위치, 내 돌과 상대방 돌 등 11개의 피처(feature)를 사용하고 있다. 11개의 피처를 표현하는 차원은 총 48차원이다.

[그림] 필터 개수별 AlphaGo 성능

• Input Feature로 depth를 만듦
• Filter 개수에 따라 성능이 달라짐
• SL policy network의 작은 성능 개선이라도 AlphaGo의 전체 승률 개선에 많은 영향을 미침

Training

[그림] AlphaGo의 딥러닝 학습 파이프라인 (출처: David Sliver 슬라이드)

Searching with policy and value networks

• RL Policy network
  > Policy Gradient Reinforcement Learing을 통해서 알파보 기보도 고려함
  > 이긴 판에 대해서는 리워드 +1, 진 판은 리워드 -1
• Value Network
  > 사람의 기보만 있을 경우 오버피팅이 일어날 수 있기 때문에 알파보의 기보(RL policy network)가 추가됨
• Distributed AlphaGo의 성능이 더 좋음

Experiments

Selection Rule

• Q값: state가 정해졌을 때 다음을 어디에 둘지 정함
• u: 어떤 policy function이 있고, 그것이 몇 번 들어왔는지 (?)
• 독립적으로 돌아가는 CPU가 동일한 걸 보고 있으면 휴리스틱처럼 이 수는 커버하지 않음

Expansion Rule

• visit count를 넘게 되면 search tree에 다음 state가 추가되며 그 트리에 확장(expansion)됨

Edge

• Rollout Net: 바둑을 끝까지 했을 때 얻어지는 점수
• N_v와 W_v가 중요한 지표 
  > N_v(s, a), N_R(s, a): 몇 번 체크했는지
  > W_v(s, a), N_r(s, a): 이겼는지 졌는지
• 람다(Lambda)는 0.5로 투닝하여 사용함

Result

[그림] AlphaGo와 상용 바둑 프로그램의 성능 비교

제한된 시간 내에서 다른 인공지능과 비교했을 때 네 점 핸디캡(접바둑)을 두고 시작하여도 모두 이김

• Distributed AlphaGo: 런타임할 때 사용함
  
• Game Result Prediction: 100번 롤아웃해서 얻어지는 결과로 평가함

Computational Power (유럽 경기용)

• Distributed AlphaGo: 40개의 셀, 1,202개의 CPU, 176개의 GPU, 2,890개의 Elo rating (판후이와 대국에 이용됨)
• Training Policy Net: 50개의 GPU
• Training Value Net: 50개의 GPU, 하나의 네트워크
• 이세돌과 경기했을 때의 컴퓨팅 파워는 밝혀진 바 없음

* Elo rating은 게임 플레이어 간의 실력을 상대적으로 나타낸 것으로, 단일/분산 AlphaGo의 성능을 측정하기 위해 기존 인공지능 프로그램과 대결하여 산출함

Conclusion

AlphaGo 연구의 의의

00. 딥러닝 기술의 성능 향상

바둑은 경우의 수가 매우 많고 복잡하여 인공지능 분야에서 아직 정복하지 못한 그랜드 챌린지(Grand challenge)였다. 그러나 AlphaGo를 통해서 인공지능의 성능을 보여주는 실증 사례가 되었다.

01. 실용적인 연구이다.

사람만이 할 수 있을 거라고 생각한 영역인 '바둑'에 인공지능을 적용함으로써 실용적인 연구를 했다는 점에서 의의가 있다. 

인공지능 분야에서는 재밌어 보이거나/실용적이지 않거나/자연지능(인간의 지능) 수준의 성능을 내는 연구들이 많은데, 알파고는 바둑에서 인간을 압도적으로 이기는 인공지능이 되었다.

02. MTCS를 이용해서도 바둑을 풀 수 있다!

이 논문은 딥러닝과 관련이 적었던 기존의 방법론(몬테카를로 방법, 강화학습 등)과 딥러닝이 가지는 중요한 특징을 고려한다. 즉, 딥러닝을 적용하지 않았던 방법들에 네트워크(신경망)를 고려하여 기존의 문제를 더 나은 성능으로 해결한다는 데 의의가 있다.

따라서, 어떤 도메인에 기존의 문제 풀이 방법 + 딥러닝을 적용하여 새로운 방법론을 적용해보는 것도 좋은 연구의 흐름일 수 있다.

03. 인공지능의 대중화

사람과 알파고의 대전을 통해서 많은 사람들이 인공지능과 딥러닝 기술에 관심을 갖게되었다. 즉, 인공지능은 그들만의 분야가 아니라 일상 속에 가까운 기술로 인식될 수 있게 한 것도 알파고의 큰 업적이라고 생각한다.

---

References

이주열님의  AlphaGo 알고리즘 요약

Silver, D., Schrittwieser, J., Simonyan, K., Antonoglou, I., Huang, A., Guez, A., ... & Chen, Y. (2017). Mastering the game of Go without human knowledge. Nature, 550(7676), 354.

(강의) 논문의로 짚어보는 딥러닝의 맥 - Neature 논문으로 살펴보는 AlphaGo 알고리즘

같이 읽으면 좋은 아티클

[카카오AI리포트] 알파고 제로 vs. 다른 알파고

알파고 논문 번역 (1/2)

알파고 논문 번역 (2/2)