몬테카를로 트리 탐색(MCTS)

mcts

Monte Carlo Tree Search, 즉 MCTS는 가능한 선택지가 매우 많아서 모든 경우의 수를 끝까지 계산하기 어려운 문제에서, 제한된 계산 자원 안에서 가장 유망한 선택을 찾아내기 위한 탐색 알고리즘입니다. 특히 바둑, 체스, 장기, 게임 AI, 로봇 계획, 의사결정 문제처럼 현재 선택이 미래의 결과에 영향을 미치는 순차적 의사결정 문제에서 널리 사용됩니다.

MCTS의 핵심 아이디어는 모든 선택지를 똑같이 탐색하지 않는다는 점입니다. 처음에는 여러 가능성을 넓게 살펴보되, 시뮬레이션 결과가 좋게 나온 선택지에는 더 많은 계산 자원을 배정합니다. 즉, 이미 좋아 보이는 선택을 더 깊게 확인하는 활용(exploitation)과, 아직 충분히 확인하지 않은 선택지를 시험해보는 탐색(exploration) 사이의 균형을 맞추는 것이 MCTS의 핵심입니다.

MCTS는 이름 그대로 몬테카를로 방식, 즉 무작위 시뮬레이션을 활용합니다. 특정 상태에서 임의의 방식으로 여러 번 미래 전개를 시뮬레이션하고, 그 결과를 바탕으로 각 선택지의 가치를 추정합니다. 이때 탐색 결과는 트리 구조로 누적되며, 시뮬레이션이 반복될수록 유망한 경로에 대한 평가가 점점 정교해집니다.

MCTS의 역사적 배경

MCTS는 2000년대 중반 이후 인공지능 분야에서 본격적으로 주목받기 시작했습니다. 이전의 게임 AI는 체스처럼 비교적 명확한 평가 함수를 만들 수 있는 게임에서는 강한 성능을 보였지만, 바둑처럼 가능한 수가 매우 많고 국면 평가가 어려운 게임에서는 한계가 컸습니다.

2006년 Rémi Coulom은 Monte Carlo Tree Search라는 용어와 아이디어를 정리하고, 이를 바둑 프로그램에 적용했습니다. 비슷한 시기에 UCT(Upper Confidence Bound applied to Trees) 방식이 제안되면서 MCTS는 탐색과 활용의 균형을 체계적으로 조절할 수 있는 알고리즘으로 발전했습니다. 이후 Crazy Stone, MoGo 같은 바둑 프로그램들이 MCTS를 활용해 기존 방식보다 뛰어난 성과를 보이면서 MCTS는 바둑 AI의 핵심 기술로 자리 잡았습니다.

2016년 Google DeepMind의 AlphaGo가 이세돌 9단을 상대로 승리하면서 MCTS는 대중적으로도 널리 알려졌습니다. 다만 AlphaGo의 성능은 MCTS만의 결과라기보다는, 딥러닝 기반 정책망과 가치망, 그리고 MCTS가 결합된 결과라고 보는 것이 정확합니다. 딥러닝 모델은 어떤 수가 유망한지와 특정 국면의 승률이 어느 정도인지 예측하고, MCTS는 그 예측을 바탕으로 실제 후보 수들을 더 체계적으로 탐색했습니다.

강화학습과 MCTS의 관계

강화학습은 에이전트가 환경과 상호작용하면서 보상을 최대화하는 행동 전략, 즉 정책(policy)을 학습하는 분야입니다. MCTS는 강화학습에서 특정 상태에 주어졌을 때 어떤 행동을 선택할지 계산하는 탐색 방법으로 활용될 수 있습니다.

강화학습에서 정책은 “이 상태에서는 어떤 행동을 해야 하는가?”에 대한 답을 제공합니다. 반면 MCTS는 현재 상태를 출발점으로 하여 여러 가능한 미래를 시뮬레이션하고, 그 결과를 바탕으로 지금 선택해야 할 행동을 결정합니다. 따라서 MCTS는 학습된 정책을 그대로 따르는 방식이 아니라, 현재 상황에서 추가적인 계산을 수행하여 더 나은 결정을 내리는 방식이라고 볼 수 있습니다.

AlphaGo와 AlphaZero 계열의 시스템에서는 이 관계가 특히 잘 드러납니다. 신경망은 특정 상태에서 유망한 행동과 상태 가치를 예측하고, MCTS는 그 예측을 이용해 탐색을 수행합니다. 탐색 결과는 다시 더 좋은 학습 데이터가 되어 신경망을 개선하는 데 사용됩니다. 이처럼 MCTS와 강화학습은 서로 보완적인 관계를 가질 수 있습니다.

