이전 글 :

지난 글에서 jjune 님께서 다음과 같은 리플을 적어주셨는데 이에 대해서 부연설명이 필요할 것 같습니다.

jjune  16/03/16 11:18 Rollout Policy 는 정책망(Policy Network) 까지는 아닌거 같고
Linear 정책?(단순 Policy 수준) 정도이고 나중에 시뮬레이션시에 활용하는거 같네요
제 추측에는 프로기사들이 중간에 추정계가를 할때 적당히 중간 라인을 그어놓고 추정계가를 하는데... 그런 용도로 사용되는게 아닐까 합니다 

타당한 지적을 해주셨고, 제가 Rollout Policy를 정책망pi 라고 부르면서 인공신경망이라 생각한 것에 대한 변명을 하자면, 첫째 논문의 그림에서 마치 신경망인 것처럼 그려져 있었으며 둘째 fast rollout policy를 train한다는 표현이 세 번 나왔으며, 셋째 fast rollout policy의 표기를 정책망sigma나 정책망rho와 비슷하게 했기 때문입니다. 그러나 사실 어디에도 fast rollout policy가 인공신경망이라는 문구는 없기에 이에 대한 판단은 논문을 좀 더 읽어본 후에 하도록 하겠습니다. 따라서 이번 글에서는 정책망pi라는 표현은 사용하지 않고, fast rollout policy라는 용어를 그대로 사용하겠습니다. 그리고 이번 글을 읽음에 있어서 fast rollout policy는 다음과 같은 특성을 가진다는 사실만 알고 있으면 이해하는데 큰 무리는 없을 것입니다.

1. fast rollout policy는 정책망(policy network)처럼 다음 수에 대한 확률분포를 생성하는 정책이며, 정책망에 비해서 훨씬 빠르고 정확도는 떨어집니다. (정책망과 비교할 때 정확도는 57.0%대 24.2%, 처리시간은 3밀리세컨드대 2마이크로세컨드)
2. fast rollout policy의 입력값은 확률값을 계산하고자 하는 착수점 위치 주변 3*3의 패턴정보와 바로 직전에 움직임이 있었던 위치 주변 12개의 패턴 및 기타 값들이 됩니다. 즉 입력값은 바둑판 전체가 아닌 국소적인 부위에 제한됩니다.

이제 본론으로 들어가겠습니다. 구글이 바둑 인공지능을 딥러닝으로 구현했다는 얘길 들었을 때 그것이 과연 가능한 것인지 의문을 품지 않을 수 없었습니다. 바둑 인공지능은 인공신경망으로 구현하기 매우 까다로운 특징을 갖고 있다고 생각했기 때문입니다. 다음의 사진은 극단적인 예를 보여줍니다. 

눈물점이 본방 때보다 조금 커 보이는 것은 기분 탓입니다. 장서희씨의 사진 여러 장으로 인공신경망을 훈련시킨 후에 위의 그림 두 장을 인공신경망의 입력값으로 사용한다면 출력값은 아마도 거의 동일한 값이 나오게 될 것입니다. (첫번째 글에서 보여드렸던 시노자키 AI 인공신경망에서, ‘약간 일반인스러운 덕후’ 0.1 과 ‘시노자키 아이 스타일의 일반인’ 0.9에 대해서도 0.845 라는 1에 가까운 출력값을 내주었던 것을 기억하시죠?) 사실 인공지능이 아니라 인간이 판단하더라도 동일인물이라고 생각하겠죠. 그러나 바둑에서는 점 하나의 상태로 인해서 그 결과가 매우 달라질 수 있습니다. 돌 하나의 위치로 인해서 큰 집이 살 수도, 죽을 수도 있는 것입니다. 그런데 인공신경망은 바둑판이 비슷한 모습일 때는 비슷한 판단을 내리게 될 것이니 문제가 발생할 것이라 생각한 것입니다.

