몬테카를로 트리 서치(Monte Carlo Tree Search, MCTS)는 선택지가 많은 문제에서 모든 경우를 끝까지 계산하지 않고, 여러 번의 시뮬레이션으로 좋은 선택지를 찾아가는 탐색 알고리듬이다. 바둑, 체스, 게임 AI처럼 가능한 수가 폭발적으로 늘어나는 문제에서 자주 언급되고, 최근에는 Graph RAG처럼 그래프 위에서 경로와 근거를 고르는 문제에도 응용 관점으로 이해할 수 있다.
핵심은 단순하다. 지금 당장 모든 길을 다 가볼 수 없다면, 일부 길을 여러 번 가볍게 시험해 보고, 결과가 좋았던 길을 더 깊게 파고든다. 그래서 MCTS는 완전한 깊이 우선 탐색이라기보다, 깊이 탐색을 확률적 시뮬레이션으로 근사하는 방법에 가깝다.
MCTS는 선택지 트리를 만들고, 시뮬레이션 결과를 누적하면서 유망한 경로를 더 깊게 탐색한다. 출처: GeeksforGeeks
왜 이런 탐색이 필요한가
트리 탐색은 보통 선택지의 가지가 계속 갈라지는 구조를 다룬다. 예를 들어 게임에서 내가 둘 수 있는 수가 30개이고, 상대도 다시 30개를 둘 수 있다면 두 단계만 내려가도 900가지가 된다. 여기에 몇 수만 더 깊게 들어가면 경우의 수는 사람이 직접 다루기 어려운 수준으로 커진다.
가장 단순한 방법은 모든 선택지를 끝까지 탐색하는 것이다. 하지만 현실의 문제에서는 시간이 부족하고, 계산 자원도 제한된다. 그래서 탐색 알고리듬은 중요한 질문을 던진다. 모든 길을 다 보지 못한다면, 어떤 길부터 봐야 하는가.
MCTS는 이 질문에 대해 경험적으로 답한다. 처음에는 여러 길을 넓게 시험하고, 시간이 지날수록 성과가 좋아 보이는 길에 더 많은 탐색을 배정한다. 이 방식은 정답을 수학적으로 한 번에 계산하기보다, 반복 실험을 통해 더 나은 선택지를 찾아가는 방식이다.
이름에 들어 있는 몬테카를로의 의미
몬테카를로라는 말은 무작위 표본 추출을 이용해 문제를 근사적으로 푸는 방법을 가리킨다. 몬테카를로 방법은 확률적 샘플링을 반복해서 복잡한 계산을 근사하는 접근으로 설명된다.
MCTS에서도 같은 감각이 쓰인다. 어떤 선택이 좋은지 정확히 알 수 없으니, 그 선택을 했다고 가정하고 무작위 또는 정책 기반으로 끝까지 진행해 본다. 이런 가상 진행을 여러 번 반복하면, 특정 선택이 평균적으로 좋은 결과를 냈는지 점차 추정할 수 있다.
여기서 중요한 점은 무작위가 곧 아무렇게나 한다는 뜻이 아니라는 점이다. MCTS는 무작위 시뮬레이션을 사용하지만, 시뮬레이션 결과를 트리에 누적하고 다음 선택에 반영한다. 그래서 반복할수록 탐색 방향이 조금씩 정리된다.
MCTS의 네 단계
MCTS는 보통 네 단계를 반복한다. Browne 등의 MCTS 서베이에서도 이 구조를 Selection, Expansion, Simulation, Backpropagation으로 정리한다.
- Selection: 이미 만들어진 트리에서 어느 노드로 내려갈지 고른다.
- Expansion: 아직 충분히 탐색하지 않은 선택지를 새 노드로 추가한다.
- Simulation: 새 노드에서 결과가 나올 때까지 가상으로 진행한다.
- Backpropagation: 시뮬레이션 결과를 지나온 노드들에 다시 반영한다.
선택, 확장, 시뮬레이션, 역전파는 MCTS를 이해할 때 가장 먼저 잡아야 하는 기본 반복 구조다. 출처: Spot Intelligence
이 네 단계는 한 번만 실행되는 것이 아니다. 제한 시간이 끝날 때까지 계속 반복된다. 반복이 쌓이면 각 노드는 방문 횟수와 평균 보상 같은 정보를 갖게 된다. 최종 선택은 보통 가장 많이 방문되었거나 평균 결과가 좋은 노드를 기준으로 한다.
아주 쉬운 예시로 이해하기
상황을 단순하게 잡아 보자. 갈림길이 A, B, C 세 개 있는 미로가 있고, 목표는 보물을 찾는 것이다. 처음에는 어느 길이 좋은지 모른다.
처음 몇 번은 A, B, C를 각각 가볍게 시도한다. A에서는 막다른 길이 자주 나오고, B에서는 중간 정도 보상이 나오며, C에서는 가끔 보물에 가까운 길이 나온다고 하자. 그러면 MCTS는 C를 조금 더 자주 탐색하기 시작한다.
하지만 C만 계속 보지는 않는다. A나 B도 아직 충분히 탐색하지 않았을 수 있기 때문이다. 좋은 길로 보이는 곳을 더 파고들면서도, 덜 본 길을 완전히 버리지 않는 균형이 필요하다. 이 균형이 MCTS의 중요한 부분이다.
탐험과 활용의 균형
MCTS에서 자주 나오는 개념은 탐험과 활용이다.
- 탐험은 아직 잘 모르는 선택지를 시험하는 것이다.
- 활용은 이미 좋아 보이는 선택지를 더 깊게 파는 것이다.
활용만 하면 초기에 운 좋게 좋아 보였던 길에 갇힐 수 있다. 탐험만 하면 좋은 길을 발견하고도 충분히 깊게 파지 못한다. MCTS는 이 둘 사이의 균형을 잡으면서 트리를 확장한다.
대표적인 방식이 UCT(Upper Confidence bounds applied to Trees)다. Kocsis와 Szepesvari의 UCT 논문은 MCTS 계열에서 널리 언급되는 선택 기준을 제시했다. UCT는 평균 보상이 높은 선택지와 아직 방문이 적은 선택지를 함께 고려한다.
수식으로 쓰면 복잡해 보일 수 있지만, 의미는 단순하다. 결과가 좋았던 길은 더 본다. 다만 아직 충분히 보지 않은 길에도 기회를 준다.
깊이 탐색의 근사적 방법으로 보는 관점
MCTS를 깊이 탐색의 근사적 방법으로 보면 이해가 쉬워진다. 일반적인 깊이 우선 탐색은 한 경로를 깊게 따라 내려간 뒤 다시 돌아와 다른 경로를 본다. 반면 MCTS는 아무 경로나 무작정 깊게 내려가지 않는다. 시뮬레이션 결과를 보고, 더 가치 있어 보이는 경로에 깊이를 배분한다.
즉 MCTS는 트리 전체를 균등하게 탐색하지 않는다. 좋은 결과를 낼 가능성이 높은 부분 트리에 계산을 더 많이 쓴다. 이 때문에 전체 경우의 수가 매우 큰 문제에서도 제한된 시간 안에 실용적인 선택을 만들 수 있다.
이 관점은 Graph RAG를 생각할 때도 도움이 된다. Graph RAG는 문서나 엔티티를 그래프로 연결하고, 질문에 필요한 근거를 그래프 구조에서 찾아 답변 품질을 높이려는 접근이다. Microsoft GraphRAG는 지식 그래프 기반 검색과 생성을 결합하는 방식으로 설명된다.
그래프 위에서 가능한 탐색 경로가 많아질수록 모든 경로를 다 평가하기는 어렵다. 이때 MCTS적인 사고방식은 후보 경로를 일부 시험하고, 더 유망한 경로에 탐색 예산을 더 쓰는 전략으로 연결될 수 있다. 엄밀히 말해 모든 Graph RAG 시스템이 MCTS를 쓰는 것은 아니다. 다만 그래프 기반 검색에서 경로 선택과 탐색 예산 배분을 고민할 때 MCTS는 좋은 비유이자 응용 가능한 탐색 틀이다.
Graph RAG 관점에서는 문서와 엔티티가 연결된 그래프에서 유망한 경로를 어떻게 고를지가 중요한 문제가 된다. 출처: AltexSoft
알파고와 MCTS
MCTS가 대중적으로 알려진 계기 중 하나는 알파고다. AlphaGo 논문은 정책망과 가치망을 MCTS와 결합해 바둑에서 강한 성능을 냈다고 설명한다.
전통적인 MCTS는 시뮬레이션을 많이 반복하면서 선택의 품질을 높인다. 알파고는 여기에 신경망을 결합했다. 정책망은 어떤 수가 유망한지 알려 주고, 가치망은 현재 상태가 얼마나 좋은지 평가한다. 이렇게 하면 완전히 무작위로만 굴리는 것보다 훨씬 효율적으로 탐색할 수 있다.
이 사례가 중요한 이유는 MCTS가 단독 기법으로만 쓰이지 않는다는 점이다. MCTS는 평가 모델, 정책 모델, 휴리스틱과 결합될 수 있다. 그래서 고전적인 게임 AI뿐 아니라 복잡한 의사결정 문제에서도 탐색 프레임워크로 볼 수 있다.
MCTS가 잘 맞는 문제
MCTS는 다음 조건을 가진 문제에서 특히 이해하기 쉽다.
- 선택지가 여러 단계로 이어진다.
- 모든 경우를 끝까지 계산하기 어렵다.
- 어떤 선택이 좋은지 시뮬레이션이나 평가로 대략 판단할 수 있다.
- 제한된 시간 안에서 그럴듯한 선택을 해야 한다.
게임 AI는 이 조건에 잘 맞는다. 한 수를 두고, 상대가 응수하고, 다시 내가 선택하는 구조가 자연스럽게 트리를 만든다. 보상이 승패처럼 명확한 경우도 많다.
추천, 계획 수립, 로봇 행동 선택, 경로 탐색 같은 문제도 구조에 따라 MCTS 관점으로 볼 수 있다. 다만 모든 문제에 MCTS를 억지로 넣는 것은 적절하지 않다. 시뮬레이션 비용이 너무 크거나, 상태 평가가 불안정하거나, 보상 설계가 어려운 문제에서는 기대만큼 잘 동작하지 않을 수 있다.
기억할 핵심
MCTS는 모든 경우를 다 보는 탐색이 아니다. 많은 선택지 중 일부를 반복적으로 시험하고, 결과가 좋아 보이는 방향으로 탐색을 점점 집중하는 알고리듬이다.
정리하자면 다음 네 문장으로 기억하면 된다.
- 트리에서 선택지를 하나 고른다.
- 아직 모르는 선택지를 확장한다.
- 가상으로 끝까지 진행해 결과를 본다.
- 그 결과를 다시 위로 올려 다음 선택에 반영한다.
이 과정을 반복하면 탐색 트리는 점점 유망한 방향으로 자란다. 그래서 MCTS는 거대한 탐색 공간을 전부 계산하지 않고도, 제한된 시간 안에서 좋은 선택을 찾기 위한 실용적인 방법이다.