[AlphaGo - The first computer program to ever beat a professional player at Go]

AlphaGo?
알파고는 구글 딥마인드에서 개발한 바둑 인공지능입니다. 이미 유럽챔피언인 판 후이 2단을 5:0으로 꺾어 화제가 되었는데요, 과거 체스 등 인간의 영역으로 여겨졌던 분야에서 인간을 꺾은 인공지능이 종종 있었으나, 바둑은 그 수의 경우가 워낙 많아 인공지능은 사람을 절대 못 이길 것이다..하는 생각을 뒤집어 버린 획기적인 사건이었죠.

사실 구글 딥마인드에서 인간에 필적하는 인공지능을 테스트하는 것은 이번이 처음은 아닙니다. 작년 초 네이처지에 "Human-level control through deep reinforcement learning"이라는 논문을 발표하면서 자체 개발한 Deep Q-Network(이하 DQN)을 아타리 게임에 적용하여 49개의 게임 중 29개의 게임에서 인간 전문가의 75% 이상에 해당하는 점수를 획득했다고 알린 바 있습니다.

왜 바둑인가?
19x19의 반상에서 펼쳐지는 바둑은 체스나 장기 등과 달리 돌이 놓이는 위치와 이후의 수에 대한 가치를 평가하는 것이 매우 어려운데다 경우의 수도 엄청나게 많기 때문에 인공지능 분야에서는 매력적인 도전으로 여겨지고 있었습니다. 체스에서는 이미 IBM의 딥 블루가 당시 세계 챔피언 그랜드마스터였던 가리 카스파로프를 압살한 바 있으나 바둑의 경우 잘해봐야 아마추어 수준을 넘어서지 못하고 있었죠.


[유럽 챔피언 판 후이 2단과 알파고의 대결]
여기에 알파고가 도전장을 던졌고, 결과는 유럽 챔피언을 상대로 5:0이라는 완승을 거둡니다. 이에 전 세계의 인공지능 연구자들과 바둑 애호가들의 이목이 쏠렸고, 이세돌 9단과의 대국까지 성사되는 등 난공불락의 철옹성으로 여겨지던 바둑에서까지 인간을 넘어서려는 도전을 하고 있습니다.

기본 동작 원리
바둑은 수가 너무 많기 때문에 brute force 방식의 '일단 다 따져보자!'는 사실상 불가능합니다. 그렇다고 임의로 찍자니 이게 제대로 된 수인지 객관적으로 판별할 방법이 없죠. 알파고는 이 문제를 해결하기 위해 1) 경우의 수를 줄이면서 2) 결과를 더 빨리 예측하는데에 집중합니다.

1) 경우의 수 줄이기(Breadth Reduction)

위와 같은 수가 놓였다고 할 때, brute force 방식으로는 다음에 놓일 수 있는 모든 수를 다 따져봐야 합니다. 이건 가장 확실하지만 동시에 가장 비효율적이기도 하죠. 알파고는 경우의 수를 줄이기 위해 학습한 기보를 기반으로 상대가 이 다음에 놓지 않을 수를 제거합니다. 기보를 학습해보니 이 다음엔 여기에 놓는 경우가 없더라..하는 식으로요.


이렇게 하면 경우의 수를 획기적으로 줄일 수 있습니다. 제가 바알못이라 바둑을 정확하게 알지는 못 하지만, 사람간의 모든 턴제 대전이 그렇듯 '말도 안 되는 수'와 '합리적인 수'는 구분되기 마련이고 알파고는 여기에 착안하여 이 다음에 올 수 없는 수를 제거하여 가능한 경우의 수를 줄입니다.

2) 결과 더 빨리 예측하기(Depth Reduction)
경우의 수를 줄인 건 좋은데, 여기에도 맹점은 있습니다. 이후에 이어질 수를 예측하고 이게 대국의 끝까지 진행되었을 때 내가 이기냐 지냐를 판별해야 하는데, 한 수 둘 때마다 이러면 brute force에 비해 줄었다고는 하나 여전히 시간이 엄청 오래 걸리게 됩니다. 알파고는 이를 해결하기 위해 depth reduction이라는 프로세스를 수행하는데, 이는 대국이 진행되면서 내가 다음에 두는 수의 가치는 어느 정도인가?를 수치로 나타내어 대국의 끝까지 예측하지 않고 이 정도면 됐어!하는 지점에서 멈춰 예측을 보다 빨리 하는 과정입니다.


위 그림에서 d를 대국의 진행 정도, 각각의 예측을 s, V를 수의 가치라고 하면, V(s)를 s라는 수를 두었을 때의 유/불리로 볼 수 있습니다. 이를 통해 대국의 끝까지 예측하지 않아도 현재 대국의 판세를 판단하고 다음에 둘 수를 보다 빨리 결정할 수 있게 됩니다.

학습은 어떻게 했는가?
4주간 3천만개의 착점으로 구성된 16만개의 고수들의 기보를 학습하고 이를 기반으로 자가 대국 100만 판을 해서, 인간이 하루에 3번의 대국을 한다고 쳤을 때 약 1천년치에 해당하는 훈련을 거쳤다고 합니다. 이 과정을 좀더 자세하게 풀면..