알파고에서는 이 문제를 여러 가지 방법으로 해결하기 위해 노력한 듯 합니다. 우선 지난번에 설명 드린 대로 입력 값을 단순히 바둑판의 현재 상태만으로 하지 않고, 부가적인 정보를 넣었습니다. 오히려 바둑판의 현재 상태 정보보다 부가적인 정보가 더 많습니다. (바둑판의 현재 상태 정보는 3*19*19 비트, 나머지 45*19*19 비트는 부가적인 정보) 또한 이 입력 값을 그대로 사용하지 않고 나중에 설명드릴 convolution filter를 사용했습니다. 그리고 몬테카를로 트리 탐색 알고리즘으로 수읽기를 구현했습니다. 이제 몬테카를로 트리 탐색에 관해서 설명 드리겠습니다.

수읽기는 게임의 미래 상태를 예상하고 현재 상태에서의 최선의 수를 찾는 것입니다. 바둑뿐이 아니라 거의 모든 게임에는 수읽기가 있습니다. 예를 들어 야구에서도 상대팀이 중요한 순간에 왼손타자를 대타로 낼 것을 미리 예상해서 왼손 투수를 아껴놓는 선택을 했다가 대타가 나온 순간 투입하는 수읽기를 생각해 볼 수 있습니다. 삼목(tick-tack-toe) 같은 간단한 게임에서도 플레이어가 여기에 돌을 두면 상대는 저곳에 두고, 그러면 플레이어는 이곳에 두고 하는 식으로 상대의 반응과 그에 대한 플레이어의 반응, 그리고 그 결과를 예상해 볼 수 있을 것입니다. 알파고는 수읽기를 위해 몬테카를로 트리 탐색 알고리즘을 사용합니다. 이 알고리즘을 이해하기 위해 먼저 몬테카를로 시뮬레이션과 최소-최대(MinMax) 알고리즘부터 알아야 합니다.

위의 그림은 몬테카를로 시뮬레이션으로 원주율을 구하는 것을 보여줍니다. 그림에서 사각형 안의 임의의 위치에 계속 점을 찍었을 때, 어떤 점은 원 안에 들어가고 어떤 점은 원 밖에 존재할 것입니다. 이때 충분히 많은 점을 찍었다면 다음과 같은 공식을 적용할 수 있습니다.

원의 넓이 / 정사각형의 넓이 = 원에 찍힌 점의 수 / 전체 찍힌 점의 수 = 원주율/4
원주율 = (원에 찍힌 점의 수 / 전체 찍힌 점의 수) x 4

이와 같이 무작위 수(Random number)와 확률로 시뮬레이션을 설계하여 복잡한 문제의 해를 근사적으로 구하는 방법을 몬테카를로 시뮬레이션이라고 합니다.

아래의 그림은 삼목(tick-tack-toe) 게임의 게임 트리를 보여줍니다.
 

체스나 장기 등 두 플레이어가 번갈아서 수를 쓰는 게임들은 주로 게임트리 라는 개념을 사용합니다. 게임트리는 각각의 노드가 게임의 한 상태를 의미하며, 각 노드의 자식 노드들은 한 수 이후에 도달할 수 있는 다음 상태들을 의미합니다. 그러한 게임의 컴퓨터 플레이어는 게임트리를 이용해서 다음 수순을 미리 예측하고 가장 유리한 수를 찾습니다.

최소-최대 알고리즘을 설명하기 위해 아래와 같은 게임트리를 생각해보도록 하겠습니다.