MCTS의 작동 원리

탐색 트리 구조와 노드 정의

MCTS는 현재 상태를 루트 노드(root node)로 하는 탐색 트리를 구성합니다. 트리의 각 노드는 게임이나 의사결정 문제의 특정 상태를 의미하고, 간선(edge)은 그 상태에서 선택할 수 있는 행동을 의미합니다. 예를 들어 바둑에서는 노드가 현재 바둑판의 상태이고, 간선은 다음에 둘 수 있는 착점입니다.

각 노드에는 보통 다음과 같은 정보가 저장됩니다. 첫째, 해당 노드가 몇 번 방문되었는지를 나타내는 방문 횟수입니다. 둘째, 그 노드에서 시작한 시뮬레이션의 누적 보상 또는 승리 횟수입니다. 셋째, 누적 결과를 방문 횟수로 나눈 평균 가치입니다. MCTS는 이 정보를 이용해 다음에 어떤 노드를 탐색할지 결정합니다.

네 가지 주요 단계 설명

MCTS는 일반적으로 선택, 확장, 시뮬레이션, 역전파의 네 단계를 반복합니다.

선택(Selection) 선택 단계에서는 루트 노드에서 시작하여, 이미 만들어진 자식 노드들 중 하나를 반복적으로 선택하며 아래로 내려갑니다. 이때 단순히 현재 승률이 가장 높은 노드만 고르면 아직 충분히 탐색하지 않은 선택지를 놓칠 수 있습니다. 반대로 모든 선택지를 무작정 고르게 탐색하면 유망한 선택지에 충분한 계산을 집중하기 어렵습니다. 따라서 선택 단계에서는 탐색과 활용의 균형을 맞추는 기준이 필요합니다.
확장(Expansion) 선택 과정을 통해 도달한 노드가 아직 모든 가능한 행동을 자식 노드로 가지고 있지 않다면, 그중 하나 이상의 행동을 선택하여 새로운 자식 노드를 추가합니다. 이 단계에서 탐색 트리는 점점 넓어집니다. 즉, MCTS는 처음부터 전체 트리를 만드는 것이 아니라, 시뮬레이션을 반복하면서 필요한 부분만 점진적으로 확장합니다.
시뮬레이션(Simulation 또는 Rollout) 새롭게 확장된 노드에서 시작하여 게임이나 의사결정 과정의 끝까지 가상의 진행을 수행합니다. 전통적인 MCTS에서는 이 과정이 무작위 행동을 통해 이루어졌기 때문에 플레이아웃(playout)이라고도 불립니다. 예를 들어 게임에서는 무작위로 수를 두면서 승패가 결정될 때까지 진행하고, 그 결과를 보상으로 사용합니다. 현대적인 MCTS에서는 완전히 무작위로 진행하기보다 휴리스틱, 정책 모델, 가치 모델 등을 사용하여 더 현실적인 시뮬레이션을 수행하기도 합니다.
역전파(Backpropagation) 시뮬레이션 결과가 나오면, 그 결과를 방금 지나온 경로의 모든 노드에 반영합니다. 예를 들어 시뮬레이션 결과가 승리라면 해당 경로의 노드들의 승리 횟수 또는 누적 보상을 증가시키고, 방문 횟수도 함께 증가시킵니다. 이 과정이 반복되면 각 노드의 평균 가치가 점점 안정적으로 추정됩니다.

UCT와 탐색-활용 균형

MCTS에서 가장 널리 알려진 선택 기준 중 하나는 UCT입니다. UCT는 각 자식 노드를 선택할 때 다음과 같은 형태의 점수를 사용합니다.

U C T_{i} = \overset{ˉ}{X}_{i} + C \frac{ln N}{n _{i}}

여기서 $\overset{ˉ}{X}_{i}$ 는 i번째 자식 노드의 평균 보상, $n_{i}$ 는 해당 자식 노드의 방문 횟수, $N$ 은 부모 노드의 방문 횟수, $C$ 는 탐색의 강도를 조절하는 상수입니다.

첫 번째 항인 $\overset{ˉ}{X}_{i}$ 는 지금까지 결과가 좋았던 노드를 더 선택하게 만드는 활용 요소입니다. 두 번째 항은 방문 횟수가 적은 노드에 보너스를 주는 탐색 요소입니다. 따라서 UCT는 성과가 좋아 보이는 선택지를 더 살펴보면서도, 아직 충분히 검토되지 않은 선택지도 일정 수준 탐색하도록 만듭니다.

