1탄 : https://gall.dcinside.com/board/view/?id=baduk&no=53252

2탄 : https://gall.dcinside.com/board/view/?id=baduk&no=53254

사실 이 전의 글 까지만 설명한다면 반쪽짜리 설명이다. 이 논문의 핵심은 딥러닝을 통해 학습한 두 네트워크(policy, value)를 어떻게 MCTS에 잘 녹여낼 것인가에 있다. MCTS는 lookahead search 라고 한다. 즉, 미리 해보는 방식의 탐색이라는 뜻이다. (안해보고 예측하는 것이 아니다. 물론 가능성이 높은 경우의 수들만 미리 해본다. 이를 위해 PN 과 VN이 있는 것이다.) 수학시간에 배운 수형도를 떠올려 보자. 뿌리에서부터 경우의 수들이 가지로 뻗어나간다. 탐색이란 이 수형도의 시작부터 끝(시작점을 루트라고 하고 끝을 리프라고 한다. 뿌리와 잎) 까지 진행하며 모든 잎들을 다 탐색해보는 것을 의미한다. 여기까진 당연한 소리이고 이제 알파고에서 사용한 탐색트리를 설명하겠다. 탐색트리에서 각 나뭇가지들은 action value Q(s,a) 를 갖는다. 나뭇가지는 가지(s,a)로 표현하며 이 뜻은 s라는 상태에서 a에 착점하는 것을 의미한다. 아까 policy network에서 P(a|s) 를 떠올려 보면 s라는 상태에서 착점가능한 지점 a의 확률분포라는 의미였다. 여기서 a도 마찬가지 의미로 쓰였다. 예를 들어 우상귀 화점에 흑돌이 있는 상태 s가 있다고 하면 나뭇가지(s, 좌상귀화점에 백 착수) 는 다음 경우의 수인 우상귀 화점에 흑돌, 좌상귀 화점에 백돌이 있는 상태로 연결되는 나뭇가지인 것이다. 또한 이 나뭇가지는 visit count N(s,a)와 prior probability P(s,a)를 갖는다. 즉, 하나의 나뭇가지는 액션 밸류(Q)와 해당 수를 몇번 탐색했는지(N)와 이전 확률(P)을 저장한다.

Q의 용도는 다음 수를 착수하기 위해서 경우의 수 마다 점수를 부여하는 것이라고 생각하면 된다. 즉, Q가 가장 높은 가지로 따라가며 착점하는 것이다. MCTS는 앞서 말했듯이

look-ahead search이기 때문에 Q의 값은 탐색을 통해 정해진다. Q를 정하는 법은 n회에 걸쳐 leaf까지 탐색한 뒤 평가한 값을 탐색 횟수로 나누어 평균 낸 것이다. 즉, Q의 정의 자체에 MCTS가 전제되어 있다. (leaf는 탐색의 최대 깊이까지 도달하는 것을 의미하는데 이는 즉, 몇 수 앞까지 탐색해 보느냐이다. 탐색의 깊이는 미리 정해둔다. 깊이 탐색할수록 시간이 오래 걸리지만 무조건 더 좋은 수를 찾는다고는 단정할 수 없다. 왜냐면 이미 최선의 수를 탐색했고 남은 수들이 그보다 가치가 낮은 수 들일 수 있기 때문이다.) leaf 의 형세를 판단할 때 사용하는 것이 앞서 학습한 value network 이다. 마치 프로기사가 게임 끝나는 수까지 200수앞을 내다보지 않아도 내가 유리하게 끌고갈 수 있는 수인지 아닌지 판단할 수 있는 것과 같은 원리이다.

Q 를 구하는 방법을 좀 더 구체적으로 살펴보자. Q(s, a) 는 n번의 탐색동안 얻어진 V(S leaf)의 평균이다. 즉, 해당 수를 뒀을 때 게임이 평균적으로 가장 유리해졌다는 것을 나타낸다. leaf의 형세판단한 값을 V(S leaf)라고 하자. 이 V값은 사실 서로 다른 2가지 방법으로 구하는데 하나는 앞서 말한 value network에서 현재 상황을 대입하여 나오는 값이고 다른 하나는 policy network로 self-game을 끝까지 진행한 뒤 그 결과로써 V값을 정하는 것이다. V(S leaf)의 값은 이 두 값을 적절한 비율로 더한 값으로 한다. Q는 실험적으로 두 값을 50%씩 더했을 때 가장 강력했다고 한다.(모든 다른 비율의 조합에 대해 95% 이상의 승률을 보여줌). 이유는 뉴럴 네트워크는 수가 많이 진행된 상태일 수록 가치판단 능력이 사람과 가까워지기 때문이다.

