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

핵심 키워드

• AlphaGo
• Nature
• DeepMind
• Monte-Carlo Tree Search
• Policy Network, Value Network

학습하기

 이번에는 AlphaGo에 대해 알아보겠습니다. 'Mastering the game of Go with deep neural networks and tree search'논문을 활용하였습니다. 이세돌과의 경기 후 AlphaGo2가 중국의 커제와 대결했는데 모두 승리했습니다. AlphaGo2에 대한 정보는 나온바가 없지만, 아마 AlphaGO와 크게 다르지 않을 것이라고 생각합니다. DeepMind는 기존에 Reinforce Traing을 통해 게임을 플레이하는 모델을 개발했었습니다. 이후 Google에서 인수하여 굉장히 성장했죠

 사실 해당 논문에서 가장 중요했던 것은 deep learning이 아니었습니다. 메인은 Monte-Carlo Tree Search이고,  이를 정의하기 위한 몇가지 구성 요소 정도로 DL이 사용되었습니다. 그래도 DL이 없었다면 절대 좋은 결과를 얻지 못했을 겁니다. 이 논문의 중요한 것은 DL의 중요한 특징. 많은 데이터셋을 고려할 수 있다 라는 점을 잘 드러냈다는 것입니다. 기존 방법론만으로는 불가능했던 것이 네트워크 구조를 통해 해결되었다는 거죠.

 Complexity of Go, 바둑판은 19X19바둑판에 흑과 백이 번갈아가며 대결하는 형상입니다. 체스가 가능한 모든 경우의 수는 10^123인데비해, 바둑은 무려 10^360으로 훨씬 많습니다. 체스의 경우, 현재 컴퓨터가 모두 고려할 수 있는 수준으로, 절대 사람이 컴퓨터를 이길 수 없지만, 바둑의 경우는 현 우주에 존재하는 원소의 수보다 많은 경우의 수라하며, 컴퓨터도 모든 경우의 수를 탐색하지는 못합니다. AlphaGO2 도 마찬가지로 할 수 없습니다. 

 Monte-Carlo Tree Search, 바둑은 서로 번갈아가는 대국이기에, Tree의 형태로 표현할 수 있고, 여기에 Monte-Carlo가 사용되는 것은, 앞서 말했듯이 모든 경우의 수를 탐색하는 것이 불가능하므로, 상대가 가장 둘법한 수를 필터링하여 나아가기 위함입니다. MCTS에서는 4가지 스텝이 반복됩니다 Selection - Expansion - Simulation - Backpropagation. 상황을 선택하며 앞으로 나아가고, 결과를 확인하고, 피드백하는. Selectin, Expansion, Simulation에서 rule을 만들때 DL이 사용됩니다. 이런 과정에서, AlphaGo의 경우 Rollout policy, Supervised Learning network, Reinforce Learning policy network, Value network를 사용했습니다. 먼저 Rp와 SLn은 사람의 기보를 통해 나오게 됩니다. Rp의 경우 network를 얕게만들어 Simulation 등에서 빠른 결과 도출이 필요할 때 사용했으며, SLn의 경우 조금 더 깊게만들어 착수할 부분에서 사용했습니다. RLpn의 경우에는 사람의 기보와 AlphaGo끼리 대결할 때 수를 가지고 얻어지는 학습입니다. policy는 항상 같습니다. 현재 바둑판 위의 데이터가 들어왔을 때, 다음에는 어디를 둬야하는가. Vn는 조금 다릅니다. 판세를 찾습니다. 현재 바둑판이 얼마나 좋은가 나쁜가 를 판단합니다. simulation을 종료하기위해서는 바둑이 끝나야하고, 그려려면 19x19라는 바둑판이 다 채워져야합니다. 그런데 이는 너무 오래걸리니까, Vn을 통해 판세에 따라 적당히 멈추는 거죠. Rp와 SLpn은 expansion에 활용됩니다. RLpn은 Vn를 학습할 때만 학습됩니다. Vn은 RLpn을 통해 얻어지는 기보로만 학습됩니다. 사람과의 기보만으로 학습된 것이 아닙니다. MCTS는 남과 내가 서로 번갈아가면서 진행되고, 상대가 어디에 둘지 예상하고, 그것을 기준으로 탐색을 진행하는겁니다. 이때는 Rp와 SLpn을 통해 학습하고, Vn은 내 기준으로, 스스로 기준으로 판세를 평가합니다. 이세돌과의 경기에서 이런 해설이 있었습니다. '어 이건 좀 이상한데요' AlphaGo가 두는 좋은 수는 사람의 기준과 다른겁니다. 그래서 Vn을 학습할 때는 AlphaGo끼리 학습했던 내용이 더 중요한 거죠. 생각해보면, 단순히 사람의 기보만으로 AlphaGo가 학습되었다면, 이세돌이 충분히 예상가능한 수만을 계속 두었을 것이고, 그러면 아무리 AlphaGo가 simulation한들, 전체 경우의 수를 탐색할 수 없다는 제약상, 이세돌이 이길 가능성이 더욱 높아졌을 것 같습니다. 다시 한번, selection과 expansion과정에서 SLpn이 사용되고, simulation과 backpropagation과정에서 Rn과 Vn이 사용됩니다.  RLpn은 Vn을 학습할 때만, 사용됩니다. 

 Pn에서는 3x3, 5x5 convolutional filter와 relu, softmax가 사용되었으며, Vn에서는 tanh가 사용되었습니다. tanh는 -1~1사이의 값을 출력하기 때문에 바둑의 형세가 좋고 나쁨을 판단할 때 적절한 거죠.

 재밌는건, 바둑을 예측한다고 단순히 이미지 한 장을 쓴 것이 아니라, 바둑에서 중요한 여러가지 Feature를 사용했다는 것입니다. 잘 모르겠지만, Ladder capture, Liberties 등 여러 Feature가 있었고, 이런 Feature를 사용햇을 때와 안했을 때의 정확도는 약 11.3% 정도가 차이났다고 합니다. 물론 filter의 개수에 따라서도 차이가 있었습니다. 

 Computational Power. Distributed AlphaGo는 40 search threads, 1202 CPUs, 176 GPUs를 활용하고, Policy Net을 학습하기 위해 50 GPU로 하루, Value Net을 학습하기 위해 50 GPU로 한주를 사용했습니다. 이는 최초 모델의 기록으로, 이세돌과 대결했을 당시의 기록은 없습니다.