몬테카를로 트리 서치 (Monte Carlo Tree Search)에 대한 정확한 정리

※해당 포스팅은 제 네이버 블로그 https://blog.naver.com/gusals1620/222497438773에서도 확인하실 수 있습니다.


알파고를 통해 AI가 크게 화제가 되면서, 알파고에 사용된 몬테카를로 트리 서치 알고리즘도 화제가 되었습니다.

대학원 세미나를 준비하면서 많은 정보를 보았는데, 한글로 된 정보 중에는 깊은 내용을 다루고 있는 것은 없어서 아쉬움이 있었습니다.

그래서 무료 강의, 논문, 책을 통해 직접 조사를 거쳐 정리해보았습니다.

우선 몬테카를로 트리 서치(Monte Carlo Tree Search, 이하 MCTS)는 MDP(Markov Decision Process)를 해결하는 방법의 한 종류입니다.

출처 : 본인

알파고 덕분에 강화학습이 유명해져서, "강화학습은 MDP를 푸는 방법이다"라는 말을 많이 접하는데요.

맞는 말입니다. 하지만 MDP를 푸는 방법으로는 강화학습 외에도 이렇게 많은 방법들이 있습니다.

Model을 알고 있는 상태(Model based)에서는 Planning
Model을 모르고 있는 상태(Model free)에서는 Learning을 통해 MDP를 해결하는데요.

여기서 Model을 모르는 상태에서 사용하는 방법인 Learning이 바로 Reinforcement Learning, 즉 강화학습입니다.

MCTS는 Tree search 방법들 중 하나에 해당합니다. MCTS 외에도 Minmax tree search 등이 있습니다.

Tree search 알고리즘은 주로 게임에 사용되었습니다. 틱택토 게임을 예로 들면, 현재 상황에서 가능한 모든 경우의 수들을 tree 형태로 뻗어나가며 좋은 수인지 판단한 후 가장 좋은 수를 선택합니다.

하지만 경우의 수가 매우 많은 체스, 바둑 등의 게임에는 모든 경우의 수를 탐색하는 것이 거의 불가능합니다. 이 한계를 극복하기 위한 tree search 알고리즘이 바로 Monte Carlo tree search가 되겠습니다.

출처 : 본인

확률 계산 알고리즘인 Monte Carlo는 많이들 아시다시피 정확한 확률 분포를 구하기 어려울 때 무작위 표본 추출을 통해 확률 분포를 도출하는 것으로써 통계열역학으로부터 만들어진 방법론입니다.

MCTS는 tree search에 Monte Carlo 알고리즘을 응용한 것으로, 어떤 상태에서 게임이 종료될 때까지 모든 경우의 수를 탐색하지 않고, Monte Carlo 기반 시뮬레이션을 통해 랜덤한 수를 두어가면서 게임을 한번 끝까지 진행해봅니다.

이 과정을 충분히 많이 반복하다 보면, 현재 상태가 게임 승리에 얼마나 도움이 되는 수인지 판단할 수 있을 것입니다. '충분히 많이' 반복하더라도 모든 경우의 수를 다 탐색하는 것보다는 훨씬 계산량이 적을 것입니다.


이제 MCTS에서 많이 사용되는 용어를 바둑 게임을 진행하는 그림과 함께 보겠습니다.

출처 : 오츠키 토모시, 정인식 역, 알파고를 분석하며 배우는 인공지능, 제이펍, 2019  & http://www.kocw.net/home/search/kemView.do?kemId=1367683

우선 첫 번째 국면, 즉 트리가 시작되는 맨 위의 노드를 루트 노드라고 합니다.

그리고 트리에서 가장 밑에 있는 node를 leaf node라 하는데, 지금은 트리가 한 번만 확장되었으므로 3개의 child node가 모두 leaf node가 됩니다. Child node가 한 개도 없는 노드를 leaf node로 이해하셔도 좋을 것 같습니다.