다음 수를 정할 때 action value Q(s, a)말고도 하나 더 고려하는 것이 있는데 가중치 u 가 그것이다. u(s, a) 는 prior probability 인 P(s, a)의 값을 N(s,a)+1 로 나눈 것으로써  P(s, a) 는 앞서 학습한 policy network의 p(a|s)의 값을 갖도록 한다. 즉, 다음 수를 정할 때 Q(a, s) + u(a, s) 가 최대가 되는 수를 고르는 것이다. 이때 가중치가 하는 역할은 기본적으로 아예 말이 안되는 수 들을 policy network를 통해 걸러 낼 수 있다는 것이며 대신 해당 나뭇가지를 탐색한 횟수 N(s, a)로 나눔으로써 그 점을 여러번 시뮬레이션(탐색) 할수록 원래의 가중치가 희석되도록 했다는 것이다. 즉, 탐색을 많이 할수록 MCTS의 영향력이 커진다.

요약.

1. 딥러닝은 사람처럼 어떤 수에 대한 가치를 경기를 끝까지 해보지 않고도 판단할 수 있도록 해 준다.

2. 수에 대한 가치판단 능력은 사람보다 떨어지지만(컴퓨터의 인공신경망 자체로는 논문 게제 당시 프로선수들이 두는 수의 57%밖에 예측하지 못했다.) 

컴퓨터의 장점인 엄청난 계산속도를 활용하여 몬테카를로 트리 써치 알고리즘과 결합함으로써 그 단점을 극복한다. 이것이 가능한 이유는 탐색의 깊이가 깊어질수록 뉴럴 네트워크가 사람과 가깝게 수의 가치판단이 가능하기 때문이다.

3. 후반으로 갈수록 경우의 수가 줄어들고 따라서 탐색공간이 줄어듦으로 MCTS알고리즘의 능력이 극대화된다. 단적인 예로써 9x9 바둑은 기존의 MCTS만 사용하는 프로그램에게 프로가 진 적이 있다.

딥러닝을 확률놀이라고 생각하는 분이 있어 내용을 추가한다. 파트 1에 추가했으나 요약만 보는 사람들이 있어 이곳에 중복추가 하였다.

(앞부분 생략) 마찬가지로 바둑에서도 각종 행마법과 정석과 같은 패턴이 존재한다. 대마잡이도 일정한 패턴(사람은 인식하지 못하는)이 존재 한다고 유추해 볼 수 있다. 왜냐면 2집을 못 나게 하기 위한 목적을 가지고 돌을 두기 때문이다. 사람이 의식하는 일종의 "목적"이 은연중에 패턴으로 표현된다고 생각해보면 바둑 프로기사들은 자신도 모르게 어떤 패턴으로써 돌을 두고 있는 것이다. 우리는 이 패턴을 기풍이라고 표현하기도 하고 격언, 정석 등 다양한 종류의 언어로 표현한다. 그러나 이것들은 모두 컴퓨터에게는 "패턴" 이라는 하나의 공통된 개념으로 다룰 수 있다. 물론 패턴만으로 돌을 두는 것은 아니다. 때문에 Deep learning 만으로는 한계가 있다. (몬테카를로 트리 탐색 알고리즘이 필요한 이유이다) (뒷부분 생략)

알파고가 얼마나 사람과 비슷하게 동작하는가를 더 잘 느끼기 위해선 이렇게 생각해보면 된다. 인간은 단지 뉴럴 네트워크가 컴퓨터보다 성능이 압도적으로 우수하기 때문에 탐색의 너비와 깊이가 컴퓨터에 비해 매우 좁음에도 불구하고 좋은 수를 둘 수 있고 컴퓨터는 그 반대이다.