위의 게임트리는 4수 앞까지 수읽기를 할 수 있습니다. 원형 노드가 플레이어가 선택하는 차례의 상태이고 정사각형 노드는 상대가 선택하는 차례의 상태입니다. 마지막 노드 안에는 숫자가 적혀있는데, 이 숫자가 높을수록 플레이어에게 유리한 상태입니다. 언뜻 생각해 보았을 때는 4수째에서 플레이어에게 가장 유리한 상태가 +무한대 이므로, 첫 수에서 1번 경로를 택하는 것이 최선의 수 인 것 처럼 보일 수 있습니다. 하지만 그럴 경우 상대방의 입장에서는 두번째 수에서 선택할 수 있는 최선의 수, 곧 플레이어에게는 최악의 수인 4번 경로를 택할 것이고, 결과적으로 플레이어는 -10이라는 매우 안좋은 상태에 빠지게 됩니다. 따라서 상대방도 항상 최선의 수를 추구한다고 가정하고 수읽기를 진행하지 않으면 안됩니다. 

위의 그림은 상대방도 최선의 수를 추구한다고 가정했을 때 선택할 수 있는 최선의 수를 찾아내는 최소-최대 알고리즘을 보여줍니다. 4수를 수읽기 하는 위의 그림에서 마지막 노드는 상대방이 4번째 수에서 선택하게 될 것이므로, 플레이어 입장에서는 최악의 수를 선택하면 됩니다. 이는 10, 5, -10, 5, -무한대, -7 이 되고, 이 값들이 한 단계 상위 노드의 가치가 됩니다. 다시 그 위의 노드는 플레이어의 3번째 수에서 선택되는 것이므로 플레이어 입장에서 최선의 수, 즉 10, -10, 5, -7을 선택하게 되고, 이 값들이 또다시 상위 노드의 가치가 됩니다. 이렇게 반복하여 첫번째 노드로 돌아왔을 때 선택할 수 있는 노드들의 가치는 -10과 -7이 되고, 이중 플레이어 입장에서 더 유리한 값인 -7이 플레이어가 기대할 수 있는 최선의 값이며(물론 상대방도 최선의 수를 택한다고 가정했을 때입니다), 이 값을 가지고 있는 오른쪽 노드를 선택하는 것(첫 번째 그림에서 2번 경로를 택하는 것)이 최소-최대 알고리즘인 것입니다.

아래 동영상은 최소-최대 알고리즘을 보여줍니다.
 

그런데 바둑에서 최소-최대 알고리즘을 사용하면 게임트리가 너무 방대해져서 계산하는 것이 불가능해집니다. 바둑 게임의 평균적 턴 수가 150 정도 이기에 게임트리의 깊이도 약 150정도가 되고, 바둑 규칙을 고려하면 평균적으로 다음 수를 둘 수 있는 경우의 수가 250개 정도이기에 250^150 = 10^360 이상의 노드가 발생할 수 있습니다. 그래서 알파고에서는 최소-최대 알고리즘을 개선한 몬테카를로 트리 탐색 알고리즘을 사용합니다.

몬테카를로 트리 탐색 알고리즘은 다음과 같은 순서로 진행됩니다.

1. 선택 : 현재 게임상태에서 특정 경로로 수읽기를 진행
2. 확장 : 일정 수 이상 수읽기가 진행되면 그 지점에서 한 단계 더 예측(게임 트리의 확장)
3. 시뮬레이션 : 2에서 선택한 노드에서 게임이 종료될 때까지 무작위 방법으로 진행
4. 역전파 : 3의 결과를 종합하여 확장한 노드의 가치를 역전파하여 해당경로의 승산 가능성을 갱신

삼목 같은 간단한 게임의 최소-최대 알고리즘에서는 전체 게임트리(혹은 일정 수까지의 게임트리) 및 최종 말단 노드에서의 상태값(플레이어가 유리한 정도)이 주어졌지만, 체스나 바둑과 같은 프로그램에서는 게임 트리의 노드들을 모두 생성하는 것도, 상태값들을 정확하게 알아내는 것도 어렵습니다. 따라서 처음부터 게임 트리의 폭과 깊이를 모두 확장하지 않고 알고리즘에 따라서 확장해 나가면서 말단 노드까지 나아가고, 말단 노드에서는 몬테카를로 시뮬레이션을 사용하여 게임 종료지점까지 진행한 후의 상태를 예측하는 것입니다.