알파고의 경우 각 child node가 서로 다른 바둑의 국면을 나타냅니다. (국면은 게임 판의 상태를 뜻합니다.)

즉 위의 그림은 루트 노드와 세 가지의 child node가 생성된 상황을 나타냅니다.

앞서 MCTS는 게임을 임의로 한번 끝까지 진행해본다 했는데, 이때 진행되는 게임을 플레이아웃이라 합니다. 반드시 기억하셔야 되는 용어입니다.

플레이아웃은 한 leaf node가 만들어질 때, 즉 새로운 국면이 만들어졌을 때 실행됩니다. 새로운 국면이 만들어졌다는 것은 한 수를 뒀다는 것인데, 이 수가 얼마나 좋은 수인지 확인하기 위해 임의로 게임을 해보는 것이죠.
승패가 가려져서 플레이아웃이 끝나는 마지막 상태가 그림의 맨 아래의 terminal state입니다.

플레이아웃은 빠르게 수행되어야 하므로 게임의 수를 둘 때 수행 시간이 오래 걸리지 않는 규칙(정책)이 사용되는데, 이 규칙(정책)을 MCTS의 rollout policy 또는 default policy라 합니다. Default policy도 꼭 기억하시길 바랍니다.

Leaf node와 terminal state를 헷갈리지 않게 주의하시길 바랍니다. Terminal state는 임의로 진행된 게임의 마지막 상태이지, 트리로 형성된 node가 아닙니다

Tree policy로는 UCT(Upper Confidence Boundary of Tree)가 사용되었다고 하는데, MCTS에서 가장 중요한 것이 되겠습니다. Tree policy는 어디에 쓰이는 정책인지, 또 UCT는 무엇인지에 대한 내용은 자연스러운 흐름을 위해 조금 뒤에 설명하도록 하겠습니다.


이쯤에서 MCTS의 네 단계를 확인해보겠습니다. 아래 그림은 MCTS 관련 자료를 찾아보시면 흔히 볼 수 있는 그림입니다.

출처 : C. B. Browne et al., "A Survey of Monte Carlo Tree Search Methods," in IEEE Transactions on Computational Intelligence and AI in Games, vol. 4, no. 1, pp. 1-43, March 2012

1. 선택(Selection) : 위에서 설명한대로 child node를 만들 node를 고르는 단계입니다. 반드시 leaf node일 필요는 없습니다. Leaf node인 경우도 있고, 아닌 경우도 있습니다. 그리고 선택된 노드가 완전 확장 노드이면 선택이 한 번 더 일어나는데, 아래 그림과 그림의 설명을 보시면 이해가 쉬우실 것입니다.

2. 확장(Expansion) : child node를 생성하여 트리를 확장합니다. 확장된 직후에는 이 child node가 leaf node가 되겠죠.

3. 시뮬레이션(Simulation) : Leaf node에서 게임이 종료될 때까지 플레이아웃을 시뮬레이션합니다.

4. 역전파(Backpropagation) : 선택된 leaf node에 시뮬레이션 결과를 반영합니다.

잘보면 앞서 말씀드린대로 확장 단계에서 한 leaf node가 만들어진 후 바로 플레이아웃이 실행됩니다. 그리고 플레이아웃을 통해 승패가 가려졌으므로 역전파 단계를 통해 확장된 leaf node와 그것의 상위 노드에 기록된 승률을 업데이트 해줍니다.

하나 더 여기서 주의할 점이, 위의 네 단계가 항상 순서대로 이루어지는 것이 아니라는 것입니다.

빠른 이해를 위해 트리가 확장되는 과정을 맨 처음부터 보여드리겠습니다.

출처 : 본인

우선 매 확장 단계마다 leaf node가 만들어지면 바로 시뮬레이션(플레이아웃이 실행되는 단계)-역전파 단계가 이어지는데 그림에서는 생략했습니다. 이 점 주의하시길 바랍니다.