알고리즘의 진행 과정 예시

예를 들어 체스에서 현재 가능한 수가 여러 개 있다고 가정해봅시다. MCTS는 처음에는 여러 수를 조금씩 시험해봅니다. 어떤 수를 둔 뒤 가상의 게임을 끝까지 진행해보고, 그 결과가 좋으면 해당 수의 평가가 올라갑니다. 이후 반복 과정에서는 평가가 높은 수를 더 자주 탐색하지만, 아직 방문 횟수가 적은 다른 수들도 완전히 배제하지 않습니다.

이 과정을 수천 번 또는 수만 번 반복하면, 각 후보 수에 대해 “이 수를 두었을 때 이후 전개가 얼마나 유리했는가?”에 대한 경험적 추정치가 쌓입니다. 최종적으로는 루트 노드의 자식들 중 방문 횟수가 가장 많거나 평균 가치가 가장 높은 행동을 선택합니다. 실제 구현에서는 평균 가치가 높은 수보다 방문 횟수가 가장 많은 수를 최종 선택으로 사용하는 경우도 많습니다. 방문 횟수는 탐색 과정 전체에서 어느 선택지가 가장 일관되게 유망했는지를 반영하기 때문입니다.

MCTS의 응용

보드 게임에서의 활용 예시

MCTS는 바둑에서 특히 큰 성공을 거두었습니다. 바둑은 가능한 수가 매우 많고, 중간 국면의 가치를 정확히 평가하기 어렵기 때문에 전통적인 탐색 알고리즘으로는 좋은 성능을 내기 어려웠습니다. MCTS는 무작위 시뮬레이션과 점진적 트리 확장을 통해 이러한 문제를 완화했습니다.

체스나 장기처럼 평가 함수가 비교적 잘 발달한 게임에서도 MCTS는 활용될 수 있습니다. 다만 체스에서는 오랫동안 미니맥스 탐색과 알파-베타 가지치기가 강력한 성능을 보여왔기 때문에, MCTS는 바둑에서만큼 절대적인 위치를 차지하지는 않았습니다. 최근에는 신경망 평가 함수와 결합된 MCTS가 다양한 보드 게임에서 사용되고 있습니다.

비디오 게임과 전략 시뮬레이션에서의 활용

MCTS는 보드 게임뿐 아니라 실시간 전략 게임, 턴제 전략 게임, 퍼즐 게임, 일반 게임 AI에도 적용될 수 있습니다. 게임 환경에서는 가능한 행동이 많고, 미래 상태가 복잡하게 전개되는 경우가 많기 때문에 MCTS가 유용합니다.

특히 NPC의 의사결정, 전투 전략 선택, 자원 배분, 경로 선택, 시나리오 분기 탐색 등에서 MCTS를 활용할 수 있습니다. 다만 실시간 게임에서는 계산 시간이 제한되어 있기 때문에, 제한 시간 안에서 충분히 좋은 결정을 내릴 수 있도록 탐색 깊이와 반복 횟수를 조절해야 합니다.

비게임 분야에서의 활용

MCTS는 순차적 의사결정 구조를 가진 여러 비게임 문제에도 적용됩니다. 예를 들어 로봇 공학에서는 로봇이 장애물을 피하면서 목표 지점까지 이동하기 위한 행동 계획을 세우는 데 사용할 수 있습니다. 자율주행이나 드론 경로 계획에서도 여러 가능한 행동 경로를 시뮬레이션하고, 위험과 효율성을 비교하는 방식으로 활용될 수 있습니다.

의사결정 지원 시스템에서도 MCTS는 잠재력이 있습니다. 재난 대응 계획, 물류 경로 최적화, 생산 스케줄링, 재무 계획, 의료 치료 전략 수립처럼 현재의 선택이 이후 결과에 연쇄적으로 영향을 주는 문제에서 MCTS는 여러 가능한 미래 시나리오를 비교하는 도구로 사용될 수 있습니다.

다만 현실 문제에서는 게임과 달리 상태 전이 규칙이 명확하지 않거나, 시뮬레이션 모델 자체가 부정확할 수 있습니다. 따라서 비게임 분야에서 MCTS를 적용하려면 좋은 환경 모델, 현실적인 보상 설계, 계산 비용 관리가 함께 필요합니다.

최근 연구 동향 및 혁신적인 응용 사례