윗 그림은 알파고의 몬테카를로 트리 탐색 알고리즘을 보여줍니다. 알고리즘은 다음과 같은 순서로 진행됩니다.

1. 최상위 노드에서 Q+u(P) 함수값이 최대가 되는 경로를 따라 수읽기 진행합니다.
2. 말단 노드에 도착했을 때 말단 노드에 대한 방문이 일정 횟수 이상이면 확장하는데 이때 확장된 노드들의 선택 확률 P는 정책망rho로 초기화됩니다.
3. 말단노드, 혹은 확장된 말단노드에서 몬테카를로 시뮬레이션으로 게임의 최종 결과를 계산합니다. 이때 사용되는 것이 fast rollout policy입니다. 원래의 몬테카를로 시뮬레이션이라면 랜덤한 수를 게임 종료지점까지 두게 하여 최종 결과를 알아내는 것을 반복하여 평균적인 승산을 구하겠지만, 알파고에서는 어느 정도는 프로 기사의 착수를 흉내내는 fast rollout policy를 반복적으로 이용하여 최종 결과를 알아내는 것입니다.
4. 3에서 계산한 결과와 말단노드에서의 가치망 출력값, 즉 말단노드에서의 승산을 더해서 Q값을 생성합니다.
5. 4에서 계산된 Q값은 상위 노드로 역전파되어서 각 노드의 Q값을 갱신합니다.
6. 1에서 6까지 절차를 수 차례 반복한 후 가장 방문 횟수가 많은 노드를 선택합니다.

Q는 fast rollout policy와 해당 노드에 대한 가치망의 출력값을 이용하여 계산되고, u(P)는 해당 노드에 대한 정책망rho의 출력값을 이용하여 계산됩니다. 또한 Q와 u(P)를 산출하는 수식은 해당 노드 방문 횟수에 반비례하도록 정의되어 있는데, 이는 트리 탐색의 폭을 제한하지 않기 위해서입니다.

몬테카를로 시뮬레이션 부분을 비유를 들어서 생각해보겠습니다. 프로 9단 두 명이 이틀에 걸쳐서 두는 바둑을 두고 있었는데 첫날 밤 한 명이 사망하였습니다. 첫날 둔 바둑판의 상황만 가지고 누가 얼마나 유리했는지 알아보기 위해서 기력이 비슷한 아마추어 1단 두 명에게 그 상태 그대로 바둑을 두게 하여 결과를 확인합니다. 또 다른 아마추어 1단 두 명에게 바둑을 두게 하여 결과를 확인합니다. 이것을 반복하여 통계를 내어 보면 누가 얼마나 유리했는지 추정할 수 있을 것입니다. 물론 프로 9단과 아마추어 1단의 수읽기는 차원이 다를 것이기에 어느 정도 한계는 있을 수 있겠습니다만, 임의의 위치에 두어서 결과를 추정하는 것보다는 훨씬 나을 것입니다. 스타크래프트로 비유하면 정전록 당시 이제동과 이영호 중 누가 유리했는지 알기 위해 정전되기 직전의 상황을 완벽하게 재현한 세이브 데이터를 만들고, 이 세이브 데이터로 실력이 비슷한 공방 저그 테란 플레이어 두 명에게 반복적으로 게임을 시켜보는 것을 생각해 볼 수 있습니다. 이 비유에서 아마추어 1단은 fast rollout policy를 의미합니다. 처음에 설명 드렸듯이, fast rollout policy는 매우 빠른 대신 정확도는 떨어지는 정책입니다.

이제 알파고가 동작하는 모습이 어느 정도 그려졌을 것입니다. 다음에는 convolution filter 및 기타 대충 넘어간 부분들에 대해서 말해보겠습니다. –꼐속