처음에는 루트 노드밖에 없으므로 child node가 없습니다. 그래서 확장을 여러 번 해줍니다.

만약 확장할 수 있는 경우의 수가 총 3개인데 child node가 3개가 다 만들어졌다면, 루트 노드는 완전 확장 노드가 됩니다. 완전 확장 노드에서는 확장을 이어 나갈 child node 중 하나를 선택합니다.

선택후에는 선택된 노드에서 확장이 일어납니다. 선택 뒤에는 시뮬레이션-역전파 단계가 따르지 않습니다. 선택된 노드에서 확장이 일어난 후에 시뮬레이션-역전파 단계가 진행되는 것입니다.

그리고 또 주의할 점이 확장-시뮬레이션-역전파 단계가 끝나면 다시 맨 위의 루트 노드에서부터 시작합니다. 그래서 (6)번 과정의 확장-시뮬레이션-역전파 단계 후 다시 루트 노드로 돌아가고 다시 한 번 선택 단계를 거칩니다.

비슷한 과정을 반복하다 보면, (12)번 과정에서 루트 노드의 한 child node도 완전 확장 노드가 됩니다. 다시 한 번 이 완전 확장된 child node가 선택되는 (15)번 과정에서는 이것의 child node들 중에서 한 node를 또 선택해야 합니다. 즉 선택이 여러 번 연속 일어날 수도 있게 되는 것입니다.

 

그리고 제가 위에서 선택되는 node는 반드시 leaf node일 필요는 없다고 했는데, 그림에서 보시다시피 (5)번, (7)번, (16)번의 경우는 트리 맨 아래에 있는 leaf node 중 하나가 선택되었지만, (9)번, (11)번, (13)번, (15)번의 경우는 leaf node가 선택되지 않았습니다.

---------------------------------------------------------------------------------------------------

이번에는 다시 돌아와서 가장 중요한 tree policy에 대해 알아보겠습니다.

Tree policy는 선택 단계에서 확장을 이어 나가기 위해 선택할 child node를 정할 때 사용하는 정책입니다.

child node를 선택할 때 아무 node나 고르는 것이 아니고 적절한 tree policy에 따라 선택을 해야 합니다.

위의 그림을 보면, 루트 노드의 맨 오른쪽 세 번째 child node는 한 번도 선택이 되지 않습니다. 맨 왼쪽 node만 계속 선택받으면서 확장이 되는데, 당장은 플레이아웃 했을 때 이 왼쪽 node의 승률이 높기 때문에 계속 선택되는 것입니다.

그런데 게임이 그리 쉬운 것이 아니죠. 수를 많이 내다보면 안 좋은 수일 수도 있습니다. 그리고 선택 받지 못한 맨 오른쪽 child node가 오히려 뒤로 가면 좋은 수일 수도 있죠.

그래서 선택을 할 때는 당장 승률이 좋은 수를 나타내는 node만 계속 선택해서 이용(exploitation)하지 않고, 당장 승률이 좋지 않은 수도 위험을 무릅쓰고 그 수에 대해 탐사(exploration)해 볼 필요가 있습니다. 이를 이용-탐사 딜레마(exploitation-exploration dilemma)라고 합니다.

알파고의 경우 exploitation과 exploration의 균형을 맞추기 위해 tree policy로 UCT(Upper Confidence Boundary of Tree)가 사용되었습니다.

UCT는 UCB1(Upper Confidence Boundary)이 tree에 사용되었다고 해서 붙은 이름입니다. 확장을 이어 나갈 child node를 선택할 때는 UCT 값이 높은 node를 선택합니다.

글이 너무 길어져서 UCT와 UCB1에 대해서는 다음 포스팅에서 자세히 다루겠습니다.




긴 글 읽어 주셔서 감사합니다. 많은 분들에게 도움이 되었으면 좋겠습니다.