최근 MCTS는 딥러닝과 결합되는 방향으로 발전하고 있습니다. 전통적인 MCTS는 무작위 시뮬레이션에 크게 의존했지만, 무작위 시뮬레이션은 복잡한 문제에서 부정확하거나 비효율적일 수 있습니다. 이를 보완하기 위해 신경망을 사용하여 어떤 행동이 유망한지 예측하거나, 특정 상태의 가치를 직접 추정하는 방식이 사용됩니다.

AlphaGo, AlphaZero, MuZero 계열의 접근은 이러한 흐름을 대표합니다. AlphaZero는 사전 인간 기보 없이 자기대국을 통해 정책과 가치 함수를 학습하고, MCTS를 통해 더 강한 수를 탐색했습니다. MuZero는 환경의 규칙을 명시적으로 알지 못하더라도 내부 모델을 학습하여 계획을 수행하는 방향으로 확장되었습니다.

이러한 연구 흐름은 MCTS가 단순한 게임 탐색 알고리즘을 넘어, 학습된 모델과 결합된 계획(planning) 알고리즘으로 확장될 수 있음을 보여줍니다.

MCTS 알고리즘의 변형

UCT

UCT는 MCTS의 대표적인 변형이자 선택 전략입니다. UCT는 멀티암드 밴딧 문제에서 사용되는 UCB1 원리를 트리 탐색에 적용한 것입니다. 각 노드에서 평균 보상이 높은 행동을 선택하면서도, 방문 횟수가 적은 행동에 탐색 보너스를 부여합니다.

UCT의 장점은 별도의 정교한 평가 함수 없이도 탐색과 활용의 균형을 수학적으로 조절할 수 있다는 점입니다. 그러나 탐색 상수 (C)의 값에 따라 성능이 달라질 수 있고, 문제 특성에 맞는 조정이 필요할 수 있습니다.

PUCT

AlphaGo 계열에서 사용된 방식은 UCT를 확장한 PUCT 계열의 선택 전략입니다. PUCT는 신경망이 예측한 정책 확률을 활용하여, 더 유망하다고 예측된 행동을 우선적으로 탐색하게 만듭니다. 즉, 모든 행동을 동일한 출발점에서 보는 것이 아니라, 학습된 정책 모델이 추천하는 행동에 더 높은 우선순위를 부여합니다.

이 방식은 가능한 행동 수가 매우 많은 문제에서 특히 유용합니다. 바둑처럼 후보 수가 많을 때, 신경망이 유망한 후보를 좁혀주고 MCTS가 그 후보들을 더 깊게 검토하는 방식으로 계산 효율을 높일 수 있습니다.

휴리스틱 기반 MCTS

문제에 대한 사전 지식이 있는 경우, 시뮬레이션 단계나 확장 단계에 휴리스틱을 넣을 수 있습니다. 예를 들어 게임에서는 완전히 무작위로 수를 두는 대신, 일반적으로 좋은 수로 알려진 패턴을 우선 고려할 수 있습니다. 로봇 경로 계획에서는 충돌 위험이 낮은 방향을 우선 탐색하도록 만들 수 있습니다.

휴리스틱을 사용하면 탐색 효율이 높아질 수 있지만, 잘못된 휴리스틱은 오히려 특정 선택지에 편향을 만들어 좋은 해를 놓치게 할 수 있습니다. 따라서 휴리스틱은 문제 구조를 잘 반영해야 하며, 탐색 다양성을 지나치게 줄이지 않도록 주의해야 합니다.

병렬 MCTS

MCTS는 많은 반복 시뮬레이션을 수행하므로 병렬화와 잘 맞는 측면이 있습니다. 여러 CPU나 GPU 자원을 사용해 동시에 여러 시뮬레이션을 수행하면 제한 시간 안에 더 많은 탐색을 할 수 있습니다.

다만 병렬화에는 동기화 문제가 따릅니다. 여러 프로세스가 같은 트리를 동시에 업데이트할 경우 충돌이 발생할 수 있고, 중복 탐색이 늘어날 수 있습니다. 이를 해결하기 위해 루트 병렬화, 트리 병렬화, 리프 병렬화 등 다양한 병렬화 방식이 사용됩니다.

MCTS의 도전 과제 및 한계점

계산 복잡성과 자원 소모 문제

MCTS는 전체 탐색 공간을 모두 살펴보지 않는다는 장점이 있지만, 여전히 많은 시뮬레이션을 필요로 합니다. 상태 공간이 매우 크거나, 한 번의 시뮬레이션 비용이 비싼 문제에서는 계산 비용이 큰 부담이 됩니다. 특히 실시간 의사결정이 필요한 환경에서는 제한 시간 안에 충분한 탐색을 수행하기 어렵습니다.