1) Supervised Learning
'16만개의 기보'를 학습하는 과정은, 현재의 수 및 반상의 판세를 바탕으로 '지금은 이랬는데 다음엔 저렇게 두는게 많더라'하는 식으로 이루어집니다. 다시 말해, 프로 기사 등 전문가들의 기보를 학습하면서 각 수와 수 사이에 예측 모델을 두고 이 예측 모델에 다음에 행해지는 수를 다 입력하는 방식입니다.

예를 들어, 아래와 같이 대국이 진행되는 기보가 있을 때..


이 기보에서는 이 사람이 이렇게 두었더라..라고 학습합니다. 이런 학습 결과를 모으고 모아서,


L:p(next action | current state)로 표현할 때, 이런 식으로 다음 착점의 가치를 계산하고 가장 승률이 좋았던 곳은 여기구나! 하는 식으로 학습합니다. 이런 식으로 판세를 읽는 데에는 입력값을 레이어별로 추상화하여 출력값을 뽑아내는데 매우 유용한 Convolutional Neural Network(CNN)이라는 기법이 사용됐습니다. 그냥 그런게 쓰였구나..하고 넘어가셔도 됩니다..^^;

2) Reinforcement Learning
알파고의 학습에서 핵심이 되는 파트입니다. 쉽게 말해, 입력된 기보를 바탕으로 자가 대국을 수행하여 상황에 따른 다음 수별 승률을 계산하고 최적의 수를 찾는 학습 과정입니다.



예를 들어, 같은 상황에서 예측 모델을 거쳐 다음 수를 이렇게 두니까 졌는데 저렇게 두니까 이기더라.. 하는 식으로 자가 대국을 거쳐 수의 가치를 보정하고 이를 통해 반복적으로 자가 업데이트를 수행하여 끊임없이 발전해나갑니다. 알파고 논문에서는 학습 완료 후 모델과 최초의 모델을 대국시켜봤을 때 학습이 완료된 모델이 80% 승률을 기록했다고 합니다.

요약 정리
이상을 요약하면, 알파고는


전문가의 기보를 바탕으로 학습을 하고 자가 대국을 통해 발전하며, 실전 대국시에는 1) 경우의 수를 줄이고(Breadth Reduction) 2) 판세를 판단하고 결과를 더 빨리 예측(Depth Reduction)하는 인공지능입니다. 대국 메커니즘을 정리하면 아래와 같으며, 이런 방식을 몬테 카를로 탐색 트리 기법이라고 합니다.


a. Selection
이게 괜찮은 수인지, 되도 않는 수인지를 판단하여 경우의 수를 줄입니다.(Policy Network)
b. Expansion, c. Evaluation
보다 빠른 예측을 거쳐 판세를 판단하고 수의 가치를 평가합니다.(Rollout, Value Network) 논문에서는 이 과정을 거쳐 2us안에 다음 수를 결정할 수 있다고 설명하고 있습니다.
d. Backup
b와 c과정의 결과값을 합쳐 최종적으로 수를 예측하고 결정합니다.

현재 수준은?

a 그래프는 ELO rating 방식으로 측정한 각각 다른 알파고간의 비교입니다. 각 버전은 한 번 수를 두는데에 약 5초정도가 걸린다고 합니다. 3번째가 판 후이 2단인데, 맨 왼쪽의 AlphaGo distributed(single machine이 아니긴 하지만)보다 낮은 걸 보실 수 있습니다. 지금 대국하고 있는 이세돌 9단과는 승부가 어찌 될지 모르겠으나, 만약 이세돌 9단이 진다면......어후..-_-;;
b 그래프는 몬테 카를로 서치 트리의 각 요소를 다양하게 조합해서 대국했을 때의 ELO 지표입니다. 당연하게도 다 쓰는게 가장 좋게 나옵니다.
c 그래프는 GPU와 연산에 사용하는 스레드의 갯수에 따른 ELO 지표입니다. 저 그래프대로라면 아무리 하드웨어를 늘린다고 해도 수렴하는 지점이 나올 것으로 예상되는데, 어디로 수렴할지는 의견이 갈리는 상황입니다. 구글 딥마인드에서는 더 이상의 CPU나 GPU 추가는 없다고 공언한만큼 결과는 아무도 모르겠지만요.

이외에, 자가 대국 수와 향상되는 실력간의 상관 관계 역시 의문점으로 남아 있습니다. 현재 네이처지에 발표된 알파고 논문에는 해당 내용이 공개되어 있지 않아 어떤 상관 관계가 있을지 개인적으로 궁금한 점입니다.


글쓰면서 일하기 싫어서 대국을 계속 보고 있었는데 이세돌 9단이 결국 패배했네요. 이후의 대국도 지켜봐야겠지만, 구글의 최종목표가 세계 정복이라고 농담삼아 그러는데 진짜일지도 모르겠다는 생각이 듭니다. 다음은 스타1이라는데, 어찌될지 기대도 되구요.

긴 글 읽어주셔서 감사합니다. 최대한 쉽게 풀어썼으나 역시 난해해 보이는데, 틀렸거나 궁금한 점은 말씀해주시면 답변드리겠습니다.

※ 네이처지에 실린 논문 "Mastering the game of Go with deep neural networks and tree search"과 ( http://www.nature.com/nature/journal/v529/n7587/full/nature16961.html ) Shane Moon님의 슬라이드 ( http://www.slideshare.net/ShaneSeungwhanMoon/ss-59226902 ) 를 참조했습니다.