Monte Carlo Tree Search (MCTS)
몬테카를로 트리 탐색(MCTS)은 시뮬레이션 플레이아웃으로 탐색 트리를 확장하고 유망한 수에 집중해 행동을 선택합니다. AlphaGo와 로봇에 사용됩니다.
몬테카를로 트리 탐색(MCTS)은 여러 시뮬레이션 플레이아웃을 통해 가능한 미래의 트리를 확장하고, 가장 유망해 보이는 수에 더 많은 탐색 예산을 투입해 다음 행동을 선택하는 계획 알고리즘입니다. 게임 규칙이나 시뮬레이터처럼 합법적인 수와 결과를 생성하는 방법만 필요하며, 사람이 직접 작성한 평가 함수는 필요하지 않습니다. 또한 언제든지 실행을 중단해도 그때까지 찾은 최선의 수를 반환하는 애니타임 알고리즘입니다. 더 오래 실행할수록 더 나은 답을 얻습니다. Rémi Coulom은 2006년에 이 방법의 이름을 붙였고, 같은 해 Levente Kocsis와 Csaba Szepesvári는 이 방법의 표준 형태가 된 선택 규칙 UCT를 발표했습니다. MCTS는 몇 년 만에 컴퓨터 바둑의 수준을 크게 끌어올렸고, 이후 AlphaGo와 AlphaZero를 구동했으며, 현재는 로봇과 차량의 동작 계획 및 추론 단계를 탐색하는 데도 대규모 언어 모델(LLM)에서 사용됩니다.
MCTS 작동 방식#
탐색은 현재 상태를 루트로 하는 트리를 유지하며, 각 노드에는 방문 횟수와 방문 중 승리로 이어진 횟수가 저장됩니다. 각 반복은 네 단계로 이루어집니다.
- 선택: 루트에서 시작해 완전히 탐색된 노드를 내려가며 UCT 점수가 가장 높은 자식 노드를 선택합니다. UCT 점수는 높은 승률과 거의 시도되지 않은 수 사이의 균형을 맞춥니다.
- 확장: 시도하지 않은 수가 있는 첫 노드에서 해당 수를 새 자식 노드로 추가합니다.
- 시뮬레이션: 새 자식 노드부터 게임이 끝날 때까지 진행합니다. 전통적으로 무작위 수를 두어 결과를 얻습니다.
- 역전파: 경로를 따라 위로 올라가며 결과를 반영해 각 노드의 방문 횟수와 승리 합계를 업데이트합니다.
탐색 예산이 소진되면 알고리즘은 루트에서 가장 많이 방문된 자식 노드를 선택합니다. 이는 평균 점수가 가장 높은 노드보다 안정적인 선택입니다.
탐색과 활용의 균형#
UCT는 각 노드의 선택을 멀티암드 밴딧 문제로 보고 UCB1 공식을 적용합니다. 자식 노드의 점수는 승률 w/n에 c·√(ln N / n)을 더한 값입니다. 여기서 n은 자식 노드의 방문 횟수, N은 부모 노드의 방문 횟수, c는 이론상 √2이며 실제로는 조정되는 탐색 상수입니다. 두 번째 항은 수를 더 자주 시도할수록 줄어듭니다. 따라서 몇 번의 운 좋은 승리를 거둔 수가 다른 수를 밀어내지 못하며, 한동안 선택되지 않은 수도 결국 다시 검토됩니다.
다음 Python 예제는 작은 게임에서 MCTS를 실행합니다. 플레이어는 10개 돌 더미에서 한 번에 돌 1~3개를 가져가며, 마지막 돌을 가져가는 플레이어가 승리합니다.
import math
import random
# Game: players take 1-3 stones in turn, and whoever takes the last stone wins
random.seed(0)
N, W = {(10,): 0}, {} # visits and wins per node; a node is the sequence of pile sizes from the root
def rollout(stones):
"""Play random moves to the end and return 1 if the player to move wins."""
turn = 0
while stones:
stones -= random.randint(1, min(3, stones))
turn ^= 1
return turn
def search(node):
"""Run one MCTS iteration below a node and return 1 if the player to move there wins."""
if node[-1] == 0:
return 0 # the opponent took the last stone
children = [(*node, node[-1] - k) for k in (1, 2, 3) if k <= node[-1]]
unvisited = [c for c in children if c not in N]
if unvisited: # expansion, then simulation
child = random.choice(unvisited)
N[child], W[child] = 0, 0
result = 1 - rollout(child[-1])
else: # selection by UCT, balancing win rate against how rarely a child was tried
child = max(children, key=lambda c: W[c] / N[c] + 1.4 * math.sqrt(math.log(N[node]) / N[c]))
result = 1 - search(child)
N[child] += 1 # backpropagation, with wins counted for the player who moved into the child
W[child] += result
return result
for _ in range(2000):
search((10,))
N[(10,)] += 1
for take in (1, 2, 3):
child = (10, 10 - take)
print(f"Take {take}: {N[child]} visits, win rate {W[child] / N[child]:.2f}")돌 두 개를 가져가는 수는 방문 2,000회 중 1,889회를 차지하고 시뮬레이션의 91%에서 승리합니다. 한 개를 가져가는 수는 68회, 세 개를 가져가는 수는 43회 방문되었습니다. 이는 승리로 이어지는 수입니다. 돌 8개를 남기면 4의 배수가 되므로, 첫 번째 플레이어는 상대의 모든 응수에 대해 4의 배수를 복원하다가 더미가 빌 때까지 진행할 수 있습니다. 탐색은 전략을 코드로 작성하지 않고 무작위 플레이아웃과 방문 통계만으로 이 수를 찾아냈습니다.
AlphaGo에서 AlphaZero와 MuZero까지#
바둑의 합법적 수는 평균 약 250개로, 체스의 약 35개보다 많아 완전 탐색이 불가능했습니다. 2000년대 후반부터 컴퓨터 바둑의 실력이 도약한 데에는 MCTS가 핵심 역할을 했습니다. DeepMind의 AlphaGo는 유력한 수를 제안하는 정책 네트워크와 가치 네트워크 및 빠른 롤아웃을 사용한 상태 평가로 MCTS를 안내했으며, 2016년 3월 이세돌을 4대 1로 이겼습니다. AlphaZero와 MuZero는 이를 한 단계 더 발전시켰습니다. AlphaZero는 롤아웃을 완전히 제거하고 가치 네트워크로 리프 상태를 평가했으며, 스스로 대국한 게임으로 네트워크를 학습했습니다. 각 탐색에서 얻은 방문 횟수를 정책 네트워크의 타깃으로 사용해 MCTS를 강화 학습 내부의 정책 개선 단계로 만들었습니다. MuZero는 학습된 환경 모델 안에서 같은 탐색을 수행하므로 규칙을 제공받지 않고도 바둑, 체스, 쇼기, 아타리 게임을 할 수 있었습니다.
계획 및 추론을 위한 MCTS#
로봇과 자율주행 차량은 교통에 합류하는 것과 같은 불확실한 상황에서 계획을 세우기 위해 MCTS를 사용합니다. POMCP와 같은 변형은 숨겨진 상태에 대한 신념 분포를 추적해 부분 관측 마르코프 결정 과정으로 MCTS를 확장합니다. 카메라 입력에서 계획하는 탐색에는 루트 상태가 필요합니다. 예를 들어 체스를 두는 로봇 팔은 보드 이미지로 학습된 Ultralytics YOLO26 모델을 사용해 모든 말을 찾고, 복원된 위치를 탐색의 루트로 삼을 수 있습니다.
LLM 추론에서 각 노드는 부분 해답이고 각 간선은 추론 단계이며, 프로세스 보상 모델이나 답 검증기가 각 분기에 점수를 부여합니다. Microsoft의 rStar-Math는 프로세스 선호도 모델과 함께 MCTS를 사용해 MATH 벤치마크의 Qwen2.5-Math-7B 점수를 58.8%에서 90.0%로 높였습니다. 사고 트리는 대신 너비 우선 탐색이나 깊이 우선 탐색으로 추론 단계를 탐색합니다. 학습 중에는 MCTS를 사용하기가 더 까다로웠습니다. DeepSeek은 DeepSeek-R1을 개발하며 MCTS를 실패한 시도 중 하나로 언급했습니다. 토큰 시퀀스 공간이 보드게임보다 훨씬 크고 탐색을 안내하는 가치 모델을 학습하기 어렵기 때문입니다. 대신 검증 가능한 보상을 통한 강화 학습으로 R1을 학습했습니다.