시뮬레이션 품질 문제

MCTS의 성능은 시뮬레이션의 품질에 크게 영향을 받습니다. 무작위 시뮬레이션이 실제 좋은 전략과 동떨어져 있다면, 그 결과를 기반으로 한 가치 추정도 부정확해질 수 있습니다. 바둑이나 체스 같은 복잡한 게임에서 완전 무작위 플레이아웃이 한계를 보이는 이유도 여기에 있습니다.

이 문제를 해결하기 위해 현대적인 MCTS는 정책 모델, 가치 모델, 휴리스틱 평가 함수를 함께 사용합니다. 즉, 단순한 무작위 시뮬레이션 대신 학습된 지식을 활용해 더 정확하고 효율적인 평가를 수행합니다.

보상 설계의 어려움

MCTS는 시뮬레이션 결과를 보상으로 환산하여 노드 가치를 업데이트합니다. 게임처럼 승리와 패배가 명확한 문제에서는 보상을 정의하기 쉽지만, 현실 문제에서는 무엇을 좋은 결과로 볼 것인지가 모호할 수 있습니다. 예를 들어 의료 의사결정에서는 치료 효과, 부작용, 비용, 환자의 선호를 함께 고려해야 하고, 재난 대응에서는 인명 피해, 시간, 자원, 위험도를 함께 평가해야 합니다.

보상이 잘못 설계되면 MCTS는 계산상으로는 최적처럼 보이지만 실제로는 바람직하지 않은 결정을 추천할 수 있습니다.

불확실한 환경과 부분 관측 문제

전통적인 MCTS는 현재 상태와 가능한 행동, 그리고 행동 이후의 상태 전이가 비교적 명확하다고 가정합니다. 그러나 현실에서는 환경이 불확실하거나, 현재 상태를 완전히 관측할 수 없는 경우가 많습니다. 예를 들어 상대의 의도, 숨겨진 정보, 미래의 외부 변수 등을 모두 알 수 없는 상황에서는 일반적인 MCTS만으로는 충분하지 않을 수 있습니다.

이러한 문제를 다루기 위해서는 확률적 상태 전이, 베이지안 추론, 부분 관측 마르코프 의사결정 과정(POMDP), belief state 기반 탐색 등과 결합된 확장 방식이 필요합니다.

대규모 상태 공간을 가진 문제에 대한 처리

대규모 상태 공간에서는 가능한 행동과 미래 상태가 기하급수적으로 증가합니다. MCTS는 전체 공간을 완전 탐색하지 않기 때문에 이러한 문제에 비교적 강하지만, 상태 공간이 지나치게 크면 여전히 탐색 효율이 떨어집니다.

이를 해결하기 위한 방향으로는 유망한 행동만 우선 확장하는 progressive widening, 신경망을 이용한 후보 행동 축소, 도메인 지식을 활용한 가지치기, 시뮬레이션 깊이 제한 등이 있습니다. 특히 연속적인 행동 공간을 가진 로봇 제어 문제나 물리 시뮬레이션 문제에서는 가능한 행동을 이산적인 후보로 적절히 줄이는 과정이 중요합니다.

MCTS의 장점과 의의

MCTS의 가장 큰 장점은 정교한 평가 함수가 없어도 시뮬레이션을 통해 의사결정을 개선할 수 있다는 점입니다. 또한 처음부터 전체 탐색 공간을 구성하지 않고, 실제로 필요하고 유망한 부분을 중심으로 트리를 확장하므로 매우 큰 문제에서도 비교적 유연하게 사용할 수 있습니다.

또한 MCTS는 언제든 중단 가능한 anytime algorithm의 성격을 가집니다. 즉, 계산 시간이 많으면 더 많은 시뮬레이션을 통해 더 좋은 결정을 내릴 수 있고, 시간이 부족하면 현재까지의 탐색 결과를 바탕으로 즉시 결정을 내릴 수 있습니다. 이 특성은 제한 시간 안에서 결정을 내려야 하는 게임 AI나 실시간 계획 문제에서 특히 유용합니다.

MCTS는 단순한 무작위 탐색이 아니라, 경험적으로 얻은 결과를 트리에 누적하면서 점점 더 유망한 선택에 계산을 집중하는 방법입니다. 이 때문에 탐색 공간이 크고 불확실한 문제에서 강력한 의사결정 도구로 활용됩니다.